By pikmike, 6 weeks ago, translation,

Hello Codeforces!

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Ne0n25 Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 Um_nik 7 149
2 jiangly 7 193
3 hank55663 7 214
4 neal 7 231
5 uwi 7 250

205 successful hacks and 712 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A Drew_is_me 0:01
B Drew_is_me 0:03
C IgorI 0:03
D xb0nS 0:09
E hongvip1638 0:17
F SunshinePie 0:28
G tfg 0:13

UPD: Editorial is out

• +356

 » 6 weeks ago, # |   +76 Is it only me or other people also feel that educational rounds are harder than div2 rounds(considering they have more number of questions)?
•  » » 6 weeks ago, # ^ |   -118 +1
•  » » » 6 weeks ago, # ^ |   -128 +1
•  » » » » 5 weeks ago, # ^ | ← Rev. 3 →   -69 why are you guys getting downvotesEDIT: why am I getting downvotes i just wanted to know -_-
•  » » » » » 5 weeks ago, # ^ |   +115 They could have simply upvoted the first post instead of spamming by adding that reply +1.
•  » » » » » » 5 weeks ago, # ^ |   -48 +1
•  » » » » » » 5 weeks ago, # ^ |   -21 Soo judgemental!! walking towards great future...
•  » » » » » 5 weeks ago, # ^ |   -51 cause they could use ++ instead of +1
•  » » » » » 5 weeks ago, # ^ |   -24 You are getting downvotes because you did not understand the +1
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   +147 I know it would be controversial, coming from a newbie, however adding a point system in Educational rounds similar to Div2 rounds, but in a compressed manner, would have fared better. Experts would have focused on harder problems upto their level, while the newbie/pupils start from the easier ones and gradually peaking up...The current system follows the number of solved problems and time penalty. While it's not bad, but why not something similar to Div2 round point system? Apology in advance, if I am missing some obvious reasons.
•  » » » 5 weeks ago, # ^ |   +29 I just see this as a different kind of Div2 event.There are Div2-only rounds (not Div1+Div2), which follow the said scoring system. This is just another way of scoring. I don't see why Div2 can't have both formats.
•  » » 5 weeks ago, # ^ |   -8 may be i am not sure
•  » » 5 weeks ago, # ^ |   0 I think so
 » 6 weeks ago, # |   -22 Thank you for providing the requested information. I hope to see Interactive Problems in the future. Thank you once again for everything you’ve done.
 » 6 weeks ago, # | ← Rev. 2 →   -89 [cf comment sections these days: no offense ]()
•  » » 6 weeks ago, # ^ |   -10 lmfao
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   +27 I don't know why but it turns out that the people are desperate to make my situation as the meme guy lol!
 » 6 weeks ago, # |   -26 Hope this contest won't be gandu like the last contest.
•  » » 6 weeks ago, # ^ |   0 brother please maintain the dignity of the platform they work hard for creating problem and organizing contest and provide us this wonderful platform free of cost.
•  » » » 6 weeks ago, # ^ | ← Rev. 3 →   -26 Abbey bhai it was a bsdk contest let me tell you why-1)The first problem was Math this is codeforces not mathforces or something2)I don't even read C, D, E, and F but they seemed boring adhoc stuff3)Also like I do codeforces for Interviews but the problems are becoming more and more bad
 » 6 weeks ago, # |   -22 All authors are very experienced. So hoping to get good problems.
 » 6 weeks ago, # |   -14
 » 6 weeks ago, # | ← Rev. 3 →   -40 I just got rekt
 » 6 weeks ago, # | ← Rev. 2 →   -19 One more Educ from pikmike!Hope, that Educ will be as good as last one from you)
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   -45 The comment is deleleted)))
•  » » » 6 weeks ago, # ^ |   -26 Ikr, and this actually defeats the purpose of 'comment section', it should be used to express your opinion or thoughts but those comments are often downvoted
•  » » » » 6 weeks ago, # ^ | ← Rev. 4 →   -34 I wrote my first comment not to be upvote. It's just my feelings
•  » » » » » 6 weeks ago, # ^ |   -22 yeah.. I'm not sure about that mate
 » 6 weeks ago, # |   +15 can i go to 2000 rating QAQ
•  » » 6 weeks ago, # ^ |   -33 no, improving your rating by a total of 1 is a very big deal. i don't think you can get 2000 at least in the near future
•  » » » 5 weeks ago, # ^ |   0 Not for you (and me) to say
•  » » » » 5 weeks ago, # ^ |   0 wzh520wzh rating is 1999 so the reply by phil213 is sarcastic obviously :)
•  » » 5 weeks ago, # ^ |   0 Just 1 point remaining. Hope you reach there. All the best
 » 5 weeks ago, # | ← Rev. 2 →   -19 is this comment section doomed already!! Edit : for newbies :(
 » 5 weeks ago, # |   +12 why does people love spamming CF announcements with "is it rated?" it's so annoying & frustrating !
•  » » 5 weeks ago, # ^ |   -11 frustation++
 » 5 weeks ago, # | ← Rev. 3 →   -16 comment deleted, figured it out
•  » » 5 weeks ago, # ^ |   -9 this is not youtube comment section.
 » 5 weeks ago, # |   -27 Upvote if you lose some rating because of this round :(
•  » » 5 weeks ago, # ^ |   0 You can always not participate if you do not like it.
•  » » » 5 weeks ago, # ^ |   0 But after the first wrong submission you lose rating ^^"
•  » » » » 5 weeks ago, # ^ |   0 Why do you do wrong submission?
•  » » » » » 5 weeks ago, # ^ |   +15 its his choice
 » 5 weeks ago, # |   0 In one of the examples, the range of cans that the customer could buy was between 3 and 4. How could we sell a pack with 5 cans to him (according to explanations?
•  » » 5 weeks ago, # ^ |   0 If the customer wants 3 cans 5 // 3 is 0 3 % 5 is 3 so the customer will buy 3 cans one by one which is smaller than 5/2 = 2.5(same thing if the customer wants 4 cans)
 » 5 weeks ago, # |   0 Wtf is pretest 2 in C
