Newtech66's blog

By Newtech66, 4 weeks 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

»
4 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

In My Submissions, Submission for B 171095283 gives Time Limit Exceeded, where as 171097503 Passes. Both submissions are nearly identical, except in the first I'm creating a list and then printing the list, and in second, I'm just printing the values with a for loop. Is this a language problem ? and why ?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That's very tricky, some test has huge(100000) test cases, you need to read all cases input and print all outputs at once, otherwise you will get TLE. The interaction of I/O will cost more time for every sub test case.

»
4 weeks 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

»
4 weeks 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?

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +29 Vote: I do not like it
    Sketch
»
4 weeks 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

»
4 weeks 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)
  • »
    »
    4 weeks 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.

»
4 weeks 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$$$.

»
4 weeks 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.

»
4 weeks 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!

  • »
    »
    4 weeks 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

    • »
      »
      »
      7 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      For problem E, can DP work? I can't come up with it

  • »
    »
    3 weeks 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.

  • »
    »
    3 weeks 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$$$..

»
3 weeks 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.

»
3 weeks 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

  • »
    »
    3 weeks 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.

»
3 weeks 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.

»
3 weeks 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

  • »
    »
    3 weeks 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.

»
3 weeks ago, # |
Rev. 4   Vote: I like it -8 Vote: I do not like it

Hi, i am getting wa but i checked my output its number of connected components c1+c2 is same as that of jurys(i.e. minimized). Can anyone tell what is the checker comment trying to say.

My Submission: https://codeforces.com/contest/1726/submission/171195357

Time: 0 ms, memory: 140 KB Verdict: WRONG_ANSWER Input 4 5 7 1 2 2 3 3 4 4 5 5 1 1 3 3 5 4 4 1 2 2 3 1 4 3 4 6 7 1 2 1 3 3 4 4 5 1 4 5 6 6 2 2 1 1 2 Participant's output 0111000 1000 1100000 0 Jury's answer 1110001 1101 1011011 1 Checker comment wrong answer jury found a smaller answer than participant (test case 1)

»
3 weeks 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

  • »
    »
    3 weeks 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.

»
3 weeks 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.

  • »
    »
    3 weeks 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

    • »
      »
      »
      3 weeks 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

      • »
        »
        »
        »
        3 weeks 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

»
3 weeks 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!

»
3 weeks 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

  • »
    »
    3 weeks 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.com/contest/1726/submission/171216269

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In case if someone needs more readable code: 171168803

    • »
      »
      »
      3 weeks 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

      • »
        »
        »
        »
        3 weeks 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 :)

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    DFS with shuffling the starting node is also sufficient

»
3 weeks 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.

»
3 weeks 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.com/contest/1726/submission/171216269 Any help is highly appreciated.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

From problem C editorial : Further we have pb=pa−1 and pk−2=pk−1−1=pk−2=pb−1. This implies a<(k−1), hence a≤(k−2)≤b, however, pk−2=pb−1<pb. [Contradiction]

can anyone explain how we get the implication? I am having trouble understanding

»
3 weeks 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
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone pls explain the approach to solve problem D?

»
3 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

Can anyone explain Disjoint Set Union Find Solution for problem C?

»
3 weeks 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!

»
3 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

Can anyone explain Problem C in more detail? Cant understand how indirectly connected components were observed? Thanking You

»
3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

Could someone provide me hindi video tutorial link to understand concept of problem H.Thanks in advanced.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please explain problem C. I am unable to understand it by reading the editorial.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    if you encounter ')' ( closing bracket) you need to check whether this bracket belongs to one component or multiple components if it belongs to one component then you increment your answer by one if it belongs to multiple components then you don't increment your answer because you already considered that component before.

    if the substring s[i...j] is balanced and the substring s[k...i-1] 0<=k<i-1 is balanced then it belongs to multiple components

    ex: ( ( ) ( ) )

    s[4...5] and s[2...5] are in the same connected component so you only treat them as one component

    have a look at my submission 171728387

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks a lot. I understood it by your explanation.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem E pk^-1 means 1/pk or something else? can someone clarify that!!!!

»
3 weeks 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

»
2 weeks 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}

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it
Another approach for D