vovuh's blog

By vovuh, history, 16 months ago,

All problems, except the problem D, are mine. The problem D author is MikeMirzayanov.

1353A - Most Unstable Array

Tutorial
Solution

1353B - Two Arrays And Swaps

Tutorial
Solution

1353C - Board Moves

Tutorial
Solution

1353D - Constructing the Array

Tutorial
Solution

1353E - K-periodic Garland

Tutorial
Solution

1353F - Decreasing Heights

Tutorial
Solution

• +150

 » 16 months ago, # |   +86 Video Editorials for D and EEnjoy watching!
•  » » 16 months ago, # ^ |   +35 dev manus ( "GOD" for those who don't know Hindi ).
•  » » » 16 months ago, # ^ |   -56 je aadmi bht bhala hai
•  » » » 16 months ago, # ^ |   -48 Haw re baba
•  » » » » 16 months ago, # ^ | ← Rev. 2 →   -42 The video really helped me understand d and e
•  » » 16 months ago, # ^ |   +10 Thanks stefdasca
•  » » 16 months ago, # ^ |   +14 Please Keep Making Videos of Div2 Problems as well. They are very helpful. Thank you so much.
•  » » 16 months ago, # ^ |   0 Hello everybody has seperate fan base now
•  » » 16 months ago, # ^ |   0 The video was quite nice. It is great to see that you made the videos while the contest was going on. lol :-)
•  » » » 16 months ago, # ^ |   +3 Well, I full solved the contest quick enough, so I had time to do the videos.
•  » » » » 16 months ago, # ^ |   0 YES. it is quite impressive. :)
•  » » » » » 16 months ago, # ^ |   -17 but not as impressive as Awesome_sheK
•  » » » 16 months ago, # ^ |   -15 bhai tere se achhe jokes maarta hain yeh laundahttps://codeforces.com/profile/Awesome_sheK
•  » » 16 months ago, # ^ | ← Rev. 9 →   0 for E, I was getting TLE for the same solution. UPDATE Ok i got it, my outer loop was running n times instead of k.
•  » » 16 months ago, # ^ |   0 Sir,can you kindly explain your appraoch for problem F?
•  » » 16 months ago, # ^ | ← Rev. 2 →   0 For E I implemented the same solution in Python. I get TLE on test 4. Are the problems not meant to be solved in python? Should I learn C++ instead?Edit: Including submission link https://codeforces.com/contest/1353/submission/80416176
•  » » » 16 months ago, # ^ |   0 If you want to stick with Python, use pypy instead, it's faster most of the times.In the long term, C++ is better in competitive programming, not every time python is guaranteed to pass.
•  » » 16 months ago, # ^ |   0 Thanks!!
 » 16 months ago, # | ← Rev. 2 →   +4 C editorial : https://youtu.be/lvNyiyobb18D editorial : https://youtu.be/xOvHv8pyQjs
•  » » 16 months ago, # ^ |   0 super fast editorial ^_^
•  » » 16 months ago, # ^ |   0 Keep it Going
•  » » 16 months ago, # ^ |   0 make one for problem E as well :)
 » 16 months ago, # |   0 Too fast editorial!!
•  » » 16 months ago, # ^ | ← Rev. 5 →   +23 F video editorial: LinkE video editorial: Link D video editorial: Link
•  » » » 16 months ago, # ^ |   0 Sir why can't we move from mat[i,j] to mat[i,j+1] or mat[i+1,j] if mat[i,j]>( mat[i,j+1] or mat[i+1,j]) bcz we can decrease mat[i,j] such that it becomes less than mat[i,j+1] or mat[i+1,j] whichever we are going to follow..here mat is the given matrix in the question
•  » » » » 16 months ago, # ^ |   0 You can decrease it. That is the question only. But when we are trying to solve the problem, we keep trying all possible values hence we are keeping the first constant, since we are trying all possible values the case you are talking about gets covered.
•  » » » » » 16 months ago, # ^ |   0 Many many thanks for answering my query.However,It's a hard to get how that case is getting covered. Your solution videos are really good.hope to be like you some day.
 » 16 months ago, # |   +15 Editorial is out but nothing under tutorial section?
 » 16 months ago, # |   0 what a super duper fast editorial :D thanks you
 » 16 months ago, # |   0 Wow!....so fast tutorial. Thanks for that.
 » 16 months ago, # |   0 ⚡Lightning speed editorial
 » 16 months ago, # |   0 which is faster @vouvh's editorial or speed of light?
 » 16 months ago, # | ← Rev. 2 →   0 Stupid question here...can someone explain the solution to first question(the last test case). Thanks
•  » » 16 months ago, # ^ |   +4 first index 0, second index the big number, and the rest is 0. u can't get any better than this (if u split it up, then ur basically splitting up the sum into two, but making the sums twice as plenty). so for all cases n>=3, u do 0, m, 00000000....
•  » » » 16 months ago, # ^ |   0 Thanks,finally i understood.
•  » » 16 months ago, # ^ |   0 In that case, n and m are equal to 1e9 . Consider it as 10 and 10, then we can make the array as 2,0,2,0,2,0,2,0,2,0. Then, we get the ans as 20. Similarly, in that test , we get ans as 2e9.
 » 16 months ago, # |   0 Omg, i don't know that i can modify the set like that.
•  » » 16 months ago, # ^ |   +4 look for custom comparators c++ , useful stuff.
•  » » 13 months ago, # ^ |   0 Especially functors they are hybrid custom functions which can take more than two variables
 » 16 months ago, # |   +1 Problem C can be solved in O(1) as well by counting for one quadrant of the board and using symmetry the answer for the rest of the quadrants is the same as calculated. There comes out to be a formula in terms of n for the counting of one quadrant.
•  » » 16 months ago, # ^ |   0 The final formula comes out to be n*(n-1)*(n+1)/3!!
•  » » » 16 months ago, # ^ |   +7 $\frac{4 \lfloor\frac{n}{2} \rfloor (\lfloor\frac{n}{2} \rfloor + 1) (2\lfloor\frac{n}{2} \rfloor + 1)}{3}$
•  » » » » 16 months ago, # ^ |   +1 Oh, now I see, it's equal to yours formula after simplification.
•  » » » 16 months ago, # ^ |   0 Please Explain How u getting it?
•  » » » » 16 months ago, # ^ | ← Rev. 2 →   0 draw each iteration out, and you'll quickly see the pattern. hint: think of the layers as actual squares
•  » » » » 16 months ago, # ^ |   +10 First, you need to get following picture: 2 2 2 2 2 2 1 1 1 2 2 1 0 1 2 2 1 1 1 2 2 2 2 2 2 So, answer is sum along this table. Now, derive formula how many zeroes there, how many ones, and so on: 0*1, 1*8, 2*16... You should get $\sum i(4(2i+1)-4) =\sum i(8i) = 8\sum i^2$Sum of squares is famous formula = $n(n+1)(2n+1)/6$. If you want derivation, google for it.
•  » » » » » 16 months ago, # ^ |   0 We can calculate answer for i and it can be extended for (i+2) where i is odd number. check it out here, link
•  » » 16 months ago, # ^ |   -8 Made a DP Solution for problem C .
•  » » » 16 months ago, # ^ |   +7 This solution doesn't actually utilize dp, since you are not using the data you precompute more than once. You can remove the memoization array (dp) and the same code will run at the same time if not faster.
•  » » » 16 months ago, # ^ |   0
 » 16 months ago, # |   +1 Is there a way to solve D in O(n)?
•  » » 16 months ago, # ^ |   0 I'm curious about that too.
•  » » » 16 months ago, # ^ |   0 I probably have a method which does for odd n in O(n), but couldn't extend it for even n!!!
•  » » » » 16 months ago, # ^ |   0 Using simple queue does it in O(n) but only works for odd values.
•  » » 16 months ago, # ^ |   0 This with counting sort instead:https://codeforces.com/contest/1353/submission/80116286
•  » » 16 months ago, # ^ |   -8 It's possible but not neccessary
 » 16 months ago, # |   0 is it like magic or what..
 » 16 months ago, # |   0 can anyone please explain D