•  » » 5 weeks ago, # ^ |   +13 If you did greedy, it wont work.
•  » » » 5 weeks ago, # ^ |   +5 Its DP. Difficult but very nice kind of DP!
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   +8 DP wasn't difficult. The difficult part was to prove that DP works.
•  » » » » » 5 weeks ago, # ^ |   +1 Isnt the very notion of dp would work in every problem even if it greedy (ignoring the part that dp solution would very slow relatively)
•  » » » » » » 5 weeks ago, # ^ |   0 How do you know that you can only assign it increasingly? Why isn't there a case that a number with ti=4 is placed at 2 and then one with ti=3 and then one with ti =4 snd then more values.
•  » » » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 I agree but I think the more hard part was to come up that its dp not greedy, which I did not during contest
•  » » » » » » » 5 weeks ago, # ^ |   0 The proof was the constructive part. To me, constructive logic comes more easily than the DP part. The DP wasn't difficult, yes, but it took a lot of time for me to realize that it can be done by DP :(
 » 5 weeks ago, # |   0 How to solve C ? My greedy solution didn't work :( .
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   +20 SpoilerKnapsack. Brief ExplanationYou can make dp[N][time]. Than transitions are pretty standard.You can remove from the oven at this time. Therefore,dp[N][time] = min(dp[N + 1][time + 1] + abs(T[N] — time), dp[N][time]);or you can skip the removal of this oven at this time. Therefore,dp[N][time] = min(dp[N][time + 1], dp[N][time]);Submission
•  » » » 5 weeks ago, # ^ |   +2 I struggled with C, but the moment I read knapsack I instantly had the solution.
•  » » » 5 weeks ago, # ^ |   0 can you explain the base case? why you check time <= 2*n + 10
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 since the cooking time lies between 1 to n (inclusive); so for every T > 2*n you will have difference of at least 'n' for each dish . which will make the answer worse .. so there is no point in going ahead of 2*n .PS:- he has kept additional 10 minutes for his convenience .
•  » » » » » 5 weeks ago, # ^ |   0 thanks!
•  » » 5 weeks ago, # ^ | ← Rev. 4 →   0 1 15 1 3 4 5 6 6 7 8 10 10 11 12 13 14 15 
•  » » 5 weeks ago, # ^ |   +7 it's dp. look at constraints, they gives hint in itself.
•  » » 5 weeks ago, # ^ |   0 You can solve using Dynamic Programming . Sort the given array . The corresponding array of times will be also sorted and will be of size n .
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +10 $dp[i][j]$ — min answer having placed the first $i$ dishes in the first $j$ minutes.First lets sort the dishes in non-decreasing order of $t_{i}$ so we can iterate on time in ascending order.$dp[0][0]$ is clearly $0$.Clearly at any state (where $i \lt n$) we can place the dish now, in which case $dp[i + 1][j + 1]$ = $min$($dp[i + 1][j + 1]$, $dp[i][j]$ + unpleasantness), where unpleasantness is of removing the $i$-th dish at the instant j or $abs(j - t_{i})$.Or we can just not place it, in which case, $dp[i][j + 1]$ = min($dp[i][j + 1]$, $dp[i][j]$)
•  » » » 5 weeks ago, # ^ |   +1 Apologies in advance if my comment seems stupid. I used a similar logic as yours. However, my dp[i][j] represented the optimal cost if time taken is i and the no. of objects picked are j, i represented the time and j represented the number of elements picked. so my dp transitions were dp(i,j)=min(dp[i-1][j],dp[i-1][j-1]+mininum of abs(A[k]-i) provided k is permitted. I have stored permitted ks in a vector of unordered_maps. However, I am getting WA. Can you please explain where my approach goes wrong. Thanx in advance.
•  » » » 5 weeks ago, # ^ |   0 I believe the 2nd equation should be dp[i+1][j+1] = min(dp[i+1][j+1], dp[i+1][j])
•  » » » » 5 weeks ago, # ^ |   0 Oops, yeah it should have been $dp[i][j + 1]$ = min($dp[i][j + 1]$, $dp[i][j]$), since we don't place a dish in this step. Thanks for pointing that out.
•  » » » 5 weeks ago, # ^ |   +1 How do you get this good of a intuition with DP? It seems so obvious when someone tells use this DP and during the contest I cannot think of any transitions or states.
•  » » » » 5 weeks ago, # ^ |   0 once you master Recursion.then just by adding few lines of code you can code TopDown Dynamic programming(recursion + storing answers at every recursion call).and if you starts with base case and use recursion logic, like how the solution builds up in call stack, you will be able to figure out BottomUp Dynamic programming.(base case + iteration)
•  » » » » » 5 weeks ago, # ^ |   0 How are you making sure that no time is used twice?
•  » » » » » » 5 weeks ago, # ^ |   0 look at my Code I won't move to next index/item untill I had chosen the current item
•  » » » 5 weeks ago, # ^ |   0 can we solve it using dp but without sorting the dishes?? i think this question would become like max biparate matching with one end as time and other as dishes.
•  » » 5 weeks ago, # ^ |   0 I did using recursion then once i saw that recursion was working then i converted it into topdown Dynamic programming.
 » 5 weeks ago, # | ← Rev. 2 →   0 .
•  » » 5 weeks ago, # ^ |   0 Dynamic Programming!Sort the intitial oven times Try giving time t to current index i note their absolute difference move forward for the remaining suffix and find the minimum sum of absolute difference of timings it can be done using bottom up dp easily.
•  » » 5 weeks ago, # ^ |   0
 » 5 weeks ago, # |   +8 How to solve B ?
•  » » 5 weeks ago, # ^ | ← Rev. 4 →   +6 .
•  » » » 5 weeks ago, # ^ |   +2 But why does it work?
•  » » » » 5 weeks ago, # ^ | ← Rev. 3 →   +1 .
•  » » » » » 5 weeks ago, # ^ |   -106 fxcking greens with no reasons but able to solve B miraculusly fxck
•  » » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   +49 .
•  » » » » » » 5 weeks ago, # ^ |   +3 This was not "miracle". I solved the same way but the intuition is tough and even tougher to put it in words. I am not even interested to try explain that and that does not imply somebody solved it with magic.
•  » » » » » » 5 weeks ago, # ^ |   +2 I want to downvote your comment but then i see -69 downvote so i not downvote your comment :-)
•  » » » 5 weeks ago, # ^ |   +1 What is "group of contiguous unordered elements" here?
•  » » » » 5 weeks ago, # ^ | ← Rev. 4 →   +8 .
•  » » » » » 5 weeks ago, # ^ |   0 The code is clear, but I still got no clue why this gives answer. In this 96877997 there is an explanation based on pairs "00" and "11", and the number of such pairs. Somehow that relates to your explanation, does it?
•  » » » » » » 5 weeks ago, # ^ | ← Rev. 3 →   +3 .
•  » » » » » » » 5 weeks ago, # ^ |   0 Ok, thanks!
•  » » » » » » » » 5 weeks ago, # ^ |   +1 I solved it in a similar manner, but ig the approach was kinda more logical..We can assuredly say, that any set of consecutive characters cannot be allowed.. Also, we can argue that k 1s are incorrectly placed only when k 0s are incorrectly placed as well.So, we just have to count the set of incorrect occurences. And it would require half steps to correct them.One of the ways of doinng so can be to count the consecutive set of characters+(bool)(s[0]==s[n-1]).(Since in an even lengthed sequence, they cannot be same..) You can check my submission here for reference-96899666
•  » » » » » » 5 weeks ago, # ^ |   +4 Let me try. Let's divide the string into : S = "A" + "B" + "C". A = alternating B = not alternating C = rest of the string Here B can either be a series of 1s(111..) or 0s(000...). We are going to pick a substring D = "B" + "some part of C" and reverse that. B = 111 then D should end at some position i such that s[i] = 0. you keep the first 1 of B, so "111" becomes "1 + 010... + 11". And we are going to do it again and again. So if you analyze at the end we will have S = "X" + "Y" + "Z" where, X = alternating Y = series of 1s/0s Z = series of 0s/1s (opposite of Y) And at the end when you are only left with Y and Z, it will take 1 operation for each 0s/1s.
•  » » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 I'll explain to you : imagine the number C which is : C = number if indices i -> so that s[i] == s[i+1] as you can guess C in our destination string (10101.. or 010101..) is zero and its obvious that :C=0 <=if and only if=> our string is 01010101 or 10101010and we know that when a substring is reversed C can change by at most 2 values (cause the adjacency of the elements in the substring does not change) so the number of moves we make is at least ceil(C/2) .and there you have it also this is my submission : 96932885
•  » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   +1 @Uvaish_ZafriAmazing Brother, positive and helpful people like you are very rare in comments, thanks for the explanation <3
•  » » 5 weeks ago, # ^ |   0
•  » » 5 weeks ago, # ^ |   +4 Another way is to count number of consecutive ones. Let this be K. Therefore, add K — 1 to the answer. Do same for zeroes. Answer is max of answer for one and answer of zero. 96876793This is mainly because when we solve for 111000, we see that we actually need 2 moves.First move => 100110. Second move => 101010.Try for higher strings like 11110000, you will notice the answer is always K — 1 for K consecutive ones.
•  » » 5 weeks ago, # ^ |   0 I used the observation that if you take an alternating sequence and reverse it once, you will have either two consecutive 1's or two consecutive 0's. Further if we reverse it, you might see a similar result where it further increases the consecutive 0's or 1's. If the reversing segment is a palindrome you don't see any difference.From this to find the solution if there is a continuous segment of 3 1's then it means 2 reversals created it and by undoing it you will get the original string. So compute consecutive count — 1 for each 1 segment and zero segment. Use max of it.
 » 5 weeks ago, # |   +27 Am I the only one who misread problem D and tried to solve thinking it was DFS for most of the contest T_T
