niyaznigmatul's blog

By niyaznigmatul, 6 years ago, translation, In English

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.

Live standings

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!

  • Vote: I like it
  • +73
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

How to solve D and E?

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it
    My solution to E
»
6 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve D?

  • »
    »
    6 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.