### 1-gon's blog

By 1-gon, history, 9 months ago,

I hope you enjoyed the contest! I will add implementations later.

1382A - Common Subsequence

Tutorial

Implementation

1382B - Sequential Nim

Tutorial

Implementation

1382C1 - Prefix Flip (Easy Version)

Tutorial

1382C2 - Prefix Flip (Hard Version)

Tutorial

1382D - Unmerge

Tutorial

Implementation

1382E - Mastermind

Tutorial

Implementation

1381D - The Majestic Brown Tree Snake

Tutorial

Implementation

1381E - Origami

Tutorial

Implementation

• +497

 » 9 months ago, # | ← Rev. 5 →   -27 DeletedIn the problem B, I tried to submit when the clock is 2 seconds but it says "Contest is over"I dont complain anything here, just asking you guys if I am correct in my code (because I cant submit right now)My approach is to calculate how many consecutive ones prefix $1, 1, 1, ...$ of the array If the number is odd then $First$ player win else $Second$ player win My code for problem Bint query() { int n = readInt(); vector a(n); for (int &x : a) cin >> x; ll sum = 0; for (int x : a) sum += x; if (sum == n) { cout << (n & 1 ? "First" : "Second") << endl; return 0; } for (int i = 0; i < n; ++i) { if (a[i] != 1) { cout << (!(i & 1) ? "First" : "Second") << endl; return 0; } } cout << (!(n & 1) ? "First" : "Second") << endl; return 0; } 
•  » » 9 months ago, # ^ |   +3 You can submit once system testing is over.
•  » » » 9 months ago, # ^ | ← Rev. 2 →   -13 DeletedYes I know but I'm excited to know whether my code is correct is not :(
•  » » » » 9 months ago, # ^ | ← Rev. 2 →   0 It is. Interestingly, the approach you described is not the same as what is written in your code.
•  » » » » » 9 months ago, # ^ | ← Rev. 2 →   +8 DeletedWell it was correct but what do you mean about my approach, am I wrong something ?
•  » » » » » » 9 months ago, # ^ |   +6 Oh, I am sorry. I got confused as I didn't directly find something not equal to 1. Your approach and code both are correct.
•  » » » » 9 months ago, # ^ | ← Rev. 3 →   0 Video Editorial of C2. Prefix Flip.
•  » » » » » 9 months ago, # ^ |   +11 Wow! The explanation is done on board. I thought it to be an explanation done using rough diagrams made on computer which I feel are satisfactory but using white board is what I go for.Shall we see you make more videos.PS: I was trying to explain my C2 solution over comment but looks like your solution is exactly same as mine, so it won't be needed anymore :)
•  » » » » » 9 months ago, # ^ |   +5 Great explanation. thanks
•  » » » » » 9 months ago, # ^ |   0 easy approach, thanks
•  » » » » » 8 months ago, # ^ |   +3 nice explanation bro.... keep it up create more like this,not now but in future you sure get more and more likes ....
•  » » 9 months ago, # ^ |   0 Yes the code is good to go but correct you last statement "If the number is odd then First player win else Second player win" with "If the number is even, then First player win, or else Second player win"
•  » » » 9 months ago, # ^ | ← Rev. 2 →   0 Totally agree, in fact my code gets accepted on same idea.
•  » » » 9 months ago, # ^ |   0 How do you ensure that the players are playing optimally if you follow this scheme? If you can kindly explain....
•  » » » » 9 months ago, # ^ |   0 Consider the case : 1 1 1 2 3 4 5 The Second player will have the chance to pick the third element, i.e 2. So if the next element is not one the player will always choose (ai-1), so that it is ensured that the other player is forced to pick the one that is left at that place. If the next element would've been one, then our current player would've picked the complete (ai) so that the next player is forced to pick one. And hence if the starting element isn't one, the First player will always win.
•  » » » » » 9 months ago, # ^ |   0 " If the next element would've been one, then our current player would've picked the complete (ai) so that the next player is forced to pick one" in this statement where from the one is coming that you are saying the next player is forced to pick up. Because if the next element is 1 then our current player will pick that 1.....I am sorry for stupid queries but this game theory problems I am very poor at.
•  » » » » » » 9 months ago, # ^ |   0 For this part consider the case to be : 1 1 1 2 3 1 4 5 Now since after 3 there is a 1, hence the player currently playing 3 will pick all of 3, hence the next player in turn is forced to pick 1, and hence the player picking 3 is still in control of the game. In short, the player whose turn it is, has to pick say x and x > 1, then that player is in control of the game, and will win the game
•  » » » » 9 months ago, # ^ |   0 To win the round, a player need to have control over the piles on it. Every number except 1 return bacha the control over the game to other player. Intially player 1 has control over the game, but as soon as it gets 1 in front in it (in prefix only) then the control will be transferred to player 2 and vice versa. Therefore, if there are odd number of 1 in prefix of array, then player 2 will have the control of game at last and will win , else if there are even number of 1 in prefix, then player 1 will control over game atleast and hence will win. This is the reason of the above logic.
•  » » 9 months ago, # ^ |   0 Yep yep, I too did the same thing, counting the no. of consecutive ones in the prefix.
 » 9 months ago, # | ← Rev. 8 →   +329 Short and concise problem statements ✓ NO BACKGROUND STORIES ✓ Useful samples ✓ Quick Editorial with well documented implementations ✓ Super interesting problems ✓ Strong pretests (I hope so, please don't let me down) ✓ RATED FOR ALL ✓ No queueforces ✓ P.S: It seems pretests turned out to be a bit short (as warned in the announcement), never mind though CONCLUSION: A perfect contest after a long time, Thanks 1-gon!
•  » » 9 months ago, # ^ |   +25 Agreed! This is probably the best contest I've ever seen on CodeForces!
•  » » » 9 months ago, # ^ |   0 Indeed, He lives up to his name
•  » » 9 months ago, # ^ |   +2 yeah, background stories just make the statements more confusing.
•  » » 9 months ago, # ^ |   -28 Give 1-gon some contribution.:))
•  » » 9 months ago, # ^ | ← Rev. 5 →   -29 [Deleted]
•  » » » 9 months ago, # ^ |   -17 Yes,It Happened with me :(
•  » » » 9 months ago, # ^ | ← Rev. 2 →   -8 I agree.Got Wrong answer on test 15! Can someone please tell me what is wrong with the code? Submission Edit: found the problem it was really stupid. I guess pretests were short ;)Anyways, loved the problem Div2. D (although I was unable to solve it).
•  » » 9 months ago, # ^ |   +15 Agreed .. This was one of the best division 2 rounds.. Hats off 1-gon
•  » » 9 months ago, # ^ |   -6 Monogon let you down becos pretest were not so good for c2. A n==3 test case could have made me realise the bug in my code.
•  » » 9 months ago, # ^ |   +2 You Forgot No QueueForces!
•  » » » 9 months ago, # ^ |   0 Yeah my bad, how could I even miss it, edited thanks !:)
•  » » 9 months ago, # ^ |   0 A very nice and balanced round! Solved some and then some to learn from.
 » 9 months ago, # | ← Rev. 6 →   0 good problem set and very fast editorial thanks to the makers and the testers of the round
 » 9 months ago, # |   -8 I think the time limit of Div.2D is too tight. I got the right solution when it was only 30 second before the contest was finished, but disappointedly got a TLE. My TLE Code
•  » » 9 months ago, # ^ |   -6 Ok I got something wrong in my code. My array f is too small.
•  » » » 9 months ago, # ^ | ← Rev. 2 →   +8 You also use memset for every testcase which sets all the elements of the array, so in total your complexity is 2020 * 2020 * No of Testcases which might be too much and results in tle :)
•  » » » » 9 months ago, # ^ |   0 Yes I got it too. I have already been away from keyboard for one year and I forget a lot of basical tricks like this.
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 I don't think so. My solution (which btw uses different approach than in the editorial: the strictly decreasing subarray must be in some of the arrays) performed in 31 ms.
 » 9 months ago, # |   +2 For C2, I basically took Solution 2 for C1 and then added a custom data structure to make operations (modifying a prefix) done in O(1) time. Basically, you maintain the left and right indices of the original string and also keep booleans indicating if the string is reversed and if the string is flipped.
•  » » 9 months ago, # ^ |   +3 Can you please elaborate your solution?
•  » » » 9 months ago, # ^ |   0 Code:static class Prefix { char[] ch; int l; int r; boolean reversed; boolean flipped; public Prefix(String s) { ch = s.toCharArray(); r = s.length()-1; l = 0; reversed = flipped = false; } public void increment() { if(reversed) { l++; }else { r--; } } public void reverse() { reversed = !reversed; } public void flip() { flipped = !flipped; } public void flipFirst() { int first = l; if(reversed) { first = r; } ch[first] = flip(ch[first]); } public char getFirst() { int first = l; if(reversed) { first = r; } if(flipped) { return flip(ch[first]); } return ch[first]; } public char getLast() { int last = r; if(reversed) { last = l; } if(flipped) { return flip(ch[last]); } return ch[last]; } private char flip(char c) { return c=='1' ? '0' : '1'; } } I think it should be pretty intuitive.
•  » » » » 9 months ago, # ^ |   +3 Thanks!
 » 9 months ago, # |   +5 Can someone further explain how to optimise the 2nd solution for C1 with a segment tree?
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 Look at my code https://codeforces.com/contest/1382/submission/87644646 If you don't understand anything do let me know.Btw my solution doesn't use segment tree
 » 9 months ago, # |   0 couldn't solve but really loved the problems Div2 C1, C2 and D.
