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.

Google codejam round 3: good bye

No surprises here, I did not advance. Even though I knew my chances and that at best I would have to battle for a good position for honor and thus. I kinda harbored the fantasy of advancing. Mind you, I really think that with the right random shuffle and combination of problems I could end in top 25. But it was unlikely. Nevertheless, I am kind of proud of my 133-th place.

Problem A: The breather

statement

This problem was one to reward intuition. I guess. It was much easier than anything else in the round.

Let us say you know the order you picked. Then, the expected time after you solve 0 levels is: f(0) = L0 + p0*f(0) + (1-p0)*f(1). Where f(1) is the expected time after solving 1 level. After some magic: f(0) = L0/(1-p0) + f(1)

Now f(1) = L1 + p1*f(0) + (1-p1)*f(2). f(1) = L1 + p1*( L0/(1-p0) + f(1)) + (1-p1)*f(2).

f(1) = L1 + p1*L0/(1-p0) + p1*f(1) + (1-p1)*f(2)
(1 - p1) * f(1) = L1 + p1*L0/(1-p0) + (1-p1)*f(2)

f(1) = ( L1 + p1*L0/(1-p0) )  / (1 - p1) + f(2)
f(1) = L1 / (1-p1) + p1*L0/(1 - p0)

After some iterations, you will find a very messy formula. But it should become clear that it is best to pick the levels in non-decreasing order of L/p. It is actually something that can happen by intuition. At least for A-small, what I did was to think that it is best to get rid of the harder levels first, so that the probability to repeat a lot of levels goes smaller with time. Then when factoring the variable Li it is also guessable that a division can occur. But after getting correct in A-small I did not want to risk it (I didn't have a proof). So I skipped to B.

If two L/p values are equal, pick the one with the smallest index, to make sure the lex first order is picked.

Problem B: The implementation hell

statement

This problem was a sand trap. I knew it was a sand trap. But I sort of thought that I could do it decently fast, and in fact I had hops to solve the large version.

I think most of the top 500 would not get scared of the hexagonal grid. Yet in this case, the grid was the least of the implementation issues. The three cases each have their complications.

You need to turn the hexagonal grid into a 2d grid. It is possible with T=2*S-1. Then you can have a TxT grid. Some of the elements in the TxT grid are invalid (don't exist in the hexagonal grid)., you have to mark them as such.

Then you need to analyze what rules involve connecting two hex cells. (x,y) is adjacent to (x-1,y-1), (x-1,y) , (x,y-1), (x,y+1), (x+1,y) and (x+1,y+1).

We need to differentiate between normal cells, edges and corners. In fact, each edge needs a different id for the cells in that edge (Forks are a pain to detect, see below). More implementation weight.

Rings: The statement help us here. We need to detect an empty cell that is not reachable to the boundary with any path of empty cells. Thus we can do a dfs starting from each of the boundary cells (borders or corners). Then if we try each empty cell, if it was not reached by the DFS, we have found a ring. A BFS also works, I used a BFS for no reason.

Bridges: Another use for a DFS, count the number of connected components of (non-empty) cells. If the number of components is less than 6, we got a bridge.

Forks: These were a pain to debug. Once I understood what was needed to detect forks, I was no longer hopeful that I could solve B-large. From each non-empty cell in an edge, do a DFS of non-empty cells. Then verify if there are two or more cells from different borders that have been visited. If there are two, we got a bridge. If you only find one of such cells, make sure to mark it out so that you don't count it as visited by a dfs from another edge...

Once I debugged my B-small, I already spent over an hour in it (fork mistakes). And it was still wrong (WA). I spent another good half an hour finding the bug (the forks again) and got a correct answer. But there were less than 30 minutes left...

The rest

I was shocked. Although I spent ages solving B-small, I somehow was still in a high position (150-th-ish). It seems that a lot of people had issues. So, I tried more problems. I could not understand what D asks for, and I did not understand what the difference between c-small and C-large was. Then I decided to take back A-large. This time, I decided to prove my intuition - it was correct. So I submitted it. It took me a while to code it because I did not have precision errors (We are sorting by (L/p, id), if we used floating points to calculate L/p, there is a risk that two different expressions L/p that give the same result are not considered the same in floating point arithmetic). So I decided to implement it only in integers (It is easy, just compare p2*L1 and p1*L2 instead of L1/p1 and L2/p2). I wonder if this was necessary.

Then I spent my last minutes watching the score boards. Many interesting surprises there. rng_58 was not in the qualifying top 25. But then the match ended, and results were updated. rng_58 got 25-th place!