### Newtech66's blog

By Newtech66, 4 weeks ago,

Hello Codeforces!

Grimoire of Code, the official Competitive Programming club of IIT Kharagpur, is happy to invite everyone to take part in Codeforces Round #819 (Div. 1 + Div. 2) and Grimoire of Code Annual Contest 2022 which will take place on 06.09.2022 17:35 (Московское время). This round will be rated for everyone.

You will be given 8 problems and 2 hours 15 minutes to solve them.

The problems have been authored and prepared by Grimoire of Code members Anubhav anubhavdhar Dhar, Debajyoti little_angel Dasgupta, and Mainak Newtech66 Roy.

We'd like to thank all the people who made this round possible:

We hope everyone will enjoy the contest.

Grimoire of Code is the official Competitive Programming club of IIT Kharagpur created by and for competitive programming enthusiasts. We promote competitive programming culture in our college, and provide a forum for interested minds to discuss their thoughts and ideas. We also conduct mock coding rounds for placements and internships in Indian colleges.

You can check out our Facebook page here.

You can check out the problems from last year's Annual Contest here.

UPD1: The contest duration has been extended to 2 hours 15 minutes.

UPD2: Score distribution: $500-1000-1500-2000-2250-2750-3250-3500$

UPD3: Congratulations to the winners!

UPD4: Editorial (editorial for F will be added soon) It is now added.

UPD5: The contest is unrated due to problem copying. Details.

• -1094

 » 4 weeks ago, # |   +337 As a tester
•  » » 4 weeks ago, # ^ |   +65 when asking for downvotes and asking for upvotes are unsurprisingly in the same SCC
•  » » » » 4 weeks ago, # ^ |   +12 you've reposted in the wrong connected component
•  » » » » 4 weeks ago, # ^ |   0
•  » » » » 4 weeks ago, # ^ |   +8 For not wasting time, the secret in lots of spoiler is help_me_please. :D.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +60 posting mind blowing meme to get upvotes :
 » 4 weeks ago, # |   +60 As the leamderGive me upvotes :)
•  » » 4 weeks ago, # ^ |   +45 Domne
 » 4 weeks ago, # |   +52 As an authorHope that everyone will enjoy the problems! :D
 » 4 weeks ago, # |   +30 Div 1+2 and 8 problems! Looking forward to it.When will scoring distribution come out?
 » 4 weeks ago, # |   +9 As a tester, I just hope everyone's super-super-supercalifragilisticexpialidocious performance on the contest.
 » 4 weeks ago, # |   +30 As not a tester, I did not test this round.
 » 4 weeks ago, # |   -10 I want contribution, I also want rating, I can't have both of them, So I choose rating instead of contribution.
 » 4 weeks ago, # | ← Rev. 2 →   +15 As a participant,I'm hoping for a great round!
•  » » 4 weeks ago, # ^ |   +14 As an author, me too.
•  » » » 4 weeks ago, # ^ |   +7 Looking forward to it :p
 » 4 weeks ago, # |   -16 Spoiler IIT KGP FTW
•  » » 4 weeks ago, # ^ |   -10 okay
 » 4 weeks ago, # |   -262 As an author We have tried our best to make the problems as interesting as possible! Hope you guys have fun brainstorming the solutions. Looking forward to see everyone on the leaderboard !! All the best for higher ratings
•  » » 4 weeks ago, # ^ |   -8 omg that thumbs up emoji looks fabulous
•  » » 4 weeks ago, # ^ |   -21 also YOU SHOULDNT BRAINSTORM THE SOLUTIONS WITH OTHERS DURING CONTEST ITS AGAINST THE RULES(yes, I couldn't believe my eyes after reading that line)
•  » » » 4 weeks ago, # ^ |   -22 what's wrong with all this downvote, I'm just stating the facts. are they all cheaters or what
•  » » » » 4 weeks ago, # ^ |   -251 Come on dude! Isn't it obvious that, by "you guys", I meant everyone, brainstorm the solutions "individually"
•  » » » » » 4 weeks ago, # ^ |   +76 Well, yes, except for the fact that brainstorming, in common sense and as stated on this wikipedia page, is a "group creativity technique". Using a group creativity technique where there isn't a group would be a pain...
•  » » » » » » 4 weeks ago, # ^ |   +6 got downvoted for being right
•  » » » » » » 4 weeks ago, # ^ |   +3 now this is a comeback
•  » » » » » » » 4 weeks ago, # ^ |   0 help me, this comeback has reversed somehow
• »
»
4 weeks ago, # ^ |
+7

after the contest, I realized.

## You (plural) might have tried your best to make the problems as interesting as possible, but you (singular) didn't! Shame on you!

•  » » 4 weeks ago, # ^ |   +6 F*ck you problem stoler.Let's downvote him to make his contribution lower than zxyoi cuz it's the second time such situation happens
 » 4 weeks ago, # | ← Rev. 2 →   0 IIT KGP !orz
•  » » 4 weeks ago, # ^ |   0 What is IIT KGP?
•  » » » 4 weeks ago, # ^ |   +10 Indian Institute of Technology, Kharagpur. It's India's one of the best engineering institute.
•  » » » » 4 weeks ago, # ^ |   -16 students of India's one of the best engineering institute. steal problems from online judges. Shame !!!
 » 4 weeks ago, # |   +6 As a pupil contestanti hope not to lose points in this contest