•  » » 9 months ago, # ^ |   0 indeed and you're an inspiration bro ... all the best for CM again ..
 » 9 months ago, # |   0 My rating hovers at 1800 and I took a leap in div 2 to try Problem E. It seems that my approach is the same as the answer, but my implementation is wrong :(I also could not find a case that fails my implementation during the contest.No regrets, other than failing to see the trick in solving D2C2
 » 9 months ago, # |   0 Anyone with a randomized solution for C2?
 » 9 months ago, # | ← Rev. 2 →   0 Does a BFS tree search work for Div 2 C1/C2?
•  » » 9 months ago, # ^ |   0 Yes, I created a pruned BFS search for Div 2 C1 but it quickly runs out of memory if you try to store the operation as the path taken.
•  » » » 9 months ago, # ^ |   0 Yes I also tried to apply the same approach. It does run out of memory.
 » 9 months ago, # |   +2 bye bye CM :(
•  » » 9 months ago, # ^ |   0 There is always a next time
•  » » » 9 months ago, # ^ |   +11 I guess,
 » 9 months ago, # |   +52 I never thought that writing 'first' & 'second' instead of some random names would have been so helpful.
•  » » 9 months ago, # ^ |   +248 You would still be surprised how many questions we received of the form: "Who goes first? First or second?"
•  » » » 9 months ago, # ^ |   +16 SUPERB!
•  » » » 9 months ago, # ^ |   0 XD
•  » » » 9 months ago, # ^ |   +17 As mentioned by Errichto earlier also, there should be some criteria or some kind of bar and users who are above that bar should only be allowed to ask questions, otherwise people just start spamming without even reading the questions carefully.
•  » » » » 9 months ago, # ^ |   +15 While there are inevitably lots of silly/spam questions, I don't think it's a good idea to stop certain people from asking. There are lots of beginners who have genuine confusion about the statements that higher rated users won't have based on experience with similar problems and the general contest format.Also, spam questions usually do not significantly increase the waiting time for genuine questions. My previous round was an exception to this because a bug made it hard for us to answer questions, and there was an extremely large number of spam questions from people complaining about the technical issues.
 » 9 months ago, # |   0 In D2-C2, how exactly will we keep track of the first bit? Won't it depend on a lot of other bits?
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 After doing 2 operation the indexes gets circularly shifted(Obviously ignoring the bits that we fixed).Consider these 0,1,2,3.....,9 After 1st operation of length 109,8,7,6....,0 After second operation of length 91,2,3,4....,9,0 Now since zero got fixed we move on with1,2,3,4....9
•  » » » 9 months ago, # ^ |   0 But now 0 is at the end?
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 imagine string one has like 10 characters.the first bit will keep changing as follows iteration 1 -> position 1 without flip , iteration 2 -> position 10 with flip , iteration 3 -> position 2 without flip , iteration 4 -> position 9 with flip , iteration 5 -> position 3 without flip , iteration 5 -> position 8 with flip , and so on .... submission link https://codeforces.com/contest/1382/submission/87589106
 » 9 months ago, # |   0 Instead, we can observe that after making the last k bits correct with our procedure, the prefix of s of length n−k will correspond to some segment of the original string s, except it will be possibly flipped (inverted and reversed). So, we need only keep track of the starting index of this segment, and a flag for whether it is flipped. Complexity is O(n).I was trying to implement this. Anyone help me how to implement this.
•  » » 9 months ago, # ^ |   0 See my answer above
•  » » 9 months ago, # ^ |   0 I have implemented it in my code using left and right pointers to our string — link
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 On closer observation, you will find a pattern, that is, suppose length is n. the bits in the first place will be, s(0) -> first round s(n-1) (flipped) -> second round s(1) -> third round s(n-2) (flipped) -> fourth round all the bits from the end will be flipped and from the front won't. so you just need to match the first bit in every round with the required bit and flip the first bit if needed.P.S.(i observed it all during contest but did sh*t for implementation. Now i solved it in 10, felt foolish)Submission
•  » » » 9 months ago, # ^ |   0 I have also tried something like that.. you can check my submission. let me correct it if it works
•  » » » » 9 months ago, # ^ |   0
•  » » » » » 9 months ago, # ^ |   0 sorry I made a stupid mistake.. how to omit such stupid mistakes?https://codeforces.com/contest/1382/submission/87635860I just thought i will work as the last pointer..my approach was right
•  » » » » » » 9 months ago, # ^ |   0 Everyone makes mistakes. You just need to track your code and print every variable, see where it's going wrong. that's how i debugged yours. :)
•  » » » » » » » 9 months ago, # ^ |   0 poor in debugging and implementing ... I will try to focus from next time
•  » » » » » 9 months ago, # ^ |   0 thank you
•  » » » 9 months ago, # ^ |   0 Same approach but after contest. 87681571
•  » » 9 months ago, # ^ |   0 See my solution https://codeforces.com/contest/1382/submission/87644646
 » 9 months ago, # |   0 Please , someone explain the approach to solce C2 of div 2.
 » 9 months ago, # |   0 Here is my solution for D, which works in O(n). I wasn't sure about greedy part of it, but it passed all of the tests. 87566235Can anyone prove/explain why this trick works? I knew it since school, but I forgot how it works.
•  » » 9 months ago, # ^ |   +10 Grredy approach is wrong. This solution is hacked. Bit disappointed that this test was not part of System tests. :(
•  » » » 9 months ago, # ^ |   0 Shout out to fsshakkhor
 » 9 months ago, # |   0 someone explain B pls .why your current wise move cant be ulter by other player when ai > 1.
•  » » 9 months ago, # ^ |   0 Try drawing a decision tree for every turn. If the current element is greater than 1, then the player has 2 options, either he can pick all but one stones, or all stones. One of these causes that player to win and the other choice causes him to lose. Same thing will occur for all subsequent choices. But no choice can be made if the current pile has only 1 stone, since the player will have no choice but to take it. So the first point where any of the players can make a decision, decides who the winner will be
•  » » » 9 months ago, # ^ | ← Rev. 3 →   0 Right
 » 9 months ago, # |   +111 Video explanations if you are interested after you give 1-gon contribution.
•  » » 9 months ago, # ^ |   +2 just a silly question, how to give contribution.
•  » » » 9 months ago, # ^ |   +11 Upvote.
•  » » » » 9 months ago, # ^ |   +7 Thanks Man i will Upvote.
 » 9 months ago, # |   +1 Loved this round!
 » 9 months ago, # | ← Rev. 2 →   +2 fourth approach for C2:Use deque and insert all indexes from 0 to n-1. Then start popping from end. If value is not equal then we need to pop from front. Also keep track of number of inversions done.Solution
•  » » 9 months ago, # ^ |   0 Can you explain more?
•  » » » 9 months ago, # ^ | ← Rev. 3 →   0 We start from index n — 1 to 0. Let's initialize our current direction to pop from deque as back direction and number of inversions as 0. Note that if inversions are even then a[i] remains same else we invert it. So we ignore all indexes where (a[i] ^ (inv % 2)) == b[i]. That handles the inversion part in the operations.Now to handle reverse part of operations, we use deque with choice of direction initialized above. Now if according to our current direction choice, it values don't turn out to be equal then it means we need to take element from other direction which will be equivalent of reversing the array. So change the direction.Hope it helps.PS — bitwise operations might be confusing. a[i] ^ (inv % 2) means if inv is odd then it's a[i] ^ 1 which is equivalent to inversion else it's a[i] ^ 0 which keeps the value of a[i] same.
•  » » 9 months ago, # ^ |   0 hey... I did exactly the same using deque too lol! 87577133
•  » » » 9 months ago, # ^ |   0 looks like a notorious coincidence to me
•  » » » » 9 months ago, # ^ |   0 notorious is a pretty bold term to describe it tho XD...i'd rather call it a brainsync 100 moment!
•  » » 9 months ago, # ^ |   0 i did without deque by using 2 variables start and end and count for inversions. but it wasted 10 min to got that.
 » 9 months ago, # |   0 My Linear Solution For Problem C Lets $a[head..tail]$ correspond to $b[0..tail - head)$ If $a[tail] = b.back()$ then we move $tail \rightarrow head$ If $head > tail$ then $tail = tail + 1$If $head < tail$ then $tail = tail - 1$ If $a[tail] \neq b.back()$ then we must reverse If $a[head] = b.back()$ then after reversing it will be different, so we have to flip itThen we can reverse in $O(1)$ by swapping $head \leftrightarrow tail$But becareful when we reverse it two times when the size is equal to one My codeint query() { int n; cin >> n; string a, b; cin >> a >> b; vector operation; for (int head = 0, tail = n - 1, flag = 0; !b.empty(); b.pop_back()) { if ((a[tail] ^ flag) != b.back()) { if ((a[head] ^ flag) == b.back() && head != tail) operation.push_back(1); flag = !flag; swap(head, tail); operation.push_back(b.size()); } if (head >= tail) tail++; else tail--; } cout << operation.size() << ' '; for (int x : operation) cout << x << ' '; cout << endl; return 0; } 
 » 9 months ago, # |   0 Solution 4Just do solution 2, but store prefix which is not solved yet using initial array and following variables: physical position $x$ of bit we think of as a[0], bool for whether $a[1], a[2]\ldots$, are located in $x + 1, x + 2, \ldots$ or $x - 1, x - 2, \ldots$ and extra bit for whether actual values of $a[i]$ are bits in array, or their negations
 » 9 months ago, # |   +3 hello friends, it might happen that this post of mine may get downvoted a lot, but I need to share something very important.I loved the problems very much and even passed the protests for problems A, B and C1 and it was very disappointing to know that my solutions for B and C1 failed, maybe due to weak pretests.I would appreciate it if I can get a fair knowledge regarding this and implore the codeforces community to make better pretest, it was very disheartening for me.P.S: I do accept my incompetence, I just wanted better pretest so that if I knew i could have improved upon that. Again, awesome round authors.
 » 9 months ago, # |   -6 I solved C2 (Hard Version) with Doubly ended queue. Here is my submission: 87597675
 » 9 months ago, # |   0 In problem A, I am getting Runtime error on pretest 1. here is my code:t = int(input())for i in range(t): a = int(input()) b = int(input()) li_1 = [] li_2 = [] for i in range(a): item_1 = input() li_1.append(item_1) for i in range(b): item_2 = input() li_2.append(item_2) li_3 = [] for number in li_1: if number in li_2: li_3.append(number) if not li_3: print("NO") else: print("yes\n") print(len(li_3),li_3)I used python. where is the problem??