•  » » 5 weeks ago, # ^ |   +14 I found D way easier than B (maybe because I'm more familiar with graph theory) Basically just give the nodes greedly and maintain the height (because if you try to store the tree you'll mle)
•  » » » 5 weeks ago, # ^ |   -20 I think C was easier than B and D was tougher than C.
•  » » » » 5 weeks ago, # ^ |   +5 I feel complete opposite. B seemed pretty trivial to me. D was standard. I still can not understand C even after reading the comments. Maybe C was easy for those who are decent in dp.
•  » » » » » 5 weeks ago, # ^ |   0 yeah C is trivial dp. if you are familiar with dp then it's just read and implement but i read it very late when unable to solve D, then tried B, and finally read C.
•  » » » » » » 5 weeks ago, # ^ |   0 I miss understood the statement of C :/
•  » » » 5 weeks ago, # ^ |   +6 To clarify, I didn't think the solution was DFS, I read BFS in the statement then proceed to solve it if the process was DFS
•  » » » » 5 weeks ago, # ^ |   +19 I'm glad I wasn't the only one lol.
•  » » » » 5 weeks ago, # ^ |   0 same. But fortunately soon I realized I was thinking about dfs not bfs.
•  » » » 5 weeks ago, # ^ |   0 I second this
 » 5 weeks ago, # |   0 how to do B ??
•  » » 5 weeks ago, # ^ |   +4 just count consecutive zeroes and ones and ans is max of both ,I learned the hard way :(
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 111000 answer here is 2. Can you explain a bit more?
•  » » » » 5 weeks ago, # ^ | ← Rev. 3 →   0 there are 2 consecutive ones and zeroes , so for minimal answer we can reverse the substring with consecutive ones and zeroes recursevily1 1 1 0 0 0 -> 1 0 0 1 1 0 -> 1 0 1 0 1 0check this
•  » » » » » 5 weeks ago, # ^ |   0 okay!! ,Now i got it...
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 find number of 1s and 0s that are not correctly placed.take max(count(1),count(2))111000 -> 2 1s and 2 0s not correctly placed.ans = 210000101110011 -. 3 1s and 4 0s not corrected place.ans = 4
•  » » » » » 5 weeks ago, # ^ |   0 why this solution is working? how to think that?
•  » » » » » » 5 weeks ago, # ^ |   0 Intuition is that if there is consecutive 1s like 11111 we need at least 5-1 swaps to actually seperate them into the right order. This is true for 0 too and when we make a swap, we can fix the order of a pair of 1 and 0. By taking the max , we get the ans.
•  » » 5 weeks ago, # ^ | ← Rev. 4 →   -18 My solution for B (counting segments)int solve() { int n; cin>>n; string s; cin>>s; vector segs; int i=0; while(i
 » 5 weeks ago, # | ← Rev. 2 →   +102 Isnt B much harder than D or im missing something obvious?
•  » » 5 weeks ago, # ^ |   +34 same feeling, couldnt solve B even after thinking more than 1.5 hr
•  » » » 5 weeks ago, # ^ |   +5 What the hell is even answer to B ?
•  » » » » 5 weeks ago, # ^ |   +1 there were only two you could have turned the strings into...either 10101010or 01010101
•  » » » 5 weeks ago, # ^ |   0 solved c but not b I thought im the only one feeling its tough
•  » » » » 5 weeks ago, # ^ |   0 Can you explain C? I read comments above but couldn't understand it
•  » » » » » 5 weeks ago, # ^ |   0 Ok its a DP solution I used recursion+ memoization. Its greedy+dp. 1. sort the array because its greedy we want to serve smaller time first. 2. if we consider an element then we have to add abs(a[k]-time) to our answer otherwise just increment time(condition only till our time is less than a[k] otherwise we compulsory have to add (a[k]-time). refer solution below for better understanding. https://codeforces.com/contest/1437/submission/96952099
•  » » » » » » 5 weeks ago, # ^ |   0 Got it, but one question rises in my mind. How did you think of this?
•  » » » » » » » 5 weeks ago, # ^ |   0 Ive practiced a lot of recursive solutions so it doesnot take a lot of time to figure out and had to hit and trial with some conditions when I got confused while solving.
•  » » » » » » » » 5 weeks ago, # ^ |   0 Perfect!!
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   -12 There is nothing harder than the "D"
•  » » 5 weeks ago, # ^ |   0 I feel B's main observation was the constraint. n//2 zeroes and n//2 ones. so if there is two consecutive 1s there has to be two consecutive zeroes except cases like this 0110 for that we have to take maximum of both consecutive 0s and 1s otherwise reversing a substring means just swapping the wrongly placed 0s and 1s. Maybe my explanation is wrong and i just got lucky lol. But i came up with the solution with this observation.
•  » » 5 weeks ago, # ^ |   0 Maybe B's time limit is a fact. I have tried a brute-force approach at the last moment and it passed with 1700+ ms timing. Now I am waiting to see if it can get a TLE in the system-test or someone hacks it.
•  » » 5 weeks ago, # ^ |   0
 » 5 weeks ago, # |   +17 RIP my ratings
 » 5 weeks ago, # |   +2 How to solve B?
