Hello.

On December 17th at 07:00 UTC we are hosting the second elimination round of our olympiad for high school students. More information on olympiad's website.

**Contest in gym: Innopolis Open, Elimination round 2, 2017-2018**

We hosted the first round Innopolis Open, Elimination round 1, 2017-2018 on December 2nd. Those, who already advanced to the final round, can skip the round, but certainly can participate if they want.

The problems are prepared by dusja.ds, burakov28, julsa, KamilBek, josdas, Nebuchadnezzar, disa, lightning, VArtem, pashka, niyaznigmatul, FireZi, iilnar. We thank the developers of PCMS for testing system, we also thank ilsaf13, who does the technical support of our olympiad. We thank the testers of the rounds kraborak, demon1999, haposiwe, zclimber, YakutovDmitriy.

We can discuss problems after the round here.

Good luck all!

Where can we find those who qualified from first round?

UPD: List of those qualified is here: https://olymp.innopolis.ru/ooui/innopolis-open-2017-2018/standings/all-final_en%20(1).htmlDamn you were really close :)

zscoder, prepare your solutions beforehand, please.

For problem E, is there a deterministic approach? I used a probablistic one to try and find the best partition, but got only 50 points.

Yes, sure. The problem can be reduced to Knapsack-problem, and since the weights are small enough (linear on the input length), it can be solved in polynomial time. You still have to do several optimization (they are deterministic) to get full score.

Yes, I saw that with knapsack we can solve it in

O(N^{2}). What optimizations are you talking about?Note that there are not many distinct weights. Also use bitsets to restore solution.

My solution works in time (which might be a bit tight but it managed to pass on first try.) and memory. Currently I'm not home so I don't have time to describe my entire solution but that should be my solution's complexity.

I see. The weights represent differences between pairs, and the sum of all values of all pairs is

N, therefor there are at most distinct values. So we can do knapsack in time, and in order to also maintain the actual sets we can use a bitset, which divides the memory by 32.By the way, the best way to pick coefficients is by picking primes, the coefficient 1 and the pairs {1, 0}, {1, 1}? This is what I did and I think it's optimal but I'm not sure how to prove it. Edit: nevermind it's actually easy to prove.

Although there may be at most sqrt(n) different values, how do you update the dp with only O(1) each time for a value, even if that value has multiple occurrences?

Let

dp[i][j] be the minimum number of typejnumbers to get a sum ofiassuming we use firstjtypes. (-1 if impossible)dp[i][j] = 0 ifdp[i][j- 1] ≠ - 1.dp[i][j] =dp[i][j-a[i]] + 1 ifdp[i][j-a[i]] ≠ - 1 anddp[i][j-a[i]] + 1 ≤cnt[j] (cnt[j] is the number of elements of typejwe can use)Note that you only need to store two rows of dp each time, so you can do this in

O(N) memory. The state transitions are clearlyO(1).Also, to restore the answers, you can use a bitset for each type as "parent" array to backtrack and find solution.

Hi! How to solve a problem B for 100% ? I solved it only for 17% . Can you give a hint or an algorithm ?

You don't need to test every single value of i, there are only a few values of i that matter (I tested 10).

And how i can find a value of i ?

check a,b,c,d,1,n ± 1

Where can I find problems? Can I submit somewhere?

For the last elimination round, they created a gym with the problems from that round.

Here: Innopolis Open, Elimination round 2, 2017-2018

Full solution to C. Credits: niyaznigmatul, 300iq.

If

nandmare odd, answer is -1.If sum of array is negative, answer is -1.

Otherwise, we can always find an answer.

Take an arbibtrary cycle. For example, when

mis even we can take:Similarly, when

nis even we can take:Write down numbers in this order and compute prefix sums

p_{1},p_{2}, ...,p_{n * m}. Letkbe the index of minimal number among them.Now, repeat this cycle infinitely many times and compute prefix sums on it again —

p_{1},p_{2}, ...,p_{n * m},p_{n * m + 1}, ...,p_{2 * n * m}, ....You can notice that there is no

p_{i}<p_{k}for anyi>k. From this you can infer thatp_{i}-p_{k}≥ 0 for alli>k. This means that we can take a cyclic shift of this cycle and putk-th element in the end and this will be the correct answer (since there will not be suchithatp'_{i}< 0, wherep' is a prefix sum array for this new cyclic shift).Can somebody show me code of B?

Where the editorial?

deleted