•  » » 4 weeks ago, # ^ |   0 Lol bro, u r on the edge of pupil-newbie
•  » » » 4 weeks ago, # ^ |   +1 and what's so wrong with it?
•  » » » 4 weeks ago, # ^ |   -8 i lost 70 points this round. now it's unrated i got my points back (Thanks god)
•  » » » » 4 weeks ago, # ^ |   0 why is it unrated?
•  » » » » » 4 weeks ago, # ^ |   0 one of problems was copied from another judge.
 » 4 weeks ago, # |   +1 I hope I can do at least the first one
•  » » 4 weeks ago, # ^ |   0 I guess we didn't bro xD
 » 4 weeks ago, # |   0 is this contest real? last one vanished from the website with no notice...
 » 4 weeks ago, # |   +91
•  » » 4 weeks ago, # ^ |   +38 When the guy who steals your meme gets more upvotes than you.
•  » » » 4 weeks ago, # ^ |   +3 first time ?
 » 4 weeks ago, # |   +50 Really happy to see IIT KGP finally setting contests in Codeforces. Kudos to the entire team of problemsetters.
 » 4 weeks ago, # | ← Rev. 2 →   +10 I love div.1 + div.2 contests Good luck for everyone!! Hoping for a nice problems❤️
•  » » 4 weeks ago, # ^ |   0 Good luck
 » 4 weeks ago, # | ← Rev. 2 →   0 Is it rated for DIV 2 ?
•  » » 4 weeks ago, # ^ |   +14 Yes, it is rated for all divisions.
•  » » » 4 weeks ago, # ^ |   +5 not any more xD
 » 4 weeks ago, # |   0 Hoping to solve 4 problems, would be great
•  » » 4 weeks ago, # ^ |   -259 Wishing you luck, to solve even more
•  » » » 4 weeks ago, # ^ |   +9 Hope you can solve more problems too
•  » » » 4 weeks ago, # ^ |   0 I hate you. I absolutely do.
 » 4 weeks ago, # |   +1 Hope to become as soon as possible Candidate Master.
•  » » 4 weeks ago, # ^ |   -266 All the best
 » 4 weeks ago, # |   0 Great Way To Rate Up
 » 4 weeks ago, # |   -15 But how will this affect Lebron's legacy?
 » 4 weeks ago, # |   +6 As a xxx Give me xxx Here is: hided content The above comment is edited as follows: 
As a xxx
Here is: hided content 
•  » » 4 weeks ago, # ^ |   +32 However, A new comment will be shown in blue background
•  » » 4 weeks ago, # ^ |   0 hidden content*
•  » » 4 weeks ago, # ^ |   0 You can also do stuff like this
 » 4 weeks ago, # |   0 good luck everyone and hope the problems this time is not mathforces qwq
•  » » 4 weeks ago, # ^ |   0 some moderate amount of math is fine, last time it was kinda excessive but the problems were very interesting
•  » » » 4 weeks ago, # ^ |   0 Yeah i agree
•  » » » 4 weeks ago, # ^ |   +23 god, you're everywhere
 » 4 weeks ago, # |   -12 Contest time collides with IND VS AFG cricket match. Very unfortunate.
•  » » 4 weeks ago, # ^ |   +22 It's IND vs SL!
 » 4 weeks ago, # |   +1 All the Best EveryOne!
 » 4 weeks ago, # |   +1 Good luck to all
 » 4 weeks ago, # |   0 HA HA HA ......
 » 4 weeks ago, # |   0 I would like to thank the authors in advance for another grid problem.
 » 4 weeks ago, # |   +1 Sometimes you win, sometimes you learn
 » 4 weeks ago, # |   0 Wishing everyone high rating!!!
 » 4 weeks ago, # |   +9 We just got trolled
 » 4 weeks ago, # |   0 How to solve D?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Is it MST (here any spanning tree would do)? I was finding a set of edges for the MST and color them, and color the remaining edges with the other color. And maybe in case of cycles for the second coloring, we could swap some edges. But wasn't able to implement this (because the idea isn't clear to me either)
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +1 Color everything in blue. Now do a DFS from node 1. Since m is at most n+2, you will get at most 3 back edges. Store those back edges while traversing by dfs.Now you have obtained some tree rooted in node 1, with some back edges. Now if you have less than 3 back edges, simply color those back edges as red.If you have 3 back edges, and they form a triangle, in other words have form a-b, b-c, a-c, color a-b and b-c as red. Now look at a-c. Coloring this as red would be a waste, because a, b, c are already connected. So instead leave it as blue. Find out whether a or c has a greater depth in the DFS tree. Let’s say d = deepest(a, c). Color the edge d and parent[d] in red. This way we preserve the tree structure of the blue subgraph and decrement the number of connected components in the red subgraph.If you have 3 back edges that do not form such a triangle/cycle. Just color them in red.I highly suggest drawing a tree structure with back edges to understand it better.
 » 4 weeks ago, # |   +17 C was so good :D
 » 4 weeks ago, # |   +5 Very goood problems A, B, C!
 » 4 weeks ago, # |   0 How to solve C? Any hints
