### Newtech66's blog

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

 » 4 weeks ago, # |   -10 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, # ^ |   0 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, # |   +334 Editorial of F for those, who can't wait:https://dmoj.ca/problem/tle16c8p6/editorial
 » 4 weeks ago, # |   +9 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 →   +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.
 » 4 weeks ago, # | ← Rev. 2 →   +59 It's hilarious only problem little_angel set is problem F
 » 4 weeks 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).
•  » » 4 weeks 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.
 » 4 weeks 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$.
•  » » 5 days ago, # ^ |   0 Why (1,3,2,4) means p=3421? if n>4, such as p=54321, how can I repesent it by cycle?
•  » » » 5 days ago, # ^ |   0 A little reading might help: https://en.wikipedia.org/wiki/Permutation#Cycle_notation
 » 4 weeks 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.
 » 4 weeks 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!
•  » » 4 weeks 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
•  » » » 7 days ago, # ^ |   0 For problem E, can DP work? I can't come up with it
•  » » 3 weeks 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.
•  » » 3 weeks 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$..
 » 4 weeks ago, # |   -18 My solution for C: https://codeforces.com/contest/1726/submission/171161877
 » 3 weeks 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.
•  » » 3 weeks ago, # ^ |   +26 Not they but he.
 » 3 weeks 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
•  » » 3 weeks 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.
 » 3 weeks ago, # |   +26 Why so many downvotes? I think the author of this blog doesn't deserve it.
•  » » 3 weeks ago, # ^ |   0 Because of this
 » 3 weeks 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
•  » » 3 weeks 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.
 » 3 weeks ago, # | ← Rev. 4 →   -8 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/171195357Time: 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 →   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
•  » » 3 weeks 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.
 » 3 weeks 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.
•  » » 3 weeks 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
•  » » » 3 weeks 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
•  » » » » 3 weeks 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
 » 3 weeks 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!
 » 3 weeks 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
•  » » 3 weeks 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
•  » » 3 weeks ago, # ^ |   0 In case if someone needs more readable code: 171168803
•  » » » 3 weeks 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
•  » » » » 3 weeks 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 :)
•  » » 3 weeks ago, # ^ |   0 DFS with shuffling the starting node is also sufficient
 » 3 weeks 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.
 » 3 weeks 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.
 » 3 weeks 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
 » 3 weeks 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?
 » 3 weeks ago, # |   0 can anyone pls explain the approach to solve problem D?
 » 3 weeks ago, # |   -8 Can anyone explain Disjoint Set Union Find Solution for problem C?
 » 3 weeks ago, # |   -8 Can C be solved using stack? If someone has done, please let me know. Thanks in advance!
•  » » 3 weeks ago, # ^ |   0 I have.
•  » » 3 weeks ago, # ^ |   -8 I have, check it out, constructed the graph using stack.171191174
•  » » » 3 weeks ago, # ^ |   0 okay wasn't expecting so many downvotes, what's wrong?
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 it can be solved with a stack yes check my solution 171728387
 » 3 weeks ago, # |   -8 Can anyone explain Problem C in more detail? Cant understand how indirectly connected components were observed? Thanking You
 » 3 weeks 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.
 » 3 weeks ago, # |   -8 Could someone provide me hindi video tutorial link to understand concept of problem H.Thanks in advanced.
 » 3 weeks ago, # |   0 Can anyone please explain problem C. I am unable to understand it by reading the editorial.
•  » » 3 weeks ago, # ^ |   0 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
•  » » » 3 weeks ago, # ^ |   0 Thanks a lot. I understood it by your explanation.
 » 3 weeks ago, # |   0 In problem E pk^-1 means 1/pk or something else? can someone clarify that!!!!
 » 3 weeks ago, # | ← Rev. 3 →   0 C can be done in a bfs like matter by utilizing a queue and a priority queue 171736806
 » 2 weeks 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}
•  » » 2 weeks ago, # ^ |   0 You're right, thanks for noticing.
 » 8 days ago, # |   0 For problem E,why O(tn) can pass it?173136257
•  » » 8 days ago, # ^ |   0 ok,I ignored the sum of.
 » 3 days 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.