SRM 567: Not blue yet

I finished it on Saturday's morning and was published the Sunday's afternoon. It was a long week. So of course, there was little to no time till SRM 567. Another editorial I will have to write... BTW, stay tuned because I might publish the editorial in parts and will announce in this blog whenever the easier parts of the editorial are ready.

I was wondering if I would get blue rating today. I knew that if I got another 0.00 score using my new self-destructive "strategy" I would most likely become blue today. But I was lucky that today was one of those matches in which I get to solve the division 1 medium...

Div1 medium: The one with strings.

Two players play a game using a set of strings/words. At the beginning of the game, player 1 picks one of the strings, and can permute it. He also gets to permute the alphabet. Then player 2 picks another string that he can also permute it. If player 1's picked string is lexicographically earlier (USING THE PERMUTATION OF THE ALPHABET) than player 2's then player 1 wins. Given an array of strings, return the indexes of the strings which, if picked by player 1 will allow the player to 1, assuming he picks the best possible alphabet and player 2 plays optimally.

It is all about the way player 1 permutes the alphabet. Afterwards, the optimal move for both players is to sort their strings using the picked alphabet. Player 2 has the advantage that he can basically sort all of the strings (other than player 1's) and then pick the the string that is best when sorted.

Let us say the alphabet is picked and the letter a[i] is the i-th letter of the alphabet. Then the string that is lexicographically earliest will be the one such that, in the earliest index i such that count(string1, a[i]) != count(string2, a[i]), has the character a[i] the largest number of times. If both strings have each letter an equal number of times, then player 1 cannot win.

At first it seemed like it is always better for player 1 to give smaller indexes in the permutation to the letters that exist a longer number of times in his string. This approach is wrong. It also seemed wrong, I had the feeling it would not be so easy. Yet it passes the example cases, which made me figure out that it would be easy to find wrong solutions.

A challenge case for the wrong approach: {"xvvvvv","vvvvxx"} When player 1 is given the second string, it would be unwise for him to pick alphabet "vx...", he would instead win with "xv...".

My quickest idea was: for each index i, pick the letter that appears the smallest number of times in string 1, and still does not cause a failing condition (One of the remaining strings is lex earlier). It is actually not necessary to pick the letter that appears the smallest number of times. After picking a letter, delete/disable the strings that are already lexicographically larger than player 1's string. This simple approach is enough to pass. In fact, I think that many people failed the problem because of attempts to make it a stronger algorithm.

Proof? When a character appears more times in another string than in the player 1 string, then we cannot use this character until we use another character that removes this other string. If it is possible to remove the string, then we will eventually do it. If the character appears an equal number of times, then using it or not will not really help us to remove the string.

vector <int> getWinningStrings(vector <string> S)
{
    int n =  S.size();
    int counts[n][26];
    for (int i=0; i<n; i++) {
        fill(counts[i], counts[i]+26, 0);
        for (int j=0; j<S[i].size(); j++) {
            counts[i][ S[i][j] - 'a' ]++;
        }
    }
    vector<int> res;
    for (int i=0; i<n; i++) {
        vector<bool> usedAlpha(26, false);
        vector<bool> active(n, true);
        active[i] = false;
        int t = 0;
        while (t < S[i].size()) {
            int pick = -1;
            // Find a good letter we can use:
            for (int a=25; a>=0; a--) if (!usedAlpha[a]) {
                bool good = true;
                for (int j=0; j<n; j++) if (active[j]) {
                    good &= (counts[i][a] >= counts[j][a]);
                }
                if (good) {
                    t += counts[i][a];
                    usedAlpha[a] = true;
                    pick = a;
                    for (int j=0; j<n; j++) {
                        // disable any string that has this letter
                        // a smaller number of times:
                        active[j] =  active[j] && (counts[i][a] == counts[j][a]);
                    }
                    break;
                }
            }
            if (pick == -1) {
                break;
            }
        }
        bool won = true;
        for (int j=0; j<n; j++) {
            won &= !active[j] ;
        }
        if (won) { 
            res.push_back(i);
        }
    }
    return res;
}

Div1 250: The one with square roots

I had free time after solving div1 500. But I did not open div1 250. The rules are that I must only open div1 250 when there are less than 10 minutes of coding phase left. No matter if I solved the other problems. I tried to solve div1 1000. I also had breakfast and those things. Making sure not to open this problem.

Given N, M: Count the number of pairs (a,b) such that (1 <= a <= N <= 77777) , (1 <= b <= M <= 77777) and (sqrt(a) + sqrt(b))² is a integer.

By using notable products we have that: (sqrt(a) + sqrt(b))² = a + b +2*sqrt(a*b) which will be a integer if and only if a*b is a perfect square. So we need to count the number of pairs (a,b) in which a*b is a perfect square.

I made the mistake of wasting my only 10 minutes in what seems to be the wrong direction to handle the problem : I tried to first generate the perfect squares between 1 and 77777*77777 and then trying to count the pairs (a,b). I could not really optimize it greatly during 10 minutes.

The solution that I like, takes a as a starting point instead. You pick a number a from 1 to N and then try to count the number of valid bs that would make a*b a perfect square.

The prime factorization of a perfect square is such that every exponent is even (Every prime factor appears an even number of times). It is easy to factorize a, and you will find that some prime factors appear an odd number of times in a. b must be a multiple of the products of these prime factors for it to work. So let us say that b = c * (multiple of necessary prime factors).

The total product is a * c * (necessary prime factors). We know that a*(necessary prime factors) is a perfect square. Thus c will also have to be a perfect square. In fact, it is easy to try all numbers 1,2,... sqrt(M/(a*necessary prime factors)), find c and thus generate b.

int countPairs(int N, int M)
{
    int result = 0;
    for (int a=1; a<=N; a++) {
        int x = a;
        int req = 1;
        // Find the prime factors of a (and their exponents)
        // in O(sqrt(a)):
        for (int y = 2; y <= x/y; y++) {
            if (x % y == 0) {
                int e = 0;
                do {
                    x /= y;
                    e++;
                } while (x % y == 0);
                // req will hold the product of all odd prime factors:
                if (e % 2 == 1) {
                    req *= y; 
                }
            }
        }
        // If x > 1, then x is another prime factor of a, that appears once (odd)
        if (x > 1) {
            req *= x;
        }
        //b = req * (a perfect square)
        // try each y (square roots of the perfect squares)
        for (int y = 1; y <= M/y && y*y <= M/req; y++) {
            result++;
        }
    }
    return result;
}

A complexity analysis: Extracting the prime factors for each a is O(N*sqrt(N)). Note that result++ will happen as many times as the result for N,M does. The number of operations is O(N*sqrt(N) + f(N,M)) where f(N,M) is the number of pairs that make perfect squares. We can test that f(77777,777777) is around 50000. So all is fine. The approach needs 0.1 seconds in the worst case.