TopCoder Open 2021, Round 1A - Balanced Strings

[Гост]

От край време се мъча по една задача. Казва се Balanced Strings. Може ли да ми помогнете с нея? В края на съобщението ще ви напиша какво съм направил по нея и колко точки съм изкарал на нея. Та ако решите да ми помогнете, моля напишете решението на Java, защото пиша на този език. Благодаря на всички дори и да не успеете да ми помогнете!
Ето задачата:

Ели има стринг S с четна дължина. Тя може да променя стринга произволен брой пъти, като в една операция може да избере някоя от текущите му букви и я "увеличи" или "намали". Увеличаване на буква я променя в следващата буква от азбуката (например 'A'→'B', 'L'→'M', или 'Y'→'Z'), докато намаляване я променя в предходната буква от азбуката (например 'B'→'A', 'M'→'L', или 'Z'→'Y'). Буквата 'A' не може да бъде намалена, а 'Z' – да бъде увеличена. Всяка позиция от стринга може да бъде променяна произволен брой пъти, тоест от S може да бъде получен всеки друг стринг със същата дължина.

В английската азбука буквите {'A', 'E', 'I', 'O', 'U'} се считат за гласни, докато всички останали - за съгласни. Сега момичето се чуди колко най-малко операции трябва да направи, така че броят гласни в получения стринг да е равен на броя съгласни?

Вход
На единствен ред на стандартния вход ще бъде зададен един стринг S с четна дължина, съставен от главни букви на английската азбука ('A'-'Z').

Изход
На стандартния изход изведете едно цяло число – търсения минимален брой операции.

Ограничения
2 ≤ |S| ≤ 100

Примерен Вход Примерен Изход
TOPCODER 1
CORONA 0
WITHOUTITIAMJUSTESPR 2
NOZAPHODJUSTVERYVERYIMPROBABLE 5
JOYFULLY 2
ABCDEFGHIJKLMNOPQRSTUVWXYZ 8

--------------------------

Благодаря предварително на всички!

[Гост]

Пак съм аз. Та изкарах 84 точки. Не мога да направя кода на 'A' и 'Z' като специални случаи. Иначе мисля, че останалото е вярно, но моля помогнете ми със задачата.

[Davids]

Ето моите два цента по задачата, типично състезателска
Оставил съм ти коментари по цялата идея, надявам се да ти стане ясно. Успех!

Код: Избери целия код

public class BalancedStrings {
   
    public static String vowels = "AEIOU";
   
    /*
    * -1 indicates that we've passed a vowel (which needs only 1 shift to become a consonant)
    *   *The negative sign is important
    * >0 indicates that we've passed a consonant (the minimal number of shifts required)
    */
    public static int signedLeastShiftsToClosestSwitch(char c) {
        //if we have a vowel, we only need to shift 1 char to get a consonant - thus a valid shift
        if(vowels.contains(String.valueOf(c)))
            return -1;
       
        //this will be the index of the "highest" preceding vowel of our char
        int index = 0;
       
        for(int i = 0; i < vowels.length() - 1; ++i) {
            if(vowels.charAt(i) < c && c < vowels.charAt(i + 1)) {
                index = i;
                break;
            }
        }
       
        //a consonant after 'U'
        if(index == vowels.length() - 1)
            return c - vowels.charAt(index);
       
        //positively signed 'distance' to closest vowel
        return Math.min(c - vowels.charAt(index), vowels.charAt(index + 1) - c);
    }
   
   
    public static int leastShiftsToBalance(String str) {
        //effectively a counter to give us the signed difference between vowels and consonants
        int disbalance = str.chars().map(c -> vowels.contains(String.valueOf((char)c)) ? -1 : 1).sum() / 2;

        return str.chars()                              //to char index stream
                .map(x -> signedLeastShiftsToClosestSwitch((char)x)) //get the closest switch for each char
                .sorted()                               //IMPORTANT! Sort ascendingly
                //only leave those shifts with same sign as the disbalance
                //(meaning, if disbalance > 0, then we'd have more consonants and thus want to turn them into vowels,
                //therefore we want only positive shifts, which stand for consonants)
                .filter(s -> s * disbalance > 0)       
                .limit(Math.abs(disbalance))            //to acquire the minimal shifts, we only take as manyswitches as we need (ascending order crucial here) - works even if disbalance == 0
                .sum();                                 //finally sum all the shifts required
    }
   
