Blog entries - Codeforces

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

At first I tell about the contest at all.

My problems in the contest were A-div2, B-div2, C-div2/A-div1, E-div2/C-div1, D-div1. I wanted to make only div.2 round, but then we decided to give you seven problems at both divisions. MikeMirzayanov prepared the problem about milk pouring and anonymous gave E-div1 problem. Also RAD gave some advices to complicate problems Azembler and Flags a bit.

And now let's start analysis.

Problem A (div.2) - Restoring Password

Password was very easy to restore. You should just iterate over groups of 10 characters in the first string and over all codes. Then, if some number's code is equal to the group - print that number.

Here's the example: http://pastebin.com/hMV0NcjN

Problem B (div.2) - Friends

Let's construct the graph where vertices correspond to the people and edges correspond to the relationships. Then paint each edge in this way: edge will be red if the men connected by it are friends and black otherwise. Now let's think what is "three pairwise acquainted people" and "three pairwise unacquainted people". We see that they are cycles of only red and only black vertices correspondingly, and the length of these cycles is 3.

Now we know the solution: write 3 "for" cycles, one cycle for one vertex, and check if the edges between these vertices are only red or only black.

Here's the solution: http://pastebin.com/gswaxGmM

Another way to solve it is to notice the answer is FAIL if and only if graph has exactly 5 edges and they all together form a cycle with a length 5. It's very funny solution, I think. Here's the code: http://pastebin.com/09T0ixrJ

Problem A (div.1) / C (div.2) - Frames

The problem is easy, but there were many tricky cases - and contestants show it successful :) I added almost all these cases to the pretests because I didn't want to arrange Beta Round 60.

So let's solve the problem. At first notice that the answer is not greater than 3 because we always can do three selections (maybe, some of them are empty): with first selection we select end of the first row, with second one - begin of the last row, and with last one - all remaining folders (they form the rectangle).

The best way is to find all cases with answer 1 and 2. Try to do it.

If the answer is 1, we can select all folders from a to b with one selection. There must be nothing hard to detect these cases:

first and last folders are in the same row (21 5 7 9);
first folder is in the first column, and the last folder - in the last column (21 5 1 15), сase m = 1 is included here;
first folder is in the first column, and the last folder is n (21 5 6 21). Case when we must select all folders is included here. I was very surprised when I saw that many contestants forgot about it.

And these are the cases with answer 2:

first and last folders are in the adjacent rows (21 5 8 14);
first folder is in the first column (21 5 6 13);
last folder is in the last column (21 5 4 15);
last folder is n (21 5 4 21);
and another tricky case: if the column where first folder is located is just at right from the column where the last column is located (21 5 3 12).

If no one of these conditions is true, answer is 3.

Here's the solution: http://pastebin.com/8QRytzzF

Problem B (div.1) / D (div.2) - End of Exams

Greedy algorithm solves this problem. We should consecutively try to pour milk from each bottle into each available cup and in maximal possible amount.

Also we always need to know, how much milk is in each bottle and each cup, for each cup - bottles from which we have poured milk, and for each bottle - cups into which we have poured milk.

Writing it is not hard. But where is one special moment - if we compare real numbers, we must use EPS, or we can get WA on test 12 (50 1000 49). Some programs write NO on this test while answer is YES, because of wrong comparing of real numbers.

It must be said that answer can be calculated in integers: just set the volume of milk in each bottle mn. And only when we will print the answer, we divide each volume by mn and multiply by w. All three jury solutions didn't think up this :)

Here's the solution: http://pastebin.com/HG5Nrxne (be careful, it's not as beautiful as previous ones)

Problem C (div.1) / E (div.2) - Azembler

I don't know why so few coders have solved it. Small limitations for n and big time limit - 5 seconds - hint that it's backtracking. Also, no need to be a soothsayer to understand that maximal answer is about 5.

Solving it is clear. You should keep all current registers at the vector and call some function that goes over all current registers and calculate new values, then calls itself recursively. In that process we can also save the program itself.

To avoid TLE you should not make recursive calls if the deep of recursion is larger than current answer, should not go to the states where you get a number larger than n or less than current biggest number. And if you reach exactly n, you should update answer and copy the program to the safe place.

There are some hacks to speed up this approach: for example, iterate over numbers in descending order (it works faster), but 5 seconds is such TLE that you can solve it any way. Or you can launch backtracking for the specific answer (increasing it) while the program won't be found (I don't know how this method is named in English). Also, some contestants have solved it using BFS.

