joseacaz's blog

COCI 2018/2019 Round 4
By joseacaz, history, 6 years ago, In English

I couldn't seem to find a blog entry for this contest (COCI Round 4), so I created one! Let's discuss the problems of the fourth round of the COCI since the contest is already over. (http://hsin.hr/coci/)

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

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

How did you guys solve the last problem, Akvizna?

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

    I am the author of the last problem.

    Let dp[i][j] be the maximum possible amount that Mirko can win in game with i rounds and j opponents at the beginning, divided by 100 000. dp[i][j] = min (dp[i — 1][j — k] + k / j), for k in 1, 2...j It is enugh to get 20 points.

    To get 50% you need some observations. Let a_1, a_2...a_k be the number of people that have been thrown out in each round. It's not hard to prove that a_1 >= a_2 >= ... >= a_k. Also a_1+a_2+...+a_k = n so we get a_i <= n/i, because otherwise we would have a_1+a2+...+a_k > n. Because of that dp[i][j] = min (dp[i — 1][j — k] + k / j), for k in 1, 2,...n/i so total complexity is now n*(n+n/2+...+n/k) = n^2*(1+1/2+...+1/k) = n^2 log k and that is enough to get 65 points.

    To get 100% you have that see that dp[i][j+1] — dp[i][j] <= dp[i][j] — dp[i][j — 1] which means that we can use aliens trick.

    More about aliens trick you can learn here. https://ioinformatics.org/files/ioi2016solutions.pdf (the last problem, subtask 6.)

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

      Wow, never before had I heard of Alien's trick, thank you so much! By the way, really nice problem, especially (now that I know how to solve it) the second subtask.

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

      You can eliminate the log factor. dp[i][j] = min(j × dp[i - 1][k] - k) / j + 1, so it's a classical problem of finding a minimum y-intercept of function dp[i - 1][k] × x - k, aka convex hull trick.

      If you are not very confident on the precision, then you may prefer faster routines to make long doubles work..

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

        Yes, and you can also use divide and conquer optimization (quadrangle inequality).

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

I need to know how to solve the third problem kisik, still don't know why my code fails so bad haha

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

    Nevermind, didn't read the FAQ. It says:

    4. Should I use %lld or %I64d for long long input/output in C++?
%lld.
    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      4. Should I use %lld or %I64d for long long input/output in C++?
      %lld.

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

        Yeah I've just read it :(

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

    I'm not sure if you still need it, but I'll leave you my code for the problem here Code

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

      I did something like that, mine only works for N <= 1000. I will check my code for correctness. Thank you!!

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

How to solve Slagalica?

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

    Suppose after a mega move number at node X moves to node Y. Add an edge between X and Y. If you do this for all N * M nodes, the whole parallelogram will be decomposed into some simple cycles. K must be equal to lcm of those cycle lengths.

    Let the prime factorization of K be p1a1p2a2...pkak. We must have . This condition is both necessary and sufficient for the existence of answer. Because it is possible to swap any 2 adjacent nodes of the parallelogram with the given operations. For example applying T(x - 1, y - 1), T(x - 1, y - 1), R(x - 1, y - 1) consecutively swaps numbers at nodes (x, y) and (x - 1, y). Since now we can swap 2 adjecent numbers, it's not hard to construct cycles of lengths p1a1, p2a2, ..., pkak

    → Reply