•  » » 4 weeks ago, # ^ |   0 Look at number of index i, such that s[i]='(' and s[i+1]!=')'
•  » » » 4 weeks ago, # ^ |   +9 or you can just count '))'s in $(s)$
•  » » 4 weeks ago, # ^ |   +1 I just use DSU.
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 How is its time complexity?
•  » » » » 4 weeks ago, # ^ |   0 I don't calculate but get only 31 ms.
•  » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   +22 oh. that's fast. maybe the time complexity is $O(\text{fastenough})$.
•  » » » 4 weeks ago, # ^ | ← Rev. 3 →   0 DSU here how? If you could explain your thought process it would be helpful
•  » » » » 4 weeks ago, # ^ |   0 suppose you are at a closing bracket. Then it will have a matching opening bracket as well. Link those two indexes in dsu. Lets say matching opening bracket is at i. Then if i-1 position also contains closing bracket then merge i and i-1 as well in dsu.
•  » » » » 4 weeks ago, # ^ |   0 I use DSU and at the last step count the different number or parent.If make count+1 at '(' and count-1 at ')' you will see that all i for 1 to 2*n where count =1 or count=0 are conected. I use this obserbation to solve. Sorry for my poor English.
•  » » » » 4 weeks ago, # ^ |   0 Link every opening bracket to it's corresponding closing bracket. Whenever there is a ")(" in the string link those two brackets to handle the "()()" case where 1 needs to connect to 4.
•  » » » 4 weeks ago, # ^ |   0 i also used the same approach but i was getting TLE, could you please share your approach/solution?
•  » » 4 weeks ago, # ^ |   0 the number of positions such that s[i] = s[i+1] = ')'
»
4 weeks ago, # |
+233

# F is shit.

•  » » 4 weeks ago, # ^ |   +73 Can't agree more.
 » 4 weeks ago, # |   +9 Problem C was nice.
•  » » 4 weeks ago, # ^ |   0 Wut it's easier than A, I'm mad because of B not saying it's hard but I'm so stupid and slow
•  » » » 4 weeks ago, # ^ |   +1 me here, getting 150 on A :(((((((((((((((
•  » » » 4 weeks ago, # ^ |   0 Good sir, can I know how you made that observation for C? I have never been so mad at a problem T-T
•  » » » » 4 weeks ago, # ^ |   0 I noticed that () () () for example is all connected then I assumed that all of are disconnected and everytime i see () then this one is connected to another sequence
•  » » » » » 4 weeks ago, # ^ |   0 "I assumed that all of" you mean 'other' instead of 'of', right? Also, Thanks but I don't know why I couldn't think of this. Would it be lack of practice of 1400-1500 rated problems?
•  » » » » » » 4 weeks ago, # ^ |   0 It needs some luck i may haven't noticed it but if we are trained on graphs it won't be a problem
•  » » » » » » » 4 weeks ago, # ^ |   0 I see, thanks once again :D
•  » » » » 4 weeks ago, # ^ |   0 I JUST use DSU and at the last step count the different number or parent.If make count+1 at '(' and count-1 at ')' you will see that all i for 1 to 2*n where count =1 or count=0 are conected. I use this obserbation to solve. Sorry for my poor English.
•  » » » » » 4 weeks ago, # ^ |   0 Thank you! I guess having a bit more knowledge of dsu might have helped ;(
•  » » » » » » 4 weeks ago, # ^ |   0 It doesn't need any of that just a for loop would work
•  » » » » » » » 4 weeks ago, # ^ |   0 Yea true, what I actually meant was, maybe knowing dsu well might have given me a different perspective because I couldn't make that observation.
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   +3 here's my crude drawing during contest for C, if it might help:notice how the component count increases for every two decreasing (or increasing, as others pointed out) steps in a row.
•  » » » » » 4 weeks ago, # ^ |   0 Ohh nice, I will try this idea after few days and see if I can get the approach. Honestly, what I did was to notice the how deep the opening bracket's are going and counted them. For eg. ( ( ( ) ) ), depth was 2.And for this ( ( ) ) ( ( ) ), the depth for both first and second balanced sequence is 1. So, it becomes 2 and added 1 for the remaining component. And, it even passed for all given TCs, which made me believe theres something wrong in the code and not in observation.I get riddled in my own ideas ;-;
•  » » » » 4 weeks ago, # ^ |   +1 What i thought is when the string is ((())) complete then the answer is n but the time you take out a () outside, a component decreases. So calculate no of instant parenthesis. We already have 1 instant parenthesis in the starting case. So answer will be n-(instant-1).
•  » » » » » 4 weeks ago, # ^ |   0 Ohh wow, this actually makes sense to me. Wish I would have thought a bit in this direction. Alsoo, Congrats on specialist!!
•  » » 4 weeks ago, # ^ |   0 i messed up preety badly at c
 » 4 weeks ago, # |   +40 Problem F is boring and hard to implement :(
