Newtech66's blog

Codeforces Round #819 (Div. 1 + Div. 2) and Grimoire of Code Annual Contest 2022 Editorial
By Newtech66, 2 years ago, In English

We'd like to thank you all for participating in the contest, and hope you enjoyed it. Hope to see you again next year!

The editorial for problem F will be added soon. It is now added.

1726A - Mainak and Array

Idea: anubhavdhar
Editorial: anubhavdhar

Hint 1
Hint 2
Solution
Implementation

1726B - Mainak and Interesting Sequence

Idea: anubhavdhar
Editorial: anubhavdhar

Hint 1
Hint 2
Solution
Implementation

1726C - Jatayu's Balanced Bracket Sequence

Idea: Newtech66
Editorial: anubhavdhar

Hint 1
Hint 2
Solution
Implementation

1726D - Edge Split

Idea: Newtech66
Editorial: Newtech66

Hint 1
Hint 2
Hint 3
Solution
Implementation

1726E - Almost Perfect

Idea: Newtech66
Editorial: Newtech66, anubhavdhar

Hint 1
Hint 2
Hint 3
Key fact
Solution 1: the easy way
Solution 2: the hard way
Implementation

1726F - Late For Work (submissions are not allowed)

Please note that it is no longer possible to submit solutions to this problem on Codeforces. You can read the details here.

Idea: little_angel
Editorial: Newtech66

Hints
Solution
Implementation

1726G - A Certain Magical Party

Idea: Newtech66
Editorial: Newtech66, anubhavdhar

Hints
Solution
Implementation

1726H - Mainak and the Bleeding Polygon

Idea: anubhavdhar
Editorial: Newtech66, anubhavdhar

Hint 1
Hint 2
Solution
Implementation

Vote for the problems here!

Feel free to vote for your opinion of each problem, and the best problem of the contest.

Vote here
  • Vote: I like it
  • -170
  • Vote: I do not like it

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

Editorial of F for those, who can't wait:

https://dmoj.ca/problem/tle16c8p6/editorial

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

As it turns out, the envelope of the unsafe area is given by the parametric equations

How do you derive these equations?

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

It's hilarious only problem little_angel set is problem F

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

I will show my idea for problem E so maybe someone can tell me where I'm wrong.

Wrong idea (thanks ffao for pointing the mistake)
→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    In the last case, you removed two values from the middle when creating your 4-cycle, so if you removed 4,5 your list of remaining values looks something like 1, 2, 3, 6, 7, 8

    Now note that 3 and 6 are adjacent in the new list, but not consecutive. So you can't use the value of dp[i-4] for this new list.

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

For problem E, the editorial says the third type of cycles is
$$$(i, j, i + 1, j + 1)$$$,
while in fact it can be one of two flavors:
$$$(i, j, i + 1, j + 1)$$$ and
$$$(i, j + 1, i + 1, j)$$$.
Here, for uniqueness, we assume the first term of the cycle is its minimum element.
Edit: I see now the above point is where this differs from the editorial.

Example 1: cycle is $$$(1, 3, 2, 4)$$$, permutation is $$$p = 3 4 2 1$$$, inverse is $$$p^{-1} = 4 3 1 2$$$.
Example 2: cycle is $$$(1, 4, 2, 3)$$$, permutation is $$$p = 4 3 1 2$$$, inverse is $$$p^{-1} = 3 4 2 1$$$.

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

Problem E, an alternative view of the "easy way" solution:

$$$\displaystyle \sum\limits_{s = 0}^{\left\lfloor\frac{n}{4}\right\rfloor} {n - 2 s \choose 2 s} \cdot 2^s \cdot (2 s - 1)!! \cdot I_{n - 4 s}$$$

Consider the individual factors:

  • $$${n - 2 s \choose 2 s}$$$: say we have $$$s$$$ cycles of length 4. This means we have to divide $$$n$$$ positions into $$$(2 s)$$$ pairs for these cycles and $$$(n - 4 s)$$$ single elements for other cycles. This can be seen as, out of a total of $$$(n - 4 s + 2 s)$$$ pairs plus singles, selecting the positions for $$$(2 s)$$$ pairs.

  • $$$2^s$$$: each cycle of length 4 can come in one of two flavors: $$$(i, j, i + 1, j + 1)$$$ and $$$(i, j + 1, i + 1, j)$$$.

  • $$$(2 s − 1)!! = (2 s - 1) \cdot (2 s - 3) \cdot \ldots \cdot 3 \cdot 1$$$: Look at the $$$2 s$$$ pairs from left to right, and pair them up in cycles of length 4. The leftmost pair has $$$(2 s - 1)$$$ choices, the leftmost pair left after that has $$$(2 s - 3)$$$ choices, and so on.

  • $$$I_{n - 4 s}$$$: The single elements form cycles of lengths 1 and 2. Again look from left to right. Either the leftmost element remains single, or it is paired up with any of the elements to the right. Thus $$$I_k = I_{k - 1} + I_{k - 2} \cdot (k - 1)$$$, which can be found by a separate linear dynamic programming.

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

