Всем привет.
23 декабря в 10:00 MSK состоится второй отборочный тур олимпиады. Больше информации можно узнать на сайте олимпиады.
1 декабря уже прошел Отборочный этап Олимпиады Университета Иннополис. Первый тур. 2018-2019. Тем, кто прошел в финальный этап по результатам первого тура, участвовать во втором туре не обязательно, но они могут это сделать, никак не повлияв на отбор. Призеры прошлых лет проходят в финал автоматически, зарегистрировавшись на соревнование. Также по результатам отборочных раундов пройдет отбор в Школу олимпиадной подготовки Университета Иннополис, информация по ней появится позже.
Предыдущие туры олимпиады можно найти по ссылке.
После конца тура здесь можно будет обсудить решения задач.
Всем удачи!
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
Хах, я понимаю, что решение D на 75 есть хорошее, но давайте подумаем как пропихнуть решение на 40 на все 75)) в моем решении все работает за n^4 (т.к. dp[n][n][2][n][n]) и это мемоизация, но при n = 100 падает память)) но у меня получилось переписать на char и вышло 400 мб.. и всего n^4 * 2.. выглядит реально, но я криворукий и не запихнул..( Проблема в том, что char медленее или это не так? или просто я очень криворукий?
UPD: это я криворукий)) по памяти n^4 а по скорости n^5 =( ну у кого проблема только в памяти, пользуйтесь =)
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.