•  » » 16 months ago, # ^ |   +5 what he's trying to do is make a set with compare function, you can make a priority queue too.COMPARE FUNCTION (class) EXPLAINED: It takes a pair as input(l,r) l = left index and r = right index . Then it sorts the pair in decreasing order of length( which signifies the length of zero sub array). This helps us to always get the longest zero sub-array with ease, hence, we can solve the problem.when it comes to why he used a struct for compare function, go through the link below.https://stackoverflow.com/questions/16111337/declaring-a-priority-queue-in-c-with-a-custom-comparator
•  » » 16 months ago, # ^ |   0 Consider the array [1,n] with initially all elements as zero let the interval [L,R] be defined as a part of array such that such all its elements are zero.Initially this part will be [1,n].Take std::set or std::map to store this interval. But the next interval which we will take should have maximum length and least 'L'; To do that we have to change the default sorting of set using comparator function. Then everytime we take the first interval from the set calculate the middle element and insert two new intervals in set [L,middle-1] and [middle+1,R] only if left<=right for this interval.If our set becomes empty at any instant then stop. Hope it helps
•  » » 16 months ago, # ^ |   0 did it with priority_queue, where one element is consists of len of segment,it's left index and right index, check it out here
•  » » » 15 months ago, # ^ |   0 How does priority queue know which pair has higher priority?
 » 16 months ago, # |   0 When do our ratings change? This is my first div 3 contest, so i don't know if it's different for div 3 than it is for other divisions.
•  » » 16 months ago, # ^ |   +2 A little while after the hacking phase (12 hours) ends
•  » » 16 months ago, # ^ |   +2 It will change after 12 hours (after passing on whole test-sets and after hacking phase will end)
 » 16 months ago, # |   +5
•  » » 16 months ago, # ^ |   +10
 » 16 months ago, # |   0 editorial speed > 3*(10^8) metre/sec
 » 16 months ago, # | ← Rev. 2 →   +2 Interesting problems! and fast editorial
 » 16 months ago, # |   0 Why B have more submissions than A?
•  » » 16 months ago, # ^ |   +17 We decided to allow $O(n^3)$ solutions because we thought that this greedy observation can be not so obvious for Div.3 participant and implementation part can be difficult, but... We were so wrong :)
 » 16 months ago, # |   0 fastest editorial in the NEWS
 » 16 months ago, # |   0 What is the correct path for the F problem in 2 example? (btw in this example n = 5 m = 5)
 » 16 months ago, # |   +10 Is vovuh competing with USAIN BOLT
 » 16 months ago, # |   0 How to solve 'D' using priority queue can someone help me with comparator function in priority queue.
•  » » 16 months ago, # ^ | ← Rev. 4 →   +4 i used this pi = pair struct cmp { bool operator()(pi const& p1,pi const& p2) { int f = p1.second- p1.first ,s = p2.second - p2.first; if(f == s){ return p1.first > p2.first; } return f < s; } }; priority_queue, cmp > pq; 
•  » » 16 months ago, # ^ |   +1 Refer to my editorial for D: https://sahilbansal17.github.io/Competitive_Coding/2020/05/14/cf-642.html
•  » » » 16 months ago, # ^ |   0 Very easy to understand. Well written code!
•  » » » 16 months ago, # ^ |   0 bro ur editorial is super awesome.
•  » » 16 months ago, # ^ |   +4 change the positive to negative for reverse priority queue
•  » » 16 months ago, # ^ |   0 You dont need comparator function. just use negative value see this 80158855
•  » » 16 months ago, # ^ | ← Rev. 2 →   +4 Approach to solve problem D with priority queue : [ With C++ pseudocode ] Create a structure for segment : struct segment { int start; int end; };  Create a comparator function by overloading the () operator in a struct such that the top of the priority queue contains the segment which has a greater length and in case of equal lengths, the element with smaller start position (left segment) is at the top. struct comp{ bool operator () (segment l1, segment l2) { int len1=l1.end-l1.start+1; int len2=l2.end-l2.start+1; return (len1,comp> pq; If you don't understand this syntax, go through this article : Priority queue for a struct in C++ As initially , the array contains all zeros. So, insert {0, n-1} to the priority queue initially. Iterate for all numbers 1 to n and pop the top segment, in the priority queue. Place the number at appropriate position as indicated in the question. Suppose the number is placed at an index ind Now, there are 2 new segments, which needs to pushed into priority queue: I. { start,ind-1} II. { ind+1,end } (Check for the corner case, when start > ind-1 or ind+1>end)
•  » » » 16 months ago, # ^ |   0 Thank you so much bro....I did using priority queue of pairs LINK : SOLUTION
•  » » » 16 months ago, # ^ | ← Rev. 2 →   +1 You don't need separate struct for comparator. You can include it in seg itself. look here for example: 80120262
 » 16 months ago, # |   0 can anyone explain this submission of 300iq?
•  » » 16 months ago, # ^ |   +3 This is the minimum subarray sum problem.
•  » » » 16 months ago, # ^ |   0 Thanks a lot bro! I got it now.
•  » » » 16 months ago, # ^ |   0 Can you explain a bit ? I didn't get it. What his solution is exactly doing?
•  » » » » 16 months ago, # ^ | ← Rev. 2 →   0 First he separates the places whose index%mod value is same..Now he may have a string like consisting of 1s and 0sHe has to light off all the ones outside of these places... And for the new string, his target is to create a contiguous block of 0s, then a contiguous block of 1s and then a contiguous block of 0s..Now solving this contiguous part making can be done using minimum/maximum subarray sum problem.
•  » » » » » 16 months ago, # ^ | ← Rev. 2 →   0 please EXPLAIN! how to make the new string a contiguous block of 0s, then a contiguous block of 1s and then a contiguous block of 0s.. by using maximum subarray sum problem??
•  » » » » » » 16 months ago, # ^ | ← Rev. 3 →   +6 Consider 1in / 0in = the number of 1s/0s inside the block of 1s and 1out/0out = the number of 1s/0s outside that block. Then the cost for a given block of 1s is equal to 0in+1out (because we need to transform the 0s inside the block into 1s and the 1s outside into 0s). Then we can see that 0in+1out = 1total-1in + 0in = 1total-(1in-0in). We want the cost to be minimum so that means we want (1in-0in) to be maximum possible, so we pick the subarray with maximum sum (after replacing 0s with -1).
•  » » » » » » » 16 months ago, # ^ |   +8 thankyou so much lucaperju you finally made me understand something which i was wondering for almost a day. Man you are a saviour !
•  » » » » » » » 16 months ago, # ^ |   0 ohhh..thanks it was helpful
•  » » » » » 16 months ago, # ^ |   0 How is this contiguous part solved by minimum/maximum subarray sum problem?
•  » » » » » » 16 months ago, # ^ | ← Rev. 2 →   +1 So, according to the explanation of lucaperju we want to find the maximum value of 1in-0in among all the subarray. Now, if we define a variable curr_sum and whenever we encounter a '0' we subtract 1 and whenever we encounter '1' we add 1. So effectively, by doing this we are keeping track of 1in — 0in. Now when we are doing maximum sum subarray problem then we are keeping track of the sum of subarray and maximising it, but instead here, we want to keep track of 1in — 0in, so in the logic of maximum subarray problem, we will change the definition of the variable that keeps track of the current sum of subarray. Here, r is the rightmost index of the subarray. curr_sum is the current value of 1in-0in. max_sum is the max_sum of the 1in-0in among all the subarrays ending before r. r = r + k because we are considering all the elements that gives same remainder with k; This code snippet gives maximum value of 1in-0in among all subarrays.If you have a problem in understanding why this is working, I would advise you to watch this video first: https://www.youtube.com/watch?v=86CQq3pKSUwFull submission: https://codeforces.com/contest/1353/submission/80282348 ~~~~~ while(r<=index2){ if(arr[r]==1){ curr_sum = max(arr[r],curr_sum+1); max_sum = max(max_sum,curr_sum); } else{ curr_sum = max(arr[r],curr_sum-1); max_sum = max(max_sum,curr_sum); } r = r + k; }~~~~~
 » 16 months ago, # |   0 https://chrome.google.com/webstore/detail/cf-predictor/ocfloejijfhhkkdmheodbaanephbnfhn?hl=en RATING PREDICTOR on standings of contest
 » 16 months ago, # |   0 vovuh , can D be solved using recursion ? Thanks.