Problem E, question: how do you people come up with the complete list of the cycles that can appear? Do you start building a cycle on paper, carefully consider all the possibilities that appear, and just obtain the list, along with the constructive proof?

My case was, after failing with just an $$$I_k$$$ solution, writing a brute force solution and looking at the permutations in the form of cycle products. Here is an example with only the most interesting permutations shown up to length 10: those that contain at least 2 cycles of length >2. So, I have not really proven that there are no other cases, but no other cycles appeared up to $$$n = 11$$$, and that evidence was strong enough.

And better late than never: thanks to the authors for this problem!

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

    When I came up with the problem, my first course of action was to write a brute force for small n and observe some basic properties of the valid permutations, like their cycles. From there I observed that only cycles of length $$$1$$$, $$$2$$$ and $$$4$$$ were present.

    From here, it was easy for anubhavdhar to come up with the formal proof that this was indeed the case.

    I'd love to hear how others approached this problem. And I'm happy you liked it :D

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

    For me, the first train of thought after seeing permutations is examining cycles. I considered enforcing constraints for some index $$$i$$$: the one before and after it, $$$p_i^{-1}$$$ and $$$p_i$$$, differ by $$$1$$$. Then I tried fixing a value. Say $$$p_i^{-1} = 3$$$. Then $$$p_i = 2$$$ or $$$4$$$. Say its $$$4$$$. I'll abbreviate applying $$$p$$$ $$$k$$$ times as $$$p_i^k$$$. Then $$$p_i^3 = 5$$$. $$$p_i^5 = 6$$$. $$$p_i^7 = 7$$$. Eventually we'll loop back to $$$p_i^{-1}$$$ and get stuck. Aha, so we can't have chains longer than length $$$2$$$. Therefore, we conclude only length $$$1, 2, 4$$$ cycles work.

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

    In my case, I did not solve the problem because I could not come up with an easy way of deciding how many ways of choosing k pairs of consecutive numbers there was, but I deduced that fact without brute forcing.

    I started working with the identity $$$|p_i - (p^{-1})_i| \le 1$$$. The first thing I did was getting rid of $$$p^{-1}$$$, since it makes reasoning more difficult (like changing from two variables to one).

    $$$|p_i - (p^{-1})_i| \le 1 \quad\text{for all $$$i$$$} \iff |p_{p_i} - (p^{-1})_{p_i}| \le 1 \quad\text{for all $$$i$$$,}$$$

    because $$$p_i$$$ is a permutation. This way, since $$$p^{-1}_{p_i} = i$$$, we can write

    $$$|p_{p_i} - i| \le 1 \quad\text{for all $$$i$$$.}$$$

    We already see that $$$p_{p_i}$$$ is appearing there. So it makes sense to consider cycles, which are sequences of the form $$$p_i, p_{p_i}, \dots$$$. In fact, we also have $$$|p_{p_{p_i}} - p_i| \le 1$$$, for example. For me, this i what can give the reasonable idea of decomposing the permutation in cycles. Let $$$a_1, \dots, a_n$$$ be indices such that $$$a_{i+1} = p_{a_i}$$$. (We are working with subindices modulo $$$n$$$). The condition becomes $$$|a_{(i+2\mod n)} - a_i| \le 1$$$. Note that making this hold for all cycles is equivalent to our initial condition.

    Call $$$a_i$$$ and $$$a_{i+2 (\mod n)}$$$ neighbors. It is easy to see that since the smallest element only has a possible neighbor, you can only have cycles of length $$$1$$$, $$$2$$$ and $$$4$$$. More precisely, $$$i - 2 \equiv i+2 \mod n$$$ if and only if $$$4 \equiv 0$$$ if and only if $$$n = 1,2,4$$$..

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

Ahhhh round is unrated

What kind of punishment are they going to get?

They should be kicked out from IIT Kharagpur for defaming its name.

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

In D, can anyone please explain this statement written in editorial in Problem D

Clearly, it would be best if there was no cycle in B.

Thanx in advance

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

    Including an edge that creates a cycle is adding a new path between vertices that already have a connection and therefore doesn't change the number of connected components. Including an edge that doesn't create a cycle connects two previously unconnected components reducing the total by 1 and the objective is to minimize this number.

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

Why so many downvotes? I think the author of this blog doesn't deserve it.

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

Problem D: 1726D - Edge Split My code almost same as described above. First I maked a tree by Blue edge on dfs(). Then checked is there any loop with Red edge, if there then swapped blue edge with red edge. Got wrong answer. Where did I wrong? My code: 171145235

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

    Because the red edge you swapped with a blue edge might create a new cycle in the blue graph. However there might be some other replacement which won't create a cycle.

    → Reply