•  » » 9 months ago, # ^ |   0 Learn python as a language first
 » 9 months ago, # |   0 dp solution for B 87559531
•  » » 9 months ago, # ^ |   0 Yeah..I also solved it using DP. You can use only 2 states.... Though, 3 states also passes.... 87571204
•  » » » 9 months ago, # ^ |   0 Glad to know I'm not the only one who did DP on B You can also use 1 state DP. 87538227
 » 9 months ago, # |   0 In problem C hard version I used an O(n) deterministic brute force method.I solved easy version with the following observation: if I have a string ....0000000 (k zeros) and I want to change it to ....1111111 (k ones) I can apply {n=current length, k, n}. Then the last k bits are OK and the first n-k bits don't change. (And don't forget to n-=k after this operation) (P.S. and if the current last bit are the same, just skip)So if k always > 2, we can do the task in 2n operations. The sad thing is that k could possibly(?) always be 1.If k is 1(suppose current length is n, this bit would be a[n-1]), if n = 1, just apply {1} to flip. If n>1, we detect one more bit(a[n-2]). If a[n-2] == b[n-2](Suppose, 01 and 11), apply {n, 1, n}. So we used 3 steps to deal with 2 bits in this case. But when a[n-2]!b[n-2] (say 01 and 10), the optimal operation is n, 1, 2, 1, n, which is 5 steps. Not good enough.So again we detect one more bit(a[n-3]), if a[n-3] == b[n-3], just do {n, 1, 2, 1, n} s, 5 steps for 3 bits, enough. If a[n-3] != b[n-3], there are two cases: (1) a[n-3] == a[n-2] (say 110 and 001}, use {n, 1, n, n-1, 2, n-1}, 6 steps for 3 bits (2) a[n-3] != a[n-2] (say 010 and 101}, use {n, 3, n}, 3 steps for 3 bitsSo the task can be done in 2n operationsSo dumb lol
 » 9 months ago, # | ← Rev. 2 →   0 my python code for problem D passed pretests but got tle in system tests. now the same code i submitted in PyPy it got accepted. But how? Why did python show TLE? My happiness of solving 5 problems for the first time was ruined in 15mins. :(((((((
•  » » 9 months ago, # ^ |   +3 PyPy is quicker than python for everything except for input and output.
 » 9 months ago, # | ← Rev. 3 →   -7 1-gon In games like the one given in problem $B$ , how to prove that there always exist a fixed answer (i.e how to prove that result of the game is fixed from beginning itself if they both play optimally).Proof in the editorial assumes this .
•  » » 9 months ago, # ^ |   0 Because it is a zero sum game. It is known that any zero sum game has an optimal strategy so the result must be fixed
•  » » 9 months ago, # ^ |   0 Every player is playing optimally , so every player will try to win the game It can proved by solving it using dp , then the player will see the best move he can do it so he will win the game , clearly if there's a move make the other player win , then he will not do it unless he can't do any other move
 » 9 months ago, # |   0 Question E (Mastermind) reminded me of the question "Bulls and Cows"
 » 9 months ago, # | ← Rev. 2 →   0 I had a different solution for C2, and used two pointers (left=0 and right=n-1), where left and right could be beginning/end of the remaining segment, and only advance in one direction (which was determined by the nubmer of flips). For example, if you start with abcdef, and you fix the last bit by flipping, now you have fedcba, and now you need to compare 'b' to 'f' (so the right pointer stayed on 'f', but the left, which was 'a', moved to 'b').
 » 9 months ago, # | ← Rev. 3 →   -12 1382B — Sequential Nim Solution video : https://www.youtube.com/watch?v=DJr1eWcXGHU1382C1 — Prefix Flip (Easy Version) Solution video : https://www.youtube.com/watch?v=uU8SUa4wrIE
 » 9 months ago, # | ← Rev. 3 →   0 where am i doing wrong for test case 1 case 4question c1 please reply https://codeforces.com/contest/1382/submission/87600400 because i get the answer wrong answer a not transformed to b (test case 4) but on ide i get the a==b when i check final state of both strings
•  » » 9 months ago, # ^ |   0 ofcourse you get a==b in your ide. but perhaps you operation get over 3*n and system test only 3*n operation. so you got wa
 » 9 months ago, # |   0 Beautiful contest especially Div 2 C hard part! I just realised it was something related to linked list.... would love to see more contests from @Monogon
 » 9 months ago, # |   0 Can someone explain solution 1 of div2-c2. I understood the first part about converting into all 1's(or all zeroes) in O(n). Now how to get the required string?
•  » » 9 months ago, # ^ |   0 you have to notice the sequence.. you can always find the ans less than 2n operation. 1. for i 0 to n 2. for each (n-i-1)th char of B string can match with either a[i/2] if i is even or a[n-1-i/2] if i is odd ... for detail you can check my code 87580566
 » 9 months ago, # |   0 I am wondering why this A solution 87591380 is giving WA, any help?
•  » » 9 months ago, # ^ |   0 why are you swap m and n in intial..this is the reason you got WA.. when m>n you swapped the m and n then some value of array will insert into array B.
•  » » » 9 months ago, # ^ |   0 Well, I believe that I have no clue why I did that, but does it really matter? I am just exchanging n and m values...
•  » » » » 9 months ago, # ^ |   0 of course it matters system takes first n values for array A and next m values for Array B. but you swapped the value.. now out of (n+m) values first m values goes to Array A and next n values goes to array B so you never operate on desire arrays so you got BIG WA.. you can remove that swap operation you will definetly get Ac verdict
•  » » » » » 9 months ago, # ^ |   0 Oh, that is right...My faultAnyway, thanks for the clarification
 » 9 months ago, # |   0 can anyone explain editorial of div2 D problem?
 » 9 months ago, # |   0 My Video solution for Problem B. Hope you Like It.
 » 9 months ago, # |   0 anyone please explain approach of C2 . i was able to make 2*n operations but not able to optimise the code from 0(N^2) to some 0(N) . i was traversing the string a in the reverse direction . and if a[i]!=b[i] then I was comparing a[i] with a[0] .If they both are same then I just apply operation [0-i] else I apply the operation on [0-0] and then [0-i] hence making atmost 2*n operations . But this is O(N*2)How could i make it in 0(N) . ANY help is appreciated .
•  » » 9 months ago, # ^ |   0 you have to notice the sequence.. you can always find the ans less than 2n operation. 1. for i 0 to n 2. for each (n-i-1)th char of B string can match with either a[i/2] if i is even or a[n-1-i/2] if i is odd ... for detail you can check my code 87580566
 » 9 months ago, # |   0 I am fairly new to this. so forgive me if I am wrong. but this code failed. and I don't understand why. I was quite proud when I had coded this one but got disappointed when the pretest failed. any help would be appreciated. ~~~~~ def game(stones): firstMove = True secondMove = False idx = 0 while idx < len(stones): if idx == len(stones) — 1 and stones[idx] == 0: if firstMove: print('Second') if secondMove: print('First') break if firstMove: if idx == len(stones) — 1: stones[idx] = 0 secondMove = True firstMove = False continue if stones[idx] == 1: stones[idx] = 0 idx += 1 secondMove = True else: stones[idx] = 1 secondMove = True firstMove = False if secondMove: if idx == len(stones) - 1: stones[idx] = 0 secondMove = False firstMove = True continue if stones[idx] == 1: stones[idx] = 0 idx += 1 firstMove = True else: stones[idx] = 1 firstMove = True secondMove = FalseT = int(input()) for i in range(T): n = int(input()) stones = list(map(int, input().split())) game(stones)~~~~~
 » 9 months ago, # |   0 In problem D, after couting the lengths of all the continous blocks as in the editorial, i checked whether it can form a sub-set sum that equals to n by brute force (run in exponential time) but i used some optimizing tricks here, that is, according to pigeon hole principle, if the total number of continous blocks is greater than or equal to n, then we can always form a subset with sum = n, so there is no needs to check subset sum in these cases, and while running brute-force, if i encounter a subset that sum up to n, then i stop the algorithm immediately .Anyway, i passed the system test though i thought i could get a tle if the test cases were strict enough.