•  » » 16 months ago, # ^ |   +1 You can store all pairs using recursion. Actually that's what I did during testing. The implementation is the same as the mergeSort function (without merging arrays function).
•  » » 16 months ago, # ^ |   0 yes, I did it.
•  » » » 16 months ago, # ^ | ← Rev. 2 →   0 That's very helpful. Thank you.
 » 16 months ago, # | ← Rev. 3 →   0 can someone explain why its TLE?80160568 it is not nlogn complexity?
•  » » 16 months ago, # ^ |   0 I'm not sure, but maybe something's wrong with PriorityQueue. I replaced it with heapq in your solution and it got AC 80179294.
•  » » » 16 months ago, # ^ |   0 хмэ. понял/принял. но все равно не понятно почему так, в документации написано что PriorityQueue это обертка над heapq. спасибо
•  » » » » 16 months ago, # ^ |   0 Обёртки по умолчанию работают хуже, так же это касается например queue/deque
 » 16 months ago, # |   +9 Super fast editorial, time complexity O(1), great!!!!
 » 16 months ago, # |   0 Can anybody help me what is wrong in this code? Problem B 80159137
•  » » 16 months ago, # ^ |   0 if k == 0 you dont read array b =>on next test prev array b reads as array a, current array a reads as array b =>error
•  » » » 16 months ago, # ^ | ← Rev. 2 →   0 yeah got it
 » 16 months ago, # |   0 How to prove that optimal solution for A is 2*m if n>2 ?
•  » » 16 months ago, # ^ |   0 Isn't that obvious? If you consider each unit independently, then it's obvious that you cannot obtain the answer more than two using one unit (because this is $1$-dimensional array). Thus if the number of units is $m$ then the maximum possible answer is $2m$.
•  » » » 16 months ago, # ^ |   0 Thanks.
•  » » » 16 months ago, # ^ | ← Rev. 2 →   -9 Not really , maybe it is because I don't have much experience.It is the first time I guess , I am seeing this idea. B-D were familiar.
•  » » » 16 months ago, # ^ |   -8 Hi can you help in getting why my code is giving wrong answer on testcase 2 for Problem F, My approach is different from the editorial, I understood the editorial solution and got AC with that approach but I am not able to get why my approach is giving Wrong Answer, I have asked about it to many people but got no replies. I am unable to generate a small testcase where it is failing, I tried on several testacases but all are working fine, can you please help me by telling what is going wrong in my approach? Actually my dp[i][j] stores a pair of integers, whose first element stores that what should be the optimal value of ar[i][j] to reach (n, m) and second element denotes the minimum total cost required from (i, j) to (n, m) with that value of ar[i][j].Here is my solution link: https://codeforces.com/contest/1353/submission/80376675
•  » » 16 months ago, # ^ |   +1 Let n be odd and suppose you divided m into (n/2) numbers such that one number is (m/(n/2) + m%(n/2)) and other (n/2) — 1 segments of (m/(n/2)). So the optimal answer, in this case, is to place these numbers on even positions i.e. 2, 4. In this case, you can observe the maximum you can get is 2*m. However, if n is even, you will get less 2*m sometimes. So, in general, the optimal way is to place m to one position such that it's not ending position of the array. But for n==2 there is not such positon.
•  » » » 16 months ago, # ^ |   0 I didn't go through your solution as I already understood one by Vovuh. But thanks for giving such a detailed solution. It might come in use to someone else.
 » 16 months ago, # |   +1 is there any chance of solving E by binary search ???
 » 16 months ago, # |   0 Did anyone solve E with D&C?
 » 16 months ago, # |   0 Thanks for good problems! I really enjoyed it! :D
 » 16 months ago, # |   0 I see a lot of priority queue submissions for problem D. Can anyone who has done using pq explain their solution? I guess it compensates for the comparator function written in editorial. Thanks!
•  » » 16 months ago, # ^ |   +1 The segment should be sorted by size (biggest first), then by index (smallest first). One can write an comparator to do this comparation. Or one can put the values into a pair, change the signs of the size of the index field (the second) and use the default comparator of the prioriy_queue.
•  » » » 16 months ago, # ^ |   0 Yeah I get the idea spookywooky, seems like I need practice in implementation of pq in problems, Thanks!
 » 16 months ago, # |   +1 So 1s can take nlogn complexity for n<10^5. Can someone help me understand the time complexity and time per test case relation? I missed D just because I thought nlogn wouldn't work fml.
•  » » 16 months ago, # ^ | ← Rev. 3 →   +5 There is a thumb rule stating that it takes roughly $1$ second for $10^8$ operations to get executed. Hence, $10^5$ operations are likely to take $5*10^5*10^{-8}$ second or $0.005$ seconds which is well within $1$ second.Disclaimer: this is a rough estimation. Constants might affect this calculation to a great extent!
•  » » » 16 months ago, # ^ | ← Rev. 2 →   0 that makes me curious, when standard computers get significantly better will time limits also be adjusted for problems?
•  » » » » 16 months ago, # ^ |   0 You can already see that happening in older problems like this. The time your solution takes is multiplied by 2 to justify the change in speed between computers 10 years ago and computers now.
 » 16 months ago, # | ← Rev. 2 →   0 I've solved D using set, it gave me Runtime error on 3rd pretest. Whereas, it passed using Priority queue. (using set) 80128604, (using priority queue) 80135811. Can someone explain the reason, please.
•  » » 16 months ago, # ^ | ← Rev. 2 →   0 I've done D using set if you have any problem you can check my code https://codeforces.com/contest/1353/standings/friends/true#[submission:80159608]
•  » » 16 months ago, # ^ |   0 Iterator p becomes invalid after you erase the first element. Just move that line backwards a bit. 80179242
•  » » » 16 months ago, # ^ |   0 Oh, now it makes sense. Actually it was working perfectly for large inputs on my PC so I never thought about that.Thanks a lot for pointing out the silly mistake.
 » 16 months ago, # |   0 C was interesting but messed up badly
 » 16 months ago, # |   0 Quick Tutorial
 » 16 months ago, # |   0 I think I did not fully get E.I understand that there are $k$ posibilities for positions of on-bulps, and for every such position we need to find the first and the last one of the optimal solution.But I do completly not get how the calculation of the dp[] values work. How do we consider the end of the block of on-bulbs? The editorial text at this point is not really clear.
