keko37's blog

By keko37, history, 2 months 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, paulica, 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

»
7 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

Reminder: the contest starts in one hour.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    How can I do submission now for practice the problems?

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Typo in the announcement

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

    Thanks! We'll fix it soon.

    • »
      »
      »
      7 weeks 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?

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

        Sorry, the registration closed at 14:10 UTC.

»
7 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

How to solve problem C?

»
7 weeks 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

  • »
    »
    7 weeks 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.

»
7 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

How to solve Volontiranje for full score?

»
7 weeks ago, # |
  Vote: I like it +77 Vote: I do not like it

My solutions:

Spoiler
  • »
    »
    7 weeks 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.

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why in Logicari taking the arbitrary edge does work?

»
7 weeks 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).

»
7 weeks 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?

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

    deleted

    • »
      »
      »
      7 weeks 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.

»
7 weeks ago, # |
  Vote: I like it -28 Vote: I do not like it

Who needs this competition? It is not in Russia