Here are two solutions: standard backtracking (http://pastebin.com/Z6ZF36st) and backtracking for the specific answer (http://pastebin.com/viiYF9CB).

Problem D (div.1) - Flags

I think my solution is not optimal, it's too long. Many solutions submitted during the contest are shorter. But I tell you about my solution.

At first I solve the problem for the number of stripes equals N (or L = R).

Let $\text{[math]}$ is the number of flags with exactly N stripes where symmetrical flags are not identical. Try to get the answer using this designation.

At first sight it seems that answer is $\text{[math]}$ . But it's not true for the palindromes. For example, for non-palindromes WBWB and BWBW we should count only one of them, but for the palindromes, such as WBW, it leads to mistake, because each palindrome is symmetrical to itself.

So for the flags with even number of stripes formula $\text{[math]}$ is correct, because there are not palindromes among them. And if N is odd, the correct formula is $\text{[math]}$ , where $\text{[math]}$ is the number of palindromes with N stripes. Each palindrome is definited by its first $\text{[math]}$ stripes, and we can write that $\text{[math]}$ .

Now we can give an answer if we know how to calculate number of flags where symmetrical flags are not equal. Notice that if we know two last stripes of the flag, we can definitely say if we can add another stripe to its end.

Let's use dynamic programming. As a state we can take a vector $\text{[math]}$ with a length 8 where each its component keeps a number of flags with N stripes and definite two last colors (exactly 8 options). And $\text{[math]}$ is total number of flags with N stripes.

As start state we can take vector $\text{[math]}$ which consists of ones (because there are 8 flags with a length 2, one flag for one possible combination of two colors). And how to calculate $\text{[math]}$ ?

It turns out that there is some matrix A that $\text{[math]}$ . Its elements can be found even using pen and paper: for example, let's we have a combination of two last stripes WB. Then it's possible to add white or yellow stripe to the end, and the last stripes will be BW and BY correspondingly. It means that we can write 1 to the matrix where the row are BW or BY and the column is WB.

We're about the finish. It's obvious that $\text{[math]}$ . Power of matrix can be calculated with a logarithmic time - that's because our problem is solved. And don't forget if N = 1 then answer is 4 and there's no need to do these calculations.

But it was only problem where L = R. Let's find a solution for the segment $\text{[math]}$ .

I know two ways to do it. First way is to add a new component to the vector and new row and column to the matrix. This new component should keep the total number on the segment $\text{[math]}$ (if L = 1, we can write "if" somewhere at the beginning of the program). And the matrix A should be changed a bit: try to do it by yourself.

I like the second way. As we did it earlier, we will find a number of flags where symmetrical ones are different, but on the segment $\text{[math]}$ . It is equal to $\text{[math]}$ . Let's learn how to calculate the sum E + A + ... + A^N quickly.

Let b is such maximal power of 2 that 2b - 1 ≤ N. We can write $\text{[math]}$ .

And apply some math magic to the first part of the previous formula: $\text{[math]}$ . And the expression in the brackets at the second part of that formula is... I think you've already understood it :)

We forgot about the palindromes, but it's very easy to calculate their number. Let's suppose that L and R are odd (if they are even, we can add one to L and substract one from R). Then $\text{[math]}$ .

That's all. Don't forget to apply "mod" operation after each operation and examine border cases carefully. And here's the solution: http://pastebin.com/wHu1tPgd (yes, "matrix" and "vector" type definitions are strange - I've totally forgotten how to write in Pascal)

Problem E (div.1) - Lostborn

This problem can be solved using inclusion-exclusion principle. If $\text{[math]}$ is the answer, then the following formula works: $\text{[math]}$ . But if you write only this recursive function, you get TLE. Many contestants got TLE and were hacked because they didn't run maximal test on their computers.

And the others who sensed that something was wrong memorized the answers for small n and all a_i. For example, you can see solution by rng_58 who won the contest, or this solution: http://pastebin.com/4kcfJdAi.

anonymous, the author of this problem, wrote his thoughts about it there: http://codeforces.net/blog/entry/2216 (but now there's only russian version). His solution works even if n = 10¹⁵ and it can be viewed here: http://codeforces.net/problemset/status/93/E?order=BY_CONSUMED_TIME_ASC. It seems that any solution submitted during the contest would get TLE if n = 10¹⁵.

Sorry for my English :)

Full text and comments »

dalex's blog