     public static void main(String[] args){
         
        String[] tests = {
            "TOPCODER",
            "CORONA",
            "WITHOUTITIAMJUSTESPR",
            "NOZAPHODJUSTVERYVERYIMPROBABLE",
            "JOYFULLY",
            "ABCDEFGHIJKLMNOPQRSTUVWXYZ",
        };
       
        for(String test : tests)
        {
            System.out.println(leastShiftsToBalance(test));
        }
     }
}


[Гост]

Благодаря ти Davids.
Състезателска е от TopCoder.

[pal702004]

VB.Net,общо взето такава идея - имаме константен масив A, съдържащ "разстоянията" на всяка буква от азбуката до най-близката гласна (за гласните е 0, за Z е най-голямата стойност 5).
Масив B, във който се пълни колко букви от входящия стринг са гласни - B(0), колко с разстояние 1....до 5
Променлива Remainder - колко трябва да са гласните в балансирания стринг, в началото е половината от дължината на входящия, после се ползва за намаляне.
Това е, при коректен вход трябва да работи.

Код: Избери целия код

Public ReadOnly A() As Byte = {0, 1, 2, 1, 0, 1, 2, 1, 0, 1, 2, 3, 2, 1, 0, 1, 2, 3, 2, 1, 0, 1, 2, 3, 4, 5}

Function BalancedString(ByVal InputString As String) As Byte
        Dim B(5) As Byte
        Dim Remainder As Byte = Len(InputString) \ 2
        Dim I As Byte
        For I = 0 To 5 : B(I) = 0 : Next
        For I = 1 To Len(InputString) : B(A(Asc(Mid(InputString, I, 1)) - 65)) += 1 : Next
        If B(0) >= Remainder Then Return B(0) - Remainder
        Dim Result As Byte = 0
        Dim MinV As Byte
        Remainder -= B(0)
        I = 1
        While Remainder > 0
            MinV = Math.Min(Remainder, B(I))
            Remainder -= MinV
            Result += I * MinV
            I += 1
        End While
        Return Result
    End Function


[Гост]

pal702004. Благодаря и на теб! Не се бях досетил дали мога да го направя така, но това е умно.

[Davids]

VB.Net,общо взето такава идея - имаме константен масив A, съдържащ "разстоянията" на всяка буква от азбуката до най-близката гласна (за гласните е 0, за Z е най-голямата стойност 5).
Масив B, във който се пълни колко букви от входящия стринг са гласни - B(0), колко с разстояние 1....до 5
Променлива Remainder - колко трябва да са гласните в балансирания стринг, в началото е половината от дължината на входящия, после се ползва за намаляне.
Това е, при коректен вход трябва да работи.

Код: Избери целия код

Public ReadOnly A() As Byte = {0, 1, 2, 1, 0, 1, 2, 1, 0, 1, 2, 3, 2, 1, 0, 1, 2, 3, 2, 1, 0, 1, 2, 3, 4, 5}

Function BalancedString(ByVal InputString As String) As Byte
        Dim B(5) As Byte
        Dim Remainder As Byte = Len(InputString) \ 2
        Dim I As Byte
        For I = 0 To 5 : B(I) = 0 : Next
        For I = 1 To Len(InputString) : B(A(Asc(Mid(InputString, I, 1)) - 65)) += 1 : Next
        If B(0) >= Remainder Then Return B(0) - Remainder
        Dim Result As Byte = 0
        Dim MinV As Byte
        Remainder -= B(0)
        I = 1
        While Remainder > 0
            MinV = Math.Min(Remainder, B(I))
            Remainder -= MinV
            Result += I * MinV
            I += 1
        End While
        Return Result
    End Function


Абсолютно добро напомняне, че понякога не е нужно да се усложняват нещата... При наличието на всичко на всичко 30 символа, съвсем спокойно въпросните отстояния могат да се hardcode-нат в масив (по посочения начин), което прави първата фунцкия от решението ми на практика излишна (така де, оптимизируема ), но пък поне онагледява идеята. Поздравления за включването!