That was not me, that was homo_sapiens.

2 0 2 2 2
| | | | |
2 4 2 4 2

Fourth 2 won’t break the scales.

My solution, which passes system tests, fails this test.

+/-1 in general doesn’t change odd/even for B%(A+1), if A is even. If B%(A+1) = 0, then (B-1)%(A+1) = A – oddness doesn’t change.

You don’t have to lose first two games. If you win the third game, you will have a bag big enough to fit any presents from first two days, should you win any.

(double post)

Let’s say the larger number is B, the smaller one is A. If A is odd, the case is pretty simple – after each turn B % 2 changes, so we win if and only if B%2 = 0.

If A is even, we win if B % (A+1) is even. To prove it we need to prove that each winning state has a move to a losing state, and that any move from the losing state only goes to a winning state.

If B % (A+1) is even, we can always make it odd by subtracting one, if B % (A+1) is not zero, or by subtracting A, if it is zero. That proves that from every winning state there’s a move into a losing state.

If B % (A+1) is odd, any turn will make it odd. This can be proven by induction: If you subtract A^0=1, B % (A+1) will obviously become even. Let’s say we have proven that subtracting A^k changes oddness. Since subtracting A^k * (A+1) obviously doesn’t change oddness (since it is divisible by A+1), subtracting A^(k+1) = A^k * (A+1) — A^k does change it. That proves that from any losing state you can only move to a winning state.

Well, even though I personally agree with Ivan, that ideally they should have stopped after the first paragraph, I've got to confess that what Yandex says is way better than what happens on ICPC or any other competition opening ceremony, when lots of people tell how proud they are to be in the same room with you and how proud they are to sponsor/organize/do whatever they do in this prestigious event (while, of course, they are not, and most of them don't really care -- most of them don't even understand what this competition is).
Yandex is honest with you, and I kind of enjoy it :)

Also I cannot help but mention one more time: solving problem doesn't make you a good coder. It's good up to certain extent, but other that that it just way of having fun (and of end up receiving prestigious achievement), and has nothing to do with developing any usefull skills.

Recent topcoder failure was not because of number of participants. TopCoder can handle 2200 participants pretty easily I believe.

> I like Codeforces hacking more than TopCoder challenges.
I definitely prefer TopCoder challenges rather than Codeforces hacks.

Потому что в раздельном контесте можно решить четыре задачи, а в общем только две. Первое делает человека более счастливым :о)

Писать сложный контест и решать в нем только А и В -- это не очень круто тоже.

Snowy, Hex

Anka, Chapay, Cleo

Troll, Dracul

gives 89, 5

My bad. I meant RRRRRL

You can see on which test your solution failed. Click on the submission ID on the status page.

I agree with al13n. This comparator seems not to be transitive.

If cross product of A and B > 0 and cross product of B and C > 0, it does not necessarily mean that cross product of A and C > 0, that said for your comparator A>B && B>C doesn't guarantee that A > C, which is required for std::sort

If N is very large (10^100 for example), and R is reasonably small (100 for instance), you can create (R+1)x(R+1) matrix A, which has ones on the main diagonal and on the diagonal above main, than compute v(A^N), where v is [1,0,0,0,...,0]. Last element of resulting vector will be the answer.

I believe this is what you were looking for

Yes, good point. Seems like it will work.

Marked it as bold for you :o)

if first K elements are non-decreasing sequence and last N-K+1 elements are non-increasing sequence

How does it handle case when left part is much longer than the right part?

1 2 3 4 5 6 7 8 9 10 3 for instance?

First of all,

a₁ * ( a₂ - 1 ) * ( a₃ - 2 )

During the contest, believing that two sequences which elements are the same, but indices are different, are different (which is wrong) I coded the following solution:

Meaning of i and j is the same as yours,

k is sum of lengths of left and right parts

z (z is from 0 to 1) is whether we ever moved right pointer or not. Since when left and right pointer meet, I cound solution if and only if either left pointer points to number strictly greater than the one right pointer points to, or if right pointer was never moved.

It gives answer=19 instead of 17 on the fourth sample, since it counts some 1 2 and 1 twice.

Have no idea how to handle equal sequences yet.

I checked my input file for that problem, and it contained only test cases where there's either unique answer or there's no answer. So likely both of you passed.

Fix what lamps are switched in the first row (2^m), iterate over all the rows starting from second (n), for each row for each lamp (m) switch it if and only if lamp above is off.

Complexity is 2^m*m*n.

I have compared my answer to the answer of the person who used gauss, and it was the same.

I used 2^n*n*m solution.

May be it can be proven that answer is alweys unique. Or facebook is lame enough to prepare only tests which have unique solution.

Even though it did appear to me that gauss works, I've chosen to do 2^n*n*m anyway. Since it seems to be much easier..

Also interedted in how to solve problem B.

Mike: just to make sure you know: this topic appears on Russian when one is watching the site in English interface.

In .NET 4.0:

using System.Numerics;

BigInteger a;

Then you can use it as a regular integer number. All the operators are overloaded, so you can easily do something like that:

BigInteger a = BigInteger.Parse( Console.ReadLine( ) );
BigInteger b = BigInteger.Parse( Console.ReadLine( ) );
BigInteger c = a + b;

But AFAIR this server doesn't support .NET 4.0, so anyway you will need to implement big integers by hands if you want to solve that problem using C#.

Decide = принять решение
Solve = решить (задачу)