Hi, Here's the editorial.
Please note that not all the codes presented below belong to me. (It's a combination of codes from our problemsetters and testers) -- And I borrowed AKGMA's account since I wasn't able to link to my own submissions somehow!
Note: It seems that the Codeforces mark-up is not functioning. To see a submission go to: http://www.codeforces.com/contest/282/submission/submission-number
A: Bit++
Just use a simple loop. (Take a look at the Python code)
GNU C: 3314471
Python: 3314475
B: Painting Eggs
This one can be solved by a greedy algorithm. Start from the 1st egg and each time give the egg to A if and only if giving it to A doesn't make the difference > 500, otherwise give it to G.
To prove the correctness, one can use induction. The base case is trivial. Suppose that we've assigned the first n - 1 eggs such that the total money given to A is Sa and total money given to G is Sg. We can assume Sa ≥ Sg. Now we must either add gn to Sg or add an to Sa. If we can't add gn to Sg, then Sg + gn > Sa + 500, so - 500 > Sa - Sg - gn, adding 1000 to both sides gives us the inequality 500 > Sa + (1000 - gn) - Sg which is exactly what we need to make sure that we can add an = 1000 - gn to Sa.
GNU C: 3314488
Python: 3314492
C: XOR and OR
First of all, check the length of the two strings to be equal. Then with a little try and guess, you can find out that the zero string (00...0) can't be converted to anything else and nothing else can be converted to zero. All other conversions are possible.
GNU C++: 3314503, 3314504, 3314509, 3314512, 3314514
D: Yet another Number Game
For n=1, everything is clear. If a1 = 0 then BitAryo wins, otherwise BitLGM is the winner.
For n=2: define win[i][j] = (Whether i,j is a Winning position). It's easy to calculate win[i][j] for all i and j, using a loop (Checking all possible moves). This leads us to an O(n3) solution.
For n=3: Everything is similar to NIM, With the same statement of proof as for NIM, i,j,k is a winning position if and only if (i xor j xor k) ≠ 0.[Don't forget the parentheses in code :) ] Complexity: O(1)
One can also solve this case using DP. We define lose[i][j]= (Least k, such that i,j,k is a losing position) ,lose2[i][j]=(Least k, such that k,k+i,k+i+j is a losing position) and win[i][j][k] just as the case with n=2. As in the codes below, one can calculate all these values in O(n3).
Using the same DP strategy for n=2 and the O(1) algorithm for n=3 and n=1, leads us to a total complexity of O(n2) which was not necessary in this contest.
GNU C++: 3314578, 3314580, 3314585, 3314588
E: Sausage Maximization
Can be solved using a trie in O(n log (max{ai})).
Start with a prefix of size n, and decrease the size of prefix in each step. For each new prefix calculate the XOR of elements in that prefix and add the XOR of the newly available suffix (which does not coincide with the new prefix) to the trie, then query the trie for the best possible match for the XOR of the new prefix. (Try to get 1 as the first digit if possible, otherwise put 0, then do the same thing for the second digit and so on). Get a maximum over all answers you've found, and it's all done. [By digit, I mean binary digit]
We hope you enjoyed the tasks.
