Блог пользователя keko37

Автор keko37, история, 3 года назад, По-английски

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!

  • Проголосовать: нравится
  • +116
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +61 Проголосовать: не нравится

Reminder: the contest starts in less than one hour!

»
3 года назад, # |
  Проголосовать: нравится +71 Проголосовать: не нравится

The problem hiperkocka was wonderful.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    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
    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      My solution:

      Solution
      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +22 Проголосовать: не нравится

      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.

»
3 года назад, # |
  Проголосовать: нравится +36 Проголосовать: не нравится

How to solve D?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Spoiler
    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      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?

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +9 Проголосовать: не нравится

        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.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

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

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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);
            }
        
        • »
          »
          »
          »
          »
          3 года назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          Ohh, i think i get it. Thank you.

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

          • »
            »
            »
            »
            »
            »
            3 года назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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);

»
3 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +19 Проголосовать: не нравится
    Spoiler
    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +19 Проголосовать: не нравится

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

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +19 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится +8 Проголосовать: не нравится

          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?).

          • »
            »
            »
            »
            »
            »
            3 года назад, # ^ |
              Проголосовать: нравится +11 Проголосовать: не нравится
            in-contest snippet of code
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +19 Проголосовать: не нравится
    Hint
    Spoiler
»
3 года назад, # |
  Проголосовать: нравится +51 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +29 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +23 Проголосовать: не нравится

    oooooh, now I seeee :(

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

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

    Spoiler

    Is there a faster solution?

»
3 года назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

When will upsolving be open?

»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    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.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        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.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +23 Проголосовать: не нравится

      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.

»
3 года назад, # |
Rev. 5   Проголосовать: нравится +11 Проголосовать: не нравится

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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +36 Проголосовать: не нравится

    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.

»
3 года назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

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

You can submit your solutions here (HONI).