mkisic's blog

By mkisic, history, 4 years ago, In English

Hi everyone!

Second round of COCI will be held this Saturday, November 14th at 14:00 UTC. You can access the judging system here. If you are not familiar with COCI contest format, we encourage you to read the announcement.

The round was prepared by paula, Gabrijel, dpaleka, bukefala, pavkal5 and me.

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

Hope to see you on Saturday!

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

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

Great contest with interesting problems! The implementation task and the binary search one were very neat. I felt like Euclid was so smart, especially the way those subtasks guide you to the right solution, though I didn't utilize that until 20-30 minutes to the end. Kept me entertained for a few hours or so. :)

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

What is the idea for Svjetlo (last problem about bulbs)?

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

    I reduced it to the following problem: assign an integer weight to every edge and every vertex. Edge weights represent the number of times the edge is crossed while walking the sequence, and a vertex weight is the number of ends of the sequence that are at that vertex (so the sum of vertex weights across all vertices must be even). I also rooted the tree at an off bulb, and pruned off subtrees that only contain on bulbs. Then one can see the following constraints:

    1. All edge have weight at least 1.
    2. For every on bulb the sum of the vertex and the incident edges must be a multiple of 4.
    3. For every off bulb the sum must be a multiple of 2 but not 4.

    Those constraints are also sufficient for an Eulerian path to exist that leaves all bulbs in the right state.

    After that it's a tree DP, where for each subtree you solve for each possible combination of edge weight to the parent and sum of vertex weights within the subtree. Edge weights never need to be greater than 4, since otherwise one can just subtract 4.

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

So what's the solution for Euklid?

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +26 Vote: I do not like it

    Let $$$K$$$ be such that $$$h^K > g$$$. Then take the smallest $$$b \ge h^K$$$ such that $$$g | b$$$, and $$$a = hb + g$$$.

    Motivation: the solutions must be less than $$$10^{18}$$$, so there aren't that many things that one can try.

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

    I reduced the problem to finding such $$$m \geq 1$$$ and $$$k \geq 1$$$ so that $$$h^k \leq 2^mg < 2h^k$$$ and then the answer is $$$2^mg$$$ and $$$(2^mh+1)g$$$.

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +12 Vote: I do not like it

    I believe you've gotten to this point, but for those who didn't get there, here's what I've got so far:

    We've got two cases:

    1. h <= g
    2. h > g

    For the first case this formula always works: a = h * g, b = g. The other part I don't know yet.

    For the partial 15 points, brute force does fine, so this way we can score 4 + 8 + 8 + 15 = 35 points.

    EDIT: Now I see, the full solutions were posted above. Don't mind me.

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

Editorial is now published here.

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

    Is there an upsolving of any kind or is running through the tests in the test set the only way to check the upsolved solutions?

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

      https://evaluator.hsin.hr/tasks/

      Go to HONI\2020.2021.\2. kolo

      There you will find all the problems, just click one of them and the process is simple from there on.

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

      You can also solve all problems here: https://oj.uz/problems/source/538

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

        I am honestly impressed by how your Korean platform is dedicated to putting out all these problems. Whenever I have a problem from certain contests that don't have upsolving on their website, e.g. CEOI, I can certainly find them on oj.uz. Keep up the good work! Thanks!