•  » » 16 months ago, # ^ |   +1 I have a simple solution for E 80161569
•  » » » 16 months ago, # ^ |   +3 What is $dp[i]$ in your code. The min value we can get if first on-bulb is at position i, plus some..values?
•  » » » » 16 months ago, # ^ | ← Rev. 11 →   0 I think of it like $000000001(k - 1 \ lamp \ 0)1(k - 1 \ lamp \ 0)1(k - 1 \ lamp \ 0)1(\leftarrow i)00000000000$$a_i be the state of the lamp i$$sum_{l, r}$ be number of lamp is on at the initial moment in $range[l, r]$, this is just prefix sum.So let $dp_i$ be the minimum move we can make first i lamp satisfy the condition and lamp i is onWe get following formula:$dp_i = min(sum_{1, i - k}, dp_{i - k}) + sum_{i - k + 1, i - 1} + !a_i$Because if it ends at $i$ all lamps from $i + 1 \rightarrow n$ need to be off so the answer is$\min_{i = 0}^{n} dp_i + sum_{i + 1, n}$
•  » » » 16 months ago, # ^ |   +21 very nice solution, it took some time for me to get it,so here I try to make more clear for those who are facing difficulty in understanding it.Please keep on referring the code below to understand better :)we will maintain dp array to get our answer, dp[i] represents cost up to indx 'i' such that the last turned on lamp is 'i'th lamp we can come to indx 'i' from previous indx i.e 'i-k' and can have two states 1. All the lamps upto indx 'i-k' are turned off ( it is nothing but prefix sum upto 'i-k') 2. Last turned on lamp is 'i-k'th lamp ( it would be stored in dp[i-k] ) we will take minimum of the above twothis is not enough we also need to turn of lights between 'i' and 'i-k' so we add (pre[i-1] — pre[i-k] ) to the one we just calculated aboveand at last, we also need to check if the 'i'th lamp is turned on or not so we add (s[i-1] != '1') // note assuming that dp array is 1 based indx and string is 0 basedhence we calculate  dp[i] = min( pre[i-k], dp[i-k] ) + (pre[i-1] - pre[i-k]) + (s[i] != '1'); as we assumed that 'ith' lamp is the last turned on lamp ( we need to turn off the remaining lights ( indx > i) )hence answer at every step would be calculated as :  ans = min( ans, dp[i] + (pre[n]-pre[i]) );  CODE#include using namespace std; signed main(){ int t, n, k, i, j, ans; string s; cin >> t; while( t-- ){ cin >> n >> k; cin >> s; vector pre(n+1,0); // prefix array for( i = 1 ; i <= n ; i++ ) pre[i] = pre[i-1] + (s[i-1]=='1'); // dp[i] = minimum cost up to indx 'i' such that lamp // at index 'i' is last turned on lamp vector dp(n+1,0); ans = pre[n]; for( i = 1 ; i <= n ; i++ ){ if( i-k >= 1 ){ // dp[i] = min( all Turned off upto i-k , last turned on is 'i-k'th lamp ) // + (cost to turn off lamp between i and i-k ) // + ( cost to turn on ith lamp (single) ) dp[i] = min( pre[i-k], dp[i-k] ) + ( pre[i-1]-pre[i-k] ) + (s[i-1] != '1') ; // note : dp array is 1 based indx }else{ dp[i] = pre[i-1] + (s[i-1] != '1'); } ans = min( ans, dp[i] + (pre[n]-pre[i]) ); } cout << ans << endl; } return 0; } 
•  » » » » 16 months ago, # ^ |   +1 Thanks for the explanation. I can now sleep peacefully :)
•  » » » » 16 months ago, # ^ |   +1 Thanks a lot, I didn't come up with an O(N) DP.
 » 16 months ago, # |   +8 Is this fair? @vovuh @MikeMirzayanovKindly ban this user who is using multiple handles and hacking one account using the other account-https://codeforces.com/contest/1353/submission/80148191https://codeforces.com/contest/1353/submission/80124724
•  » » 16 months ago, # ^ |   +5 Well, they are not getting any kind of advantage by doing this. I don't get the reason why some users are doing this.
 » 16 months ago, # |   0 So good contest, thanks
 » 16 months ago, # |   0 Can D be Solved with recursion ? My recursive solution is failing
•  » » 16 months ago, # ^ |   0 I don't think so, it's not about just dividing the array into segments and process them. You have to chose the leftmost maximum segment. Recursion — I think — can't handle this.
•  » » 16 months ago, # ^ |   0 Yes
•  » » » 16 months ago, # ^ |   0 can you explain how you solved it using recursion ! here is my code : int res[MAX] = {0} ; int val = 1 ; void action(int start,int end,int val,int t) { if(start>end) return ; int length = end - start + 1 ; int mid = (start + end)/2 ; db(mid,t); res[mid] = val ; if(length&1) { action(start,mid-1,val+1,t); action(mid+1,end,val+2,t); } else { action(mid+1,end,val+1,t); action(start,mid-1,val+2,t); } } can you point out the mistakes ?
•  » » » » 16 months ago, # ^ | ← Rev. 2 →   0 while making function call i.e in action you cant just select part of previous segment bcz it may case that their exist segment with greater size that is not explored yet . So you need additonal data structure which can help you decide what will be your begining and end for your next call .for example segment which is being explored now have size 7 so you mark the middle element . But after marking middle element you can't just call(be,m-1)or call(m+1,en) . bcz their may be case that their exist segment of size 5 which is not explored yet .
•  » » » » 16 months ago, # ^ |   0 You are trying to solve the subproblem on one segment of the splitting first, and then going to the other segment. But the required solution is for you to solve only one step in either direction. This cannot be done using recursion. You check the outputs of your code for sample cases and you will get a clear picture of what I am saying.
 » 16 months ago, # |   0 I failed to solve D because I used '==' operator instead of using equals method, Amazing :) .
 » 16 months ago, # |   +3 Hi, could anyone explain in problem F, why a certain cell doesn't change its height? How to prove it?
•  » » 16 months ago, # ^ |   +1 Suppose there is any optimal path. Now, look at array of heights in all steps $h_i$. You need somehow make them into array of consecutive numbers, for example: 3,4,5,6,7 or -3,-2,-1,0,1. First, understand that resulting array has values of form: $i+b$ where $i$ is index of value and $b$ some constant. We need to find value of $b$. You can't increase any of $h_i$ so you want such $b$ so $h_i$ >= $i+b$ for each $i$. In other words, it's condition to be able to make from original heights, heights of consecutive numbers. From the other hand, we need to have maximum $b$ among all possibilities to reduce heights as less as possible. Now two points of view: let say you set $b$ to some very big value like 1e18. then for each $i$ you'll have $h_i$ < $i+b$. Lets call those indexes like "bad" indexes. Now, decrease one by one $b$. At some point number of "bad" indexes will decrease. Then, it'll decrease again. Until their number hit zero. Zero number of "bad" indexes means that it's maximum $b$ that we need. Also, it's time when last $h_i$ become equal to $i+b$. As you can see, this index $i$ is our non-changing height. Other view is: rearrange $h_i - i >= b$, now we can make new array $z_i = h_i - i$ and find minimum here. Index of minimum is index of height that won't change.
•  » » » 16 months ago, # ^ |   0 Hi, Can you please help me in understanding why my solution for Problem F is giving WA, I am really not able to find a case for it! https://codeforces.com/contest/1353/submission/80304472
 » 16 months ago, # |   +3 In problem F, why is Now we can notice one important fact: in the optimal answer, the height of some cell remains unchanged true? And how to approach to that result?
•  » » 16 months ago, # ^ |   +43 Imagine that you have a path, on which every cell has been decreased at least once. You can increase each value by 1, which still produces valid path, but gives us better result. Doing that multiple times leads to some cell being unchanged.
 » 16 months ago, # | ← Rev. 2 →   +5 Oof I used segtree instead of prefix sums for E like an idiot :(
 » 16 months ago, # |   0 In C: what is this wrong with this logic? logically we are counting the outer part of the odd squares * distance from the centre, which is (2*i+2*(i-2))*(i-1)/2 i.e adding 1 on both the sides(left and right of the previous odd square ) to get 2*i and remaining part(above and below) becomes 2*(i-2) and the outermost square is at a distance of (i-1)/2 hence the expression (2*i+2*(i-2))*(i-1)/2for(int i=3;i<=n;i+=2)sum+=(2*i+2*(i-2))*(i-1)/2;Example | | | | 0 | | | | "|" this denotes the outermost square which has elements 2*3+2*(n-2)=8
•  » » 16 months ago, # ^ |   +1 We are moving from the center of the square grid, to the outermost square. It is obvious, that on moving towards the bigger square we find that, number of cells for each square we reach is 4*(n-1) where n is an odd number dimension of grid. Now, as we know that how many cells are at a particular distance from center. We simply iterate all odd numbers from 0 to size of grid and multiply each with their distances.for i in range(0,n+1): sum+=4*(i-1)*dist; dist+=1Also, if you look closely you find that after doing a little rearrangement the number of moves, boils down to just finding the sum of squares upto floor(n/2) and multiply result by 8. 80118906
 » 16 months ago, # | ← Rev. 2 →   0 I think priority_queue is more sutible than set for D
•  » » 16 months ago, # ^ | ← Rev. 5 →   0 My code is here 80151427
 » 16 months ago, # |   0 Video Tutorial for C:https://www.youtube.com/watch?v=TEHIuSXOv8o
 » 16 months ago, # | ← Rev. 2 →   0 After reading the tutorial of F, I am still confused.If I got it right, the b(i, j) represents the real height of cell(i, j). So how could a(i, j) < b(i, j) happen? We can only decrease the height, so the real height of cell(i, j) must be less or equal to the initial height. Can anybody explain that to me? Thanks a lot.