•  » » 4 weeks ago, # ^ |   0 Any hints for D?
•  » » » 4 weeks ago, # ^ |   0 The connected components are trees.
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   +3 Could you explain how to find spanning tree such that remaining 3 edges don't form a cycle( triangle )?
•  » » » » » 4 weeks ago, # ^ |   +30 Random algorithm .
•  » » » » » » 4 weeks ago, # ^ |   0 How to solve d with random algorithm
•  » » » » » » » 4 weeks ago, # ^ |   0
•  » » » » » 4 weeks ago, # ^ |   +34 Determenistic solution: Do a DFS, for every vertex record parent and depth in DFS tree, find the 3 additional edges. If the edges do form a cycle, take any of the 3 edges (let's say (u-v), where depth[u] > depth[v]) and replace it with edge (u-parent[u]).
•  » » » » » 4 weeks ago, # ^ |   +32 Find any tree, then, if the remaining edges form a cycle, build a new tree with one edge of this cycle in it. It will guarantee that the new tree is ok.
•  » » » » 4 weeks ago, # ^ |   0 Nope, for an example, in test case 2, you have one connected component and it is cycle.
•  » » » » » 4 weeks ago, # ^ |   0 I mean the connected components formed by same color.
•  » » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Oh, okey when.
•  » » 4 weeks ago, # ^ |   0 By the way , The $O(n\times \sqrt{nlog_2n})$ solution may be easier to implement.
•  » » » 4 weeks ago, # ^ |   +1 FST now :(
 » 4 weeks ago, # |   +1 hints for D?
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   +3 I also failed it, my approach was this: use union find to color all red without loops at the end at most 3 blue edges will be left over if those three blue edges happen to form a loop, swap the last blue edge with one of the red edges -> there will be no blue loop any more my problem was I didn't know how to select the correct red edge to swap with, since for some red edges you will create a red-cycle
•  » » » 4 weeks ago, # ^ |   0 You have to check if the edge you are changing from blue -> red should not be between an ancestor and child in the red tree
•  » » 4 weeks ago, # ^ |   +4 Hint 1 Note that for trees the answer is always n + 1 no matter what coloring you will use. Hint 2 Since graph is almost a tree (at most 3 more edges) think in terms of spanning trees. Hint 3 Consider two cases: if non-spanning tree don't form a triangle and when they do. Solution When $m \leq n + 1$ or $m = n + 2$ but the edges don't form a triangle, just color the whole spanning tree in blue and the non-spanning-tree edges in red. Otherwise, color two of the triangle edges blue and one red (call it $X$). Find the shortest paths IN THE SPANNING TREE from $X$ to the remaning vertex $v$ and colour neighboring edges that are on the path from $X$ endpoints to $v$ red. Everything else is blue (3 edges red, and remaning n — 1 blue). Draw some pictures to understand this idea better ;)
•  » » » 4 weeks ago, # ^ |   0 How is this optimal?
•  » » » » 4 weeks ago, # ^ |   +3 Each edge has to decrease number of either red components or blue components, and it can only decrese one of those by exactly 1. Thus, the optimal value is $2 * n - m$. In case of there not being a triangle we have exactly this value with the above method. In case of triangle also this value, but it's a little bit harder to see.
 » 4 weeks ago, # | ← Rev. 2 →   +34 Defeated by the memory limit of problem F.I wrote a segement tree without optimizing anything in the last minutes, using the memory of $O(n\log n)$. When I noticed the memory limits I didn't have time to make a change.
•  » » 4 weeks ago, # ^ |   +10 Same here. 256MB is unnecessarily too tight! Lose the chance to gain rating.
•  » » 4 weeks ago, # ^ |   +20 My ST table didn't get MLE.However, I forgot to check whether there's a time which can reach n without passing any red lights and got WA on test 7. What a pity.
 » 4 weeks ago, # |   +3 What is the expected time complexity for D?
 » 4 weeks ago, # | ← Rev. 2 →   +3 Can we solve D by randomizing? My idea is you only need to randomize m — n + 1 edges, and check if any of the two sets create a cycle. m-n+1 is at most 3 so it should be fast enough?The proof of correctness is that, if the graph is a tree, obviously it makes no difference how the edges are allocated. If we have extra edges, then every edges will reduce the connected component by 1, so we make a tree for the blue, and the rest for red, as long as they are both trees.
•  » » 4 weeks ago, # ^ |   +12 Make MST. Pick the $m-(n-1)$ edges not in MST. Only when $m = n+2$ can these edges create a cycle. If they do, then take one edge and transfer it to other color and the edge to its parent to current color, provided that the swapped edge is not in its subtree.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 I had the same idea but I don't know how to implement it.
 » 4 weeks ago, # |   0 What is a 'connected component' in Problem D? In the first example, it says blue edges form 2 components, but I only see 1.
•  » » 4 weeks ago, # ^ |   +1 $1,2,3,5$ was one component, $4$ was the other
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Thanks, I understand the problem now, have to consider all the vertices and not just the ones connected by the specific colored edge.
 » 4 weeks ago, # |   +41 F is so annoying to implement (256MB memory limit makes it even worse!). But D and E are interesting.
• »
»
4 weeks ago, # ^ |
Rev. 2   0

#### How to solve E? I thought its about calculating sums of $\frac{P^n_{2k}}{2^k k!}$ or smth for $1\leq k \leq \lfloor \frac{n}{2} \rfloor$

