Hello.
On December 23rd at 07:00 UTC we are hosting the second elimination round of our olympiad for high school students. More information on olympiad's website. The rules are IOI-like. Round will last for 5 hours, and consist of 5 problems to solve.
We hosted the first round Innopolis Open, First elimination round, 2018-2019 on December 1st. Those, who already advanced to the final round, can skip the round, but certainly can participate if they want.
We can discuss problems after the round here.
Good luck all!
How to solve D and E?
Transform the expression to a tree; each internal node is an operation with 2 children, and a leaf has a value. Every updates changes something in some node and you need to update on the path up, and finally output the value of the root.
My solution consists of a daunting HLD with about 300 lines (although I did not try conserving on lines, I tried to have the least amount of bugs possible). I ended up with only 3 bugs and managed to fix them in time (and then also had to do some constant optimization).
I will leave the remaining details for you to figure.
If you manage to find some sqrt decomposition solution, I highly suggest using it instead. I didn't find one.
When will be upsolving opened? I found a bug and fixed it in 20 minutes after contest was over. Here is my code. Possibly, contains some errors: https://hastebin.com/ditikicuje.pl
Oh, cfuk, I see there might be (((1|1)|1)|1) etc
When will test cases be awailable? I need test case #3 of group 2, 3, 4 or test case #16 of group 5 for problem D.
Innopolis Open, Second elimination round, 2018-2019
How to solve D?
My 75-point-solution:
We need 2 dp-tables, dp1 is the result player 1 reaches from this state of the game, if it's his turn, dp2 is the result of player 2. dp1 has 4 dimensions (for dp2, it's similar): i: the number of potions player 1 has (he didn't drink it and player 2 didn't destroy it). j: the number of potions player 2 has. ii: units of mana player 1 has (including the potion he drinks in this round). jj: units of mana for player 2.
If ii is bigger than j or jj is bigger than i, the game ends, since the player can destroy all potions of the opponent, therefore we don't have to store these cases.
In normal cases (i,j,ii>0), we have the following recursion: dp1[i][j][ii][jj]=max(conv21(dp2[i-1][j][ii][jj+b[m-j]]), dp1[i][j-1][ii-1][jj]), where conv21 calculates the result of player 1 from the result of player 2.
We can do the same to calculate values of dp2.
The result is dp1[n][m][a[0]][0].
With this solution, you might have problem with memory, but you can solve this easily.
Well that was my solution and I got 40 points and a TLE on test 63 for the 35 points subtask.
I want to know the full solution.