•  » » 9 months ago, # ^ |   0
•  » » 9 months ago, # ^ |   0 how can you say if sum of contigous block size is equal to n we can divide that array .. in subset order is not fixed. but in this question the first block always fixed with respect of other blocks.
•  » » » 9 months ago, # ^ | ← Rev. 2 →   0 sorry, i had a mistake, the total number of continous blocks must be greater than n. What i meant is that: if the number of blocks is greater than n, then there always exist such a way to form a subset with sum equals to n, remind that to total sum of all blocks size is always 2n. for example, if n = 4, then we may have block sizes of one of the following: 4 1 1 1 1 3 2 1 1 1 2 2 2 1 1 clearly, we can always choose a subset in each of the above so that their sum equals 4
•  » » » » 9 months ago, # ^ |   0 wow, I studied that theorem in probability but i can never think it can applied here in such beautiful manner. thanks for that theorem.. but i want to ask one more thing. In editorial there is a way to get this ans in O(n*sqrt(n)). Can you explain how can i find subset sum problem in O(n*sqrt(n)).. thanks in advance..
•  » » » » » 9 months ago, # ^ |   0 Which theorem are you mentioning ?
•  » » » » 9 months ago, # ^ |   0 "if the number of blocks is greater than n, then there always exist such a way to form a subset with sum equals to n" Can you please prove why this is true.
•  » » » 9 months ago, # ^ |   0 and yes, the order of subset is not important, as you said, the first block is fixed with respect to others, but that doesn't matter too :v
 » 9 months ago, # | ← Rev. 2 →   +1 How to solve div-2 D in O(n root n). Thanks in advance.
•  » » 9 months ago, # ^ | ← Rev. 3 →   +12 First notice that there are O(sqrt(n)) distinct values because 1 + 2 + 3...+k >= 2*n implies k = O(sqrt(n)). Then you can take all distinct values with their count and then make a dp: dp[i][j] = 1 if it is possible to make sum 'j' using starting first 'i' elements(i <= sqrt(n), j <= n)Now the recursion is: dp[i][j] = dp[i-1][j]|(dp[i-1][j — val[i]])|(dp[i-1][j-2*val[i]])|....|(dp[i-1][j-cnt[val[i]]*val[i]]), where | is OR operator, val[i] is distinct value and cnt[val[i]] denotes it's count.Note that it is still O(n^2) if we do it in this way....however make a 2D pref array which is defined as:pref[i][j] = dp[i][j] | pref[i][j — val[i+1]], in this way dp[i][j] = pref[i-1][j]. Now it is O(n*sqrt(n))
•  » » » 9 months ago, # ^ | ← Rev. 2 →   0 why your submissions are not visible?
•  » » » » 9 months ago, # ^ | ← Rev. 3 →   0 Hmm....I made those submissions in the morning, I don't know why they are not visible....also I haven't implemented the O(n*root(n)) algo....do tell if you want its implementation...
•  » » » » » 9 months ago, # ^ |   0 Yes that would be very helpful ^_^
•  » » » 9 months ago, # ^ |   0 Can you give a proof for this "First notice that there are O(sqrt(n)) distinct values because 1 + 2 + 3...+k >= 2*n implies k = O(sqrt(n))"
 » 9 months ago, # |   0 Can someone explain what is wrong with the following approach for div1 C(Mastermind):- Let "nc" be the color which has not occurred. Let's first sort the sequence and keep track of corresponding index in original array.Let's try to first color (y-x) indexes which can be done by swapping color of first((y-x)/2) with last (y-x)/2 indexes if colors of cells to be swapped are different,if (y-x)is odd we will make one index equal to color "nc", else we cannot find a solution(I chose first and last (y-x)/2 because if possible they only can be of different color) . After that we will left with some indexes in middle, then we can color x indexes from the remaining indexes in same color and leftover indexes in color "nc". But, i am getting wrong answer in testcase 38 of test 2. Link to submission:- https://codeforces.com/contest/1381/submission/87596300
•  » » 9 months ago, # ^ |   0 Don't quite get your code, but if (y-x)is odd we will make one index equal to color "nc" would result in no solution if y == n
•  » » » 9 months ago, # ^ |   0 Thanks ,I found my mistake.
 » 9 months ago, # | ← Rev. 2 →   0 I had the following solution to Div1D. Unfortunately I did not manage to implement it correctly in time, but I am still curious if this is the correct approach. Div1D potential solutionRepeat the following until one of the end conditions is reached: If both the head and the tail of the snake are in a leaf, it is impossible. (Done.) If the head is in a leaf, remove the head (i.e. shorten the snake by one segment). Otherwise, remove the tail. Remove all leaves from the tree. If the remaining tree is a path, it is impossible. (Done.) If the snake consists of only its head node and its tail node, then it is possible. (Done.) Does this work? If not, what is a counterexample?
•  » » 9 months ago, # ^ |   0 I have now implemented this solution, in submission 87661047. It gives WA, but I cannot think of a counterexample (or my code may have a bug). I cannot get the killing test case out because the test case file gets truncated. Anyone have an idea?
•  » » » 8 months ago, # ^ |   +8 Your implementation has a simple one-line bug. It's surprising to me how often your program gets the right answer in spite of that bug. Its smallest failing test case seems to have n=12. Here is one such case: Minimal failing test case1 12 3 7 10 1 10 4 3 11 8 4 2 12 2 1 9 5 8 7 9 10 3 4 5 6  Bug summaryYou add the head back in when it is a leaf, rather than leaving it out, and likewise add the tail back in when the head is not a leaf.
•  » » » » 8 months ago, # ^ |   0 Thank you so much! It's very satisfying to get an answer to this, it's very unlikely I would have figured it out myself. Indeed I just have to change a single byte to get AC.
 » 9 months ago, # | ← Rev. 2 →   +4 For anyone looking for a fun DP approach for Problem B. Here is the code, basically dp[i] signifies if a player starting from the ith index of the array can win. In order to solve the problem for any index i, you check if the you can force a loss from (i+1) index by taking all the stones at ith index or if you can't do that check if you have more than 2 stones at index i, if so, leave 1 stone so that you can win from the (i+1)th index. If none of this works, then the person starting at the ith index cannot win. Spoiler/* package codechef; // don't place package name! */ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; import java.util.*; public class HelloWorld{ public static void main(String[] args) throws IOException { Scanner input = new Scanner(System.in); input.nextInt(); while(input.hasNext()){ int n=input.nextInt(); boolean[] dp=new boolean[n]; dp[n-1]=true; int[] l=new int[n]; for(int i=0;i=0;i--){ if(dp[i+1]==false){ dp[i]=true; continue; } if(l[i]>=2){ dp[i]=true; continue; } dp[i]=false; } System.out.println(dp[0]?"First":"Second"); } } } 
•  » » 9 months ago, # ^ |   0 i did the same, dp is the only way that i could think of and it is pretty simple
•  » » 9 months ago, # ^ |   0 Could you please elaborate this part "In order to solve the problem for any index i, you check if the you can force a loss from (i+1) index by taking all the stones at ith index or if you can't do that check if you have more than 2 stones at index i, if so, leave 1 stone so that you can win from the (i+1)th index. If none of this works, then the person starting at the ith index cannot win."
 » 9 months ago, # |   0 Nice Contest!
 » 9 months ago, # | ← Rev. 2 →   0 is this the only solution for 1382B ? like is there any technique or algorithm for problem like this..? just curious..thank you for the round..
•  » » 9 months ago, # ^ |   +1 There is a dp approach which I have mentioned in one of the comments.
•  » » » 9 months ago, # ^ |   0 thanks man..
 » 9 months ago, # |   +1 Is the score of c2 too low? I found that problem D is a relatively simple dp, but there is not enough time to solve it. It takes a lot of time to solve c2, but the score of c2 is only 1000 points
 » 9 months ago, # |   0 What is wrong in my this code (for C1)-> Codeforces is saying a is not converted into b but here is my code: https://codeforces.com/contest/1382/submission/87603260 Uncomment last two lines and run to see that a is onverted to b . Someone please explain!
•  » » 9 months ago, # ^ |   0 For test case 4 in sample cases answer must be 7 1 10 8 7 1 2 1
•  » » » 9 months ago, # ^ |   0 Yep I got it bro . I wrote wrong swap(). I used < instead of <= . Anyways thanks a lot .
 » 9 months ago, # |   0 can someone explain to me problem B of div2. especially this test case 6 1 1 2 1 2 2 why is the answer First??
•  » » 9 months ago, # ^ |   0 init : 1 1 2 1 2 21st : 0 1 2 1 2 2 2nd: 0 0 2 1 2 2 1st : 0 0 0 1 2 2 2nd: 0 0 0 0 2 21st : 0 0 0 0 1 22nd: 0 0 0 0 0 21st : 0 0 0 0 0 02nd cannot move. 1st wins.
•  » » » 9 months ago, # ^ |   0 for me a doubt in why it cant be like this, eg: for testcase: 1 2 2 1 1 second wins, init: 1 2 2 1 1 first: 0 2 2 1 1 second: 0 1 2 1 1 first: 0 0 2 1 1 second: 0 0 1 1 1 first: 0 0 0 1 1 second: 0 0 0 0 1 first 0 0 0 0 0 2nd cannot movie, so first wins, but the answer is second wins why
•  » » » » 9 months ago, # ^ |   0 "why it cant be like this" because the player "second" is much more intelligent and will pick up 2 in the 3rd pile.init: 1 2 2 1 1 first: 0 2 2 1 1 second: 0 1 2 1 1 first: 0 0 2 1 1 second: 0 0 0 1 1 first: 0 0 0 0 1 second: 0 0 0 0 0
•  » » » » » 9 months ago, # ^ |   0 yeah that is also right.. got it thanks
•  » » » 9 months ago, # ^ |   0 sir,does this match the idea told in the editorial? it says count hte maximum number of 1,i.e. 3 in the above case so the answer should come out to be,second. sorry,if I have misinterpreted,please help me out. thanks in advance.
•  » » » » 9 months ago, # ^ |   0 maximum number of 1 such that $a_1=⋯=a_k=1$ i.e. consecutive 1s in the beginning. Read the editorial carefullly.
 » 9 months ago, # |   0 Can someone please explain me the solution 1 of div2-C2(hard) given in tutorial.I am not able to think a way in which the string is made all 0 in atmost n operations in O(n) time.