»
2 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

For problem D

I used union-find to create spanning tree, but cannot get rid of cycle for other color

Can any one explain how will dfs for spanning tree will help in getting rid of cycle as mentioned in tutorial.

Thanks in advance.

Also can this question be solved using Union Find

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

    I used union-find to solve the problem. submission

    To handle the cycle:

    1. Force one of the 3 edges making the cycle into the original tree

    2. Exclude the other 2 edges from the next building of the tree

    3. Now try building the spanning tree again. You will end with a complete tree and one edge that don't make a cycle with the 2 excluded edges.

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

Why is my solution for D giving WA on test 2. For removing the Blue cycle of length 3, I am taking one vertex u from cycle. Find any black edge adjacent to u and color it blue and color any blue edge in cycle adjacent to u black.

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

    if you color a black edge adjacent to u randomly,then color a blue edge in cycle adjacent to u black,the graph constructed by black edges may not be connected;

    for example 6 8 1 2 1 3 2 3 1 4 1 5 2 6 3 6 5 6 firstly,if we construct a spanning tree with black edge 4,5,6,7,8 blue edge 1,2,3 form a cycle then we expect there is no cycle,if we make edge 4 blue ,then make edge 2 black,the graph constructed by black edges is not a spanning tree anymore

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

      we should make one of 3 blue edges black,other two edges are still blue,then select n-2 edges from remaining n-1 edges to form a spanning tree,it's obvious that there is no cycle in blue graph or black graph

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

        would it be correct if I generalise this: out of all the extra edges(edges joining already connected components) , give first one to Red edge set and rest to Blue edge set then start giving edges that join the connected components to the Red set

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

I don't know about F, but problems A, B and C are good ones! (though problem A ruined my first 30 minutes of the contest)

Also, a request to everyone, Since all the problems except F are made by anubhavdhar and Newtech66, they are not the ones who should be downvoted. The thief only contributed problem F to the problem set. Instead of blindly downvoting the blog and the editorial, please be mature!

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

You can solve D by shuffling the order of edges and building a spanning tree using DSU while the edges you haven't included in a spanning tree are in a cycle 171135740

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

    Hi. I tried the same here. Did one iteration from index 1 to m and one from m to 1 but my submission is failing for some reason. Any help is appreciated. https://codeforces.net/contest/1726/submission/171216269

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

    In case if someone needs more readable code: 171168803

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

      why did you choose to go for a randomized solution? Did you prove that your solution will pass the Time limit. If so, how did you assess the time complexity

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

        I didn't choose. In the contest, I implemented not randomized solution.

        After the contest, I was just curious will it work, and if yes, how fast?

        Turned out that my solution is now the fastest :)

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

    DFS with shuffling the starting node is also sufficient

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

    I used the same idea but if you solve a problem with a shuffle should you define your self as a accepted?

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

I have another solution for D.

We first build DFS tree and color the tree edge $$$x$$$ with color $$$dep[x]\bmod 2$$$, and write a brute force enumeration other edges' color.

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

I tried to solve D using DSU but my submission is failing. "wrong answer jury found a smaller answer than participant (test case 150)". Not sure what that means. I tried to build the spanning tree using DSU and marked an edge connecting u and v '1' if there is another existing path between u & v and both u & v are not in the set of nodes which are connected by already marked edges. I ran the iteration once from 1 to m and once from m to 1 so that I get maximum possible marked edges without breaking the connectivity of the graph.

https://codeforces.net/contest/1726/submission/171216269 Any help is highly appreciated.

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

Why so many downvotes? The problem was stolen by one person. That doesn't make the whole org responsible.

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

can anyone pls explain the approach to solve problem D?

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

Can C be solved using stack? If someone has done, please let me know. Thanks in advance!

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

I can't completely understand the editorial of G, but I have a solution which doesn't need segment tree and works in $$$O(n)$$$ time. My submission is now the second shortest solution, and I believe many of the shortest submissions used this solution.

For a $$$\langle x,0\rangle$$$, it in fact requires exactly $$$T-x$$$ numbers which are strictly less than it to be after it. And for a $$$\langle x,1\rangle$$$ ($$$x\ne T$$$), it requires exactly $$$i-m$$$ numbers which are no more than it to be after it. So we can insert the numbers from small to big. My code can help understand.

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

C can be done in a bfs like matter by utilizing a queue and a priority queue 171736806

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

In the solution of problem G,I think the formula might be like this: \begin{aligned}P=\prod_{\text{all }<u,v>} {cnt_{<u,v>}!}\end{aligned}

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

For problem E,why O(tn) can pass it?173136257

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C using (Stack + DSU) 197719883

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem B: According to tutorial, for N = 6 and M = 16 ans will be — 1, 1, 1, 1, 6, 6 but xor these elements is 0 which is less than every element of sequence so either question is wrong or solution is wrong, Please correct me if I am wrong.

→ Reply