### Newtech66's blog

By Newtech66, 13 months ago,

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
• -170

| Write comment?
 » 12 months ago, # |   +334 Editorial of F for those, who can't wait:https://dmoj.ca/problem/tle16c8p6/editorial
 » 12 months ago, # |   +9 As it turns out, the envelope of the unsafe area is given by the parametric equations How do you derive these equations?
•  » » 12 months ago, # ^ | ← Rev. 2 →   +29 SketchImagine rotating the chord so that it goes from tangent to the diagonal edge to tangent to the horizontal edge. That is, the angle the chord makes with the $x$-axis is given by $\pi-\theta$, where $\theta$ goes from $\alpha$ to $\pi$.Let $\ell(\theta)$ denote the position of the leftmost vertex of the chord (lying on the diagonal line), and $r(\theta)$ denote the position of the rightmost vertex of the chord (lying on the $x$-axis). By the Law of Sines, $|\ell(\theta)|=\frac{\sin\theta}{\sin\alpha}$ while $|r(\theta)|=\frac{\sin(\theta-\alpha)}{\sin \alpha}$.Let $x(\theta)$ and $y(\theta)$ be as defined in the editorial. It remains to show that $m(\theta)=(x(\theta),y(\theta)))$ is the intersection of the line segments $\overline{u(\theta)\ell(\theta)}$ and $\overline{u(\theta+\epsilon)\ell(\theta+\epsilon)}$ as $\epsilon\to 0$. Indeed, we can verify that$\frac{-d |\ell(\theta)|}{d |r(\theta)|}=\frac{-\cos\theta}{\cos(\theta-\alpha)}\implies \frac{|\ell(\theta)-m(\theta)|}{|m(\theta)-r(\theta)|}=\frac{-d |\ell(\theta)|\sin(\theta-\alpha)}{d |r(\theta)|\sin \theta}=\frac{-\cos\theta \sin(\theta-\alpha)}{\cos(\theta-\alpha) \sin \theta}.$It follows that$m(\theta)=\frac{\cos(\theta-\alpha) \sin \theta\cdot \ell(\theta)-\cos\theta \sin(\theta-\alpha)\cdot r(\theta)}{\sin \theta\cos(\theta-\alpha)-\cos\theta \sin(\theta-\alpha)}=\frac{\cos(\theta-\alpha) \sin \theta\cdot \ell(\theta)-\cos\theta \sin(\theta-\alpha)\cdot r(\theta)}{\sin \alpha}$.After substituting in $\ell(\theta)=\left(\frac{\sin\theta}{\sin\alpha},0\right), r(\theta)=\frac{\sin(\theta-\alpha)}{\sin \alpha}\cdot (\cos\alpha, \sin \alpha)$ and simplifying, we can verify that this gives the equations for $x(\theta)$ and $y(\theta)$ described in the editorial.
 » 12 months ago, # | ← Rev. 2 →   +59 It's hilarious only problem little_angel set is problem F
 » 12 months ago, # | ← Rev. 3 →   -10 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)I tried a single dp. Let $dp[i]$ be the number of almost perfect permutations.We consider the last two elements $i-1$ and $i$. We have the identity $(i-1)$ and $(i)$ or the transposition $(i-1, i)$. This is $2 \cdot dp[i-2]$. Fix $(i)$ and make a transposition of $i-1$ with some element from the first $i-2$. This is $2 \cdot (i-2) \cdot dp[i-3]$ since it is the same case when fixing $(i-1)$ and changing $i$. Neither $i-1$ nor $i$ remain there. We can do two transpositions. Choose two elements from the first $i-2$, where the order matters. This is $(i-2) \cdot (i-3)$, so we have $(i-2) \cdot (i-3) \cdot dp[i-4]$. Now instead of two disjoint transpositions, we consider the 4-cycles. We have $i-1$ and $i$, so we need two other consecutive elements. There are $i-3$ choices, and two different 4-cycles can be made. This is $2 \cdot (i-3) \cdot dp[i-4]$. Overall we get$dp[i] = 2 \cdot dp[i-2] + 2 \cdot (i-2) \cdot dp[i-3] + (i-2) \cdot (i-3) \cdot dp[i-4] + 2 \cdot (i-3) \cdot dp[i-4]$.I think all these cases do not overlap, but of course I may be wrong. I have been trying different small changes to these cases but I couldn't get it right, although I think the general idea should work. Maybe someone can find the mistake(s).
•  » » 12 months ago, # ^ |   +6 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, 8Now 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.
 » 12 months ago, # | ← Rev. 2 →   0 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$.
•  » » 12 months ago, # ^ |   0 Why (1,3,2,4) means p=3421? if n>4, such as p=54321, how can I repesent it by cycle?
•  » » » 12 months ago, # ^ |   0 A little reading might help: https://en.wikipedia.org/wiki/Permutation#Cycle_notation
 » 12 months ago, # |   +48 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.
 » 12 months ago, # |   +14 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!
•  » » 12 months ago, # ^ |   0 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
•  » » » 12 months ago, # ^ |   0 For problem E, can DP work? I can't come up with it
•  » » 12 months ago, # ^ |   +13 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.
•  » » 12 months ago, # ^ |   +16 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$..
 » 12 months ago, # |   +25 Ahhhh round is unratedWhat kind of punishment are they going to get?They should be kicked out from IIT Kharagpur for defaming its name.