•  » » 16 months ago, # ^ |   0 a[i][j] is initial height and b[i][j] is final height.
•  » » » 16 months ago, # ^ |   0 Yes I got it. My thoughts go wrong elsewhere. Thank for your reply.
 » 16 months ago, # | ← Rev. 2 →   0 Problem statements are very clear and even a beginner like me could understand all of them very well, solved ABC.In problem D, I thought I have to come up with a solution that can have $O(t.n)$. Here $t.n = 10^9$ that made me confused as it might give TLE.I also didn't understand: It is guaranteed that the sum of n over all test cases does not exceed $2⋅10^5 \sum n ≤ 2⋅10^5)$.Please teach me, how I should calculate the complexity properly in this kind of problem? Please explain that statement as well. Thank you.
•  » » 16 months ago, # ^ |   +6 It is guaranteed that the sum of n over all test cases does not exceed 2e5. This means that say, u have n=n1 in 1st testcase, n=n2 in 2nd testcase and so on. Then (n1 + n2 + ...... n(t)) will not exceed 2*(10^5). In short you don't need to multiply t with n . You can calculate the complexity using n = 2*(10^5) only.
•  » » » 16 months ago, # ^ |   0 Thank you Aditya_13
 » 16 months ago, # |   0 I have doubt in B sol . what if the 3rd case would be 5 3,9 9 10 10 10,1 2 3 4 5,this??
•  » » 16 months ago, # ^ |   +1 all element of array a will be considered
•  » » 16 months ago, # ^ |   0 In problem B, it saidYour task is to find the maximum possible sum you can obtain in the array a if you can do no more than (i.e. at most) k such moves (swaps).No more than k moves, so you can just do 2 moves in your example
•  » » » 16 months ago, # ^ |   +1 why two moves?? it will reduce the answer, if you will do 0 move answer will be maximum for this case
•  » » » » 16 months ago, # ^ |   0 Yes, 0 move will be the maximum, and 2 moves give the same answer, I just give out an example to show you that you don't need to do exactly k moves
•  » » » 16 months ago, # ^ |   0 when run the exact same code in code chef compiler , the output was 48 but, it should be 39which indicates that there is a problem in solution .
•  » » » » 16 months ago, # ^ |   0 It says at max k moves. It doesn't mean that we have to perform all k swaps. We can choose to use less than k swaps if that gives us the optimum answer.
•  » » » » » 16 months ago, # ^ |   0 But in the test cases the solution should be 39 , or it would reject the solution .
•  » » » » » » 16 months ago, # ^ |   0 Can you explain
•  » » » » » » 16 months ago, # ^ | ← Rev. 2 →   0 What do u mean by it will reject the solution. ? The answer should be 48 only. 39 will give you a Wrong Answer Verdict.
•  » » » » » » » 16 months ago, # ^ |   +1 ok ,thank you got it.
•  » » » » 16 months ago, # ^ |   0 Ans will be 48 only and one more protip prefer using offline compiler like sublime or any other as sometime online platform take too long to compile due to traffic
•  » » » » » 16 months ago, # ^ |   0 Thank you kingkong1. I would prefer taking your advice next time . :-)
 » 16 months ago, # |   +2 how to solve F .i didn't understand second paragraph of F editorial.
 » 16 months ago, # | ← Rev. 2 →   0 Issue solved.
•  » » 16 months ago, # ^ |   0 You can generate some random input and compare result of your solution with of the editorial solution. I am sure you can find a bunch of short counter test cases.
 » 16 months ago, # | ← Rev. 2 →   0 Someone please point out the mistake in my approach for 1353F — Decreasing HeightsFor a fixed value of a[0][0], I can find the min number of operations required to reach a[n — 1][m — 1] (if possible). The approach for this is pretty similar to the one explained in the tutorial. ll solve(vvl &a, vvl &e, int &n, int &m) { ll z; f(i, 0, n) { f(j, 0, m) { if(i == 0 && j == 0) { e[i][j] = 0; continue; } z = i + j; e[i][j] = LLONG_MAX; if(j > 0) { if(a[i][j] >= (a[0][0] + z) && e[i][j - 1] != LLONG_MAX) { e[i][j] = e[i][j - 1] + (a[i][j] - a[0][0] - z); } } if(i > 0) { if(a[i][j] >= (a[0][0] + z) && e[i - 1][j] != LLONG_MAX) { e[i][j] = min(e[i][j], e[i - 1][j] + a[i][j] - a[0][0] - z); } } } } return e[n - 1][m - 1]; } Now, I try fixing different values for a[0][0] (<= a[0][0]), and the maximum value of a[0][0] for which we are able to reach a[n — 1][m — 1] is optimal value of a[0][0]. For this, I used binary search.Also the minimum value of a[0][0] for which we'll definitely get an answer is somewhere close to -1 * (n + m). ll st = -300, en = a[0][0], z = a[0][0], ans = 1e18; while(st < en) { ll mid = ((st + en + 1) / 2); a[0][0] = mid; ll y = solve(a, e, n, m); if(y != LLONG_MAX) { st = mid; ll temp = y + (z - mid); ans = min(ans, temp); } else { en = mid - 1; } } 
•  » » 16 months ago, # ^ | ← Rev. 2 →   +6 I don't think the maximum value of a[0][0] for which we can reach a[n — 1][m — 1] is always the optimal value of a[0][0]. Consider this case:3 3 5 5 6 9 9 7 9 9 9The answer is 2, but if you use the maximum value of a[0][0], which is 5, you'll need more than 2 steps.
•  » » » 16 months ago, # ^ |   0 Now, I try fixing different values for a[0][0] (<= a[0][0]), and the maximum value of a[0][0] for which we are able to reach a[n — 1][m — 1] is optimal value of a[0][0]. For this, I used binary search.What I meant was, the max value of a[0][0] has to be less than or equal to the original value of a[0][0].Here the max value of a[0][0] for which we are able to reach a[n — 1][m — 1] is '1', and hence answer = 4.
•  » » » » 16 months ago, # ^ |   0 I'm sorry, added a different test case now.
•  » » » » » 16 months ago, # ^ |   0 Got it, thanks.
•  » » » » 16 months ago, # ^ |   0 Let M be a very large numberTry this case:2 24 M4 6You can reach the last cell while keeping a[0][0] = 4 and by decreasing M to 5 thus incurring cost M — 5.Whereas the optimal solution is to reduce a[0][0] and a[1][1] by 1 each incurring total cost 2.
 » 16 months ago, # |   +1 OMG! A was that easy! xD I did it in a very bad way :( my one-> 80090151
 » 16 months ago, # | ← Rev. 2 →   0 I have query about problem D, if n is odd the problem have O(n) solution so is there any ways to do same when n is even??
•  » » 16 months ago, # ^ |   0 I don't think so but even if it existed it will be easier to submit O(nlogn) solution as it would be quite difficult to observe
 » 16 months ago, # |   0 Anyone solved E recursively ? Please reply with your submission. I'm having trouble understanding the editorial and iterative code.
•  » » 16 months ago, # ^ |   +1 Here you go.
 » 16 months ago, # |   0 I have solved D using priority queue. When I am running my code for T=1 and n=10000, it is taking long time to execute. But I submitted the solution and it got accepted. In question n<=2*10^5. Then why it is not showing TLE during submission. My submission 80166026
•  » » 16 months ago, # ^ |   0 Now don't say you were using online compiler as it was the queue time of online compiler
•  » » » 16 months ago, # ^ |   0 No I am not using online compiler.
 » 16 months ago, # | ← Rev. 4 →   0 For problem D// set element is pair>define pi pair bool cmp(pair a, pair b) { if(a.first != b.first) return a.first < b.first ; else return a.second.first < b.second.firstd ; } I use this type of function while sorting a vector using sort(). But it is not working for set declaration. Do I always need to make a structure as shown in editorial or am I doing some error? Please help.