•  » » 5 weeks ago, # ^ |   +1 Here is an intuitive solution that worked for me.For each consecutive pair of 1s, u have to insert a 0 between them and u will always have a "smart way" to do that in a single move(considering the fact that we have equal zeroes and ones). The same holds for pair of zeroes as well.Doing it for a single pair of 1s, also do the job for a single pair of 0s. So count the consecutive 0s(00)-> cnt0 and 1s(11) -> cnt1, then max(cnt0, cnt1) will be the answer.Hope it helps.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +56 At this kinds of problems, you usually want to search for alternative statements that are more helpful. We can see that we could reframe it as: given a string s consisting of n/2 0's and n/2 1's, lets define f(s) = the number of i for which s[i] = s[i + 1], 1 <= i < n.To make s alternating, we want to make f(s)=0.A reverse operation changes f(s) with at best 2. So f(s) can be decreased with at most 2 in one operation. A lower bound for the answer to this problem is ceil(f(s)/2).Now we only have to prove that you can always decrease f(s) by 2, excepting the case where f(s) = 1.if f(s) > 1, then we will always have at least a pair of consecutive 0's and at least a pair of consecutive 1's. So we can just reverse the substring cotaining one of this 1's and one of this 0's and decrease f(s) by 2.For example s = 01001011,f(s) = 2. we have the 0 pair (3,4) and the 1 pair (7,8). So if we reverse (4,7) we get 01010101.If f(s) = 1, than the string will have to be either 0101..0110101...1010 or 1010....1001...0101. So you can reverse a prefix/suffix and decrease f(s) by 1, arriving at f(s)=0.
•  » » » 5 weeks ago, # ^ |   +12 Thank you so much for such a detailed explanation!
•  » » » 5 weeks ago, # ^ |   0 Thanks a lot for the great explanation.
 » 5 weeks ago, # |   0 Guys, where can I hack? I don't see any locks..
•  » » 5 weeks ago, # ^ |   +6 Educational rounds do not have the same hacking feature as div2 or div1. You can hack after the contest, but you'll not get any points for that.
•  » » » 5 weeks ago, # ^ |   +6 So it was incredibly stupid to hack myself lmao.
 » 5 weeks ago, # |   0 how to solve G? is nsqrtnlogn supposed to pass? (I had tle on test 17)
•  » » 5 weeks ago, # ^ |   +3 nlogn is intended, nlog^2 or nsqrt can pass if written carefully enough but I highly doubt sqrtlog can pass.
•  » » » 5 weeks ago, # ^ |   0 when will editorial be published?
•  » » 5 weeks ago, # ^ |   +5 Just make Aho-Corasic, and calculate link2(v) = link(v) but only with ends of strings. Now u just go left-to-right in some string of query. After adding some char, you have node V, u must check every suffix, that's end of some string, of this node. U can do it with link2(v). It works O(q * sqrt(5*10^5)), bcs u have only sqrt(5*10^5) different lengths of strings;
•  » » » 5 weeks ago, # ^ |   0 How the O(sqrt(5e5)) comes?Can you explain further. My solution with HLD is O(log^2 n).
•  » » » » 5 weeks ago, # ^ |   +5 you have maximum fail depth when calculating query value only if size of n strings must be strictly increasing.For example : a, aa, aaa, aaaa, aaaaa .... so n is sqrt(5e5) in worst testcase
•  » » » » » 5 weeks ago, # ^ |   0 Oh, I didn't notice this during the contest. So I built the FAIL pointer into a tree and then solved it by HLD+segment tree.
 » 5 weeks ago, # | ← Rev. 2 →   -161 problem 2 ~~~~~ string solve(){ // CALM DOWN : — ) ll n; cin>>n; string s; cin>>s; ll l=0; ll r=n-1; vector ans1(n); bool t=0; for(int i=0;i=r) break; last++; swap(tl,tr); rev=!rev; } l=0; r=n-1; tl=l; tr=r; ll last1=0; rev=0; while(l=r or l>=n or r<0) break; last1++; swap(tl,tr); rev=!rev; } ret(min(last,last1)); ret(""); } ~~~~~ why this code is giving TLE .... i have created both the ans array and then used 2 pointer one pointer at left and another at right and i swap the pointers please if any one could help
•  » » 5 weeks ago, # ^ |   +28 Please put code in spoiler tags like this:)
•  » » 5 weeks ago, # ^ |   +3 code looks very dirty... plz polish up
•  » » » 5 weeks ago, # ^ |   0 can you explain how to do this question with two pointer??? thanks for help
•  » » » » 5 weeks ago, # ^ |   0 i can't understand what your code exactly works..i don't solve this problem using not two pointer but greedy.so i recommend to read the tutorial of this problem.. main idea of that is gorgeous in low rating problem
•  » » » » » 5 weeks ago, # ^ |   0 thanks i got the idea
 » 5 weeks ago, # | ← Rev. 2 →   +2 WTF is test 11 in E?
 » 5 weeks ago, # |   +11 Very nice problemset.
 » 5 weeks ago, # |   0 Why doesn't assignment problem work for C?
 » 5 weeks ago, # |   +17 Even D was much easier than B.. what the hell is answer to B ?
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Just count adjacent identical elements and print max of them
•  » » » 5 weeks ago, # ^ |   0 can you explain it more?
•  » » » » 5 weeks ago, # ^ |   0 For code you can just see my submission. For intuition, here's how I got itFirst observation was that, when you are iterating, your left should be at the first occurrence of the digit that has adjacent identical digits. Let's say it was 1. Now move your right pointer until you find the first complimentary adjacent pair, 0 in our case. You reverse l-r substring and do the same. The key observation here was, you'd have to this the max of number of times there are adjacent pairs in the string. In case of 00110110, 1 has adjacent count 2, 0 has 1. So the ans is 2.Dry run: 01010110 01010101Hope this helps
•  » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 I got ur point. and key observation will let us know the answer....but I have a doubt in that iteration part... "When you are iterating, your left should be at the first occurrence of the digit that has adjacent identical digits. Let's say it was 1. Now move your right pointer until you find the first complimentary adjacent pair, 0 in our case. You reverse l-r substring and do the same".......implementing this approach on 11101000 dry run: 10111000 10101100 10101010 will take 3 steps and answer should be 2 so, iteration should be done in some different manner
•  » » » » » » 5 weeks ago, # ^ |   0 The dry run for 11101000 is(L->1, R->5) gives 10101100 (L->5, R->6) gives 10101010Your right pointer should point to that position where there are 2 identical bits (complimentary to the l pointer).
•  » » 5 weeks ago, # ^ |   0 whats the solution of D???
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   +2 D can be solved with this observation. SpoilerFor a continuous segment if the array is strictly increasing. Each value in this segment can be made into a new node. Also, each of these nodes can be child of a single parent node.(Note: Try to think why making each of these values of segment in a new node will be beneficial for us.)You can ask me why this is beneficial. But would be helpful if you try it yourself.Now what is left is to implement this.If you get stucked, maybe my submission can help you. Submission
•  » » » » 5 weeks ago, # ^ |   0 I also did that observation...T_T but i guess my implementation had some problem...btw thanks...
•  » » » 5 weeks ago, # ^ |   +3 Use queue and push the levels into the queue. When you find a smaller number, pop and push the popped level + 1 in the queue. Keep track of max level pushed. Print the max level pushed.
•  » » 5 weeks ago, # ^ |   0 My Solution was to count the number of 01(say cnt01) and 10(say cnt10) in the input String and then the answer is the minimum of (n/2)-cnt01 and (n/2)-cnt10. I dont have any proof but it took me almost 1 hr to come up with this observation
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +28 We may assume the array is circular. An alternating array has no monochromatic adjacent pair (like 00 or 11). If the array is not alternating, there are always two adjacent pairs 00 and 11. We can remove both of them in one operation. Every operation removes at most two adjacent monochromatic pairs.
•  » » » 5 weeks ago, # ^ |   0 Man I went for this exact approach other the fact I still dont get why we assume it to be a circular array ? Please help on this one ...
•  » » » » 5 weeks ago, # ^ |   0 Just for convenience. Otherwise the third statement is false.
•  » » 5 weeks ago, # ^ |   0
 » 5 weeks ago, # | ← Rev. 2 →   +1 What is the expected time complexity for E?
