SRM 569 Editorial

It is not published yet, but I finished it last night and it is in a state that is sort of ok: http://apps.topcoder.com/wiki/display/tc/SRM+569

Remember when I said that I liked the mathy div1 1000 points problem of this match? I predicted that although difficult, it would have a solution that would not be impossible to explain, so that was good by me.

It turns out this problem is the coolest thing I have solved in months. I just really like this twist on the usual matrix exponentiation idea. This problem does not use matrix exponentiation, but it adapts that idea into something (that at least to me is) fresh.

Read More

SRM 569 editorial preview

Division 2 and division 1 easy explanations are complete. Go here: http://apps.topcoder.com/wiki/display/tc/SRM+569

I think I have div1 medium figured out, I just need to make sure to understand a couple of thing. Div1 hard is hard as usual, but after rng_58 explanation I think/hope this won't take me as long as last match.

There are forces at works towards compensating the current trend of unsolvable div1 1000s by extending the duration of the matches. I really dislike the idea. A similar change happened to Google's Code Jam and I think that the problem set quality has been on a downwards spiral since then. And the longer matches have been less comfortable to my taste. Instead of increasing the chances to solve problems, problems became longer to solve.

What I do know is that we used to have people solving div1 hard problems in the past. So it is certainly possible to make problem sets that are solvable in the current 75 minutes.

Read More

SRM 569 : Blunder

Having a bad day here because even after a whole week I was still not able to finish the editorial for SRM 568. The first big delay was because of the harder than usual div1 500, but the worst happened later when I got sick... I recovered on Monday and tried to use that time to understand the div1 hard. It is a work in progress.

Then it was SRM time, and I scored another flat zero.

Div1 1000: Mega factorial

This problem was like an evil over the top version of SuperSum, but this time with factorials. And you have to count the number of leading zeros in a very recursive variation of the factorial. Seems mathy. That's probably good because I am tired of those silly div1 1000s in which the solution comes out of nowhere. At least this one will be easy to explain once I find the solution, I think

Div1 500: The one with Jedis

You are given an array of numbers called students that contains the initial number of students in each floor. When assigning Jedis to floors with some students you compute sum( ceiling( students in floor i) / K). However, you can move any students from a floor to either the next or previous one. Let us minimize that sum.

The constraint on the number of floors is low (20). I knew the solution was going to be exponential, making a binary decision for each floor. But no idea how to make that decision.

Some cases I thought of seemed very confusing, like {7,2,7} K=8, it is best to move 1 student to the first floor and another to the third floor. This specific case can be solved by moving 14 students to the middle floor, but there are other variations. It was a bit confusing to my brain.

Div1 250: The one with binary operations.

As my new strategy says, 10 minutes before the end of the match and I have to open the easy problem.

You have a device that takes 2 sequences of bits, and for each bit position in the sequence performs binary AND, OR or XOR between the two bits of the corresponding positions of the input sequences . You already got a number of sequences of bits you can use. What is the minimum number of additional sequences you will need?

Each bit position is a separate problem in reality. If for a bit position all the sequences have bit 0 , you probably will need a sequence with bit 1 in that position. Let us say you know the number of required extra bits for each position. The maximum of them all is the final result : Just make some new sequences with the required bits in total, for the slots that do not need as many new sequences, feel free to repeat some bits.

What is left is this question, that deals with only one bit position: You have z sequences that contain 0 in this position and o sequences that contain 1, what is the number of additional sequences this position needs?

Here is when I made the blunder. I knew that I had to make truth tables for XoR, OR and AND to know what sort of bits are needed to differentiate between the three. But for some stupid reason I decided to rush and make a stupid assumption instead. So I assumed that you need 2 zeros and 2 ones.

That is wrong and fails example cases. Then I made another stupid assumption. That you need two different bits and either one extra 1 or one extra 0. This is also wrong.

Match ended.

This is when I make a truth table in paper:

		AND	OR	XOR
0	0	0	0	0
0	1	0	1	1
1	0	0	1	1
1	1	1	1	0

And it was so fast and it makes things so clear that I really regret I didn't do it during the coding phase. Note how having two zeros is completely useless, (0,0) cannot help you differentiate between AND, OR, XOR. Having two different bits (0,1) helps you differentiate between OR and AND or between OR and XOR, but cannot help you when differentiating between OR and XOR. 1,1 helps you differentiate between OR and XOR. In conclusion you need at least two sequences with 1 and one with 0.

int minimumAdditional(vector <string> plates)
{
    int need = 0;
    for (int i=0; i<plates[0].size(); i++) {
        int z = 0;
        int o = 0;
        // count the number of sequences with 0 and 1 in this bit position
        for (int j=0; j<plates.size(); j++) {
            z += ( plates[j][i] == '0');
            o += ( plates[j][i] == '1');
        }
        // we need 2 ones and 1 zero:
        int x = 2 - std::min(2, o) + 1 - std::min(1, z) ;
        need = std::max(need, x);
        
    }
    return need;
}

Read More

SRM 568: Last second

This was hard. The division 1 medium problem was solved by very few people. It seems that problems are becoming harder.

Div1 500: The one with a matrix

A matrix with numbers in it is called nice, if every perfect matching between rows and columns gives the same sum of matched cells. In other words, in a NxN matrix pick N cells such that no two cells share a row and a column, all sets of picked cells possible must yield the same sum of values written in the picked cells.

You are given a NxN matrix , which contains digits from 0 to 9 or -. Count the number of ways to fill each of the - in the matrix with non-negative (possibly greater than 9) integer numbers such that the matrix is nice. It is guaranteed that the number of ways is finite.

... finite. It seems that for the number of ways to be finite, then there should be initially a set of N cells that do not share row/column that do not contain any - character in them. The sum of this set will be the same sum shared by all the sets and can be at most 50*9 = 450. That's about the only progress I could make.