•  » » 12 months ago, # ^ |   +26 Not they but he.
 » 12 months ago, # |   0 In D, can anyone please explain this statement written in editorial in Problem DClearly, it would be best if there was no cycle in B.Thanx in advance
•  » » 12 months ago, # ^ |   0 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.
 » 12 months ago, # |   +26 Why so many downvotes? I think the author of this blog doesn't deserve it.
•  » » 12 months ago, # ^ |   0 Because of this
•  » » 5 weeks ago, # ^ |   0 Repost the Editorial explaining it and then ask why so many people downvoted. I guess you should get the answer. If not People Who downvoted will get a nice editorial
 » 12 months ago, # |   0 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
•  » » 12 months ago, # ^ |   +3 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.
 » 12 months ago, # | ← Rev. 4 →   0 For problem DI used union-find to create spanning tree, but cannot get rid of cycle for other colorCan 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
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 I used union-find to solve the problem. submissionTo handle the cycle: Force one of the 3 edges making the cycle into the original tree Exclude the other 2 edges from the next building of the tree 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.
 » 12 months ago, # |   0 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.
•  » » 12 months ago, # ^ |   0 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
•  » » » 12 months ago, # ^ |   0 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
•  » » » » 12 months ago, # ^ |   0 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
 » 12 months ago, # |   +42 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!
 » 12 months ago, # |   0 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
•  » » 12 months ago, # ^ |   0 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
•  » » 12 months ago, # ^ |   0 In case if someone needs more readable code: 171168803
•  » » » 12 months ago, # ^ |   0 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
•  » » » » 12 months ago, # ^ |   0 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 :)
•  » » 12 months ago, # ^ |   0 DFS with shuffling the starting node is also sufficient
 » 12 months ago, # | ← Rev. 2 →   0 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.
 » 12 months ago, # | ← Rev. 3 →   0 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.
 » 12 months ago, # |   0 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
•  » » 6 months ago, # ^ |   0 You can also see that as pb=pa-1 and p(k-2)=pk-2=pb-1, if we put pb from 1st equation pk-2=pa-2. So, pk is equal to pa (pk=pa). In my opinion, this proof is rather observation.I also didn't understand the above implication.
 » 12 months ago, # |   +16 Why so many downvotes? The problem was stolen by one person. That doesn't make the whole org responsible. SpoilerHow would you have prevented this if you were the author?
 » 12 months ago, # |   0 can anyone pls explain the approach to solve problem D?
 » 12 months ago, # |   -8 Can anyone explain Disjoint Set Union Find Solution for problem C?
•  » » 6 months ago, # ^ |   0 Editorial of C is quiet about observation, rather than proof. The person who wrote this editorial should use the term observation rather than proof.
 » 12 months ago, # |   -8 Can C be solved using stack? If someone has done, please let me know. Thanks in advance!
•  » » 12 months ago, # ^ |   0 I have.
•  » » 12 months ago, # ^ |   -8 I have, check it out, constructed the graph using stack.171191174
•  » » » 12 months ago, # ^ |   0 what is logic behind making a edge for ) ( if(i&&s[i-1]==')'){ adj[i].push_back(i-1); adj[i-1].push_back(i); } in this piece of code??
•  » » » » 12 months ago, # ^ |   0 see if u observe.....see every open bracket "(" can be mapped to a particular unique close bracket ")" . so a edge between these always exist.constituting a component in itself, like so what i am trying to say is () () () open-close bracket pair is a component.// this is what u asked ->when these two component coalesce that is this case ( (1) (2) ) here 1-2 pair will also have an edge that is two components are going to share an edge or coalesce or merge in to 1. that will happen when we encounter this case "....)(....." in this situation two components are always merging.
 » 12 months ago, # |   +26 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.
 » 12 months ago, # | ← Rev. 3 →   0 C can be done in a bfs like matter by utilizing a queue and a priority queue 171736806
 » 12 months ago, # |   +8 In the solution of problem G,I think the formula might be like this: \begin{aligned}P=\prod_{\text{all }} {cnt_{}!}\end{aligned}
•  » » 12 months ago, # ^ |   0 You're right, thanks for noticing.
 » 12 months ago, # |   0 For problem E,why O(tn) can pass it?173136257
•  » » 12 months ago, # ^ |   0 ok,I ignored the sum of.
 » 12 months ago, # |   0 Another approach for D... make spanning tree for Red and then see the Blue part if cycle exist then transfer one of the edges of blue to red ..let the endpoints of this edge be x1,x2...in a way cycle has been passed to red part ...now find all the edges in the cycle in red and change colour of any edge that has one endpoint as x1 or x2 (but not both) to blue ..in this way cycle will be removed from red part too and an optimal ans is obtained.
 » 10 months ago, # | ← Rev. 4 →   0 My submissioncan someone figure out the TC or whats wrong in my approach ?My approach: I am forming stree with Blue vertices and all other edges I am throwing into red The extra edges can be atmost three red edges<=2 => No cycle in red. so We found the answer => Red edges==3 and red vertices>3 no cycle in Red we found answer Red edges==3 and vertices in red are 3 => There is cycle in red. so I select one of the red edge(x1,x2) in the triangle formed by the three edges and swap with another blue edge which is inside a blue cycle. This blue cycle is formed when I added back the edge(x1,x2) to blue tree. There will always be a single cycle in blue tree and that cycle contains edge(x1,x2)
 » 6 months ago, # |   0 Problem C using (Stack + DSU) 197719883