i.e's blog

By i.e, history, 3 weeks ago, translation,

1407A — Ahahahahahahahaha

Tutorial
Solution

1407B — Big Vova

Tutorial
Solution

1407C — Chocolate Bunny

Tutorial
Solution

1407D — Discrete Centrifugal Jumps

Tutorial
Solution

1407E — Egor in the Republic of Dagestan

Tutorial
Solution

• +165

 » 3 weeks ago, # | ← Rev. 3 →   +315 top 3 reason for depression breakup Substance Abuse WA in div2 A
•  » » 3 weeks ago, # ^ |   -24 hahhahaha right bro
•  » » » 3 weeks ago, # ^ |   +152 excuse me? Ahahahahahahahaha should be the reply
•  » » » » 3 weeks ago, # ^ |   -19 what rply?
•  » » » » » 3 weeks ago, # ^ |   -19 ahahahahahaahahaha happy??
•  » » » » » » 3 weeks ago, # ^ |   +10 It's a joke, based on that the title of problem A is "(A)hahahahahahahaha"
•  » » » » » » » 3 weeks ago, # ^ |   -67 Not a joke. It is called pun.
•  » » » » » » » » 3 weeks ago, # ^ |   -10 Hey bro,please help me with question A Link:https://codeforces.com/contest/1407/submission/92360608 I dont know whats wrong in my code,giving wrong answer in test case 2
•  » » » » » » » » » 3 weeks ago, # ^ | ← Rev. 3 →   0 160 1 1 1 1 1 check for this input. I guess you misunderstood the question. This is what you need to do a1−a2+a3−a4+…=0 not just to checksum at even and odd places
•  » » » » » » » 3 weeks ago, # ^ |   -22 Any idea why my "Not a joke. It is called pun" comment got so many down votes?? I am confused.
•  » » » » » » » » 2 weeks ago, # ^ |   0 Your comment seems fine to me. Let me know when you find out the reason.
•  » » » » » » » » » 2 weeks ago, # ^ |   -19 Even that comment got so many downvotes. Apparently some people downvote for no reason.
•  » » » » » » » 2 weeks ago, # ^ |   0 I am happy that you got it..
•  » » » » 3 weeks ago, # ^ |   +11 yeah, it was like question is laughing on me on WA lol Ahahahahahahahaha
•  » » » 3 weeks ago, # ^ |   0 Ahahahahaha would be better ;-)
•  » » » » 3 weeks ago, # ^ |   0 Hey bro,please help me with question A Link:https://codeforces.com/contest/1407/submission/92360608 I dont know whats wrong in my code,giving wrong answer in test case 2
•  » » » » » 3 weeks ago, # ^ |   0 Dont spam, I answered your question
•  » » 3 weeks ago, # ^ |   +9 We're together (A)hahahaha
•  » » » 3 weeks ago, # ^ |   -12 Hey bro,please help me with question A Link:https://codeforces.com/contest/1407/submission/92360608 I dont know whats wrong in my code,giving wrong answer in test case 2
•  » » » » 3 weeks ago, # ^ |   -13 Dont spam, I answered your question
•  » » » » » 3 weeks ago, # ^ |   +11 Ironic, you just did what you are saying not to do
•  » » 3 weeks ago, # ^ |   +21 I read div2 A problem Write a solution submitted WA checked the solution find no error have a emotional breakdown think should quite have time one last attempt AC still depressed A took soooooooooooooooo much time :(
•  » » 3 weeks ago, # ^ |   0 It's okay buddy, All says :) I say while all of this happen together I mean can come chunks :))))
 » 3 weeks ago, # |   +109 For problem D, I didn't use DP at all. Instead, I build the graph of valid jumps and do BFS.To build the graph, I process all values increasing by height, connecting a node to the first one it sees in the left and right directions that was processed earlier. This is just maintained with a set. Of course, I do this again but decreasing by height as well.
•  » » 3 weeks ago, # ^ |   0 I tried doing the same but I think I missed cases where heights are same.
•  » » 3 weeks ago, # ^ |   -10 I am trying to do the same thing as you, the difference being, that I am using stack to maintain the next Smaller element's index and the Next_Greater_Elements index using stack ( Yes I am also keeping track of the equal elements as well )Still, I am facing WA. It would be very nice, if you could help me figure out how will stack implementation fail.I think I coded it out properly, but in case : MY Almost Clean STACK+BFS CODE
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 Your code fails at74 6 1 7 3 6 5answer should be 3, your code is showing 5.how to correct it- after popping in while loop inside the for loop, you still have to check for last stack element without popping itDry run at above test case and you will know what is going wrong
•  » » » » 3 weeks ago, # ^ | ← Rev. 2 →   -8 I have same problem and I didn't get what you're trying to say.can you please elaborate a little bit more, if possible with some code? Thanks. :)
•  » » » » 3 weeks ago, # ^ |   -8 Sorry, if this sounds stupid, but could you please elaborate a bit more on this.I understood something with the test case you provided ( Thanks for that ).So, the problem I guess is cases like — 310 20 15My graph should have an edge between vertex number 1 and 3, but value[3] is neither the next greater, nor the next smaller element to value[1].So, my graph won't have that edge. Hence, I decided to implement what you said, but now, I guess I placed some extra edges, due to which it fails on Case 8 (And note, my answer is smaller than the expected answer, means, somewhere I might have placed more edges, however I can't find the issueI also thought, that you might have solved the problem successfully, with the same method, so I thought of giving your implementation a look, there I found you also had experimented on my code ( I would thank you again on that )So, I decided to do something on your code as well. However, that fails on case 32 nowPlease help, whenever you are free. Thanks : )
•  » » » » » 3 weeks ago, # ^ |   -7 See this is my submission using exact same approach https://codeforces.com/contest/1407/submission/92349038
•  » » » » » 3 weeks ago, # ^ | ← Rev. 3 →   0 Your code now fails at1210 15 16 14 13 12 9 8 9 8 9 17answer is 2, your code shows 3its because while building graph, you are assuming that there can be one edge for greater condition and smaller condition, but there can be multiple edgesin your code instead of using nse or nge directly add edge when requiredpath is 10->13->17 (your code don't have edge 10->13)but according to my understanding your code gives 10->15->16->17
•  » » » » » » 3 weeks ago, # ^ |   -22 Hey bro,Can you tell me what is wrong in my code.its problem B Link:https://codeforces.com/contest/1407/submission/92360694 Please help
•  » » » » » » » 3 weeks ago, # ^ |   -17 Explain your approach.. Then it would be a lot easier.
•  » » » » » » » 3 weeks ago, # ^ |   -28 Dont spam, I answered your question
•  » » » 3 weeks ago, # ^ |   -7 I think you should find next greater&smaller element to both left and right, then add edges to the graph accordingly. If you find only from one side you will miss out on some valid jumps.
•  » » » » 3 weeks ago, # ^ | ← Rev. 2 →   -8 Thanks for the reply first of all, I understood your concern. Basically, my previous code would fail at cases like : 310 20 15My graph should have an edge between vertex number 1 and 3, but value[3] is neither the next greater, nor the next smaller element to value[1].So, my graph won't have that edge. Hence, I decided to implement what you said, but Sadly, that also fails, now on case 8
•  » » » » » 3 weeks ago, # ^ | ← Rev. 2 →   +1 Yeah. I can see that you are adding edges undirected. But if you look at the problem statement it says that "Let's call a jump from i-th skyscraper to j-th (i 4 -> 3 -> 7. Here the move 4 -> 3 is not valid since i > j.The correct answer would be 4, by making the moves 0 -> 1 -> 2 -> 3 -> 7.I hope this helps. Correct me If I got something wrong.Edit: 92320227 Here is the link to my submission. I've done it using the same approach.
•  » » » » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 I don't even know, how much can I thank the Codeforces community. Sometimes, it feels, that it is only you, who is here, having all the troubles in the world, and sometimes, you get that proved so Wrong.Thanks a lot aswwwanth and manpreet.singhTo Both, the test cases, and also, for finding time in looking at the code, and finding the bugs. I love u both.Finally, I have managed to get AC. Yes, you are correct aswwwanth, that I was building the undirected edges, because of which, some path did come, which should not have been there. I removed the undirected edges, introduced the Directed edges, and it worked.Also, for manpreet.singh, your test cases came handy. I understood the mistake of my code, through your test case only ( However, I am stupid enough to not correct it on my own ).May God Bless you both !!!For other people, who might get benefitted with the discussion, although a code has already been provided, still, another CODE might help you in case you are trying the stack approach !
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   -8 I tried building the graph using Sparse Table and Binary Search, but ended up with Wrong Answer on test 5, It would be appriciated if someone could help me figure out what's wrong with my code or algorithm. Thank you in advance.My submission: I tried to make it clean and concise
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 You need to add edges for previous high and low too.eg 4 1 3 5 . . . only consider the 1st number 4. You'd add edge from 4->1 (getNextLow for 4) and 4->5 (getNextHigh for 4), but 4->3 is possible too. By repeating the same process from right to left the getPrevHigh for 3 would give us 4, so we add an edge from 4->3
•  » » » » 3 weeks ago, # ^ |   0 I finally managed to get it Accepted, thanks a lot man!
•  » » » » 3 weeks ago, # ^ |   0 Hey bro,Can you tell me what is wrong in my code.its problem B Link:https://codeforces.com/contest/1407/submission/92360694 Please help
•  » » 3 weeks ago, # ^ |   -12 Monogon closing up on Errichto u know where.
 » 3 weeks ago, # | ← Rev. 2 →   0 ahahahaha.. so clever