•  » » » 4 weeks ago, # ^ |   0 Yeah, the way you do that subproblem is by thinking about it conceptually instead of combinatorially. You're trying to find the ways to pair some elements from n things. This can be written as a dp[n] = dp[n-1] + (n-1)*dp[n-2] (you either pair the first element with something, or u don't), which can be precomputed before you do the loop over number of 4-cycles.
•  » » » 4 weeks ago, # ^ |   0 Instead of permutations I thought about the problem with cycles (by building the graph of the permutation). To be almost perfect, cycles either have length 1 (pointing to itself) or length 2 (pointing to each other) or length 4, see picture. Rest was combinatorics. I will link my solution after the grading finished (was 7 minutes too late sadly...). I iterated over the amount of length-4 cycles.
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   +8 OHHHHHHH. I was thinking about cycles too, in this process I came up with that formula. totally missed the length-4 cycles though. E was a good problem after all!
•  » » » » » 4 weeks ago, # ^ |   0 First I calculated $P_i$ by this recursion: $P_0=1$, $P_1=1$, $P_i=P_{i-1}+(i-1)\cdot P_{i-2}$. This is the amount of partitions of $i$ elements into sets of size $1$ and $2$.Then we calculate the following: $\sum_{i=0}^{4i\le n} \binom{n-2i}{2i} (2i-1)!! \cdot 2^i P_{n-4i}$The sum goes over the amount of length-$4$ cycles. The binomial calculates how many different distributions for $2i$ neighbouring 2-tile-pairs there are. The Double Factorial is the amount of combinations to form $4$-tile-cycles by choosing $2$ each from the previously distributed $2$-tile-pairs. Each $4$-tile cycle then can have 2 different orientations, so we need to multiply by $2^i$. Then $P_{n-4i}$ is the amount of combinations to form $1$ or $2$ tile pairs from the remaining nodes.
 » 4 weeks ago, # | ← Rev. 7 →   +5 why getting TLE at problem B? someone help me t = int(input()) while t>=1: n,m = map(int,input().split()) if m
•  » » 4 weeks ago, # ^ |   0 @u1602016 You are not decrementing variable t, so it continues to loop forever :)
•  » » » 4 weeks ago, # ^ |   +5 oops sorry,last line just got canceled while copy pasting the code.still getting TLE
•  » » » » 4 weeks ago, # ^ |   +5 Can you share the your original submission link?
•  » » » » » 4 weeks ago, # ^ |   +5
•  » » » » » » 4 weeks ago, # ^ |   +4 use sys module for input, here's my solution- https://codeforces.com/submissions/Varad2002
•  » » » » » » » 4 weeks ago, # ^ |   0 thanks a lot @varad2002
•  » » » » » » » » 4 weeks ago, # ^ |   +3 You’re welcome :)
•  » » 4 weeks ago, # ^ |   0 Same problem. TLE with Python/PyPy3 (pretest 4), OK with C++ (system testing). Slow input/output in Python, maybe. Is it possible to get pretest 4 for experiments? Submission https://codeforces.com/contest/1726/submission/171110352 Room (with the other submissions with slightly smodified input/output) https://codeforces.com/contest/1726/room/464
•  » » » 4 weeks ago, # ^ |   +5 The way it works is that the input function in Python calls sys.stdout.flush. So everytime you call input you flush stdout, which can be really slow. The way to get around this is to use sys.stdin.readline instead of input. Worth noting is that input internally calls sys.stdin.readline. If you take a look at C++ submissions will probably see cin.tie(0), which is how you turn off this very same feature in C++. Knowing how to avoid flushing can be very useful in general. For example your (savsmail) C++ submission speeds up by a factor of 16 by avoiding to flush 171253842 .
•  » » » » 4 weeks ago, # ^ |   0 Wow, that explains a lot. Thank you!
•  » » 4 weeks ago, # ^ |   +3 @u1602016 yes, the problem is with the slow I/O in python as it takes 5-10 times more to run compare to c/c++.For the cross-check part I have also converted your solution in c++, and tried to submit, and it works perfectly fine within time(561ms, note: your solution is correct) hereSolution??? you could either use the fast I/O for python while doing CP (as @Varad2002 mentioned) or you could use c++ for CP (I would personally recommend this, as I have experienced the situation where my JAVA code throws TLE (even after using fast I/O) whereas same algorithm works within time limit in C++)
•  » » » 4 weeks ago, # ^ |   +1 thanks a lot for your suggestions.@Nikhil19259
 » 4 weeks ago, # |   +8 I couldn't enjoy this contest :(, might be very clever problems.
 » 4 weeks ago, # |   +9 hint for c?
•  » » 4 weeks ago, # ^ |   +1 )(
•  » » » 4 weeks ago, # ^ | ← Rev. 5 →   0 Spoilercnt(')(') ???
•  » » 4 weeks ago, # ^ |   +12 Spoiler 1Each component is enclosed in a corresponding Open-Close-bracket Spoiler 2You just need to count how many bracketpairs have non-empty content inside them. SolutionCount the occurences of (( and add one. 171090971
•  » » » 4 weeks ago, # ^ |   0 Was this easy to catch this observation as i tried to solve trivally by making DSU but not able to do it
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Phew, well, depends on your understanding of easy. As I was solving the problem, the Spoilers/Solution which I posted reconstruct my thought process. And I'd say I have noticed them pretty quickly. I didn't even consider building the graph explicitly (and using DSU or similar) yet. I guess the first thing you want to do is find observations about the structure of the problem. Only if you can't find any structure, you take out the harder techniques. And then try to find structure on the harder techniques. And always user pen and paper!
 » 4 weeks ago, # |   0 Any hints for E?