•  » » 16 months ago, # ^ |   +1 You either define struct with implemented operator, or use hacks based on fact how pairs compared under hood (lexicographically), or you need to define class or struct implementing operator () like this: struct cmp { bool operator() (pair a, pair b) {... comparator code ...} }; // then your set will be: set, cmp> my_set; 
•  » » » 16 months ago, # ^ |   0 Thanks!
•  » » 16 months ago, # ^ |   0 oh, I didn't check what is in editorial. Here is what I thought is there, this is from my code: struct seg { int l, r; seg (int l = 0, int r = 0) : l(l), r(r) {} bool operator < (const seg &s) const { int a = r - l; int b = s.r - s.l; if (a != b) return a > b; return l < s.l; } }; set segs; // usage. 
 » 16 months ago, # |   +3 For problem D: If anyone like me hates to make a custom comparator, then just keep values in your vector or pair in the order in which you want it to be sorted. For example, here length is more important than start index, so make it the first value of the vector. In case of a tie we need to check on the basis of start index, so make it the second value. But, since we want it to be on the basis of the min index. So, if we were using max priority queue, then this value should be negative(to reverse the effect).Code: 80167424
•  » » 16 months ago, # ^ |   0 Just make the length negative, that's solved !!!!!. so initially make s.insert({-n,{1,n}}); Btw i also hate comparator function its a waste of time
•  » » 16 months ago, # ^ |   0 Thanks!!!
 » 16 months ago, # |   0 i didn't get problem C! !
•  » » 16 months ago, # ^ |   0 You are asked to count the minimum steps to bring everything on one point. Initially every block on board has one element. Your task to arrive at solution was to bring everything at center.
•  » » 16 months ago, # ^ |   0 Here's an approach
 » 16 months ago, # | ← Rev. 2 →   0 Good
 » 16 months ago, # |   0 The queue is so fast today. Thank you.
 » 16 months ago, # |   0 Hello guys,I tried a different DP for Problem E. For each period from 1 to k, I stored the value of last and the first appearance of 1 in the string in an array for each period and stored the total number of ones in 'sum'. Then iterating for a period, as all periodic position between 'first[i%k]' and 'last[i%k]' has to be either one or zero,I chose a minimum value as 'ans' and added the leftover ones in the array in the 'ans'. Still I am getting WA in test 2.Solution Link : https://codeforces.com/contest/1353/submission/80167997Please help
 » 16 months ago, # | ← Rev. 2 →   +5 I wan't to share my solution for 1353F - Decreasing Heights. Because I think it's simple.First, consider we have optimal path. Let's look at its array of initial heights $h_i$ in order of visit. Resulting heights should be $i+b$ for some constant $b$. And answer is $\sum (h_i - (i+b))$ We know that $i$ is also number of step. Notice that any path from cell $(0,0)$ to cell $i,j$ require $(i+j)$ steps. So, any cell $(i, j)$ can be only at index $i+j$ in array $h$. This means from this height will be subtracted $i+j+b$ where $b$ is constant that we don't know. Now, let $c_{ij} = a_{ij} - (i + j)$. Consider array $d_i$ to be values of $c_{ij}$ that we travel across optimal path in order of visit. Then answer is $\sum (h_i - (i + b)) = \sum (h_i - i - b) = \sum (d_i - b)$ because $d_i$ is exactly height without index of step. The sum has exactly (n+m-1) elements (cells required to travel). So answer is $(\sum d_i) - (n+m-1)\cdot b$. This means, for known b we only need to find path with minimum sum.Now, what is $b$? It is the minimum value across the path. Why? Well, you may look here: https://codeforces.com/blog/entry/77373?#comment-622300 Probably it will help. I'll just add. Value $b$ can be used if for each $h_i >= i + b$ rearrange $h_i - i >= b$ and we have $d_i >= b$ so $b$ should be less or equal than all of values in $c_{ij}$ across the path. Also, we want it to be maximum. Thus, it's just minimum among all $c_{ij}$ across the path.The only issue left: for different paths there is different minumum. Solution: fix minimum to be $b$ and then find minimum path with all cells in the path greater than $b$. Change $b$, find minimum path again.My implementation: make array $c_{ij}$, now find minimum path using dp. Remember answer. Because we know answer, we also know minimum along all table. now, ban all cells with value equal to current minimum. This will forbid any path having current minimum cells. Find minimum path again. Also, find minimum among allowed cells. Update answer. Ban cells with current minimum again. And so on. Repeat this cycle until no valid path left.This works in $O(n^4)$ Source: 80165280
•  » » 16 months ago, # ^ |   +1 Here is cleaned source. 80174342. In previous source dp was filled diagonally (I'm retarded). And, there was check for int64 overflow.
 » 16 months ago, # | ← Rev. 2 →   +3 I managed to find a DP Solution for Problem C . To compute a particular solution for $n$ , I recursively calculated the solution for $(n - 2)$, which is like emptying out the inside of the board and keeping only a border of figures around the square of dimensions $(n - 2)\times(n - 2)$.PictureThen , with simple mathematics , it can be shown that , this border of symbols can be converged to the center in $2\cdot(n - 1)^2$ moves . Thus, the solution becomes : $solve(n) = solve(n - 2) + 2\cdot(n - 1)^2$ for $n > 1$.
 » 16 months ago, # |   +1 A smaller solution for problem E. https://codeforces.com/contest/1353/submission/80167362
•  » » 16 months ago, # ^ |   +3 I have doubt, can you help? I tried an approach that is similar to yours, but in my case, the time complexity is O(N * N / K) which will give TLE. But you have done it in O(K * N / K) => O(N). But, with what I am thinking, we need to consider each index as start and then take jumps of k. How does your code check other cases with considering only K indices as start?My TLE approach: 80175775
•  » » » 16 months ago, # ^ |   +1 Explanation to my solution: Basically what we need in the string is, for every consecutive 1 in the string, the distance has to be equal to k. Now consider all the characters that have their index modulo k as equal (i%k) because we wanna make string k palindromic. For example if we have string as 10100 and k=2 then we can see that for indices i=0,2,4, i%k==0 and for indices i=1,3, i%k=1. So we have to only evaluate for two cases in the mentioned case in the first for loop that is running from 0 to 1(0 for calculation of 0,2,4 part and 1 for 1,3 part). Generalizing this will be running a for loop with variable i between 0 to k-1 inclusive. Now for every i we will see into the sequence by running a for loop with variable j from i, incrementing j with k and limiting j less than n(in above case if i=0 then we will look into 0,2,4 indices and if i=1 then we will look into 1,3 indices). Now comes the logic part. Remember we have choice of changing state of any bulb. So firstly for every j, we will see that if changing it's state is worth doing or not. Consider the following example, n=11,k=2 and string is 00010001000 then we don't need to turn on the bulbs at indices 1,9(because what we want is just k length gap between consecutive 1s). We will just turn on the bulb at index 5 and we are done with one move. Consider another example, n=11,k=2 and string is 01000001010. In this case, rather turning on bulbs at indices 3,5; we can just turn off the bulb at index 1 to minimize number of moves. These examples show that the method of counting 1s and 0s in every kth character and subtracting total ones in the "sequence" from number of ones in the "string" and then adding number of zeros in the "sequence" to that will not work.That's why we can have a variable d which will display if we have s[j]=='1', is it worth to let it remain to '1' or is it worth to make it '0' and similarly for s[j]=='0'. That's why when we have s[j]=='1' then we will just increment d assuming that it will remain '1'. But when we encounter '0', we make d as max(0,d-1); because if we had encountered one '1' or zero '1' then changing that previous to zero will cost us 1 or zero move respectively, but if we had encountered more than one '1's then changing the current '0' to '1' is worth doing. We will save this d in co for every position in the "sequence"(talking about loop on j) we visit and we will try to maximize this co because you can say that d is the number of free '1's you are getting overall and we will maximize these free '1's. For every "sequence" (talking about loop on i) we will try to minimize m which is the number of total '1's in the "string" minus total free '1's in the sequence you are hoping to become k palindromic. the sequence which will have minimum m will be candidate to the answer but we are only asked to write total moves which are m.I hope this will help.
•  » » » » 16 months ago, # ^ |   0 Thanks for the detailed explanation. Got it now.
•  » » » » 16 months ago, # ^ |   0 Great explanation.Thanks!!
 » 16 months ago, # |   0 https://youtu.be/DtWXAHIN2ys Solutions and Discussion.
 » 16 months ago, # |   0 Anyone can help to understand how problem C can be solved using this formula ..sum of squares of all integers from 1 to n−1 / 2. Thanks
 » 16 months ago, # | ← Rev. 2 →   -8 In problem F, I had used binary search in range(-201 to a1,1) to find the optimal height of (1,1) position.But it didn't work. Can anyone explain why binary search property failed here?
