niyaznigmatul's blog

Innopolis Open, Elimination round 2, 2017-2018
By niyaznigmatul, 6 years ago, translation, In English

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.

Scoreboard

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, budalnik, 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 craborac, demon1999, haposiwe, zclimber, YakutovDmitriy.

We can discuss problems after the round here.

Good luck all!

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

»
6 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

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).html

→ Reply
»
6 years ago, # |
  Vote: I like it +11 Vote: I do not like it

zscoder, prepare your solutions beforehand, please.

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

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.

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

    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.

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

      Yes, I saw that with knapsack we can solve it in O(N2). What optimizations are you talking about?

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

        Note that there are not many distinct weights. Also use bitsets to restore solution.

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

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it

      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.

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

        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?

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          Let dp[i][j] be the minimum number of type j numbers to get a sum of i assuming we use first j types. (-1 if impossible)

          dp[i][j] = 0 if dp[i][j - 1] ≠  - 1.

          dp[i][j] = dp[i][j - a[i]] + 1 if dp[i][j - a[i]] ≠  - 1 and dp[i][j - a[i]] + 1 ≤ cnt[j] (cnt[j] is the number of elements of type j we 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 clearly O(1).

          Also, to restore the answers, you can use a bitset for each type as "parent" array to backtrack and find solution.

          → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Where can I find problems? Can I submit somewhere?

→ Reply
»
6 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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

If n and m are 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 m is even we can take:

Similarly, when n is even we can take:

Write down numbers in this order and compute prefix sums p1, p2, ..., pn * m. Let k be the index of minimal number among them.
Now, repeat this cycle infinitely many times and compute prefix sums on it again — p1, p2, ..., pn * m, pn * m + 1, ..., p2 * n * m, ....
You can notice that there is no pi < pk for any i > k. From this you can infer that pi - pk ≥ 0 for all i > k. This means that we can take a cyclic shift of this cycle and put k-th element in the end and this will be the correct answer (since there will not be such i that p'i < 0, where p' is a prefix sum array for this new cyclic shift).

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody show me code of B?

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -31 Vote: I do not like it

Where the editorial?

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

deleted

→ Reply