•  » » 9 months ago, # ^ |   0 you have to notice the sequence.. you can always find the ans less than 2n operation. 1. for i 0 to n 2. for each (n-i-1)th char of B string can match with either a[i/2] if i is even or a[n-1-i/2] if i is odd ... for detail you can check my code 87580566
 » 9 months ago, # |   +1 Thanks For the good problems. I really enjoyed the contest. First time I am able to solve the 5th question in Div 2. It's really nice feeling.
 » 9 months ago, # |   0 In problem div2D/div1B I saw some submissions using bitset. How to solve it using bitset?
•  » » 9 months ago, # ^ |   0 It's pretty much the same, just that I think it's shorter to code. Every bit represents whether the value is reachable or not. For each value x, b = b | (b << x). In the end just check if b[n] is set or not. Code
 » 9 months ago, # |   0 I want to notify you that omaik786 is also my account . I want to grow two accounts at the same time . If handling two channels is not appropriate , notify me . I won't continue the 2nd account
•  » » 9 months ago, # ^ |   0 It is better to only participate in contests with one account, so you don't introduce bias in the rating system. In fact, a recent change to the rating system was made to discourage secondary accounts.
 » 9 months ago, # | ← Rev. 2 →   +1 In Solution 1 of C2, how is it possible to convert string 010 to 000 in 3 operations??
•  » » 9 months ago, # ^ |   0 110->000 by only operation..by taking 2 prefix.
•  » » » 9 months ago, # ^ |   0 Sorry for typo mistake I mean to say 010
•  » » » » 9 months ago, # ^ |   0 010->110->000 ...by <=3 operation..by taking 1 & 2 prefix serially .
•  » » » » » 9 months ago, # ^ |   0 Thank You!!
 » 9 months ago, # | ← Rev. 2 →   +4 I love how 1-gon has given 2-3 solutions for every problem
 » 9 months ago, # |   0 Thought about question C2 but wouldn't flipping for randomization also (takes steps) make it come close to the 3*n mark? P.S-Please explain a bit more about this randomization concept if you can,please.
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 It's 3 * (number of mismatches). If you flip some prefixes of random lengths initially, the hope is that the number of mismatches is closer to n/2 than n. Then we achieve about 3n/2 < 2n operations, plus the initial random flips. It's difficult to compute the exact probability, but it's easy to see that we can repeat trials until it works, and we can even handle small n separately if needed.
 » 9 months ago, # |   0 4 years later we will see comments crying out for implementation
 » 9 months ago, # |   +5 Almost same code gets once runtime error and once AC in Div1C. AC CODE vs RUNTIME ERROR . Can anyone check please ? This is very weird.
•  » » 9 months ago, # ^ |   0 Got it, made a stupid mistake.
 » 9 months ago, # |   0 @2wrist thank you!!
 » 9 months ago, # |   0 I got pupil lol! Thanks for an amazing contest with very interesting problems!
 » 9 months ago, # | ← Rev. 7 →   +19 I think I have a deterministic solution for С2 with ratio 5/3 operations per bit.Here is my code:https://codeforces.com/contest/1382/submission/87592131The main idea is: you scan both strings from the end to the beginning, taking suffixes of length 2 (or 3) making these suffixes alike. If suffixes of length 1 are equal, we just go on. For example (converting suffix 00 to suffix 01): - ......00 -> filp the whole string - 11..... -> filp prefix of length 1 - 01..... -> filp the whole string - ......01We filp the whole string only two times in each case, in the beginning and in the end, so dots part remains unchanged.The most operations-consuming case is, for example, when you want to convert suffix 001 to 010. It takes 5 operations per 3 bits. So overall complexity in operations is 5/3 operations per bit. Here is how you deal with this case: ....001 -> flip the whole string 011... -> filp prefix of length 1 111... -> flip prefix of length 2 001... -> flip prefix of length 1 101... -> flip the whole string .....010
 » 9 months ago, # |   0 Simple approach for C1 and C2, make the first string all 0s,make it 2nd string from there. as handling all 0s or all 1s is O (n)
 » 9 months ago, # | ← Rev. 11 →   +8 "If you find a deterministic solution with a strictly lower ratio than 2 operations per bit, we would love to hear about it!"if last bit of a is equal last bit of b,we can erase it(decrease length to 1)else let's try to do last 2 bits of a equal last 2 bit's of b 1)reverse string a2)if we can do at most 1 operation to do first 2 bits of a reversed 2 last bits of b,do it and after that reverse all string a(decrease length to 2)if we failed in it our last bits of a and b is 01,10 or 10,013) in this case try to decrease length of s by 3 doing <=3 operations,and after that reverse ain addition: decrease to 1(case 1):0 operations decrease to 2(case 2):<=3 operationsdecrease to 3(case 3):<=5 operations we are doing at most (5*n/3) operationsi missed some cases in explanations you can see it in my code code:https://codeforces.com/contest/1381/submission/87606984my solution seems like:reverse string a,trying to do something with first <=3 first bits,reverse string a
•  » » 9 months ago, # ^ |   0 reverse a,doing something with <=4 bits,reverse awe can do it in <=3*n/2 operations
 » 9 months ago, # |   0 All the problems were interesting and statements were simple and straight..thanks 1-gon!!
 » 9 months ago, # |   0 how we can use the randomization in third problem div2(1382C2) to reduce time complexity as mentioned in tutorial
•  » » 9 months ago, # ^ |   0 The randomization is used to reduce the number of operations, not the time complexity. In fact, it increases the time complexity since it may require multiple trials until the number of operations is low enough.
 » 9 months ago, # |   +6 Nor that anyone is interested but still ...I have another approach for div2B , we start from the end and will use a boolean win and set it to 1. whoever selects the last pile will select the full pile and win. now moving from endwhen w = 1 (next move is of the winner) if v[i] > 1 the winner should select v[i] — 1 and leave 1 for the looser so that he would have won in the next step and if v[i] = 1 we change the move to looser and set w = 0 as looser would have maken this movewhen w = 0 (next move is of losses) we will just set w = 1 because last move would have been of a winnerif we end up at w = 1 then the first person won otherwise the second person won. bool w = 1; for (int i = n - 2; i >= 0; --i) { if (w) { if (v[i] == 1){ w = 0; }else { w = 1; } }else{ w = 1; } } if (w) first else second code : 87607154
 » 9 months ago, # | ← Rev. 2 →   0 Best Contest for me still now as I got +163, those subtask C1 and C2 were so interesting.Thank u 1-gon
 » 9 months ago, # |   0 Can someone pls explain Div2 C2 Solution 2 from editorial , I know the N^2 solution...
•  » » 9 months ago, # ^ |   0 Look, you just need a data structure that allows you to do quickly the following: reverse a prefix. toggle a prefix We can use a more general data structure like Implicit-Key Treap + Lazy Update that allows to do that over a range in $O(\log n)$ per operation. This is what I did in contest. You can learn about this Data Structure here.But there's no need for this. Oberseve that we are updating the prefixes from right to left. So, after any operation over a prefix, the smaller prefixes are a subarray (maybe reversed) of the original array, so each time you make a reverse operation is like popping elements from the front of the original array. So, all you need is a double-ended queue (deque in C++) and a boolean flag that tells you whether the prefix is inverted or not.
•  » » » 9 months ago, # ^ |   +3 Thanks man for this great explanation... I ended up doing the same thing you described using two pointers , for first and last index of a particular segment
 » 9 months ago, # | ← Rev. 5 →   0 I have 2 questions about Div. 2E/Div. 1C: How to prove that we can get at least 2f-(n-x) forced matches? Why are (n-x)/2 rotations of indices optimal ? UPD: Never mind, I got answers by myself, if anybody has same questions, ask me and I will explain :)
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 I have the same question....I think the pattern would be alternate knitting but I can't do the math.
•  » » 9 months ago, # ^ |   0 please explain
 » 9 months ago, # |   0 what's wrong with this code? Problem C1 my submission is 87608593
 » 9 months ago, # |   0 Can someone provide a sample code for Div2C2/Div1A2 that uses the solution 2 mentioned in the editorial for the problem?
•  » » 9 months ago, # ^ |   0 Implementations for all problems are posted in editorial now.
 » 9 months ago, # |   0 I was unable to find out the reason behind MLE on test case 2 of this submission of problem 1382C1 - Prefix Flip (Easy Version). I've tried for a long to find out this. Can someone please tell me what is wrong with the code? My Submission -> 87609365