•  » » 4 weeks ago, # ^ |   0 Look at cycle decomposition of $p$.
 » 4 weeks ago, # |   +9 Really nice problems ! Keep it up authors ^_^
 » 4 weeks ago, # |   +16 D: randomly color all edges. Break if both colors do not form cycles.
•  » » 4 weeks ago, # ^ |   +20 We tried our best to break such solutions, but it seems it was not enough :(
•  » » » 4 weeks ago, # ^ |   +13 I would like to know how to break (or attempt to) these kind of solutions.
•  » » » » 4 weeks ago, # ^ |   0 My attempts were primarily focused on maximising the number of tests, with $n+2$ edges in every case, with graphs of ~1e3 (I think?) size. So mostly randomisation. I didn't have much hope of blocking everything because of the small number of extra edges compared to the number of possible spanning trees. If anyone has better ideas, I would be very interested to know...
•  » » » 4 weeks ago, # ^ |   +21 Break? Isn't that correct?
•  » » » » 4 weeks ago, # ^ |   +8 Some of our testers' solutions using the same idea didn't pass, so I assumed it is incorrect.Of course, if the number of iterations are sufficient it should pass with high probability. Admittedly, I did not do a thorough analysis of a randomised solution because the model solution does not use randomisation.
•  » » » » » 4 weeks ago, # ^ |   +17 Well, this one looks way simpler than anything with some logic inside. I'm talking about the version with a guess that we can achieve maximum possible score ($2n - m$) and we repeat until we succeed. The intuition for me was that if it's anyhow hard/not straightforward to color the edges so that there are no cycles, these additional edges (yes, it's relative which ones are additional, but I'm talking about kind of a part of the graph in which something interesting happens) have to be close to each other, so the "hard" part of the graph is small, so there are not so many possibilities and we will find good one quickly.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +1 I did this: Colored red if nodes are in different disjoint sets, blue otherwise. However, for m=n+2, there is a possibility of a cycle of 3 formed.In that case, I made this observation: Suppose the 3-cycle is ABC then there is a node in A,B,C say A, such that AB and AC are connected using red. Then just take the last edge in the AB red path and make it blue, and make AB(blue) as red. It can be seen that this removes cycles in both red and blue.
•  » » » 4 weeks ago, # ^ |   0 Why the downvotes?
 » 4 weeks ago, # | ← Rev. 2 →   -38 b
 » 4 weeks ago, # |   +6 Really enjoyed the contest, especially because all the questions were not only mathematics based. Also, waiting to submit D, solved just after the time ended. Same thing happening for the second time :')
•  » » 4 weeks ago, # ^ |   +16 D accepted in 1 go after the contest :')
 » 4 weeks ago, # |   +16 Code of Problem C <<< Solving Problem C
 » 4 weeks ago, # |   -13 wait what the heck Spoiler
 » 4 weeks ago, # |   -14 I had to gain only 2 points to reach CM, and solved D on paper, started coding it more than 1 hr before the end, but in the end got TL 9 because i use maps which work slow. But my idea was fully correct. Now end up losing 7 points, and only 9 will be left before CM. this is fucking disqusting, it will be already 5th time when i have <10 points bafore CM!
•  » » 4 weeks ago, # ^ |   +1 Oh :/
 » 4 weeks ago, # |   0 Isn't $1.205710448301$ the answer for the first sample in H? I've checked that in geogebra and it seems to be so.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +8 Are you sure it's the first sample? I mean to say, you don't mean the second sample by any chance, right?
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 I think so, here's the geogebra link: we are looking for the area bounded by $AB$, $AC$, and the circle passing through H and center O.
•  » » » » 4 weeks ago, # ^ |   +26 The area is bounded by a curve, but not an arc
•  » » » » 4 weeks ago, # ^ |   +8 If you are using a circle as an envelope for the red part, that's incorrect. The curve is not a circle.Check this: Click here
•  » » » » » 4 weeks ago, # ^ |   +8 Oh I see, thanks
 » 4 weeks ago, # | ← Rev. 2 →   +1 My solution to problem C passsed system tests, Even though I am pretty sure its so different from the intended solutionI solved with a sparse table and DSU, I am interested to know if the solution is correct and actually fast enough (I am 99% sure its fast enough but I don't know about its validity)Can Someone Verify? Submission : https://codeforces.com/contest/1726/submission/171128759
•  » » 4 weeks ago, # ^ |   -8 do note that a lot of the faster ones (usually in Div1) solved it with DSU
•  » » 4 weeks ago, # ^ |   0 I too solved it using seg tree and DSU.
 » 4 weeks ago, # |   +5 Back to back bad performance from me, hope I can bounce back soon. People who are in a phase like me, "This shall pass too" :)
•  » » 4 weeks ago, # ^ |   0 thanks bro, you are my ray of hope (:
 » 4 weeks ago, # | ← Rev. 2 →   0 Check out this ridiculously easy solution for C: 171112911 (don't pay attention to that bin_power_of_two function — I forgot to delete it)
