keko37's blog

Croatian Open Competition in Informatics (COCI) 2021/2022 — Round #2
By keko37, history, 2 years ago, In English

Hi everyone!

The second round of COCI will be held tomorrow, November 13th 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 Bartol, paula, pavkal5, 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
  • +116
  • Vote: I do not like it

Comments Comments (44)
| Write comment?
»
2 years ago, # |
  Vote: I like it +61 Vote: I do not like it

Reminder: the contest starts in less than one hour!

→ Reply
»
2 years ago, # |
  Vote: I like it +71 Vote: I do not like it

The problem hiperkocka was wonderful.

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

    I normally hate construction problems but this one wasn't too bad. Here's my construction — I'm curious whether others had significantly different ones:

    Spoiler
    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      My solution:

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

        I think that probably ends up being equivalent to my solution (certainly the ith edge of my trees have xor $$$2^i$$$, for certain numbering of the edges), but obviously is a little easier to code.

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

      My solution is similar to kshitij_sodani's one but I make the additional observation that one can choose the roots as the vertices which belong to a subspace of $$$\mathbb F_2^n$$$.

      Let us root the tree at $$$n$$$ and, for each $$$0\le i<n$$$, let $$$p_i$$$ be the parent of $$$i$$$. The edge $$$p_i - i$$$ corresponds to flipping the $$$i$$$-th bit. So, if we choose where to put the vertex $$$n$$$ in the hypercube we have fixed a placing of the whole tree in the hypercube. How do we choose the $$$2^{n-1}$$$ roots? Let $$$z = \sum_{a: p_a=n} 2^a$$$. A vertex $$$0\le v<2^{n-1}$$$ is chosen as a root if $$$z\wedge a$$$ has an even number of bits.

      It is not hard to check that this produces a valid tiling.

      → Reply
»
2 years ago, # |
  Vote: I like it +36 Vote: I do not like it

How to solve D?

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

      I think I have thought a very similar way, but I couldn't build DP. First, I considered sorting the array. Then I thought of building a DP like $$$dp[i][j][k]$$$ where this element holds the number of ways of permuting numbers from $$$i^{th}$$$ index to $$$j^{th}$$$ index such that at least $$$k$$$ slots are needed for permuting that way. Can I continue from here or do I need to think something else?

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

        I started thinking along those lines (although 1..j instead of i..j), but I don't see a way to define the recurrence relation since knowing the slots required by a permutation of 1..j doesn't give you enough information to know how many extra slots are required when inserting j+1 into all possible positions.

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

      Could you elaborate a bit more on the full solution ? What exactly your states and transitions look like ?

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

        Here's the core of the DP from my solution. $$$i$$$ is the number of the magnet being added, $$$p$$$ is the number of segments before adding it, $$$x$$$ is the number of empty spaces required before adding it. The three sections of the inner loop are for if the new magnet gets attached to 2, 1 or 0 of the existing segments.

            vector<vector<mr>> dp(1);
    dp[0].resize(L + 1);
    dp[0][0] = 1;
    for (int i = 0; i < N; i++)
    {
        vector<vector<mr>> dp2(i + 2, vector<mr>(L + 1));
        for (int p = 0; p <= i; p++)
        {
            for (int x = 0; x <= L; x++)
            {
                if (x + 2 * r[i] <= L && p >= 2)
                    dp2[p - 1][x + 2 * r[i]] += dp[p][x] * p * (p - 1);
                if (x + r[i] <= L && p >= 1)
                    dp2[p][x + r[i]] += dp[p][x] * p * 2;
                dp2[p + 1][x] += dp[p][x];
            }
        }
        dp = move(dp2);
    }
        → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          Ohh, i think i get it. Thank you.

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

          Hello! I'm having trouble understanding the first recurrence relation in the dp.

          dp2[p - 1][x + 2 * r[i]] += dp[p][x] * p * (p - 1);

          I understand that this is the transition where we merge two segments so, in my head, we should increase dp2[p — 1][x + 2 * r[i]] by dp[p][x] * the number of all the 2 consecutive segments we can chose to merge aka (p-1). I know this way of thinking about it is somehow wrong, but I can't figure out why.

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

            I considered the segments to be unordered relative to each other. Your way would work too (treating the segments as having an order), as long as you also adjust the transition for adding a new segment. Off the top of my head, I think it would become dp2[p + 1][x] += dp[p][x] * (p + 1);

            → Reply