•  » » 5 weeks ago, # ^ |   +13 O(NlogN)
•  » » 5 weeks ago, # ^ |   +21 I solved it in $O(n log(n))$, if LIS is required to solve it I don't think it can be any better.
•  » » » 5 weeks ago, # ^ |   +10 Can you explain your approach?
•  » » » » 5 weeks ago, # ^ | ← Rev. 7 →   +105 First of all, if $a_{b_{i + 1}} - a_{b_{i}} \ge b_{i + 1} - b_{i}$ isn't true for all $i \lt n - 1$ there is no way to place numbers between them, so the answer can't exist.Now lets mark the closest left and right $b_{i}$ for each index. (for any position b/w $b_{i}$ and $b_{i + 1}$, the closest left one is $b_{i}$ and the closest right one is $b_{i + 1}$, so we can mark it in $O(n)$). Lets call these $left_{i}$ and $right_{i}$.Now clearly for the increasing condition, for any $i$, $a_{i} \ge a_{left_{i}} + (i - left_{i})$ so we can actually place some valid numbers in this range (if not we can't even place $a_{left_{i}} + 1, a_{left_{i}} + 2, \ldots, a_{i} - 1$ between $left_{i}$ and $a_{i}$ while keeping it increasing). Similarly we must also have $a_{i} \le a_{right_{i}} + (right_{i} - i)$. If either of these don't hold, we will have to update $a_{i}$. So lets set $marked_{i} = 1$.Now in each range $(b_{i}, b_{i + 1})$, all values with $marked_{i} = 0$ are individually valid. We want to take a maximum subset of these such that they are increasing and values can be placed between them. Now for increasing the first thing that comes to mind is longest increasing sequence, but if we just do LIS we can end up with issues in cases like this (which Sample 4 thankfully contains): 3 0 2 1 3 Here the longest increasing sequence may give us $(2, 3)$ but this isn't actually valid, we can't place any digit between them such that it forms an increasing sequence. So we also need that for any $i, j, (i \lt j)$ we pick, $a_{j} - a_{i} \ge j - i$ must hold. This can be simplified to $a_{j} - j \ge a_{i} - i$. Or in other words, we just want to find the longest non-decreasing sequence of $a_{i} - i$ in each segment.Adding the sizes of all these sets together will give us the total number of values which don't need to be changed, so the answer will just be $n$ minus this total size.
•  » » » » » 5 weeks ago, # ^ |   +8 Perfect!! Thanks ExplodingFreeze.
•  » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   +5 i was almost there, unfortunately i didn't knew nlogn approach for LIS :(((.
•  » » » » » » 5 weeks ago, # ^ | ← Rev. 3 →   0 A pretty easy way of writing LIS in $O(n log(n))$ — LinkOr with vectors when multiset is too slow — LinkAnd an explanation of how / why it works — Link
•  » » » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 thankyou.AC submission. https://codeforces.com/contest/1437/submission/97012483thankyou this a very handy snippet.
•  » » » » » » » 5 weeks ago, # ^ |   +1 I think it is LIS rather than LCS :)
•  » » » » » » » » 5 weeks ago, # ^ |   0 Fixed. Yeah, don't know how I wrote LCS xD
•  » » » » » 5 weeks ago, # ^ |   0 shouldn't it be longest increasing subsequence of ai-i instead of longest non-decreasing??
•  » » » » » » 5 weeks ago, # ^ |   +5 nope1 2 3 4 5 becomes -> (1-1) (2-2) (3-3) (4-4) (5-5)0 0 0 0 0if 1 2 3 4 5 is good then we should count longest non-decreasing of ai — i
•  » » » » » » » 5 weeks ago, # ^ |   0 But why do we consider a[i]-=i for eg in one of the editorials it is written [2,5,3,1] we can' take 2,3 as LIS but after doing above operation it solves the problem. I am not getting the exact problem and solution by this.
•  » » » » » » » » 5 weeks ago, # ^ |   0 Go through this ,it helped me
•  » » » » » 5 weeks ago, # ^ |   0 Thanks for the explanation..
•  » » » » » 5 weeks ago, # ^ |   0 Thanks! It really helped!
•  » » » » » 4 weeks ago, # ^ |   0 Thanks a lot for this explanation. During virtual I got stuck on the point where : while finding LIS , we must keep in mind that a[j] >= a[i] + (j-i) It didn't strike me that we can move that j over to the other side of the equation and started thinking it might require something like convex hull trick to work. -_-
•  » » » 5 weeks ago, # ^ |   0 You should write an unofficial editorial man, you're awesome!!
 » 5 weeks ago, # |   0 In problem D , for first vertex 1 i considered largest increasing sub-sequence starting from i=2 as it's children . For example if input was 1,2,3,5,6,4 . I considered 2,3 as child of 1 and 5,6 as child of 2 and 4 as child of 3 . What is wrong in this approach or in my solution
