SRM 444 + answers to previous questions

Here's the SRM 444 screencast: AVI from narod.ru.

Summary: this screencast may seem a bit "slow motion". Somehow it took me much more time than usual to solve the problems (which I think were nice although probably too heavy with "standard" ideas, and I couldn't understand the problem statement of the easy problem for quite some time) - heh, it's strange to be sleepy at 3pm - but it's of course ACRush's superb performance that we should blame for the 500+ point margin :) Good job!

I wonder if there exists a non-exponential solution for the medium problem. Intuitively, it seems like with only one kind of block there might be some matching-style algorithm to solve it, but maybe the intuition is wrong. A reduction of an NP-complete problem to this problem would also be of interest, though :)

And here are the answers for the questions posted previously on this blog:

1) Why did the SRM 442 screencast interrupt in the middle? Imagine that you've coded the solution and submitted it almost without testing. Then, you realize you're not sure whether you should exchange i with j in one place in your code. You do that change, and see the code still pass all sample tests. You compile it in the arena, and find a test where it seems to break. You then change indexes back and compile in the arena again to see that the old version works on that test case. After all these changes, you realize that you don't remember which of the two versions you actually have submitted! How to find that out? Easy! Stop the screencast, open the recorded video and find the submission time :)

2) How to find last 10000 digits of x=a/b in base 31? First, if b ends with 0, then a also must end with 0, and we can remove both those zeros without changing the answer. Let's repeat that until the last digit of b isn't 0. Then, how to find the last digit x0 of the answer? Obviously, when multiplied by the last digit of b, it should give the last digit of a. But exactly one digit will satisfy that equation since 31 is prime! Then, we subtract b*x0 from a, and we can find the next-to-last digit x1 of the answer from the fact that multiplied by the last digit of b it should give next-to-last digit of a-b*x0 (the last digit of a-b*x0 is zero). We can repeat this process k times then. The final note is that one doesn't need to calculate a-b*x0 completely, as we only need the last k digits of it during the future process, and thus each step of the algorithm takes O(k), with the entire algorithm taking O(k^2).

Here's sample code that assumes a and b are given as arrays of digits with 0-th item representing the least significant digit (so the numbers are 'reversed'):

 1: int start = 0;
 2: while (b[start] == 0)
 3:     ++start;
 4: for (int i = 0; i < k; ++i) {
 5:     int x;
 6:     for (x = 0; x < 31; ++x)
 7:         if (x * b[start] % 31 == a[start + i])
 8:             break;
 9:     res[i] = x;
10: 
11:     // Subtraction
12:     int carry = 0;
13:     for (int j = start + i; j < start + k; ++j) {
14:           carry = carry + a[j] - b[j - i] * x;
15:           if (carry < 0) {
16:             int ncarry = (carry - 31 + 1) / 31;
17:             a[j] = carry - ncarry * 31;
18:             carry = ncarry;
19:           } else {
20:             a[j] = carry;
21:             carry = 0;
22:           }
23:         }
24: }