»
2 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Could anyone share the solution for E? Thanks for the contest btw

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it
    Spoiler
    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +19 Vote: I do not like it

      What exactly do you mean by a "sparse table"?

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

        CP algorithms definition linked here.

        I think of sparse tables as the data structure which enables performing binary lifting, but I admit I do not really follow the terminology myself.

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

          For binary lifting I stored the position reached after inserting $$$2^i$$$ maximal lineups starting from each position $$$j$$$. But that doesn't sound like quite the same as the sparse tables you've linked to — I'm not sure what you'd store in a sparse table (number of lineups and endpoint of the last one?).

          → Reply
          • »
            »
            »
            »
            »
            »
            2 years ago, # ^ |
              Vote: I like it +11 Vote: I do not like it
            in-contest snippet of code
            → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it
    Hint
    Spoiler
    → Reply
»
2 years ago, # |
  Vote: I like it +51 Vote: I do not like it

I ended up wasting a lot of time on problem E because I missed the constraint that a lineup must consist of a contiguous range of people — I thought one could pick any subset. If you're interested in a challenge see if you can find a sub-quadratic solution (I did).

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

    I now know at least 3 people who read it wrongly this way. Kinda weird how so many people read it wrongly...

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

      Good to know it's not just me :-) My guess is that when I wrote the code to read the input I only saw reference to two sorts of ranges (range of heights and range of people for queries) so forgot that there is a third sort of range (range of people in a lineup).

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

      Now at least $$$4$$$.

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

    oooooh, now I seeee :(

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

    I also misread the problem this way, but I couldn't come up with a solution faster than

    Spoiler

    Is there a faster solution?

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

      Sounds like you came up with the same solution as me. I also got TLE with it, even on the smaller cases.

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

      +1

      → Reply
»
2 years ago, # |
  Vote: I like it +21 Vote: I do not like it

When will upsolving be open?

→ Reply
»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I struggle to understand why the solution for problem Kutijie works. I understand the graph representation as I also used in my own 35p solution. But, I feel like the we should look for strongly connected components instead of only connected components. Could anyone please enlighten me why it works?

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

    Looking at strongly connected components is the right idea. You may notice that the graph generated by a permutation P, where there only exist directed edges i -> P[i], is made up of multiple simple cycles. For each cycle, all the vertices on it are in the same SCC. This is the same as saying that all the vertices in one connected component (ignoring how edges are directed) are in the same SCC.

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

      I think I get it now. The graph generated by a single permutation consists only of simple cycles and singletons because P is a permutation and at some point and this means that checking for a SCC is the same as checking for a CC. Tho, is there any proof for the fact the simple cycles thing? I can visualize why it happens but I'm just wondering.

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

        Each node in the graph generated by the permutation has exactly one edge entering it and one edge leaving it, so if you choose a node V and repeatedly go forward using the edge leaving V, you will at some point return to V, thus V is on a simple cycle.

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

      I didn't realize each CC is a SCC during the contest.

      So I used a stupid method with bitmask and get passed. Time complexity is $$$O(n^3/w)$$$.

      Now I know how silly I was.

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

Problem D is very nice and the way the recurrence is built is very interesting. I have never seen such a way of thinking :

"Instead of finding the answer for a whole subarray, find the sum of the answers if this subarray is splitted into $$$k$$$ independent groups. If we do it this way, the answer for the whole subarray is stored in the 'DP for splitting the subarray into 1 group'."

It is very, very clever to do so. Are there any other problems that relies on this idea or is it a very specific DP? If there are no known similar problems, Bartol [orz], can you at least share the story for the preparation of the problem? Thank you so much.

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

    There was a great blog post some time ago about this topic — link.

    This idea is usually used when trying to construct permutations with certain properties.

    → Reply
»
2 years ago, # |
  Vote: I like it +26 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).

→ Reply