•  » » 5 weeks ago, # ^ |   0 Your approach is correct Maybe you glitched your code or failed maintaining the height ?Here is my code which AC https://codeforces.com/contest/1437/submission/96920232
•  » » 5 weeks ago, # ^ |   +3 For this test case-8 1 2 3 8 7 6 5 4Answer should be 3 your code is giving 1 . I might be wrong
•  » » » 5 weeks ago, # ^ |   0 you are right.Thanks a lot for your help . There was very silly coding mistake .
•  » » 5 weeks ago, # ^ |   0 1 as root2 3 5 6 can all be childrens of root4 can be a child of 2 so overall the height is $2$The easy way to describe the answer is to calculate the number of increasing sequences, and in each sequence count the number of elements in it. In each node, you can put an entire increasing sequence as the children of it. and now the number of nodes for the next level increases by the number of elements in the increasing sequence. for example this: $1, 7, 8, 5, 6, 2, 3, 4$$[7, 8] [5, 6] [2, 3, 4]so [5, 6] will be a child of 7 , and [2, 3, 4] will be a child of 8. and now for the next level you have 5 nodes namely [5, 6, 2, 3, 4]. •  » » » 5 weeks ago, # ^ | 0 i did same can but it is giving wrong on 273rd input in test case 2. Can you check.96912116 •  » » » » 5 weeks ago, # ^ | 0 Your code break on this such case: n = 10$$1, 2, 3, 6, 5, 4, 10, 9, 8, 7$Your code output $4$, while the correct answer is $3$How the answer is $3$? well at depth $0$ you have $1$and at depth $1$ you have $2, 3, 6$and at depth $2$ you have $[5]$ under $2$, and $[4, 10]$ under $3$, and $[9]$ under $6$. and at depth $3$ you have $[8]$ under $5$, and $[7]$ under $4$, and you still can put many more.. so the answer is $3$Hope that helps !
•  » » » » » 5 weeks ago, # ^ |   0 thanks, but somehow i found the answer i was doing wrong with queue insertions.
 » 5 weeks ago, # |   0 I try to hack C but it returns this: FAIL Expected EOLN (test case 1, stdin, line 3, why?
•  » » 5 weeks ago, # ^ |   +3 I hacked my solution, ez.
•  » » » 5 weeks ago, # ^ |   0 Sorry graphter lol.
•  » » » » 5 weeks ago, # ^ |   +4 Why are you sorry ?
•  » » » » » 5 weeks ago, # ^ |   0 I hacked cuz I thought a lot of people would have had it wrong, while it was just the 2 of us and it was thus stupid, since it probably wouldn't have been hacked lol.
•  » » » » » » 5 weeks ago, # ^ |   0 Although my solution was hacked, it wasn't hacked by you. Am I missing something ?
•  » » » » » » » 5 weeks ago, # ^ |   0 Oh really it wasn't? I thought it was cuz we were the only ones hacked. Oops I'm seeing wrong lol. That's even worse if I only hacked myself lmao.
•  » » » » » » 5 weeks ago, # ^ |   0 you haven't hacked him.
 » 5 weeks ago, # |   +15 Can someone explain how to prove the answer to B is just half the number of positions where $s_{i} = s_{i + 1}$ cyclically? It intuitively feels correct as we can fix at max 2 such positions in each operation but I have no clue how to prove that we always can.
•  » » 5 weeks ago, # ^ |   +6 If there are at least $2$ positions to fix, there are always indices $x, y$ such that $s_x = s_{x+1} = 0$ and $s_y = s_{y+1} = 1$.Proof by contradiction: suppose wlog that $s_i = s_{i+1} = 0$ is false for each $i$. Let $z_i$ be the position of the $i$-th $0$. Then, the inequality $2(j - i) \leq z_j - z_i \leq 2(j - i) + 1$ holds.But there are two positions to fix, so $z_{i+1} - z_i = 3$ should hold for two indices $i = a, b$, $a < b$.Then $z_{b+1} - z_a = (z_{a+1} - z_a) + (z_b - z_{a+1}) + (z_{b+1} - z_b) \geq 3 + 2(a + b - 1) + 3 = 2a + 2b + 4$.But $z_{b+1} - z_a \leq 2(a + b + 1) + 1 = 2a + 2b + 3$ (contradiction).So $x, y$ exist, and you can fix $2$ positions by reversing either $[x + 1, y]$ or $[y + 1, x]$.
•  » » 5 weeks ago, # ^ |   0 My solution was also intuitive , although I didn't consider it as a cycle. I counted positions where $s_{i}=s_{i+1}$ and $ans = (cnt+1)/2$. No idea why this works either but it just seemed right and it passed. Was able to solve B in just 4 mins. Felt really good after failing terribly in the Techno Cup :)
•  » » 5 weeks ago, # ^ | ← Rev. 4 →   0 Hey I didn't participate in the round, so don't know if this solution is correct. But maybe can help with intuition.Keep a count of number of chunks of 1s(c1) and number of chunks of 0s(c0). When we reach n/2 chunks each of 0s and 1s, we are done. In one operation if you reverse a sub-array starting and ending in different bits you can increase both c0 and c1 by 1 potentially (potentially coz that won't happen on the ends). It can be proved that while there are more breakable chunks of 0s and 1s there are sub-arrays ending in opposite bits that break these chunks, incrementing both c0 and c1 by 1. You may need one extra operation if you have an almost alternating sequence but with just c1 = n/2 — 1 and c0 = n/2 or vice versa. With this you can see that you will need max(n/2 — c0, n/2 — c1) reversal operations.
•  » » » 5 weeks ago, # ^ |   0 I did this and got accepted.
 » 5 weeks ago, # |   +12 What is the intended solution of B and how to prove it? I... I just believe...
