At first I tell about the contest at all.
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
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 :)
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.
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 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 . 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 is correct, because there are not palindromes among them. And if N is odd, the correct formula is , where is the number of palindromes with N stripes. Each palindrome is definited by its first stripes, and we can write that .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 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 is total number of flags with N stripes.
As start state we can take vector 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 ?
It turns out that there is some matrix A that . 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 . 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 .
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 (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 . It is equal to . Let's learn how to calculate the sum E + A + ... + AN quickly.
Let b is such maximal power of 2 that 2b - 1 ≤ N. We can write .
And apply some math magic to the first part of the previous formula: . 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 .
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 is the answer, then the following formula works: . 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 ai. For example, you can see solution by rng_58 who won the contest, or this solution: http://pastebin.com/4kcfJdAi.
Sorry for my English :)