•  » » 4 weeks ago, # ^ |   0 The interesting thing is that I haven't found any of the red guys yet who would have approached the problem the same way.
•  » » » 4 weeks ago, # ^ |   +3 yes, because for them, the simpler (in the sense of observation) DSU implementation came first in mind.
•  » » » » 4 weeks ago, # ^ |   0 Could you explain the DSU solution?
•  » » » » » 4 weeks ago, # ^ |   +3 they just constructed the DSU like how they would do a normal graph and counted the components like how they would do a normal graph. only tricky part is what to merge and that's it
•  » » » 4 weeks ago, # ^ |   -8
•  » » » » 4 weeks ago, # ^ |   0 ty
•  » » 4 weeks ago, # ^ |   0 literally ('('+input()+')').count('))') in python.
•  » » » 4 weeks ago, # ^ |   0 Absolutely
•  » » 4 weeks ago, # ^ |   +1
•  » » » 4 weeks ago, # ^ |   0  ll ans=1; forsn(i,1,2*n){ if(s[i]=='(' && s[i-1]=='(') ans++; } 
 » 4 weeks ago, # |   -10 These unfamiliar names kinda throw me off the track. Wish we could use simpler names
 » 4 weeks ago, # |   0 If the current problem C(bracket sequence) were problem A, would it have been as difficult as it is now?
 » 4 weeks ago, # |   0 what a contest wasnt able to solve a single problemaah my life is a lie
•  » » 4 weeks ago, # ^ |   0 same here xD
 » 4 weeks ago, # |   +5 My exactly same code got ac after system testcode was same compiler was same.... Just for system test load my code got tle...Please @authors do something about this...MikeMirzayanov please do something
•  » » 4 weeks ago, # ^ |   -10 code was same, compiler was same, the difference is the seed
•  » » » 4 weeks ago, # ^ |   0 what is seed?
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   -10 the seed is the value an RNG uses to start with. in your code this is chrono::steady_clock::now().time_since_epoch().count(), which varies by when the submission is run.
•  » » » » » 4 weeks ago, # ^ |   0 I haven't used rng anywhere in my code...so it was not my fault at all.
•  » » » » » » 4 weeks ago, # ^ |   -10 oh, didn't notice it. turns out that your code barely just fit into the TL. I think you would've gotten hacked if this happened during competition, though.
•  » » 4 weeks ago, # ^ |   0 can you do something ? Newtech66
•  » » 4 weeks ago, # ^ |   +15 Do you really think 1996ms solution for 2s problem is correct?
•  » » » 4 weeks ago, # ^ |   -7 How should I calculate this in contest time? Pretests got passed and even system tests too. But the judge load caused me TLE. Whats my fault here?
 » 4 weeks ago, # | ← Rev. 2 →   +116 On A, I saw a solution which initializes the answer with $|a_n-a_1|$ and, while I could've simply made a test case which breaks that solution very obviously, I instead decided to make fun of the pretests by hacking it with a test case of 50 tests with $n$ being a random number between $1$ and $6$ and $a_i$ being random numbers between $1$ and $10$. While most obviously wrong solutions like the one I hacked FSTd due to hacks specifically made against such solutions, this test case of 50 random tests also unintentionally caused FST of almost 100 solutions that don't work if a test with $n=1$ has a test right before it such that $a_2$ of the test right before the test with $n=1$ is greater than $a_1$ of the $n=1$ test.
•  » » 4 weeks ago, # ^ |   -13 LOL that is awesome. this is a legend, as you are too
 » 4 weeks ago, # | ← Rev. 2 →   0 what is the approach in D and why DSU?
 » 4 weeks ago, # |   +23 Why is the D's constraints so big? I can't understand why sum of N is 1e6. It is hard for python... (I passed pretest but got TLE on system test)