•  » » 3 weeks ago, # ^ |   0 I'm sorry, but what does the title signify in this case, I didn't get the title.
•  » » » 3 weeks ago, # ^ |   0 it shows 22hrs ago, contest was just few hrs ago, he edited another blog post most probably
•  » » » » 3 weeks ago, # ^ |   +4 No the editorial is made before, you can set the time when to make it public
•  » » » » » 3 weeks ago, # ^ |   0 Ohhh thanks!
 » 3 weeks ago, # |   +20 After 1 hr of unsuccessful struggle on A, i saw the title.
 » 3 weeks ago, # |   +6 I actually got "ahahahahad" in problem A after a struggle of 1 hour:/
• »
»
3 weeks ago, # ^ |
-85

A

t = int(input()) for _ in range(t): n = int(input()) l = map(int, input().split()) out = [] for _ in range(n//2): if next(l) + next(l) == 2: out.append(1) out.append(1) else: out.append(0) print(len(out)) print(' '.join(map(str,out)))

•  » » » 3 weeks ago, # ^ |   +21 I know this is a succinct code or whatever, but ew.
•  » » » » 3 weeks ago, # ^ |   +6 It's okay, the guy is playing code golf here.
•  » » » 3 weeks ago, # ^ |   0 the soltution is correct guyes,,, try it
 » 3 weeks ago, # |   +34 The constraints on task C were way too tight for no reason. I barely passed (with Java) in 997 ms after failing to 3 times.
•  » » 3 weeks ago, # ^ |   0 Sorry, it's my fault. I've tried to make $n$ smaller instead of big time limit.
•  » » » 3 weeks ago, # ^ |   0 Don't worry. I think most of the time is not used by the "meat" of the program but rather just by the inputs and outputs and since it's an interactive problem you can't use fast I/O (u really cant for output, u probably can for input but i mostly prefer the slower method which can just take the next integer so you don't have to worry where the next line falls (which can be not so clear in interactive problems)). Just next time make the time constraints less tight in a problem where having a worse complexity of the program doesn't even help you solve it more easily.
•  » » » » 3 weeks ago, # ^ |   0 whats ur fast io? i was able to fast io it
•  » » » » » 3 weeks ago, # ^ |   0 By fast io I just mean buffered reader. In the contest I just used scanner unfortunately and it didn't pass. Buffered reader passes but just barely.
•  » » » » » » 3 weeks ago, # ^ |   0 oof is bufferedreader unable to interact? that's p unfortunate. if u want a fast io template that can interact i can dm u i got it from g4g iirc
•  » » » 3 weeks ago, # ^ |   0 Same thing with my submission. I was wondering if my O(nlogn) 92255144 was computationally expensive.As a general suggestion, it will good to have coverage for all languages (especially Java and Python) in tester's solutions to understand time limits better.BTW, nice question, I enjoyed solving it.
•  » » » » 3 weeks ago, # ^ |   0 While your O(nlogn) solution should also be able to pass in my opinion, the thing is that I had an O(n) solution and it didn't pass.
•  » » 3 weeks ago, # ^ |   +8 EDIT: lol, it didn't pass the system test. After switching to fast input it passed in 982 ms.
•  » » » 3 weeks ago, # ^ |   0 rip. do u know why System.out.printf TLEs although System.out.println passes? Shouldn't printf be fast (like C++) compared to normal concatenation of integer and string?
•  » » » » 3 weeks ago, # ^ |   0 You are flushing all the time so it isn't really important.
 » 3 weeks ago, # |   0 Was getting WA's everytime on pretests for the first 1.5 or so hours. Then managed to solve A,B in 20 mins. Felt super dumb even after solving them as it did not matter much by then haha. A very good contest indeed!!
 » 3 weeks ago, # |   +34 The editorial for D is too bad. Can anyone explain me, Thanks in advance.
•  » » 3 weeks ago, # ^ |   -6 The concept is just next_greater and next_smaller. Greedy Approach
•  » » 3 weeks ago, # ^ |   +27 Here is my solution. For every element, find: - The closest element to the left of that element that is <= than the element. - The closest element to the left of that element that is >= than the element. - The closest element to the right of that element that is <= than the element. - The closest element to the right of that element that is >= than the element.Make a directed edge from the elements that you found to that element (smaller index to larger index). There are a maximum of 4 different nodes that you can find using that method, so there are max 4N edges. Do a BFS or dp to find the shortest path from 1 to N.
•  » » » 3 weeks ago, # ^ |   +14 why we need to consider the right side values?
•  » » » » 3 weeks ago, # ^ |   +24 I did the same mistake during the contest. Think about this:You are considering the jump in which both ends are smaller than what is in-between them (case A).By only drawing the back-edges (left) you are only jumping from a smaller building to a bigger one, like this: 4 7 9 6, but you might be missing out from jumping from a bigger building to a smaller one (still fitting the A-case!) 7 9 8 100 3The following case fails:n = 124 100 100 100 4 6 6 5 9 8 7 3Here, the 12th node is "missing out", having no smaller values to its left. By putting only back-edges my answer would be 4, while also adding the front-edges the answer would become 2(1 -> 5 -> 12).
•  » » » » » 3 weeks ago, # ^ |   +4 Thanks for this nice explanation.Now Understood clearly.
•  » » » 3 weeks ago, # ^ |   +6 Why Can't we make A bidirectional edge instead ? I tried it, it gives WA. Though I don't understand the logic behind it ?
•  » » » » 3 weeks ago, # ^ |   +11 "i < j", you can only jump forward
•  » » » 3 weeks ago, # ^ |   +11 But why are we considering only those paths?
•  » » » » 3 weeks ago, # ^ |   +6 We are considering all the paths I suppose.
•  » » » » » 3 weeks ago, # ^ |   0 got it thanks
•  » » » » 3 weeks ago, # ^ |   +8 These paths cover all possible paths. For each element, there is a maximum of four other nodes (1 for each type, and you can't possibly have more than 1 path type starting from the same element).
•  » » » » » 3 weeks ago, # ^ |   0 got it thanks
•  » » » 3 weeks ago, # ^ |   0 Hey I did just what you said here. Can you tell me what I'm doing wrong here?
•  » » » » 3 weeks ago, # ^ |   +3 Your method for making paths seems different. I used stack, and it looks like you are using set. I'm not super familiar with C++ so maybe your way is also correct, but I recommend checking this out.
•  » » » » » 3 weeks ago, # ^ |   0 Ok thanks I'll check it out.Btw I was using set to find out the lowerbound of elements from 0 to i of a[i]. This would basically be the element just greater than a[i] and the --lowerbound will give the element just less than a[i]
•  » » » » » » 3 weeks ago, # ^ |   0 To clarify:Say you had an array of [4,9,3,9,5]The "closest element to the left of that element that is <= than the element" of the 5 is 3, not 4. By closest I mean closest in proximity, not closest in value.
•  » » » 2 weeks ago, # ^ | ← Rev. 2 →   0 Hi, I got how the graph approach works, can you pls explain how will the dp approach work ?
•  » » » » 2 weeks ago, # ^ |   0 So by now you should have a bunch of directed edges. Let dp[i] be the minimum number of moves to the ith element. Initialize everything at infinity, except for dp[1] which equals 1.For all i from 1 to n-1, loop through all neighbors of the ith element. Let's call the neighbor nei. Set dp[nei] = min(dp[nei],dp[i]+1).Answer is dp[n].Hopefully this submission will make everything clearer. The dp portion is at the end. I used an array called path instead of dp. 92266290
•  » » 3 weeks ago, # ^ |   0 Unofficial EditorialD's explanation
 » 3 weeks ago, # |   +3 I solved problem C in a different way. I used the same observation. My program asked for each $i$ and $i + 1$ for odd $i$ and divides the indexes in two groups, the one of the smaller elements, and the one with the larger elements. We know the values for the smaller elements ($\min(x, y) = \max(x \mod y, y \mod x)$). Now we can solve recursively for the second set. It converges to $2n$. 92266927
•  » » 3 weeks ago, # ^ |   0 I used the same logic , but implemented little different
•  » » 2 weeks ago, # ^ |   0 Based on the same observation as that of editorial, but a nice approach :)
 » 3 weeks ago, # | ← Rev. 3 →   0 How to solve problem B if you change $c_i = \gcd(b_i, b_{i + 1})$
 » 3 weeks ago, # |   +4 How to die peacefully when solution of D failed just because of == in place of =
•  » » 3 weeks ago, # ^ |   +3 solve E in next round... that might help(to not to die) :)
 » 3 weeks ago, # |   0 Alexandra has an even-length array a, consisting of 0s and 1s. The elements of the array are enumerated from 1 to n. She wants to remove at most n2 elements (where n — length of array) in the way that alternating sum of the array will be equal 0 (i.e. a1−a2+a3−a4+…=0). In other words, Alexandra wants sum of all elements at the odd positions and sum of all elements at the even positions to become equal. The elements that you remove don't have to be consecutive._ what was the meaning of consecutive element not to be removed but most solution got accepted without this condition being fulfilled
•  » » 3 weeks ago, # ^ |   0 Not being consecutive and don't have to be consecutive are different things. It says it not necessarily needs to be consecutive. Consecutive elements are still allowed.
•  » » 3 weeks ago, # ^ |   0 why last test case passed
•  » » » 3 weeks ago, # ^ |   0 okay thanks got it :)
 » 3 weeks ago, # |   +3 I think my solution of A is a bit easy to understand (idk you tell me)Approach: run a while loop with $i = 0$ as initial index, if I see a $0$ I will include this in my sequence, else if I find a $1$ I will see the next element and if it is also $1$ I will include these both since they cancel out each other and increment the index by 2finally I print the sequence.
•  » » 3 weeks ago, # ^ |   0 Yeah, I solved it as this also, for each consecutive sequence of ones, if its length is odd, then remove the last one.
•  » » 3 weeks ago, # ^ |   0 But the number of zeros should be even, because 1 0 0 0 1 will not work... So whenever you will find the 2nd one, you have to check number of zeros between 1st & 2nd one... & if it is odd, then remove a zero from there... So it will be like 1 0 0 1...
•  » » » 3 weeks ago, # ^ |   0 0 0 0 can be the answer, am I wrong?
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +6 Here is my approach to problem A. Divide the array into pairs. For an array of size n, there will be $\frac{n}{2}$ pairs each having either $00$, $01$, $10$ or $11$. Pairs with $00$ or $11$ will contribute equally to the even and odd sums. Only $01$ or $10$ could be problematic, so for each such pairs remove the $1$ so that there is only $0$ remaining. There will be atmost $\frac{n}{2}$ such removals which staisfies the problem condition.Here is my submission using this approach.
•  » » » 2 weeks ago, # ^ |   0 Solved (after 1hr head scratch) using the same approach
 » 3 weeks ago, # |   0 Incomplete EdItOrIaL
 » 3 weeks ago, # | ← Rev. 3 →   +4 I was thinking to use seqment tree with Dp to solve D
•  » » 3 weeks ago, # ^ |   0 I did it (2 sparse tables for the heights + 2 segment trees to query minimum value of elements on the stacks + 2 binary searches to find the range on which I must query), but turns out this was completely useless, because after every query on a range of elements in the segment trees I would pop out exactly the same elements from the stack.92278634
 » 3 weeks ago, # |   -18 i.e Just never write editorial again, worst D explaination!
 » 3 weeks ago, # |   +25 Was problem $A$ "Ahahahahahahahaha" written by dick? Seems so to me after reading it's name.
 » 3 weeks ago, # |   -59 BINOD
 » 3 weeks ago, # |   +24 If a part of turorial is missing we can still use mango_lassi submission 92251944
•  » » 3 weeks ago, # ^ |   0 Hey how did you get that ? None of the submissions on his 1st submission page is accessible, the reference number doesn't have link attached to it.
•  » » » 3 weeks ago, # ^ |   +3 In the result list, if clicked "show unofficial", then we can see all the red ones. Then simply click those submissions.
•  » » 3 weeks ago, # ^ |   +27 mango_lassi's submissions are better than editorials
•  » » » 3 weeks ago, # ^ |   +5 Damn! He literally explains it. Thanks for sharing. xD
 » 3 weeks ago, # |   0 Can anyone please point out mistake in my code for 2C?I have been looking for an hour but can't find it :( (Got WA on Test case 8) https://codeforces.com/contest/1407/submission/92283806
 » 3 weeks ago, # |   +8 thanks finally i will be expert :)
•  » » 3 weeks ago, # ^ |   +2 Congrats!!!!
 » 3 weeks ago, # |   -6 How does one even get to that observation in C?
•  » » 3 weeks ago, # ^ |   +21 In general, think about constraints of problem, and what features they have. In this problem in particular, think about how modding by x will always give less than x, so if you can just find largest number you could mod everything else by that, and because numbers are distinct ai % max will always equal ai if ai != max. Now realize that you only need the maximum up to a point your currently at if iterating through array one by one, so you just check to see if current number is greater than maximum so far using similar mod features. Hopefully that gives some insight on at least how I thought about it.
•  » » 3 weeks ago, # ^ |   0 I made a 7x7 grid with x%y in each cell to see if there's a pattern I can use. Though 7x7 was a bit overkill lol
•  » » 2 weeks ago, # ^ |   0 Well, it is all about practice. You have such thought for prob C, I have a similar feeling for prob D/E. You may solve some problems on the ladder to get idea of actual contest problems. Here is the link — https://a2oj.pratikdaigavane.me/
 » 3 weeks ago, # |   +15 Hi, my dp solution for problem D got WA on testcase 27 with just a slight difference with Jury’s answer.Participant's output 102549 Jury's answer 102548Basically my way of approaching it is for every building i, save the first building to its left/right that has height >= h[i], <= h[i] (4 dp values for each building).Then using this information, compute another 2 arrays rg, rs. rs[i]/rg[i] means the leftmost building which has height smaller/greater than h[i] and has i as its corresponding dp value talked about above. After we got this values, just go from f[1] ~ f[n] and take the min of the previous steps that could jump to this point. Can someone see why I got WA? Thanks!
•  » » 3 weeks ago, # ^ |   +5 same problem with me :(WA at test case 27, Participant's output 102549 Jury's answer 102548
•  » » » 3 weeks ago, # ^ |   +5 Actually I figured out. When you transit during dp, you need to check all previous nodes than could come to this one, not just the leftmost one.
•  » » » » 3 weeks ago, # ^ |   0 It would be great if you tell me what's wrong in my code.
•  » » » » 3 weeks ago, # ^ |   0 Do you mean that for any index i we have to consider both forward jump and backward jump from it??
•  » » » » » 3 weeks ago, # ^ |   0 after doing this still getting wrong answer :(
•  » » » » » » 3 weeks ago, # ^ |   0 I got AC after doing this. You can check my last submission of this problem.
•  » » » » 3 weeks ago, # ^ |   0 Thanks Bro
 » 3 weeks ago, # |   +1 can anyone tell me what is the problem with this submission? I just cant understand why my answer isnt correct...
•  » » 3 weeks ago, # ^ |   0 Why are you always taking a gcd with the first element? You should take the maximum of gcd(arr[j], last).
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 EDIT: oh thanks a lotttttt
•  » » » » 3 weeks ago, # ^ |   0 Sorry, I did not quite get you. Is what you wrote a testcase for which your solution is incorrect?
•  » » » » » 3 weeks ago, # ^ |   +3 sorry I got it .. and Im really thankful :)
 » 3 weeks ago, # |   0 Can someone please help me find an example test case where my solution for Question D will fail? I can't quite figure out why it is getting WA on TC 5 92270795
•  » » 3 weeks ago, # ^ |   0 Consider the test case: 3 3 1 2The correct answer should be 1, i think
•  » » » 3 weeks ago, # ^ |   +3 I think the shortest valid sequence is 0 -> 1 -> 3. So the answer should be 2.
•  » » » » 3 weeks ago, # ^ |   +6 Sorry, formatting issues. I meant 3 elements, and the heights are: 3 1 2so we can just from 0->2 in 1 step
•  » » 3 weeks ago, # ^ |   0 Even I am getting the participant's output as 50. I am unable to figure out what is going wrong, if you figured it out then pls tell.
 » 3 weeks ago, # | ← Rev. 2 →   0 a
 » 3 weeks ago, # | ← Rev. 2 →   0 I got stuck in the 1st question !! So, I decided to start with the 3rd one. But even after solving 3rd, I could not figure out the logic of 1st question. A(hahahahahahahaha) .... Anyway a nice contest !!
•  » » 3 weeks ago, # ^ |   0 Hey bro,please help me with question A Link:https://codeforces.com/contest/1407/submission/92360608 I dont know whats wrong in my code,giving wrong answer in test case 2
•  » » » 3 weeks ago, # ^ |   0 Your code is complicated and may be you are missing some cases. Solution to this problem is simple. Suppose you have >= n/2 0s in the string, then simply you can put n/2 0s in the string and remove the rest. Now when you have > n/2 1s then you can put only n/2 1s if n/2 is even else you can only put n/2+1 1s. Then each case will be considered!! I hope you understand it now.
•  » » » » 3 weeks ago, # ^ |   0 Thanks a lot man!!
•  » » » » 3 weeks ago, # ^ |   0 But here we can't remove consecutive elements.if the case is: 1110000000 we can't remove 111 because they are consecutive. I couldn't understand this logic. plz help me.
•  » » » » » 2 weeks ago, # ^ |   0 You have to keep n/2 0s, thats enough!! So you will remove all the three 1s and then remove any two 0s which are not consecutive.
 » 3 weeks ago, # |   0 In 3rd approach of problem B , i got that number of distinct values of $c_i$ should be $O(logA)$.But i didn't got why we need to iterate only $O(nlogA)$ times ? It might be possible that first few values of $c_i$ might be equal ? Can someone explain through an example .
•  » » 3 weeks ago, # ^ |   0 could u explain if u got the whole thing??
 » 3 weeks ago, # |   0 I can see, Div-2 A laughing at my coding skills. Sed
 » 3 weeks ago, # |   0 Can anyone please point out mistake in my code for 2C?I have been looking for many hours now but can't find it :( What can be the mistake? (Got WA on Test case 8) https://codeforces.com/contest/1407/submission/92283806
•  » » 3 weeks ago, # ^ |   +5 you have 2 i, in your code. one for i j and another one for your last for. its the only thing i can see
•  » » » 3 weeks ago, # ^ |   0 Thanks for the reply,but actually that isn't the problem unfortunately. I noticed that and submitted it again https://codeforces.com/contest/1407/submission/92297960 But stil WA on Test case 8.No idea why
•  » » » » 3 weeks ago, # ^ |   +9 umm, i cant get your solution completely but i think this while(p < n — 2) it could be wrong. look at this case, 4 1 2 3 5 6 7 ..., in this case when a = 1, b = 5, then you come and refind the second — fourth places again and in each step you are adding p by one i think its better to say while(a < n)
•  » » » » » 3 weeks ago, # ^ |   +8 Yes that is the problem.Thanks!
 » 3 weeks ago, # |   +5 how to solve E?
•  » » 3 weeks ago, # ^ |   +4 change the order of the edges, and then run a bfs from node number n. then in your bfs, when you computing a node, you will see some nodes which never comes before in your queue. then if you put that node in the queue, its dis will be dis[current_node] + 1, and you want to maximum the distance of each node from node number n(its a greedy approach you can prove it by yourself) and then for not putting this node in the queue, if you can, you will set its color equal to the opposite color of the current edge.
 » 3 weeks ago, # |   0 your example Test case INPUT: 4 1 1 0 0 OUTPUT : 4 1 1 0 0BUT YOUR SOLUTION is showing 2 0 0.i didn't get that..
•  » » 3 weeks ago, # ^ |   0 me too why is that? anyone?
•  » » » 2 weeks ago, # ^ |   0 they are using ingnore.exe.......:(
 » 3 weeks ago, # |   0 I did terrible this round.
 » 3 weeks ago, # |   -18 The question actually "ahahahahahaha"ed me for the first 20 minutes, then I "ahahahahahaha"ed the question with a pretest passed verdict.
 » 3 weeks ago, # |   0 An alternative solution for A is to remove 1 from each streak of 1's of odd length.
 » 3 weeks ago, # |   +6 In problem D, one can observe that using the DP approach for calculating the first next larger element, the jumps done while calculating $dp[i]$ are exactly the valid jumps stated by the problem. This can make the code simpler.The other solution (the also computes for each index, the first previous larger/smaller), proves that the complexity of the DP approach is $O(n)$, or more precisely, the DP approach will make $2n$ jumps.
 » 3 weeks ago, # | ← Rev. 3 →   +8 Greedy Solution to 1407E - Egor in the Republic of DagestanSave all edges in the reverse direction (save edge $(u,v,t)$ at $v$ instead of $u$). Now do a BFS from $n$. Supposing we are currently dealing with $v$. For an edge $(u,v,t)$, if $u$ has been colored in $t$, then $u$ is inevitable and needs to be added to the queue. Otherwise, we set $u$'s color to be the opposite of $t$ so that $u$ would not be added, at least temporarily.In the end, we check if $1$ has been visited. If $1$ has not been visited, then we have found a way to make $1$ and $n$ not connected. Otherwise $dist[1]$ is exactly the longest shortest path we are required to find.The greedy strategy works, because it is always better, or at least not worse to make the decision at an earlier stage. Supposing there are $(3,5,0)$ and $(3,6,1)$, and we visit $5$ first during the BFS. If we set $3$'s color to $0$ (so as to ban $6$ instead of $5$), then $(3,5)$ will be a valid path, and since $5$ is visited earlier than $6$, the distance from $5$ to $n$ is no larger than that from $6$ to $n$, which is not what we want.Since we have set the colors during the BFS, we only need to output them. For those uncolored nodes, either color is OK. Code: 92282786
 » 3 weeks ago, # | ← Rev. 2 →   -14 Problem D should add following statement to clarify the task: Vasya can ONLY use discrete jumps, It means that all non-discrete jumps are not accepted. I'm a bit confusing why doesn't Vasya jump straight from 1 to n in the first sample test :-)
 » 3 weeks ago, # | ← Rev. 5 →   0 There is another solution of A. The final sequence shouldn't contain sequences of odd number of ones in a row. i.e. 1 1 0 0 1 1 1 is incorrect sequence but 1 1 0 0 1 1 is correct. So we can minimize number of removals because max number of sequences of odd number of ones in a row is n/2 and when there is no such sequences the answer will always be correct because each one on odd position has its oposite on even postion and everything turns to zero. Code: 92294664
 » 3 weeks ago, # | ← Rev. 3 →   0 In Problem C, in editorial's solution we are not flushing the stream.My Code gives AC when I flush, But EXACT SAME Code gives Idleness limit error when I don't flush the stream.If author's solution is working why mine isn't :/ Can anyone please tell the error ?(Code is printing a new line after ever output!)EDIT: Got it. I had a macros which defined endl as "\n", thereby not flushing with endl.
•  » » 3 weeks ago, # ^ |   +1 Endl, which is being called by editorial solution, besides printing a newline, flushes the stream. On the other hand "\n" does not flush the stream.
•  » » » 3 weeks ago, # ^ |   0 Yes. I forgot that I had defined my endl as "\n" itself. My mistake. Thanks !
 » 3 weeks ago, # |   +16 Chinese tutorial has been uploaded.
 » 3 weeks ago, # |   +1 For task E: Why is it necessary to reverse the edges? Why not just begin from 1st Node and try to reach the Nth node.From what I understand, it might be to reduce the number of unnecessary nodes that the queue visits. Can someone explain it more clearly? What is the intuition behind it and when is such a modification helpful?
•  » » 3 weeks ago, # ^ |   0 according to me , If we start BFS from node 1 then we can't fix the color of node 1 but if we reverse the all edges and start the BFS from node n and if is it possible to reach node 1 then we can fix the color of node 1.
•  » » » 3 weeks ago, # ^ |   0 Yup, got it later. When you move backward, you will either use a black edge or a white edge. Depending on the color of the edge, the color of the node you will reach using that edge will be fixed. We can't really fix the node color when moving forward because we have a bunch of outgoing edges of both black and white color, so deciding the node color becomes ambiguous.
 » 3 weeks ago, # |   0 The problemset was well balanced in terms of difficulty level.
 » 3 weeks ago, # | ← Rev. 3 →   0 SubmissionMy logic seems similar to editorial still got WA, Please see it guys..!!!
 » 3 weeks ago, # |   +3 May someone please explain how do we implement the third idea in the solution of problem B? Thanks in advance :D
 » 3 weeks ago, # |   0 In editorial of C, how come the first query is valid given you are querying for (0, 1) and according to constraints : 1 <= x ,y <= n
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 Check the ask function properly.
•  » » » 3 weeks ago, # ^ |   0 oops.My bad. Thanks nagaraj41
 » 3 weeks ago, # | ← Rev. 2 →   +1 In problem E editorial, why are edges reversed and then processed starting from n ?
•  » » 3 weeks ago, # ^ |   0 according to me , If we start BFS from node 1 then we can't fix the color of node 1 but if we reverse the all edges and start the BFS from node n and if is it possible to reach node 1 then we can fix the color of node 1.
 » 3 weeks ago, # |   0 @i.e . for (int i = 0; i < n; i++) { for (int to : jumps[i]) { dp[to] = min(dp[to], dp[i] + 1); } } cout << dp[n — 1];could u please explain it and time complexity of this particular loop in soln of problem D div-2. Thanx in advance.
•  » » 3 weeks ago, # ^ |   0 You can add at most 2 new jumps for each skyscraper, so there is O(n) jumps, which means that the inner cycle works in O(n)
•  » » » 3 weeks ago, # ^ |   +5 There are O(n) jumps in total, that is correct, but I believe it is possible to add more than 2 jumps for some skyscrapers.eg: 8 3 2 4 7 8From the first 8, you can jump to 3, 4, 7, or 8.
•  » » » » 3 weeks ago, # ^ |   0 Yes, and?
•  » » » » » 3 weeks ago, # ^ |   +5 Just wanted to point out that "You can add at most 2 new jumps for each skyscraper" isn't necessarily accurate. Although, maybe I misunderstood your comment.
•  » » » » » » 3 weeks ago, # ^ |   +14 I didn’t say that we jump at most 2 times from each skyscraper, I said that we jump at most 2n times in total.
 » 3 weeks ago, # |   0 Can someone please explain me the logic of question B...
•  » » 3 weeks ago, # ^ |   0 The idea is that the first element must be the biggest from a[], because that makes the biggest possible c[0].Then we can maintain the gcd from all choosen elements so far, and add n times that remaining element from a[] which results in the biggest gcd. So it is basically brute force.
 » 3 weeks ago, # | ← Rev. 2 →   0 My Logic For A: traverse the whole array and check whether there is a '1' after the current '1' if this is the case then ok other wise delete '1' we are currently on.  ll cnt=n; // denotes size of array for(ll i=0;i
 » 3 weeks ago, # |   0 Apparently A(hahahahahahaha) was not so apparent
•  » » 3 weeks ago, # ^ |   0 Hey bro,please help me with question A Link:https://codeforces.com/contest/1407/submission/92360608 I dont know whats wrong in my code,giving wrong answer in test case 2
•  » » » 3 weeks ago, # ^ |   0 1 8 1 0 1 1 1 0 1 0try for this test caseYour code is giving 5 0 1 0 1 0which is definitely wrongRemoving 1s from odd position will not solve it, as after removing one digit, the sum f and s will change, as the positions after the first removed digit, will interchange(odd becomes even and vice versa) in the final answer.
 » 3 weeks ago, # | ← Rev. 4 →   0 Doubt in DIV2 — A How can we directly remove all the 0's and 1's as it is written in the problem statement that "The elements that you remove don't have to be consecutive." So, if the input array is 0 1 0 1 1 0, then according to the editorial the output must be 0 0 0. So, we have removed two consecutive 1's (i.e. 1 at 4th and 5th position). This is against the problem statement. The correct output for the array 0 1 0 1 1 0 should be 1 1 0 (2nd 4th and 6th position) Please explain. Thanks in advance :)
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 You don't really have to remove the elements just check if where the consecutive 0,1 or 1,0 is present. You can do this using a difference array keeping in count where the (1 or -1)is and iterate through this difference array and everytime you find a one just skip it and print the rest elements.92272863 you can check my code here
•  » » 3 weeks ago, # ^ |   0 Hey bro,please help me with question A Link:https://codeforces.com/contest/1407/submission/92360608 I dont know whats wrong in my code,giving wrong answer in test case 2
 » 3 weeks ago, # |   0 The Problem E, Test #11.92324802 Emmm, what happened? why the hint say the answer is 5?
•  » » 3 weeks ago, # ^ |   0 I guess it means that your answer doesn't match the real value of the shortest path length for the schedule output by you, and if you delete all unsafe edges for your schedule, the shortest path is 5 edges length
•  » » » 3 weeks ago, # ^ |   0 I think you're right. Thanks a lot!
 » 3 weeks ago, # |   0 Can we use "\n" in c++ to flush the output instead of cout.flush()? I have solved interactive problems on other platforms and "\n" works fine. I used "\n" in problem C to flush output and got Idleness limit Exceeded.
 » 3 weeks ago, # |   0 Can C be solved this way? First of all we have all the queries of the type "? i n" where i varies from 1 to n-1. We store all the remainders and for finding the n'th element we check what is the first remainder that hash not occurred.Similarly we do the above process of the type "? i 1" where i varies fromc n to 2. In this way we find the 1st element.Now to find from 2nd element to n-1th element. We check (i*ans[n]+rem1)%a[1] == rem2 where rem1, rem2 are corresponding remainders when the ith element was divided by a[n] and a[1] respectively. i can be any multiplier of ans[n].Here is my implementation https://codeforces.com/contest/1407/submission/92321825
 » 3 weeks ago, # |   0 A nice stronger version of (A) would be to find out the array such that minimum number of removals are required.
 » 3 weeks ago, # |   0 Why my last problem B submission is wrong?On the test case 2, output of my submision has similar c as the judje answer. Did I miss something?
 » 3 weeks ago, # | ← Rev. 2 →   0 Editorial of D states that if hx <= hy than hy is first skyscrapper that not smaller than hx.Consider this case: heights: 2 6 4let hx = 2 and hy = 4here hx <= hy but hy is not first skyscrapper not smaller than hx. Instead it's the 2nd skyscrapper.
•  » » 3 weeks ago, # ^ |   0 This is for the case when all skyscrapers between $x$ and $y$ are smaller. Your example is the case when all skyscrapers between $x$ and $y$ are taller.
•  » » » 3 weeks ago, # ^ |   0 got it !! thanks
 » 3 weeks ago, # |   0 I have easier code for D = 92333067
 » 3 weeks ago, # |   -7 Question D. Discrete Centrifugal Jumps With an explanation.I hope my comments will help others to understand the solution :) // vrkorat211 - Vivek Korat const int N = 3e5 + 5; int n; int a[N]; void GO() { cin>>n; for (int i = 1; i <= n; ++i) { /* code */cin>>a[i]; } std::vector dp(n+1); stack> st1,st2; st1.push({a[1],1}); st2.push({a[1],1}); // dp[i] = minimum step to reach at index i with given two jump properties. // pair.second in stacks will store index of pushed element. // it will be used to access dp array. /**Algo.**/ // st1 will keep elements with strictly decreasing order. // st2 will keep elements with strictly increasing order. // for both sequence, if the sequence is broken then pop some elements // to get sequence property(strictly increasing or strictly decreasing) back. // when we pop element than one of the jump properties will be followed so update dp[i] // accordingly. /**\Algo.**/ // Above comments may help to understand the code :) dp[1]=0; for (int i = 2; i <= n; ++i) { //one move always possibee from index (i-1) to index (i) in 1 step; dp[i] = dp[i-1] + 1; if(a[i] > a[i-1])//st1 property violates. { //pop untill strictly deacreasing property follows with current element while(!st1.empty() && st1.top().first < a[i]) { st1.pop(); if(!st1.empty()) { //a[i] and top element follows jump property. //update dp[i] dp[i] = min(dp[i],dp[st1.top().second]+1); } } } else if(a[i] < a[i-1]) //st2 property violates. { //pop untill strictly increasing property follows with current element while(!st2.empty() && st2.top().first > a[i]) { st2.pop(); if(!st2.empty()) { //a[i] and top element follows jump property. //update dp[i] dp[i]=min(dp[i],dp[st2.top().second]+1); } } } // remove top equal elements from both stacks. // Because they violates sequence property of both stacks. while(!st1.empty() && st1.top().first == a[i])st1.pop(); while(!st2.empty() && st2.top().first == a[i])st2.pop(); // Now current element is in proper sequence for both stacks. // So push it in both stacks. st1.push({a[i],i}); st2.push({a[i],i}); } //finally d[n] is minimum step to reach at index n. cout<
 » 3 weeks ago, # |   +4 In the 5th question is making the edegs opposite necessary?? shouldnt it work on the original graph too?
 » 3 weeks ago, # | ← Rev. 2 →   0 Thanks to problem B, I've learnt that:GCD(a, b, c) == GCD(GCD(a, b), c)But I do not get why GCD of a,b,c must divide GCD of a,b.Why it is not possible that there is an x which divides a,b,c but does not divide GCD(a,b)?How to prove it?
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 Let's explicitly write two integers with all of their common primes:a = p1^i1*p2^i2*..*p_n^i_nb = p1^j1*p2^j2*..*p_n^j_n(where p is a prime and max(i, j) > 1)So we can write their GCD:GCD(a, b) = p1^min(i1, j1)*p2^min(i2, j2)*...*p_n^min(i_n, j_n)Therefore we get that GCD(a, b) divides a and divides b(same factors with a power less than or equal to original power)Now you asked why GCD(a, b, c) must divide GCD(a, b)As you stated:GCD(a, b, c) = GCD(GCD(a, b), c)Denote GCD(a, b, c) as y and GCD(a, b) as x:y = GCD(x, c)As proved above, the GCD of two numbers always divides both of them, therefore y must divide x
•  » » 3 weeks ago, # ^ |   0 By definition GCD of $GCD(a,b)$ and $c$ must dividide both $GCD(a,b)$ and $c$. Since their GCD is equal to $GCD(a, b, c)$ then $GCD(a, b, c)$ must divide $GCD(a,b)$
 » 3 weeks ago, # |   +4 Hey, I had written a code for yesterday's problem D just for testing whether my algo was correct but in my opinion it is an O(n^2) algorithm ,but when I ran it on the problem just for testing it passed all tests so I wanted to ask if the tests were weak or my code is somehow amortized to O(n).Here is link to my code:https://codeforces.com/contest/1407/submission/92338883
 » 3 weeks ago, # | ← Rev. 2 →   0 Lame doubtFor problem B, I wrote a O(n^2) solution combined with the number of test case it becomes around O(n^3), But why does it pass?
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 Sum of n over all test case was 10^3. So, test cases were already counted.
 » 3 weeks ago, # |   0 I would like to share my stupid approach for problem C, it is wrong because it may use at most 2.5*n queries to get answer (which I mistakenly thought it to be at most 2*n during the contest).Firstly, set pos=1 and iterate for i in range [2,n]. Ask the value of (p[pos]%p[i]), if it is 0 then set pos=i, else do nothing. Then, we will get such a pos that make p[pos]>n/2 hold. Now, for i in range[1,pos-1], ask the value of (p[i]%p[pos]). Then note that each remainder can appear at most twice in (p[i]%pos), query it if it appears twice.For example, if p[]={1,2,5,6,4,7,3}(1-indexed) then we will get pos=4 and the remainder is {1,2,5,-,4,1,3} and only 1 appears twice so we use one additional query (1,6) to determine their value.Apparently, it may use (n-1)+(pos-1)+(a[pos]-1) queries, which is at most 2.5*n, but I just keep thinking it is no more than 2*n queries during the contest :(
 » 3 weeks ago, # |   0 My submission for 1407C was 92267975 and i got runtime error on test 31. I don't understand why I am getting this as it is working fine on my machine without any error(even on test 31). Some help please!!!
•  » » 3 weeks ago, # ^ |   0 It is because you are using fast io in an interactive problem. Remove the line fast and it will be AC. See 92343642
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 Ok, now I am confused. I submitted the code after removing fast io but still got the same result 92344000. Then I tried submitting the code in GNU C++17 and got AC in both (with and without fast io).Now, I am wondering what is wrong in GNU C++17 (64).
•  » » » » 3 weeks ago, # ^ |   0 fi(i,0,n)vis[i+1]=0,l[i]=-1;This is out of range. vis has dimension n only. Thus you have undefined behaviour.
•  » » » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 Yeah! I saw that and I changed its dimension to n+1, see 92344148 but still the same result.I guess the problem lies in the language in which it was submitted. But I don't know what exactly it is.
•  » » » » » » 3 weeks ago, # ^ |   0 No, it is because you are not using consistently the range 1 to n. You replace your line by fi(i,0,n)vis[i+1]=0,l[i+1]=-1; and you get accepted see 92347506
•  » » » » » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 All right! Thanks a lot.But still one doubt: why 92344465 this got accepted?
 » 3 weeks ago, # |   0 can anyone explain problem A to me? I tried the solution code but it was producing the wrong output using the test input in A
 » 3 weeks ago, # |   0 what if in problem A, the elements removed are consecutive?
 » 3 weeks ago, # |   0 Here's a simple way to solve E: 92321081
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   0 you have pushed back u in g[v] not viceversa... the edges are bidirectional, I had the same approach but got wrong answer.However , when I made the directed graph of input all worked fine , can you explain?NVM the graph is directed !!shit!!!
 » 3 weeks ago, # |   0 Can anyone explain why in Problem D, we are interested in first height j lower than i and vice versa and not farthest j which satisfies the condition in the question?
 » 3 weeks ago, # | ← Rev. 3 →   -11 thx
 » 3 weeks ago, # |   +6 I didn't get D, how can we prove that the number of pairs i
•  » » 3 weeks ago, # ^ |   0 Because for a particular index there can be at most 4 just next nearest neighbours(left smaller , right smaller , left greater , right greater) which are smaller or greater than its value!. So in total there will be at most 4*n edges + n normal edges of adjacent elements . Thus at most 5*n such pairs exist!
•  » » » 3 weeks ago, # ^ |   +1 Thanks got it now
 » 3 weeks ago, # | ← Rev. 2 →   0 How to solve problem C if we have an additional condition, i
 » 3 weeks ago, # |   0 92352918Please someone help why my simple dp solution is not working.. And sorry for dumb mistake since I am new to this!
•  » » 3 weeks ago, # ^ |   0 Sorry, I found mistake but still can't solve problem D.
•  » » » 3 weeks ago, # ^ |   0 You need to consider jumping in both directions. Assume 4 2 2 2 4 4 4 4 2 Answer should be 3.
•  » » » » 3 weeks ago, # ^ |   0 but isn't jump only one directional? since it says i < j ..
 » 3 weeks ago, # |   0 Could someone explain in D, why do we need greater and less to the left side? Can't we just calculate possible jumps to the right side of each building?
 » 3 weeks ago, # | ← Rev. 8 →   +13 In Case anyone feels difficulty in understanding official editorial of problem D Try this At first try solving this problem It is the basic prerequisite :-Next Smaller ElementNow you are much knowledgeable to solve the problem yourself or just give another try if you are here for first time . I would recommend 5 to 6 more try!Consider this problem as a source given (1) and you need to reach destination (n) under the given conditions in minimum time . Now one basic transformation one can think of is to draw a graph with various edges depending upon the conditions. and then if the graph is weighted then apply DIjskarts or if it is unweighted then apply BFS!.Don't be confused actual main idea starts here .Creating the graph Graph CreationMove 1--> We can always move from i to i+1th node so our graph is connected that is we can always follow this route to reach n.node ---- 1-->2--->3--->4--->5----6...--->ntime ---- 0-->1--->2--->3--->4--->5------>n-1so for ith node minimum time taken is i-1 (self explanatory) if we dont draw any other edges. SO now we have our basic connected graph that is a tree!Move 2 was that from a node i we can jump to node j (means an edge exist if all elements in the range i+1 to j-1 are strictly lesser than both a[i] and a[j].Now how can I find these pairs efficiently. First lets consider for i =a[i] and all in middle indices(i+1 to j-1) between i and j are lesser than a[i]. ( Because if middle index would have been greater than a[i] then we never would have reached j.)thus to move 1 finding these and same for left to j. and right to i is sufficient. Thus to draw {i,j} edges in our original array represented as graph! we have to add following edges. for each i find next greater element to left and next greater element to right.MOVE:-3 From a node i we can jump to node j (means an edge exist if all elements in the range i+1 to j-1 are strictly greater than both a[i] and a[j].)For strictly greater part to draw {i,j} edges in our original array represented as graph! we have to add following edges. for each i find next smaller element to left and next smaller element to right. Proofs are same as in first part. Now our graph would look something like this at each index ! >>>>> >>>>>> 1-->2--->3--->4--->5------->6.....-->n <<<<<< <<<<<<<<this extra dashed edges are created by moves 2 and moves 3. Now we have constructed our graph and we need to find shortest path from node 1 to node n Approach 1: BFSAs It is unweighted graph we can use one simple thing is to find Single source Shortest Path using bfs! Pretty common technique.First option of bfs works for only unweighted graphs but consider another problem that edges have a weight of (j-i)/k then in case of weighted graph we would have used Dijskarts but complexity would be O(nlogn) . Also what if there is a negative edge means for some edges weight becomes negative then we would go for Other advanced algorithms like Johnson Algorithm . Which is again having O(nlogn) solution but what if we have to consider all the things in linear time. If the graph is having any type of edges without having negative cycle then definitely the below given solution with Dynamic Programming works well for handling all such scenarios in linear time. I liked that approach very well but Bfs can do this easily. So if you only have to go in more conditions and more conditions then only consider the next spoiler with DP. Approach 2: DPSolution is use DP.Lets define dp[i]= the minimum time taken to reach node i if we consider only first i nodes and minimum time taken to reach here from node 1. Ok how to make transitions in this dp.Well lets say for a particular node i we have 4 edges . jlefts,jrights,jleftg,jrightg.g=greater element,s=smaller,jrights , jrightg > i > jlefts, jleftg.for node i following 3 transitions are possible.dp[i]=min({dp[i-1]+1,dp[i]});dp[i]=min({dp[jlefts]+1,dp[i]});dp[i]=min({dp[jleftg]+1,dp[i]});And for future coming nodes node i can play a role to its minimum value thus we have to make extra 2 transitions! dp[jrights]=min({dp[jrights],dp[i]+1});dp[jrightg]=min({dp[jrightg],dp[i]+1});If you won't make these extra transitions answer won't be minimal in worst case. THUS I tried to explain it clearly. If further doubts occur consider my simple solution!92355697THank You!
•  » » 3 weeks ago, # ^ |   0 Thanks for such a clean code and wonderful editorial
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 "First option of bfs I won't recommend as it doesn't involve much thinking and what if the graph would have been weighted?"- if graph was weighted, we would have used dijkstra. How do you conclude that graph approach doesn't require thinking, how dumb are you Mister specialist. If it didn't require much thinking why were you not able to solve it during contest, you dumbass SpoilerNa gaand hai na chuchi, aur baate kare uchi uchi
•  » » » 3 weeks ago, # ^ | ← Rev. 4 →   -6 I have a personal choice of algorithms where to use which one may be It contradicts you. The idea to Solve the problems was crystal clear to me around 10.minutes before the contest. But due to my slow implementation speed I was not able to implement. Lets say Now There is a edge with weight x>1 in graph or I can better say that for each I to j transformation the time taken is (j-i)/k where k is some constant factor for a particular graph. Apply Bfs if you can! The only option is to involve deep thinking in this case. When a problem is solved during a contest sole moto is to compete but when an editorial is written or when you are upsolving we have to consider 4 to 5 ways to approach problems and consider side effects of each and every approach that's what I did in my editorial.If it hurts you I am sorry but my way of thinking is not to strict my self in a bound of known algorithms.Ya I am a specialist but capable of understanding data structures and Algorithms clearly.
•  » » » » 3 weeks ago, # ^ | ← Rev. 2 →   +1 You could have said that you liked dp approach more, but instead you concluded that graph approach does not require thinking. Don't fucking contradict your statement, you dumbass.Your rating graph shows how things are crystal clear to you LolFirst of all try to do C in every contest, then try to write editorials of D. You wasted 2 minutes of every person who tried to read your cancer editorial Competitive programming is not data structure and algorithm, it is problem solving. Go do leetcode Mister specialist 
•  » » » » » 3 weeks ago, # ^ |   +1 Mind your business. I know what I have to do and where I have to practice. I have written editorial because official version was not much clearer to many persons. And if you Think that it is cancer then just skip it . I have not forced you to read it and do harsh comments and spread hatred.
•  » » » » » » 3 weeks ago, # ^ |   +2 Thanks AM_I_Learning for writing your editorial. You have nicely explained all the things.
•  » » » » » » » 3 weeks ago, # ^ |   0 Your welcome !
•  » » » » 3 weeks ago, # ^ |   +3 You are so stupid that i have to repeat myself, IF GRAPH WAS WEIGHTED WE WOULD HAVE USED DIJKSTRAAnd you are talking about capability of understanding data structures and Algorithms clearly
•  » » » » » 3 weeks ago, # ^ |   0 What if edges would have negative weight . That is in my above comment if k becomes -ve for some transition then you would go for Johnson's right but Dp is a universal solution I take back my words of deep thinking. I have revised it you can see orz! Not going to talk more
•  » » » » » 3 weeks ago, # ^ |   0 Ya I have said that I have the potential to learn clearly . I have never said that I already knew them clearly. I am just beginning learning them. Anyway thanks to bring deep insights in me.
•  » » 3 weeks ago, # ^ | ← Rev. 3 →   0 wrong ans case 32 code: 92383805i tried too much.my approach al most same to you..i can't find wrong. do you please check my code ?also i can't understand why need those dp[jrights]=min({dp[jrights],dp[i]+1}); dp[jrightg]=min({dp[jrightg],dp[i]+1});
•  » » » 3 weeks ago, # ^ |   0 We need these transition because there exists edges both to the left and. Right side of a node . If you won't update these right nodes with the current node. Then when you reach any node j>i for which j is the next right greater element then there is a possible jump but at i only we know that there is a jump possible not at J . Thus To consider all the possible cases we have to make both left and right transitions while parsing a single node.
•  » » » » 3 weeks ago, # ^ |   +1 thank you got it..i handle this bit different process...I consider jleftg,jlefts.. if any i there is no jleftg or jlefts then I load possible maximum jump for this i..this is done here Spoilerfor(i=1; i<=n; i++) { while(1) { if(stk.empty()) break; z = stk.top(); if(z.first0; i--) { while(1) { if(stk.empty()) break; z = stk.top(); if(z.first
•  » » » » » 3 weeks ago, # ^ |   +1 Thanks if any one person got insight with my editorial I feel good .happy coding keep learning!
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   +1 Thanks AM_I_Learning for the detailed explanation and the suggestion to solve "Next Smaller Element" which helped a lot.
 » 3 weeks ago, # |   0 According to the Editorial for question div2 A -for a test case say — 1111000000 the answer has to be 000000 since number of 0's >= n/2but in question it is written that "The elements that you remove don't have to be consecutive."so how 1111 can be removed without taking consecutive elements ??Please answer
•  » » 3 weeks ago, # ^ |   0 don't have to be doesnot mean that** it can't be**. the problem just says if you wanna delete consecutive elements, then you can do so! so i repeat, you can take both consecutive and non-consecutive elements
•  » » 7 days ago, # ^ |   0 Dont have to be consecutive means you can remove anywhere you want, he's trying to say you ar not obligated to use consecutive numbers, not necesarily 1,2,3,4 for example you can 1, 3, 7, 10 etc, study the difference between can, must, do, have to etc, greetings.
 » 3 weeks ago, # |   -13 In the problem AHahahahahahaha.(1407A) I am confused about the editorial solution .It says if count_one<=n/2 , we remove all ones and the alternating sum will be oviously zero. But what if suppose n=12 and array will be like 0 0 1 1 1 1 0 0 0 0 0 0. According to the i.e's solution we should print 0 0 0 0 0 0 0 0. But according to the question "The elements that you remove don't have to be consecutive.".Just correct me if I am wrong.P.S:- You will get AC on submitting the solution described in Editorial
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +5 "elements don't have to be consecutive" — they can be both consecutive and nonconsecutive. It's written in this way because some participants could think that it's allowed to erase only subarrays, not subsequences.
•  » » » 3 weeks ago, # ^ |   -16 You are right but You should have written "need not" in place of "Don't" coz these terms are very critical if we read it as English. BTW I took it as "don't" while contest and didn't remove more than 1 consecutive element from the array. and result for above e.g is the same as the original array i.e [0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0].
•  » » » » 3 weeks ago, # ^ |   +5 bro, english is not my first language, but as I know "don't have to" means "you can do it, you're not forbidden to do it". and as you can see this task have been solved by too many users, they understood this line so it's not typo.
 » 3 weeks ago, # |   0 what is the mean " The elements that you remove don't have to be consecutive." in problem A !!
•  » » 3 weeks ago, # ^ |   0 It simply means that you can remove both consecutive and non consecutive elements
•  » » » 3 weeks ago, # ^ |   0 thank you a lot.
 » 3 weeks ago, # |   0 In C, how do we decide the index to place a or b (which is either mx or i) in the original permutation ? Thanks in advance :)
•  » » 3 weeks ago, # ^ |   0 suppose permutation P in P[1]=3,P[2]=5 call for ? 1 2 will return 3 (a=3), but call for ? 2 1 will return 2 (b=2) though ? 1 2 return maximum .so it is clear that index 1 < index 2; so index i mean p[1] will be max .(like as P[1]=a)...next check for index 2,3 and so on
 » 3 weeks ago, # | ← Rev. 2 →   +12 Who interested, I found out that we can always erase not more than one number in the first task. It's not hard to prove, you can do it by yourself (I can write, if you really want, but I'm too lazy :) ). So we can solve it with $O(n^2)$ — simply check initial array and array without each element.(maybe somebody wrote about this solution in the comment, in this case, I'm sorry)
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +9 After discussion with my friends we came up with the same conclusion lolIt can be implemented in O(n) tho: 92392220
•  » » » 3 weeks ago, # ^ |   0 I actually implemented the same during contest but it took me 40 frickin minutes so there's that. https://codeforces.com/contest/1407/submission/92247136
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 i.e or Nezzar can you prove this please ? I tried to prove using induction but didn't succeed.
•  » » » » 3 weeks ago, # ^ | ← Rev. 5 →   +6 Briefly (not formally):For any input, we can keep ignore(virtually delete) neighbouring 00/11s.The result string will always be 1010101010... or 01010101...Let number of 1s be kIf k is odd, delete the middle 1 (so that there will be floor(k/2) 1s for odd and even positions)If k is even, delete the middle 0 (the 0 between k/2th 1 and (k/2+1)th 1).(Obviously if result string is empty then we don't delete anything)
•  » » » » » 3 weeks ago, # ^ |   0 But aren't we deleting more than 1 time in your proof ? Also in that case number of deletion can be more than n/2 .
•  » » » » » » 3 weeks ago, # ^ |   0 By virtually delete we are not actually deleting them, just that we pretend they do not exist. The actual deletion (if any) only happens at last step.
•  » » » » » » » 3 weeks ago, # ^ |   0 I think my O(n) solution is more intuitive than your's. Take a look :P
 » 3 weeks ago, # |   0 In problem A : we can not remove consecutive elements. But In this tutorial we may remove consecutive elements. if the case is: 1110000000 we can't remove 111 because they are consecutive. I couldn't understand this logic. plz help me
•  » » 3 weeks ago, # ^ |   0 No, problem says the elements you remove don't have to be consecutive. It doesn't say it can't be consecutive. So to simply put it, you can remove both consecutive or non consecutive elements. Doesn't matter!
 » 3 weeks ago, # |   +8 92410698Why is editorial for Problem D so complicated when we can have much simpler and shorter implementation.
 » 3 weeks ago, # |   0 Can anyone please help me, I'm getting answer as 50 instead of 18 in test case 5 of problem D. Many of people were getting the same exact problem but idk how to correct it.
 » 3 weeks ago, # |   0 In problem(A) — Ahahahahahahahaha according to the tutorial For array 1 1 1 0 0 0 the resulting array would be 1 1 but in this case we have removed 4 consecutive elements 1,0,0,0 but it is given in the question that the element removed must not be consecutive .
•  » » 3 weeks ago, # ^ | ← Rev. 5 →   0 The resulting array would be [0, 0, 0] (size>= n/2). Every one is doubt regarding — "it is given in the question that the element removed must not be consecutive". But I was not in doubt while contest, I didn't remove more than 1 consecutive element. Here is my O(n) Solution and output(for 1 1 1 0 0 0) by my code is 1 1 0 0 0.P.S — In place of "don't" they should have written "need not"
 » 3 weeks ago, # |   0 In 1407B — Big Vova, method 2's time complexity is O(AnlogA), but I think it should be O(len(set(a))^2 * log(max(a))), any ideas?
 » 2 weeks ago, # |   0 Can anyone explain problem D?
 » 2 weeks ago, # |   0 Guys, any idea why this code TLE's on test 6?https://codeforces.com/contest/1407/submission/92785936
•  » » 2 weeks ago, # ^ |   0 I figured it out. I should've submitted the solution with g++ instead of clang.
 » 13 days ago, # |   0 Guys, can anyone help in understanding why my solution for E is wrong. Basically, my logic is, start from vertex 1 and explore all edges to vertex n. If there's an edge that lies on the shortest path to n, color the vertex opposite to that edge so that we cannot travel on it. It feels like a simple solution, but it's giving WA. Can anybody help in explaining why along with a smaller test case? Thank you! Solution: https://codeforces.com/contest/1407/submission/92859047
 » 13 days ago, # |   0 someone can explain the 2nd question acc to me it seems wrong answer
 » 12 days ago, # |   0 Sorry, I'm a bit confused here. Could somebody help me? For problem D, why do we have to check both from the left and right? Wouldn't checking just from the left suffice?
•  » » 12 days ago, # ^ |   0 My bad, I got it
 » 8 days ago, # |   0 In E, edges are from u to v or undirected ? i.e please look into.