•  » » 16 months ago, # ^ |   0 Try this case — https://codeforces.com/blog/entry/77373?#comment-622460
•  » » » 16 months ago, # ^ |   0 Got it.Thanks prashiksahare110044 for your kind help.
•  » » » 16 months ago, # ^ |   0 Hi, can you help me in telling whats giving WA for my code, I really can't get it for Problem F https://codeforces.com/contest/1353/submission/80304472
 » 16 months ago, # | ← Rev. 2 →   0 Please someone tell me the mistake in my approach for E my submissionApproach for every possible series with period k I am building up a dp[i][j] where i is the state 0(lamp off) or 1(lamp on) for jth lamp. for every series the table value only contains the count of moves applied from the first 1 in that series to the last 1. 3.to get minimum number of moves = min(#moves to turn on series i + #moves to turn off every other series) for every series.
•  » » 16 months ago, # ^ | ← Rev. 3 →   0 At same test case my submission was going wrong and I had almost similar approach. Probably to get minimum number of moves, you had to check whether turning that bulb on in the series is worthy or not. For example, lets say we have n=11,k=2 and sequence is 01000001010. Here, bulbs at index(0-indexed) 1,7,9 are turned on. Now if we turn on the bulbs at index 3,5 then it is gonna cost us two moves. But if we turn off the bulb at index 1 then it will only cost 1 move. I think that's where this solution of yours might go wrong. You can look at this. https://codeforces.com/contest/1353/submission/80167362
•  » » » 16 months ago, # ^ |   +3 Can you explain the reasoning behind your code calculating max(co,d) at every index and min(m,c-co) for every series? Please I am not able to understand it.
•  » » » » 16 months ago, # ^ |   0 This might help. https://codeforces.com/blog/entry/77373?#comment-622489
•  » » » » » 16 months ago, # ^ |   +3 Thanks! Your explanation was really thorough and it helped greatly.
 » 16 months ago, # |   +5 Is there an O(N*M*(N+M)) solution for problem F? I was unable to find one, but luckily the O(N^2 * M^2) solution worked just fine for me.
•  » » 16 months ago, # ^ | ← Rev. 2 →   -16 I don't know slope trick well hence I might be wrong, but the question seems similar with dp, but if it is applicable here it is solvable in nmlog(n+m)
 » 16 months ago, # | ← Rev. 3 →   0 Is D solvable using segtree(by substituting 0 with 1 and updating each element with negative infinite values) ,have anyone done D in this way.question gets converted to max subarray sum with leftmost boundary. Update:: my submission using segment tree using priority queue without custom comparator
 » 16 months ago, # |   0 For problem F editorial, "in the optimal answer, the height of some cell remains unchanged". What is the proof of that?
•  » » 16 months ago, # ^ |   +15 Imagine if all cells were changed, and the minimum number of changes applied to a cell was $x$. Then you could have done $x$ fewer changes on each cell and not affected any of the paths. It follows that in the optimal solution, $x$ must be $0$, and thus at least one cell must be unchanged.
•  » » » 16 months ago, # ^ |   +3 Thanks a lot!
•  » » » 16 months ago, # ^ |   0 Hi, Can you help me in getting whats going wrong in my approach, I am unable to get a testcase for which my approach is giving Wrong Answer in Problem F. Here is my code link: https://codeforces.com/contest/1353/submission/80304472
•  » » 16 months ago, # ^ | ← Rev. 3 →   +19 Check out this picture for some intuitions.Basically if none of the positions on the final path have unchanged heights. We can shift up the final heights therefore getting a lower total cost.
•  » » » 16 months ago, # ^ |   0 Wow! Thanks
•  » » 16 months ago, # ^ |   +3 Let's say there is a path in which we have decreased every element value. Let "x" be the minimum amount of decrease in any value on the path. We can increase every element on the path by "x" and still the path will remain valid. But notice that we have just made the element which had least amount of decrease to be same as it's original value.
 » 16 months ago, # |   0 Well commented and clean code for E Submission — 80186993
 » 16 months ago, # |   0 Thanks vovuh for the amazing and fast editorial (like always :) )
 » 16 months ago, # | ← Rev. 2 →   0 https://codeforces.com/contest/1353/submission/80187990using heap for D problem, gives TLE in python, any tips? (code is working for all sample cases)using (length of subarray, [left index, right index]) in queue
•  » » 16 months ago, # ^ |   +1 Try to submit your code in Pypy3 it will probably work.
•  » » 16 months ago, # ^ |   0 https://codeforces.com/contest/1353/submission/80135152. my solution got accpted
 » 16 months ago, # |   0 Was this contest unrated? My rating is still not updated
•  » » 16 months ago, # ^ |   0 Hacking phase is still open
 » 16 months ago, # |   +9 How about this approach for E: I made a 2-D dp as dp[N][2] where if dp[i][j] represents minimum number of moves to make [1....i] k-periodic and the last character as j. Now dp[i][0] can be minimum of dp[i-1][0] and dp[i-1][1] plus state of ith character. Now, when we want to put 1, if (i=k), we have 2 options: if this the 1st one till now we will do as in previous case, and if it is not the 1st one, dp[i][1]=state of ith character + dp[i-k][1] + number of ones between [i-k+1......i-1]. In the end, we can do min(dp[n][0],dp[n][1]).Solution Link:80187295
•  » » 16 months ago, # ^ |   0 Hey, I have tried a similar approach but its giving WA, can you please look into it 80174010
 » 16 months ago, # |   0 Great Editorial.
 » 16 months ago, # |   0 Please tell me what is wrong with this code?(E) https://codeforces.com/contest/1353/submission/80154768
 » 16 months ago, # |   0 problem E: if you know regex, idea is make a automata like 0*1+0+, state count is 3, trans is simple. use state stand for mod k index. finally, answer is find 1 state is 0*1+0+ or 0*1+, and k — 1 state is 0*.
 » 16 months ago, # | ← Rev. 2 →   0 I have a doubt in Problem B .The solution given in the tutorial is O(nlogn). If we use buckets, can we do it in O(n). Basically,Take input array A(in a bucket array of size 30) — O(n)Take input array B(same as above) — O(n)While loop, two iterators, for the bucket arrays, — O(c*n)Total = O(n) Is this correct?EDIT- Here's is a link to my submission, you can check to see how to do away with sorting by using "bucket array" LINK
•  » » 16 months ago, # ^ |   0 Not sure what a "bucket" does, but somehow it has to sort the elements. Which is the logn factor.
•  » » » 16 months ago, # ^ |   0 I've updated the comment with link. You can have a look to see what I mean by "bucket".Basically, since the elements are in the range [1,30]. I have an array of 30 elements, all initialized to 0. When taking input in some variable x, you do the follwing — arr[x]++;You can check the submission for the whole solution. I think its O(n).
•  » » » » 16 months ago, # ^ |   0 You are right. Using the fact that not only the size of the array but also the values are limited to $n$ you get along without sorting.
•  » » 16 months ago, # ^ |   0 Yes, the range of elements was small, so we can do that.
 » 16 months ago, # |   -8 For problem D, one can also avoid the comparator function (if one feels uncomfortable using it) by modifying the set a bit: set< pair > > s; We can insert values as follows: s.insert({-length, {left, right}}); The negative value of length makes sure that the maximum element is at the beginning.
•  » » 16 months ago, # ^ |   0 https://codeforces.com/blog/entry/77373?#comment-622307 Also, I don't feel the need of using a pair >, we can just use a vector.
 » 16 months ago, # |   0 Please can someone elaborate the tutorial for Problem F.
 » 16 months ago, # |   0 Can anyone pls explain the intuition or proof behind the last line os solution of F. The line is -" Now we can notice one important fact: in the optimal answer, the height of some cell remains unchanged."
•  » » 16 months ago, # ^ |   0 https://codeforces.com/blog/entry/77373?#comment-622484(Also, the comment below mine has a nice image)
•  » » » 16 months ago, # ^ |   0 Hey, Thanks....Idk why I missed it
 » 16 months ago, # |   0 In problem E, C++ in-built function count which has linear complexity and we run for loop for k times. So shouldn't it be O(n*k) time complexity? It's mentioned as O(n) in the editorial. Could anyone explain?