•  » » 4 weeks ago, # ^ |   +5 It was because we were attempting to block randomised solutions. I'm sorry about the situation with Python being too slow >_<
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   +5 I caught TL52 on the task D (https://codeforces.com/contest/1726/submission/171125630). After contest I sent the same solution again and it got Accepted (https://codeforces.com/contest/1726/submission/171157258). How did it happen? (>2 seconds vs 1.7 seconds)
•  » » » 4 weeks ago, # ^ |   0 I didn't know randomized wasn't intended. Is this hackable? https://codeforces.com/contest/1726/submission/171121286
 » 4 weeks ago, # |   0 Done C with DSU... how u guys come up with so easy solution...
•  » » 4 weeks ago, # ^ |   -13 observation, but observation isn't all so easy. observation comes along with experience as well
•  » » » 4 weeks ago, # ^ |   0 I am not very comfortable with these graph problem as you can see from my rating that i havent encountered many graph problems till now . Do these graph problem usually have these kind observation asking wrt C And please guide my what i should do to reach specialist as while practicing i am comfortable upto *1500 problems but during contest i keep on getting stucked on problem C which are usually in the range of *1400 to *1600
•  » » » » 4 weeks ago, # ^ |   0 I am not very comfortable with these graph problem So am I! This was a different case though. I just drew some parentheses strings with pen and paper, like '(' = rising slope, ')' = falling slope. Then I connected what I needed to connect based on the statements. After that, it was a long phase of thinking, thinking hard. Usually time for thinking > time for coding, this is very normal. Accepting this is one crucial step to Specialist, imho.
 » 4 weeks ago, # |   +10 Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!
•  » » 4 weeks ago, # ^ |   0 thanks thanks thanks so much.
 » 4 weeks ago, # | ← Rev. 2 →   0 Got Accept with FST code for D.Why is this so slow? It's just O(NlogN) and N <= 1e6Can someone explain?
•  » » 4 weeks ago, # ^ |   +5 Same happened to me and costed me losing CM. @admins should look at this.
•  » » 4 weeks ago, # ^ |   0 maybe try having a function fix(pair p) that returns a sorted pair(smaller element before larger element). idk if it fixes your solution but it did work for my friend
 » 4 weeks ago, # |   +18 Btw, I FST for D, but when I try to resubmit the exact same code, it passes (barely). Is it possible to reverse the FST?
•  » » 4 weeks ago, # ^ |   +5 Faced the same issue. Not sure if they will take it into consideration, but I hope they do.
 » 4 weeks ago, # | ← Rev. 2 →   0 Hello everyone, I'm a newbie participant. On problem A, although it runs perfectly on my computer, I got runtime error. How Can I fix this problem? I copy my code below. Thank you. (I use Microsoft Visual Studio BTW) #include using namespace std; int main() { int t; int n[1000]; int s; int qr; int zr; int result; cin >> t; while (t--) { cin >> s; for (int i = 0; i < s; i++) { cin >> n[i]; } for (int z = 0; z < s; z++) { for (int q = z; q < s; q++) { if (n[z] > n[q]) { zr = n[z]; qr = n[q]; n[z] = qr; n[q] = zr; } else { continue; } } } if (s == 1) { result = 0; } else { result = n[s - 1] - n[0]; } cout << result << endl; } return 0; } 
•  » » 4 weeks ago, # ^ |   0 you need to increase the size of array. notice n<=2000 but you have declared an array of size 1000 only
 » 4 weeks ago, # |   +4 After decades of the contest, Benq is on the top! Happy to see this (❁´◡`❁)
•  » » 4 weeks ago, # ^ |   0 He didn't get the rating, though.
 » 4 weeks ago, # |   +7 Just a shit
 » 4 weeks ago, # |   +1 Before I sleep,I saw my name turn green..What F???
•  » » 4 weeks ago, # ^ |   0 Unrated competition is not as good as virtual participation(hh)
•  » » 4 weeks ago, # ^ |   +3 Because F!!!
•  » » » 4 weeks ago, # ^ |   0 You know that a person with blue even purple name are not able to solve this problem
 » 4 weeks ago, # |   +3 lol everyone is downvoting this post and the editorial.
•  » » 4 weeks ago, # ^ |   +2 And even the comments, XD. Spoiler
 » 4 weeks ago, # |   -15 The coding club of IIT KGP is gonna face a lot of disrepute now becoz of you guys
•  » » 4 weeks ago, # ^ |   +3 Exactly , they may set 7 problems instead of 8 and time for 2 Hours would be better.
 » 4 weeks ago, # | ← Rev. 2 →   +58 A sincere request to everyone!Newtech66 and anubhavdhar have worked really hard for this round and they weren't aware of what happened in problem F. If you don't like the problems(except F), feel free to downvote the blog, but please refrain from doing so if this is the only reason! It would be very unfair and unjustice with them :(
•  » » 4 weeks ago, # ^ |   -38 This is bullshit. I support downvoting the blog post because of F, it's high time all the authors start asking their co-authors how they developed the problems, so situations like this don't repeat. Every author of the round should be held equally accountable for each problem, and the round in general.
 » 4 weeks ago, # | ← Rev. 2 →   -6 oh after a night(in China), so many people downvoted the postlol
 » 4 weeks ago, # |   -8 where is my ratings for this contest.
•  » » 4 weeks ago, # ^ |   +2 unrated because of a problem dupe
•  » » » 4 weeks ago, # ^ |   +3 ppl downvotes for literally no reason lol
 » 4 weeks ago, # |   0 Why this contest is Unrated?
•  » » 4 weeks ago, # ^ |   0 Problem F was a stolen problem.The discoveryThe announcement
•  » » » 4 weeks ago, # ^ |   0 Thanks!
 » 4 weeks ago, # |   0 my rating where is gone?!! i just reached pupil pls any information?
•  » » 4 weeks ago, # ^ |   0
•  » » » 4 weeks ago, # ^ |   -6 this is unfair who are they truly punishing if the author is cheater and has no morals why would he care if the round is rated or not he is just punishing the participants in fact there is a part of the problem on those who host contests the must make sure that the problem set is unique
•  » » » » 3 weeks ago, # ^ |   0 Even some people downvote to you.Maybe they still support the author and do not want to apologize，who set the problem F as a thief.In short, I support you.
 » 4 weeks ago, # |   +3 This is has happened 2nd or 3rd time, that contest has been declared unrated due to picking problems from other platforms. Please make sure that problems are original beforehand. There goes a lot of effort in solving them and then finding that contest has been declared unrated just breaks the heart :( .
•  » » 4 weeks ago, # ^ |   +3 cope kro
 » 4 weeks ago, # |   0 To that author(cheater): Why are you spoiling CodeForces?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   -11 It seemed that my review annoyed someone,haha
 » 4 weeks ago, # |   0 Why my rating is gone suddenly?
 » 4 weeks ago, # |   0 why did this contest get unrated?
 » 4 weeks ago, # | ← Rev. 2 →   -8 It's awful
 » 3 weeks ago, # |   0 funny how the competitive programming club has a logo very closely related to web/app development