keko37's blog

By keko37, history, 3 years ago, In English

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!

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

| Write comment?
»
3 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Reminder: the contest starts in one hour.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Typo in the announcement

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Thanks! We'll fix it soon.

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

      Sorry, but I can't see the tasks in the given site. Where should I go in this site?

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it -18 Vote: I do not like it

        Sorry, the registration closed at 14:10 UTC.

»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

How to solve problem C?

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

... 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 years ago, # ^ |
      Vote: I like it +36 Vote: I do not like it

    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 years ago, # |
  Vote: I like it +5 Vote: I do not like it

How to solve Volontiranje for full score?

»
3 years ago, # |
  Vote: I like it +77 Vote: I do not like it

My solutions:

Spoiler
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

    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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why in Logicari taking the arbitrary edge does work?

»
3 years ago, # |
  Vote: I like it +23 Vote: I do not like it

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

You can submit your solutions here (HONI).

»
3 years ago, # |
  Vote: I like it -15 Vote: I do not like it

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

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

    deleted

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      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.