•  » » 5 weeks ago, # ^ |   0 i just Bruteforce it,there are 2 possibilities,whether the string S become 101010... or 010101... here is my code 96881167
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 consider the case 1110111000001**1101110**0000 : flip the selected part, it becomes : 1**0111011**0000101**110110**000 -> 101**011011**00010101**10110**00 -> 10101**01101**001010101**1010**0 -> 1010101**0101**0the selected part in each step is from the first occurrence of 11 to first zero after all ones, which by flipping reduces consecutive 1s by 1 and eventually become zero. So, the answer would be no of 1s for which (a[i]==a[i-1] && a[i]==1).Same goes for 0 as well and minimum of those two will be the answer. codevoid solve(){ int n;cin >> n; string s; cin >> s; int one=0, zero=0; for(int i=1;i
 » 5 weeks ago, # |   +4 If I submit two solutions for the same problem, first one can be hacked while the second one can't be. Then if after the 12-hour hacking phase, the first one gets hacked but second one is still is accepted, will my second submission be considered for total score or not ?
•  » » 5 weeks ago, # ^ |   +3 Most likely yes: the first will incur time penalty, and the second, along with its time, will be counted towards the score. Generally, the submissions would be (re)judged as if all the hack cases were there from the start.
•  » » » 5 weeks ago, # ^ |   -23 It would have been a relief if you wouldn't have said "Most likey", but your comment stopped me from crying. So thanks !!Will anyone confirm it pikmike vovuh BledDest adedalic ?
 » 5 weeks ago, # |   +72 Yay solved A, beware CF for when i become red
 » 5 weeks ago, # |   0 nice testcases...
 » 5 weeks ago, # | ← Rev. 2 →   0 96914153 why this solution is giving TLE O(n) solution — i have created both the answer and used 2 pointer .... insted of swapping the string i swapped the pointers every time left and right pointer doesnt matches the character at string PLEASE HELP
•  » » 5 weeks ago, # ^ |   0 I think it's supposed to be solved in O(n), sol
 » 5 weeks ago, # |   +26 I wish I could ask "how to solve G?" instead of "how to solve A?" :) anyway, How to sole A?
•  » » 5 weeks ago, # ^ |   0 if (float(r+1)/2)>l then NO else YES
•  » » 5 weeks ago, # ^ |   0 if((2*l)>r)-YES else-NO
•  » » » 5 weeks ago, # ^ |   0 but why?
•  » » » » 5 weeks ago, # ^ | ← Rev. 4 →   0 We are basically trying to exploit the fact that for all m>n, n % m =n. Let us say l=14 and r=26We have to find a number x such that it gives a no larger than or equal to x/2 for all numbers from l to r, modulo x. Like 14 % x => x/2 .. 15 % x >= x/2 , up to 26 % x >= x/2 . It is clear that the number should not exceed 2*l , as on taking modulus, any number x larger than l would return l itself. Hence after x=2*l, l itself will give a remainder smaller than x/2.If by any means, the number r lies beyond 2*l ; we are certain there exists no solution x , as l % x < x/2 i.e. l < x/2 .P.S. In the above example, 28 would be an optimal answer
•  » » 5 weeks ago, # ^ | ← Rev. 4 →   -10 Lets assume that $l = \frac{a}{2}$, now $a=2l$.If $(a>r)$, we know that all elements in $(l,r)$ are greater than or $\frac{a}{2}$ as $l = \frac{a}{2}$, therefore whatever the customer buys, he will have to buy $a$ cans which is what we wanted so answer is YES. If $(a<=r)$, He can just buy $a$ cans and he doesn't need extra cans as $a$ lies in $(l,r)$.Why assume $l = \frac{a}{2}$? Because it is optimal and it gives us the biggest window.
 » 5 weeks ago, # |   +3 Did anyone solve problem C, greedily ?
•  » » 5 weeks ago, # ^ |   +2 No. Now I know trying to solve a dp problem greedily is dumb.
 » 5 weeks ago, # |   +27 The key education that I seem to get from these Educational Rounds is how to get my ass kicked. How did people go about spotting the pattern for B — tried so many approaches but none of them worked.
•  » » 5 weeks ago, # ^ | ← Rev. 6 →   0 It did using two pointers. I'm not good in explaining or proving things. It was mainly intuition. You can see my solution . Edit: Why downvotes?
•  » » » 5 weeks ago, # ^ |   0 what was your approach?
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   +1 I just counted the number of consecutive 0's, and that is the answer. Because, the number of consucutive 1's/0's are present is == number of minimum swap required.
 » 5 weeks ago, # |   0 Hello for question D I used a greedy approach which I have seen others use. But my code WA and I have no idea why. Can someone please look: https://codeforces.com/contest/1437/submission/96922858 ? Thank you!
•  » » 5 weeks ago, # ^ |   +4 For god's sake it's not a question, it's either 'problem' or 'task'
•  » » » 5 weeks ago, # ^ |   +3 Depends on which English do you speak. In Indian English, anything that requires your mind to solve is tagged a "question" . I only came to know that "question" and "problem" have different meanings after coming to cf.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +5 1 17 1 17 2 16 3 15 4 14 5 13 6 12 7 11 8 10 9 Maybe check your last for-loop?
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 How did you create this diagram (I mean the tool used)?
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   +6 .
•  » » » » 2 days ago, # ^ |   +1 You can use 'Graph Editor' by csacademy: https://csacademy.com/app/graph_editor/. It is similar to the one above.
•  » » » 5 weeks ago, # ^ |   0 thanks for this one.
 » 5 weeks ago, # |   0 Can anyone please explain me why greedy will fail on problem C.
•  » » 5 weeks ago, # ^ |   +7 Can you explain why greedy will work in problem C!
 » 5 weeks ago, # | ← Rev. 2 →   0 In problem e : "In one operation, you may choose two integers i and x (1≤i≤n, x can be any integer) and assign ai:=x. This operation can be done only if i does not belong to the set b." in the first example :7 21 2 1 1 3 5 13 5So I understand that I can never apply such operation on the elements with indices 3 and 5. So a[3] = 1 for always. Why the output is not -1?
•  » » 5 weeks ago, # ^ |   +9 x can be negative4 possible moves are : (1, -1), (2, 0), (4, 2), (7, 6)Array after these moves : -1, 0, 1, 2, 3, 5, 6
•  » » » 5 weeks ago, # ^ |   0 ahh,thank you!
•  » » 5 weeks ago, # ^ |   +3 Because you can change value to negative.
 » 5 weeks ago, # |   0 Did anyone's greedy solution get accepted for problem C?
 » 5 weeks ago, # |   +23 Did someone else solve C in O(N*logN) with the solution for 713C in this blog? Thanks zscoder for such a useful trick.
 » 5 weeks ago, # |   +6 in problem A possible a always be r + 1 ? why..
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +3 If possible, we want to fit the whole range [L, R] within [A/2, A-1]We can include R for any A > R, but to also include L we have to extend it as left as we can, means we need smallest A > R
 » 5 weeks ago, # |   +5 Here's a more formal explanation of solution to problem B. Let's say you need to make the input string S equal to T 101010.... The procedure for converting a string equal to the other target string i.e. 010101... is quite similar. Now, let's xor our input string S with the target string T. Say this string is R. It's easy to analyse that R shall have even number of ones. Now, reversing a substring in S is equivalent to reversing the same substring in R. Also, on reversing a substring of even size, with all ones, changes all the ones to zeros. So, basically, the best strategy for us is to bring all the ones closer to each other and then use one operation to change all ones to zeros. Thus, the ans is number of blocks of consecutive ones in R
 » 5 weeks ago, # |   0 C has a greedy tag too. How to solve it greedily?
•  » » 5 weeks ago, # ^ |   +6 Sorting the array before doing the dp is a greedy observation.
•  » » » 5 weeks ago, # ^ |   0 Oh. I see. I didn't notice. Thanks for pointing out.
 » 5 weeks ago, # |   +38
 » 5 weeks ago, # |   -24
•  » » 5 weeks ago, # ^ |   +12 Uhh I think B is veryyyyyyyyyyyyy different the one you posted
•  » » » 5 weeks ago, # ^ | ← Rev. 5 →   0 The key idea is the same in both problems.we will compare the actual string with 010101.. and 101010.. and check which will give the minimum result. The only difference in today's B was we can select contiguous subsequence of any length. while in the problem similar to B, we can select only one element.submission for today's B 96936502submission for similar to B https://atcoder.jp/contests/abc124/submissions/14613891you can check yourself.
•  » » 5 weeks ago, # ^ |   0 How can you forget C. It's just knapsack.
 » 5 weeks ago, # |   +3 How to approach C with DP?
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   +8 First sort all the dishes in increasing order, then define dp state as dp[i][t] = the minimum unpleasantness possible in taking out the first i dishes in that order within time t.There are two possibilities here: You can take out dish i at time t, in that case dp[i][t] = dp[i-1][t-1] + abs(t[i]-t). You don't do anything at time t, in that case dp[i][t] = dp[i][t-1]. Pick the minimum of these two.
 » 5 weeks ago, # |   0 https://codeforces.com/contest/1437/submission/96883973 https://codeforces.com/contest/1437/submission/96876758 please check ... those submissions are doubtful. i think, it's a Plagarism case.
 » 5 weeks ago, # |   +13 What is the expected time complexity for F? My solution works in O(NlogN) (only because of sorting) and I don't realy know how to solve this problem with different aproach, but N<=5000 and time limit is 4s.
•  » » 5 weeks ago, # ^ |   +10 That's really interesting, can you describe your solution? My solution (which is the model one for this problem) uses dynamic programming with $O(N^2)$ states.
•  » » » 5 weeks ago, # ^ |   +13 Оно немного непонятным может быть, поэтому я лучше на русском) Я писал дп с N-1 состоянием, где dp[i] — количество способов расставить первых i рыбаков, если мы уже както *хорошо росставили остальных n-i рыбаков. Сразу стоит сказать что если a[n-1]*2>a[n], то ответ 0.Теперь, как мы пересчитываем dp[i]: Если мы хотим поставить a[i] на первую позицыю, то для начала надо росставить все числа от L[i]-того до (i-1)-го надо поставить на любые позицыи кроме первой(L[i] — такое минимальное j, что a[j]*2>a[i]). Количество способов ето зделать — (n-i)*(n-i+1)...*(n-L[i]-1). А теперь нужно еще росставить числа от 1 до L[i]-1, при том что мы уже *хорошо росставили тех кто от L[i] до R[i], а ето по опредилению — dp[L[i]-1].И еще мы можем не на самую первую позицыю ставить, но тогда количество способов ето зделать — (n-i)*dp[i-1]. Вот решение с етой идеей, но произведение я тут считал, так сказать, в тупую, так что там O(N^2) 96921154. А вот уже за линию — 96930477. Если непонятно(а скорее всего, учитывая что писал ето я — непонятно), я постараюсь ответить на вопросы.
•  » » » » 5 weeks ago, # ^ |   +5 If someone needs the translation, I can try to do that, but I don't but I don't guarantee)
•  » » » » 5 weeks ago, # ^ |   +10 Почему мы можем расставить всех от L[i] до (i-1)-го на ЛЮБЫЕ позиции? Почему это ничего не ломает в конструкции?
•  » » » » » 5 weeks ago, # ^ |   +10 Когда мы считаем dp[i], мы считаем что суфикс из (n-i) рыбаков росставлен так, что бы самое левое число было хотя бы в 2 раза больше a[i].
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   +25 Very cool. I haven't yet read your solution in detail, but I believe that the model solution that BledDest mentions with the $N^2$ states is this:Let's first sort the numbers. For every person $i$, we know that there is a certain prefix of people such that each element $j$ of the prefix has $2*a[j] <= a[i]$. These people can freely be placed once person $i$ is placed, since they are guaranteed to become sad due to $i$. Let' call this the sad prefix of $i$, and say it has length $pref[i]$.Let $dp[i][j]$ represent the number of (suffix of) emotional sequences which start with person $i$ and $j$ elements from the sad prefix of $i$ has already been used. That is, they must not appear in the generated sequence once again.The transitions can now be writted as: $dp[i][j] = (pref[i]-j) * dp[i][j+1] + sum[suf][j+1]$Here, $suf$ represents the least index of any element with value $>= 2*a[i]$. $sum$ maintains the suffix sum of the DP.This works because we can choose to select one of the available items in the sad prefix and then the remaining sequence generated will be $dp[i][j+1]$, or we can choose to continue to another number which will be happy.
•  » » » 5 weeks ago, # ^ |   +3 Yes, the model solution does exactly the same.
 » 5 weeks ago, # |   +3 Is there a greedy solution for problem C? If no can you prove it?
•  » » 5 weeks ago, # ^ |   -6 Isnt "Wrong answer on test 2" enough of a proof in itself?
•  » » 5 weeks ago, # ^ |   +8 I think you meant if so*
•  » » » 5 weeks ago, # ^ |   0 No, I meant exactly what I wrote
•  » » 5 weeks ago, # ^ |   0 Can someone proove that why greedily taking the nearest time (before or after ti) is wrong ? This looks correct on drawing some cases.
•  » » » 5 weeks ago, # ^ |   0 1 8 3 4 4 6 6 7 8 8 Greedily, output would be 6 but actual output should be 4 .
•  » » » » 5 weeks ago, # ^ |   0 Thanks shahil_005 .
 » 5 weeks ago, # |   0 Editorial when?
 » 5 weeks ago, # |   0 Who else is waiting for editorial ???
•  » » 5 weeks ago, # ^ |   0 Don't wait, it will come after hacking phase.
•  » » » 5 weeks ago, # ^ |   0 Why not earlier?
•  » » » » 5 weeks ago, # ^ |   +6 So that, during hacking phase, hackers won't have the advantage of editorial.
•  » » » » » 5 weeks ago, # ^ |   0 I think it doesn't make any difference for the hackers.
•  » » » » » 5 weeks ago, # ^ |   +10 I'm not sure if it's still the same or not, but I remember that I hacked someone in educational rounds about 2 months ago by resubmitting my solution and copy-pasting the last test which was added to problem tests, so it doesn't really matter and you can hack someone even without reading the problem statement :/
•  » » » » » 5 weeks ago, # ^ |   0 A hacker does not get any points for hacking, so hacking is for educational purposes only.
•  » » » » » » 5 weeks ago, # ^ |   +1 Still you can decrease someone's rank.
•  » » » » » 5 weeks ago, # ^ |   0 And see this comment from the mike himself: https://codeforces.com/blog/entry/77130?#comment-618436
•  » » » » » » 5 weeks ago, # ^ |   0 Great then! Hopefully this will be followed in upcoming contests. But setters always wait for hacking phase to finish.
 » 5 weeks ago, # |   +1 Hi all I am unable to construct a case for which my code for problem D fails. Can anyone please help? Link to submission: https://codeforces.com/contest/1437/submission/96924627
•  » » 5 weeks ago, # ^ |   0 Same here, same test of test case 2.Link of my submissionPlease help.Thank you.
•  » » » 5 weeks ago, # ^ |   0 The case is 1 2 7 6 5 4 3As the inputs are permutations in increasing order, I used this code to find the case. Spoiler` vector v; v.push_back(1); v.push_back(2); int c=0, ct=3; while(c<273){ do{ if(v[0]!=1) break; c++; if(c==273) { for(auto i: v)cout<
•  » » » » 5 weeks ago, # ^ |   0 Thank you!
•  » » » 5 weeks ago, # ^ | ← Rev. 4 →   0 You're missing a case. If you are decrementing the previous level nodes by 1 then you should also increment current level nodes with 1. Link to your modified code : AC code
•  » » » » 5 weeks ago, # ^ |   0 Thank you!
 » 5 weeks ago, # | ← Rev. 3