•  » » 16 months ago, # ^ |   0 Well, I think prefix array can also be used(instead of count) to serve the purpose which will eventually lead to O(n) complexity. If we are using count, we are increasing complexity to O(nk). Thanks!
 » 16 months ago, # | ← Rev. 2 →   0 Can anyone help me with E? This is my submission 80196393I'm getting WA on 71st test case on test 2.P.S. Spent a lot of time debugging it.
•  » » 16 months ago, # ^ |   0 Got it, my approach was actually incorrect.
 » 16 months ago, # |   +3 An easier solution for E(at least more understandable)- let our answer be number of ones in the string(because "0000...000" is also acceptable)Now let say ith position has 1 in resultant string then we will calculate left cost and right cost which means the cost because of left substring(1, i-1) and right substring(i+1,n).LEFT COST ---LEFT_COST[I]=min(cost of having all element in left to zero, LEFT_COST[i-k]+number of ones in substring(i-k+1,i-1))+(s[i]=='0') number of ones in substring(i-k+1,i-1) is added because u don't want any one between i-k to i as it will decrease the period to lees than k. and first term and the window term can be calculated easily by prefix function.Similarly RIGHT COST ---RIGHT_COST[I]=min(cost of having all element in RIGHT to zero, RIGHT_COST[i+k]+number of ones in substring(i+1,i+k-1))+(s[i]=='0')Now the total cost of having s[i]=='1' in the resultant string is COST[i]= s[0]=='1'?(LEFT_COST[i]+RIGHT_COST[i]):(LEFT_COST[i]+RIGHT_COST[i]-1); try to find out why that -1 is in above termnow traverse from i=1 to n and update answer as min(answer, COST[i])
 » 16 months ago, # | ← Rev. 2 →   0 Can someone explain me how did he come up with the formula of dpi[p] in the problem of kth-periodic garland(Prob 1353E)??
•  » » 16 months ago, # ^ |   0
 » 16 months ago, # |   0 when ratings will be updated??
 » 16 months ago, # |   0 Hi all, why is the time complexity of D nlogn? Is sorting always logn?Also, I'm a beginner and I'm not sure why this code is getting TLE. Am I doing something differently from the editorial? 80201800Thank you for your help :)
•  » » 16 months ago, # ^ |   +1 Good sorting techniques are O(nlogn). There's no sorting technique with a complexity of O(logn).You sort all the numbers for every iteration of the for loop so your complexity turns out to be O(n*nlogn).Use heaps to do what you intend to do. Sorting for every iteration will time out here.
•  » » » 16 months ago, # ^ |   0 hi, thanks for the speedy reply. Appreciate it very much. Will look into heaps now, :)
 » 16 months ago, # |   0 Another solution for C part[submission:80129435]
 » 16 months ago, # |   0
 » 16 months ago, # | ← Rev. 2 →   0 1353B - Two Arrays And Swaps can be solved by sorting array B and inserting the last K elements to array A. Then we sort array A and find the sum of last N elements. Time complexity will be O(NlogN).
 » 16 months ago, # |   0 The tag for Problem F also contains "$dfs$ $and$ $similar$". Does anyone know the approach?
 » 16 months ago, # |   0 I have solved 1 problem(A), yet my rating is decreased. Would someone please tell me the reason?
•  » » 16 months ago, # ^ | ← Rev. 2 →   0 As a new user your rating is initially 1500. This is a completly arbitrary value, so it takes some contests until your rating is on a more realistic level. Solving one problem in a Div3 contest is seen from a rating perspective some hundred points below 1500.
•  » » » 16 months ago, # ^ |   0 Ohh, I got that bro. So if I solve Div2A then what will happen?Shall i touch the rating of 1500? Thanks for your reply
•  » » » » 16 months ago, # ^ |   0 The calculation of ratings is based on ranking in contests. The changes in ratings of people sum up to zero.
•  » » » » » 16 months ago, # ^ |   0 thanks
•  » » » » » » 16 months ago, # ^ |   0 So... did it went well?
•  » » » » » » » 16 months ago, # ^ |   0 I am now understanding the system first. will participate in contest bit latter.Actually I am a clear newbie. What is meant by rated problem?whereas every problem have a rating..
•  » » » » » » » » 16 months ago, # ^ |   0 The problems in the problemset have a "rating", too. It is an indicator of the difficulty of the problem. But this problem rating has nothing to do with contests, it is just usefull while practice.
•  » » » » » » » » » 16 months ago, # ^ |   0 I would be glad if could make result like you in contests. Will you please help me grow guiding me in the way that you have followed?
•  » » » » » » » » » 16 months ago, # ^ |   0 Just practice, there is no silver bullet.
•  » » » » » » » » » 16 months ago, # ^ |   0 your progress looks stable. You have never dropped as much as me :)
 » 16 months ago, # |   -9 Is there something wrong with the time complexity in D part.n=order of 10^5we are able to solve in nlognand test cases=order 10^4But time limit is 1 sec which only supports 10^8... so why is the solution not giving tle ?
•  » » 16 months ago, # ^ | ← Rev. 2 →   +1 "It is guaranteed that the sum of n over all test cases does not exceed $2 \cdot 10^5$ ($\sum n \le 2 \cdot 10^5$)"
 » 16 months ago, # |   +1 class cmp { public: bool operator()(const pair> &p1,const pair> &p2) const { if(p1.first==p2.first) { if(p1.second.first==p2.second.first) { return p1.second.secondp2.first; } }; I used this comparator function for set>,cmp>, it works perfectly fine. But when I used this for priority_queue>,vector>>,cmp>,it is not working. Can anyone please tell why this comparator function is not working for priority_queue?
•  » » 16 months ago, # ^ | ← Rev. 2 →   0 A priority_queue works with biggest element as next, ie it returns what set.rbegin() returns. Just a guess.
 » 16 months ago, # |   0 for problem F, I also had same solution but I was stumbled on the proof of optimal situation, can anyone help me to prove that if we change all values, how it can not be optimal answer?
 » 16 months ago, # |   0 vovuh Someone please explain clearly the tutorial for problem F — Decreasing Heights
 » 16 months ago, # |   0 My code is getting TLE in D but I think my code is n*logn, am I missing something here? I created a vector of l, r and number of zeros and I sort it according to the logic, delete the first element and push break-up parts #include #include #include #define ll long long #define loop(i,a,b) for(int i=a;ia.zeros){ return false; } if(b.zeros==a.zeros){ return b.l>a.l; } return true; } void solve(){ int n; //cin>>n; cin>>n; vector v; vector ans(n); seg f={1,n,n}; v.pb(f); int cnt=n; int i=1; while(cnt--){ int left=v[0].l; int right=v[0].r; int mid=(v[0].l+v[0].r)/2; //this is the index; ans[mid-1]=i; i++; //v[0]={left,mid-1,mid-left}; v.erase(v.begin()); seg gh={left,mid-1,mid-left}; seg g={mid+1,right,right-mid}; v.eb(g); v.eb(gh); sort(v.begin(),v.end(),cmp); } for(int i=0;i>t; while(t--){ solve(); } return 0; } 
•  » » 16 months ago, # ^ |   +1 Bro, your TC is O(NlogN * N) because you are sorting vector at every point. Use a data structure like set(ordered) or priority queue which performs insertion and deletion in logN.
•  » » » 16 months ago, # ^ |   0 Thanks bro
 » 16 months ago, # |   0 can anyone plz tell me what is wrong with my solution for E https://codeforces.com/contest/1353/submission/80215731
•  » » 16 months ago, # ^ |   0 How this code is supposed to work?
•  » » » 16 months ago, # ^ |   0 initially ans is all the 1's then in the while loop we will count all the zeroes that are between two ones that is for example in this case 9 2 010001010 in first loop there we will encounter with 0,0,0,0,0 and in second 1,0,1,1 so in first there are 0 no. of zeroes that we need to switch on where as in 2 there is only 1
•  » » » » 16 months ago, # ^ |   0 I do not see how you handle the case where you in example switch the first 1 to 0, and some other 0 to 1.
•  » » »