•  » » 9 months ago, # ^ |   0 Got it! Made a simple mistake.
 » 9 months ago, # | ← Rev. 2 →   0 Awesome problems.. c1 and c2 was really good.
 » 9 months ago, # |   0 In My solution of C1 I followed the second approach mentioned in the tutorial. But my code is getting runtime error. I am still not able to figure out the problem. It would be really helpful if someone can debug my solution.
 » 9 months ago, # |   0 contest was awesome but the score distribution was not good div2 C2 was harder than B
•  » » 9 months ago, # ^ |   +9 But you if you solved c2 directly without trying c1. You will get points in both c1 and c2 with same code. So it gives more points than B.
 » 9 months ago, # |   0 Why does the following submission: 87526271 for Div. 2 A fail the test case: 1 1 1 1 2Even though in the CF ide it is printing "NO".
 » 9 months ago, # | ← Rev. 3 →   0 I used a similar approach for C1 Suppose a1>1. If removing the entire first pile is winning, player 1 will do that. Otherwise, player 1 can leave exactly one stone in the first pile, forcing player 2 to remove it, leaving player 1 in the winning position. Otherwise, if a1=1, then it is forced to remove the first pile.. I have iterated over all the numbers with each time making a choice as removing the entire first pile is winning, player 1 will do that. Otherwise, player 1 can leave exactly one stone in the first pile, forcing player 2 to remove it and see who is the last one to choose. Can someone please tell what is the problem with this approach? link to my submission 87556049
 » 9 months ago, # |   0 I used a different approach for C2 by considering 3 consecutive bits of A and changing them but getting WA for test case 2. Can someone tell me what is wrong with my code? It gave WA. Its a big test case so I can't read it.https://codeforces.com/contest/1382/submission/87594112I tried to change every 3 consecutive bits from end of string A by considering all the possible cases. Any 3 consecutive digits bits will have at max 6 operations. **** I didn't forget to check first two digits for input of type n = 3k + 2. Thanks in advance :)
 » 9 months ago, # | ← Rev. 5 →   0 My solution for C2: Actually an O(n) approach of C1 Solution 2.My approach for C1 was brute force.(Like Editorial C1 Sol.2).We Fix the bits one by one from the end. i.e. Firsly we have make a[n] same as b[n]. (We flip a[0] if it's same as b[n]). Then perform the operation on a[1...n]. Now you'll observe that a[n]=b[n], performing same operations for(n-1...0). At the end we have our answer in O(n2).C1 Code. Same concept goes for C2 as well.You would have noticed that.for(i=n...1) we always check for a[1] (Perform flip operation on it if necessary). Then we perform operation on (1...i) to get b[ i ] = a[ i ]. We flip and reverse this [1...i] part of string a. Now we have the newer a[0], (for the next value of i in loop) and we repeat the process.But , for a moment think of string as "abcdef" instead of 0/1's and perform these operations. You'll realize that after every operation, firstly index 1 is a[0], then after flipping and reversal a[n] becomes a[0], then a[1] becomes a[0] and so on... (Ignore their parities for a moment and think on the fact I just stated).So now we know that 1st index of the string changes in a Pattern. Now we keep a variable to keep a track of the number of flips faced (To maintain the correct parity order as we are not reversing the string[1...i] anymore ) , and we perform it in O(n). I hope my Code would make it clearer.EDIT: Absolutely loved C2's 1st solution!
•  » » 9 months ago, # ^ |   0 This approach is O(n^2) which works great for C1 as sum of all n is less than 1000. But this will give TLE for C2 as sum of all n goes around 10e5.
•  » » » 9 months ago, # ^ |   +1 By mistake I published the incomplete draft . I have edited it. I used the same concept for O(n) Approach. Please have a look.
 » 9 months ago, # | ← Rev. 2 →   +8 I solved C2 using the brute force idea for C1 (2n operations and N^2 time) which I optimized to O(N) using a doubly linked list.Solution link: codeforces submission Video Explanation: https://youtu.be/TSr0x3EBWSgP.S. I feel the idea is very simple, the implementation maybe not :p
 » 9 months ago, # |   +6 I solved B by dp lol My observation skills are low <.<
•  » » 9 months ago, # ^ |   0 at least you found the dp.. spent hour just for B.. didnt even read D
 » 9 months ago, # |   +3 I solved C2 the following way. Starting from back, if the ith position is different, we need to perform the said operation (flip and reverse). But for the ith position to be same after the operation, the first char and the current char need to be same. So if they are different, we first perform the op on just the first element and that flips the bit. Then we continue with the op at position i. This guarantees 2 * n operations. To find the current element at i, we just need to know where would the current element be going after the swaps.Let's assume we did the swap and pos1, pos2, pos3, .... (starting from back).So pos1 > pos2 > pos3 > .... After we perform a swap at pos1, all the elements behind that will move to pos1 - i + 1. When we perform a swap at pos2, all the elements will now move to pos2 - (pos1 - i + 1) + 1 = pos2 - pos1 + i. Swap at pos3 gives, pos3 - (pos2 - pos1 + i) + 1 = pos3 - pos2 + pos1 - i + 1. let's call pos1 - pos2 + pos3 .... as shift_pos.ith bit will be at shift_pos - i + 1 if i is odd. Hence the current value at ith position will be shift_pos - i + 1. i - shift_pos if i is even. The current value at ith position will be shift_pos + i. And we know how many swaps happened until now. We can keep updating the value of shift_pos traversing from back and can find the current value in O(1).
•  » » 9 months ago, # ^ |   0 I was trying to apply this but was not able to do so.Thanks for explanation.
 » 9 months ago, # |   +37 1-gon I implemented an optimal (in worst case for each n) solution to 1382C2 — Prefix Flip. It runs in linear time.https://codeforces.com/contest/1382/submission/87617645It uses at most n operations except for the case when n = 2 where it might need 3 operations. This is optimal, as ...0101 -> ...0000 takes n operations for any n (we can decrease the number of pairs of consecutive bits with different values by at most one per operation, and we need one operation to make the last bit 0). Also, 01 -> 10 takes 3 operations for n = 2.The approach greedily changes the last bits of a and b which are not equal, by performing flips on both a and b (operations on b are applied in reverse in the output). It looks at the two first bits and three last bits of a and b to find some sequence of operations of length <= k to make the k last bits equal for some 1 <= k <= 3, this is just a bunch of cases. Repeat the process until length <= 4, then run a simple brute force.
•  » » 9 months ago, # ^ |   0 Very interesting to know it can be done efficiently. Thank you!
•  » » 9 months ago, # ^ |   -10 When you say it's optimal, do you mean that your solution uses at most $n$ operations and there exists no solution that uses at most $n-1$ operations?There's another stronger notion of "optimal", which would be your solution uses the minimum number of operations possible for each given test case -- does it satisfy that too?
 » 9 months ago, # |   +3 The implementations provided are very beautiful and elegant. For C2, Another approach is to optimize the simulation for solution 2 from the easy version. You can do this with a data structure such as a balanced binary search tree in O(nlogn) time, how does one do this simulation using a BST?
•  » » 9 months ago, # ^ | ← Rev. 3 →   +3 I've actually used a Fenwick tree: for each position, I save the bit that was initially in that position. I use the difference array (so that it's possible to do point queries and range updates). For each move, it's easy to calculate the initial position of the bit that is in the first position before that move (the pattern is $1, n, 2, n - 1, \dots$). The updates are also nice (the ranges are $[1, n], [2, n], [2, n - 1], \dots$)87569413
•  » » 9 months ago, # ^ |   +11 Treaps and splay trees are examples of binary search trees that can implement this in $O(\log n)$ time per flip. You can read about reverse operations on a treap here: https://cp-algorithms.com/data_structures/treap.htmlThe idea is very similar, in that you split the treap to identify the interval you want to flip, then push flags when needed, and inverting bits when the flag reaches a leaf.
•  » » 9 months ago, # ^ |   0 This is my solution using Treap. It has some useless things cause I recycled part of the code.
 » 9 months ago, # |   +1 Anyone here who tried solving D2D/D1B using memoization. Here is my time limit exceeded solution for this: https://codeforces.com/contest/1382/submission/87615728. What I did was, get all the numbers greater than the current number and then put the numbers in between, into one array and then do the same for the next element alternating between arrays. Help appreciated.
 » 9 months ago, # |   0 At last my rating increased <3
 » 9 months ago, # |   0 The time complexity in solution2 in C1 should be O(t*n^2)? Do I need to take t into account? In this case, it seems to be overtime, because both t and n may reach to 1000. Thanks.
•  » » 9 months ago, # ^ |   -8 No u don't need to consider t.. As it is mentioned that the time limit of 1(or)2sec is per testcase
•  » » » 9 months ago, # ^ |   0 Thank you. I didn't look at it carefully.
•  » » » 9 months ago, # ^ |   0 Actually the time limit applies to all test cases in the same file. The real reason it doesn't matter is that the sum of n across all test cases is small.
 » 9 months ago, # |   0 1-gon In the editorial for problem E what do you mean by forced matches? Thanks!
•  » » 9 months ago, # ^ |   +8 I mean when we shuffle colors around, we are forced to have a certain number of them as fixed points. For example, if we reorder the colors 1,1,1,2, no matter what there will be at least two indices where the color matches. So I say there are 2 forced matches.
 » 9 months ago, # | ← Rev. 3 →   +16 using bitset in div2D/div1B : submission
