Блог пользователя keko37

Автор keko37, история, 3 года назад, По-английски

Hi everyone!

The 16th season of COCI is starting soon! The first round will be held tomorrow, October 16th at 14:00 UTC. You can access the judging system here. If you are not familiar with the COCI contest format, we encourage you to read the announcement.

The round was prepared by pavkal5, paula, ominikfistric, Shtef and me.

Feel free to discuss the problems in the comment section after the contest ends.

Hope to see you tomorrow!

  • Проголосовать: нравится
  • +177
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

Reminder: the contest starts in one hour.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Typo in the announcement

»
3 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

How to solve problem C?

»
3 года назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

... if the intended solution for problems sets was actually FWHT like what I described here, why is TL so tight. I had to optimize the for loops for it to pass.

If that was going to fail I was legitamately going to find the answer under modulo $$$1000000009$$$ and $$$1000000033$$$ (because $$$3$$$-rd root exists there) then combine them using CRT.

TLE code AC code

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +36 Проголосовать: не нравится

    The official solution runs in 0.135 seconds, so it seemed fine to leave the TL at 1 second.

    The difference is probably because we stored numbers in the form a + bw, where a and b are integers and w^3 = 1, so there is no need for floating point values.

»
3 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

How to solve Volontiranje for full score?

»
3 года назад, # |
  Проголосовать: нравится +77 Проголосовать: не нравится

My solutions:

Spoiler
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +31 Проголосовать: не нравится

    The crucial observation which proves the correctness of the algorithm you described for Volontiranje is the following one.

    Let $$$i_1,i_2,\dots, i_q$$$ and $$$j_1,j_2,\dots, j_q$$$ be two disjoint longest increasing subsequences. Then also $$$\min(i_1,j_1), \min(i_2,j_2), \dots, \min(i_q,j_q)$$$ and $$$\max(i_1,j_1), \max(i_2,j_2), \dots, \max(i_q,j_q)$$$ are disjoint longest increasing subsequences on the same set of indices.

    Thanks to this fact, we may assume that there is a set of disjoint longest increasing subsequences of largest cardinality where the subsequences are ordered (we say that $$$(i_k)\le (j_k)$$$ if $$$i_k\le j_k$$$ for each $$$1\le k\le q$$$). If we replace the smallest of such subsequences with the absolute minimum among all subsequences we still get a valid solution. Hence we have shown that we may assume that the minimum longest increasing subsequence is chosen; then we repeat the algorithm on the remaining indices.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Why in Logicari taking the arbitrary edge does work?

»
3 года назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

The tasks, test data, and solutions are now published! You can find them here.

You can submit your solutions here (HONI).

»
3 года назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится

In the editorial of problem Kamenčići it is solved by DP, how can we solve it without dp?

  • »
    »
    3 года назад, # ^ |
    Rev. 3   Проголосовать: нравится -21 Проголосовать: не нравится

    deleted

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +11 Проголосовать: не нравится

      Getting AC on a YES/NO problem without multitest is not something that allows you to say "I got AC so I think it's safe to say my solution works." I recommend stress testing your solution before saying it's correct if you don't have a proof.

      If k=2 and the string is CCCCPC, then according to you player 1 takes from the left, player 2 takes from the right(arbitrarily), player 1 takes from the right, player 2 loses.

      In reality, player 2 has a winning strategy: just take from the left if player 1 took from the left and take from the right if player 1 took from the right.