In order for there to be only one possible sum, then the min-cost matching and the max-cost matching of the matrix must be equal. That's it. There are probably many other ideas and the solution is hopefully simple, but I have no idea.

I tried many things during the match. Kept thinking. Opened div1 1000. Eventually I spent my time until the 10 last minutes of the coding phase watching the division summary. It was clear that I was not the only one having difficulty with this problem. Petr was the only coder to have a solution for a looong while. Some blue coders were solving the hard problem, but I doubted those solutions would stay.

Div1 250: The one with colored balls

Less than 10 minutes left. Faithful to my suicidal strategy, I open 250. It seemed like most people would only have a score in this problem, and thus speed would have been quite crucial. From the scores it seemed that taking less than 10 minutes was doable, so I put all my effort.

There are N boxes, each with at least 1 ball and at most 1000000 of each color (red, green or blue). A single step consists of taking a ball from a box and putting it in another box. What is the minimum number of steps needed to make it so no box contains balls of more than one color?

The first idea you can have is to, for each box, pick the color that has the maximum number of balls, and move the other balls to other boxes. The problem is to where?. You can assume that you just move those balls to boxes that will end with that color only, so you can add up, for each box, the number of balls of the colors that are not the maximum in the box. There is an issue with this logic, for example, what happens when all boxes have more red balls than the other colors? Then we cannot move the blue and green balls from each box to somewhere else, because there is no such box.

We can overcome this issue by first fixing three boxes: One that will forcefully have only red balls, another for green balls and another for blue balls. We first need to take the balls with the wrong color from each of these boxes. Then we can continue with the remaining boxes. For each box i, we can take the green balls to the fixed green box, the red balls to the red box, and the blue balls to the blue box . But we can leave one of the groups of balls, the maximum for each box unmoved. This will minimize the number of balls needed. Repeat for every possible combination of 3 balls that are assigned red, blue or green and the minimum possible is the answer.

I finished this when there were 6 minutes left, too bad that there was some mistake in the code stopping me from passing the example cases. I had no idea what it was. Until the timer reached 20 seconds, and I suddenly noticed! In a part I had res += instead of c +=. I corrected the bug and compiled and submitted without testing (20 seconds left!). I was able to submit it almost at the last second!. And it passed.

int minOperations(vector <int> red, vector <int> green, vector <int> blue)
{
    pair<int,int> res = make_pair(2100000000,-1); //std::pair is good like this
    int n = red.size();
    for (int fr = 0; fr < n; fr++) {
        for (int fg = 0; fg < n; fg++) if (fr != fg) {
            for (int fb = 0; fb < n; fb++) if (fb != fg && fb != fr) {
                int moves = 0;
                // fr is a box that is forced to be red
                // fg is a box that is forced to be green
                // fb is a box that is forced to be blue
                
                // Move balls of the wrong color from each of the picked boxes:
                moves += green[fr] + blue[fr];
                moves += green[fb] + red[fb];
                moves += blue[fg] + red[fg];
                // For each other other boxes, leave the maximum color and move
                // the rest to their assigned boxes:
                for (int i=0; i<n; i++) if (i != fr && i != fg && i != fb) {
                    int x = std::max(red[i], std::max(blue[i] , green[i]) );
                    moves += red[i] + blue[i] + green[i] - x;
                }
                
                res = std::min(res, make_pair(moves,moves) );
            }
        }
    }
    return res.second;
}

This is exactly what I wanted to happen ever since I started using that strategy. If I opened the problems in the [Correct] order, I would have probably spent more time in 250 instead of less than 10 seconds (The pressure of the time reaching 0:00 made me wake up and notice the issue), so I would have acquired a far worse score. Then I would not have even had a chance to try the medium problem.

Comments?

Read More

HTTPS Everywhere ruleset for topcoder (Updated)

At this moment topcoder is my only source of revenue. Things like how, even if you manually use https, it tends to redirect you to a version with no https in some links, really bother and worry me.

Today I thought of Firefox's HTTPS Everywhere plugin (Also for Chrome). And tried to look how to make it do its magic on TopCoder.com and its subdomains. Surprise! it works:

<ruleset name="TopCoder">
  <target host="topcoder.com" />
  <target host="*.topcoder.com" />

  <!-- https://forums.topcoder.com does not exist, they should remove that link...-->
  <rule from="^https?://forums\.topcoder\.com/" to="https://apps.topcoder.com/forums/"/>
  <!-- Will the earth still spin if there were no regular expressions? -->
  <rule from="^http://([^.]+\.)?topcoder\.com/" to="https://$1topcoder.com/"/>
</ruleset>

For info about how to install it, take a look at this guide: https://www.eff.org/https-everywhere/rulesets.

Update I knew it was way too easy, there were bugs with the forums. subdomain. This new version should fix it.

Read More

Editorial for TopCoder SRM 567

We have changed the way I release topcoder editorials, now I first submit it to the wiki, then the admins publish it. This saves up the time that was spent between me sending the editorial by email and an admin submitting it manually to the wiki and uploading pictures and fixing the links himself... So editorials shall be available a bit faster than before. In fact, you can access http://apps.topcoder.com/wiki/display/tc/SRM+567 right now to read the editorial without waiting for [[rng_58]]'s post.

Regarding the editorial. I think the explanation for div1 1000 really sucks. It is really a challenging problem to explain. The solution is seemingly easy and even trivial (just memoization). But go ahead and try to prove that it works, or to explain how to come up with the idea, and it really broke my brain.

Since the last two editorials had huge delays, I decided to not wait till I can find the perfect explanation for this problem and instead release something that is mostly ok (but sucks). At least this time we did not wait 1 week for the editorial...

Read More

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.

Read More