•  » » 9 months ago, # ^ |   0 Most red coders also did the same. Is there any reference where i can read about how it works? Thanks
 » 9 months ago, # |   0 Wow I did get the right idea on how to solve Div 2 D — Unmerge. But for some reasons my Python 3 solution keeps getting Runtime Error. Earlier today I got another Runtime Error on a different practice problem with Python and consequently I discovered about Python's small recursion depth limit (~1000). I have been enjoying coding with Python because of its short, clean syntax but now I realize my lack of knowledge about how Python works internally makes it harder for debugging.I guess it's time to go back to C++. Or at least I will use C++ when trying to solve C and above :P.Thanks for the great contest!
 » 9 months ago, # | ← Rev. 2 →   0 sir,for the second problem(sequential nim),I have a confusion. while taking off the stones from a particular pile do I know the number of stones in the next pile? if so then,consider the test case 5 3 8 1 6 4 what should be the answer to this according to you?
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 Both persons know the number of stones on each pile in the first place, hence whoever gets the first chance to make an active decision will play in a manner such that he is guaranteed a win. Notice that by saying active decision, I mean to have piles with more than one stone.
•  » » » 9 months ago, # ^ |   0 thanks for replying sir,but still I am confused,as the test case mentioned the following steps may happen 3 8 1 6 4 1 8 1 6 4 0 8 1 6 4 now if the if the first leaves 1 stone in this pile he wont be optimal as he knows that then he will lose. so my doubt is first should pick all the 8 stones from this pile resulting 0 0 1 6 4 is that how he wins?
 » 9 months ago, # |   0 While making all bits 0 in C2 solution1, consider the string 11011, according to the solution choose i=2 (1-based indexing) s = 00011, then i=3 s= 11111 If we choose i = 5, it will become 00000. To apply operation in each step it will take O(n^2) complexity. How to resolve this?
 » 9 months ago, # |   0 can pls someone explain how second is wining in this case 1 2 2 1 1
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 First takes 1 from first position(0 2 2 1 1) then second takes 1 from 2nd position (0 1 2 1 1) then first takes 1 from 2nd position(0 0 2 1 1) then second takes the entire pile at 3rd position(0 0 0 1 1) then first takes 1 from 4th position(0 0 0 0 1) then second makes the last choice(0 0 0 0 0).
•  » » » 9 months ago, # ^ |   0 thanks for the help so we have to find which player gets the first pile which is greater than 1 whoever gets the this pile wins,right?
•  » » » » 9 months ago, # ^ |   0 yup
 » 9 months ago, # |   0 For problem 1382D — Unmerge, if we consider the fact that every element will belong to either 1st set or 2nd, can we do a DP like this way? Is there any overlapping subproblem? I tried but could not find any. Can anyone suggest whether it can be solved that way or not? I wanted to solve it other than the subset-sum DP that the editorial has suggested.
•  » » 9 months ago, # ^ |   +8 For example, you could keep an array dp[i][j][k] = x where i = length of the prefix of $p$, j = number of elements in the prefix of $p$ that belong to the array $a$, k = the array that contains $p[i]$ ($1$ if it's the array $a$, $0$ otherwise), x = the maximum possible index such that $p[x]$ and $p[x - 1]$ are in different arrays. The transitions are pretty intuitive. 87598663
•  » » » 9 months ago, # ^ |   0 Could you please explain why are you maintaining only a given maximum x, for an i , j, k ? In other words, why is it dp[i][j][k] = x and not dp[i][j][k][x] = true / false, something like that? In other words, why is the maximum x always best?
•  » » » » 9 months ago, # ^ |   +8 You can change array iff $p[i]$ is greater than all $p[j]$ such that $j \geq x$, and keeping the maximum is optimal because if the condition is true for some $x$, it's true also for $x' > x$ (the indices with $j \geq x'$ are a subset of the indices with $j \geq x$)
•  » » » » » 9 months ago, # ^ |   0 You mean if p[i] is greater than all previous p[j] then we could also have kept p[i] in the other array, so this gives p[i] more freedom, so we try to keep max(p[j]) as less as possible?Very nice idea!
•  » » » » » » 9 months ago, # ^ |   0 Yes.
•  » » » 5 weeks ago, # ^ |   0 I think I arrived at something sort of similar: 109365062
 » 9 months ago, # |   0 i m not able to understand the tutorial of sequential nim pls can someone explain it
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 I'll explain my solution to you So initially let's assume the sizes of all the piles are greater than 1 Notice that the first player can always leave one stone remaining in a pile so that the second player has no other option than to take the remaining stone in the pile (since you must choose from the leftmost non-empty pile) and continues this till it reaches the last pile Let's assume the sizes of the piles are $a_0, a_1, \ldots, a_{n-1}$ The gameplay will look like this Pile $0$ :- First chooses $a_0 - 1$ stones, second has to take remaining stone Pile $1$ :- First chooses $a_1 - 1$ stones, second has to take remaining stone Pile $2$ :- First chooses $a_2 - 1$ stones, second has to take remaining stone . . . Pile ${n-1}$ :- First takes the whole pile and wins the game So with this it should be obvious that the first player always has an advantage since he can force the moves of the second player But if the size of the beginning pile is 1 notice that the first player doesn't have a choice but to take the pile making the second player the one with the advantage So basically the parity of the ones at the beginning excluding the last pile will determine the player with the advantage Submission: Link Hope this helps!.
 » 9 months ago, # |   +10 This solution explains better than editorial. Thanks. And the best part was you haven't included unnecessary templates which makes it very convenient to understand. Kuroni SecondThread
 » 9 months ago, # |   0 Really hats off guys the approach of solution in Q C2 is really a fascinating and an elegant one , really a miraculous way!
 » 9 months ago, # |   0 is it possible to do problem D without DP?
 » 9 months ago, # |   0 "To fix the bit i (when si≠ti), we can flip the prefix of length i, then flip the prefix of length 1, and again flip the prefix of length i." how the author is getting to this solution? is he doing this by observation or is there any method in getting this solution?
 » 9 months ago, # |   0 can anyone help me out that in problem E unmerge. My approach was to count maximum length of increasing subarray in array of p of length 2n.If this length is >=n then answer is "YES" otherwise "NO". As for two different array A and B there should exist such a subarray? can anyone tell me why this approach is wrong?
•  » » 9 months ago, # ^ |   0 Look at 11, 10, 13, 12, 15, 14, 17, 16. The longest increasing subarray is of size 2, but you can easily build a and b.a = 11, 10, 15, 14b = 13, 12, 17, 16
•  » » » 9 months ago, # ^ |   0 ok thnx now in understood
 » 9 months ago, # | ← Rev. 2 →   0 Check out our Video Editorials for the problems A-Common SubsequenceB-Sequentials NimsC1-Prefix FlipLike, Share and Subscribe to our channel for more such editorials :)
 » 9 months ago, # | ← Rev. 2 →   0 I submitted two solutions, one with vector and other with array. The one with vector got TLE, and the array was accepted in 46ms. I was astonished.vector (TLE) — https://codeforces.com/contest/1382/submission/87648649
•  » » 9 months ago, # ^ |   +16 The second part of your dp[][] array isn't big enough so you end up writing outside of the array and corrupting your stack. It's purely luck that the corruption doesn't break your array solution too.For the below testcase check is [1,4] and dp[1][check[1]] is out of bounds. 1 3 4 5 3 2 1 6 
•  » » » 9 months ago, # ^ |   0 So it could have been hacked. Damnn that was nice observation
 » 9 months ago, # |   0 My solution to C2.Lets do things like in second solution to C1, and we need somehow to reverse string quickly. Let all operations with reverse that we have done so far will be array $k$. Now we are going to fix $i$ bit of string. I assume that $k_j \geq i$ We need to find out what number is on $i$s position in string. Before last operation it was on pos $k_m - i - 1$. Before last two on $k_{m - 1} - (k_m - i - 1) - 1$. If we open brackets its easy to see that we have formula for initial position of i depending only on parity of m, its easy to count it with some sums. Now about our assumption about $k_j \geq i$. Sometimes we should flip first letter of string, i wont add this operation to list, I only flip it on its position in string.It may seem overcomplicated, but I just wanted to share this.
 » 9 months ago, # |   0 If anyone need detail explanation for C1 and C2 Here
 » 9 months ago, # |   0 In problem B can we calculate the number of moves till end based on the conditions that : 1 — if(ar[i]==n-1) then moves++; 2 — else if(ar[i]!=1) then move+=2; 3 — else move++;at the end if moves is even then second wins else first wins ? but i don't know where am i going wrong ?
 » 9 months ago, # | ← Rev. 2 →   +3 In div2 Problem E mastermind can someone explain it to me that why can't we continue to greedily choose colors for the remaining n-y garbage values(the ones we are going to replace with some unused color) after greedily choosing x perfectly matching values, because we can further reduce f using these values, I realize that that would also reduce the spaces available for imperfect matches, but I a not sure why it should harm the arrangement in any way.
•  » » 9 months ago, # ^ | ← Rev. 2 →   +3 Consider the second test case of the sample. $x=3, y=4$, and $b=[1,1,2,1,2].$ Let's see what your solution does, if I understand it right.First you greedily choose $x=3$ spots to match: $[1,1,2,\_,\_]$. Then you fill in $n-y=1$ garbage value: $[1,1,2,3,\_]$. But now it's impossible to shuffle the $1$ remaining index to avoid a perfect match.The reason this fails is that the colors you fill with garbage values should still be available for the imperfect matches.
•  » » » 9 months ago, # ^ |   0 ok, Now I understand ....using garbage values to try and decrease f might not work because we might not be able to decrease f right away( as there can be many candidates for f) and will also loose a place in doing so which is not optimal....Thanks for the explanation....
 » 9 months ago, # | ← Rev. 2 →   +8 Did anyone solved div1C/div2E using Hall's marriage theorem to prove correctness?
 » 9 months ago, # |   0 In Div2D(Unmerge), to find subset-sum I used the algorithm with TC:- O(N*M) & SC:- O(N*M), I got TLE in the contest. After the contest, I got to know about an algorithm that uses Linear space to find subset-sum but the TC of that algorithm is same as O(N*M), but it got accepted. Can anyone explain why I am getting TLE in the first approach? First Approach:- https://codeforces.com/contest/1382/submission/87597226 Second Approach:- https://codeforces.com/contest/1382/submission/87612296
•  » » 9 months ago, # ^ |   +1 You need to do something better than memset on the entire dp array. Setting 4 billion ints to -1 isn't going to fit in the time limit.
•  » » » 9 months ago, # ^ |   0 Thank You! Found my mistake!
 » 9 months ago, # |   0 i cannot understand the solution 2 of prefix flip easy version.pls help
 » 9 months ago, # |   0 In Solution-2 of "C2-Hard Version" editorial it is mentioned that the simulation can be optimised by the use of balanced binary tree, can someone elaborate on that please ?
 » 9 months ago, # |   0 This was the best contest. No bullshit stories.No confusing statement. No long queue.thanks 1-gon for the contest!
 » 9 months ago, # |   +15 My Solution for C1-87677440Can Anyone Tell What will be the Time Complexity of my Solution Mentioned above.I think its O(n^2) (Considering the Complexity of reverse function too ).Can Anybody Correct me if i am wrong?
 » 9 months ago, # |   0 one of the most balanced contests in a long time 1-gon , u rock !!
 » 9 months ago, # |   0 can anybody point out any mistake in B. here is my code in c++. 87685097. thnx in adv
•  » » 9 months ago, # ^ |   0 What you are doing is counting the number of piles of '1' elements, whereas, for the correct solution, you need to count the number of consecutive '1' sequentially from the starting. But Why ? Because the person that encounters the first pile with elements greater than 1, will win the game, since they both make optimal choices. @daddy_puff
 » 9 months ago, # |   0 Need help!! My solution for div2 problem E/ div1 problem c Mastermind fails on test case 2 with the verdict "wrong answer jury has a solution but participant doesn't (test case 40)". I can't understand why is it so.....would appreciate if some one could help.
 » 9 months ago, # |   0 Can anyone explain the editorial of div 2 D more elaborately?
 » 9 months ago, # | ← Rev. 2 →   0 Can anybody please tell me that is there any way to optimise my solution using the same approach as I have done for problem div-2 D because it is showing TLE https://codeforces.com/contest/1382/submission/87693512
 » 9 months ago, # |   0 For c2(hard)，can any one explain how to implement solution2 use balanced tree in O(nlogn)?
 » 9 months ago, # |   0 Soneone can cleary explain prolem D. I still don't understand it ?
 » 9 months ago, # |   0 Can someone explain the observations made in Div2 D. I am unable to understand the editorial Sorry if i am missing something really silly
•  » » 9 months ago, # ^ |   +3 The suffix starting at the largest element must be a contiguous block in one of the two partitioned arrays. Once thats done, imagine stripping off this suffix, and putting this whole suffix in one of the arrays. Apply the same argument to the suffix of second largest array, this must also be a contiguous block in one of the two arrays. At the end, you will end up saving different lengths of suffixes. let's say you have p of these lengths. The answer is "YES" if you can combine all these p lengths into two segments, each of length n. So if any subset sum is n, the sum of the remaining lengths will also be n. These can be combined together to get two segments of length n, which can finally be combined to get the full array of length 2*n. Let's take an example:1, 5, 2, 3, 6, 4, 8, 10, 9, 7You will get the following suffixes if you consider the suffix of first largest, second largest, 3rd largest and so on[10, 9, 7] [8] [6,4] [5, 2, 3] [1]Their lengths are 3, 1, 2, 3, 1. Is there any subset with length 5? Yes. Lets combine [6, 4] and [5, 2, 3] You get [5, 2, 3, 6, 4] This is partition 1. Now lets combine[1] [8] --> [1, 8][1, 8] [10, 9, 7] = [1, 8, 10, 9, 7]Finally [1, 8, 10, 9, 7] + [5, 2, 3, 6, 4] = [1, 5, 2, 3, 6, 4, 8, 10, 9, 7]The answer is no if there does not exist a subset with sum = n. Because you can never get 2 arrays with length n each. Hope this helps!
•  » » » 9 months ago, # ^ |   0 Thanks a lot I figured out the pattern but was unsure how to proceed with it.
 » 9 months ago, # |   0 Wow. D is bootiful
 » 9 months ago, # |   0 My Approach for DIV2 C2We come from last, i.e. prefixes are n,n-1,n-2,.. and at times we may have to flip first element.say n = 6, x' indicates conjugate of that element.1 2 3 4 5 66' 5' 4' 3' 2' (1'/1) (prefix — 6)2 3 4 5 (6/6') (1'/1) (prefix — 5)5' 4' 3' (2'/2) (6/6') (1'/1) (prefix — 4)3 4 (5/5') (2'/2) (6/6') (1'/1) (prefix — 3)4' (3/3') (2'/2) (6/6') (1'/1) (prefix — 2)(4'/4) (3/3') (2'/2) (6/6') (1'/1) (prefix — 1)We can see a pattern here and at before every flip we may or may not flip the first elementMy solution : 87780335
 » 9 months ago, # |   0 For the The hard version, I actually found another deterministic solution inspired by the first solution to the easy one. I took them 3 chars by 3. this means that I have 8 states and when I tried to see the transitions between any of these, it was in range [0,4] -> now add the 2 steps to make the substrings of length three in the first 3 indices and then bring them back without changing any thing else and you get a range of [2,6]. Also, keep in mind, that you need to reverse the substrings of length 3 on the target as well as the input. if n%3 = 1 just fix the first bit, and if n%3 = 2 you need 1 step for first bit and 3 for second(using same method as the easy version) thus 2*n atmost for the reminder and 2*n atmost for the part divisible by three which is range [2,6] per 3 chars. Calculating the transitions for the states was rather easy by hand and other than that I just needed to loop in multiples of three and access the precalculated transitions so O(n)This is the interesting part of the code:  for (i = 0; i < n%3; i++) if (A[i] != B[i]) tripleOp(A, i); // if i = 1 -> 1 is pushed, if i = 2 -> 2,1,2 are pushed for (i = n % 3; i < n; i += 3) { string RevTargA = A.substr(i, 3); reverse(RevTargA.begin(), RevTargA.end()); string RevTargB = B.substr(i, 3); reverse(RevTargB.begin(), RevTargB.end()); bitset <3> X(RevTargA), Y(RevTargB); Cnt++; Ops.push_back(i+3); for (auto T : Mat[X.to_ullong()][Y.to_ullong()]) //Mat[current][target] = vector of Operations { Cnt++; Ops.push_back(T); } Cnt++; Ops.push_back(i + 3); } `
•  » » 9 months ago, # ^ |   0 https://codeforces.com/contest/1381/submission/87817029 My submission :D
 » 9 months ago, # |   0 does anyone have code for solution 3 of c2?
 » 9 months ago, # |   0 For C1/C2 I was thinking a solution on these lines...Suppose we havea = a_1, a_2, a_3 ... a_n-2, a_n-1, a_nb = b_1, b_2, b_3 ... b_n-2, b_n-1, b_nSuppose we have a operation called "OP" which does the following:-It tries to match first element of a and last element of b, if a_1 == b_n, then we can flip the first bit using prefix operation on prefix of length 1 and then apply prefix operation on prefix of length n. This make the changes to the array in the following way.a = a_n, a_n-1, a_n-2 ... a_3, a_2, a_1b = b_1, b_2, b_3 ... b_n-2, b_n-1, b_nThen we try to match b_n-1 with a_n using the same steps as above but apply prefix operation on prefix length n-1 instead of n. After this we have:a = a_2, a_3, a_4 ... a_n-1, a_n, a_1b = b_1, b_2, b_3 ... b_n-2, b_n-1, b_nSince we now know that a_n = b_n-1, and a_1 = b_n, we now have a recursive problem...a = a_2, a_3, a_4 ... a_n-3, a_n-2, a_n-1b = b_1, b_2, b_3 ... b_n-4, b_n-3, b_n-2That is we have new "a" array with first and last element removed and new "b" array with last 2 element removed.I was wondering if someone solved this problem on these lines. I am getting wrong ans for this. Can't see the flaw in the solution.PS: there are some edge cases when n<=3
 » 9 months ago, # |   0 In Div1 E it is sufficient two have a pivot p with 3 children with length more than the snake's length l.If yes than why the solutions are using two pointers.
 » 9 months ago, # |   0 Prefix Flip (Hard Version) in this problem my code convert first string into second string but my output is optimized and different but first string convert perfectly into second and my solution is not accepted. can anyone help me with this ?[submission:88217011][problem:1381A2]
 » 8 months ago, # |   0 How could one possibly come up with a solution like Solution 1 of C1 during a contest? I could never do it if I haven't solved a similar question before.