### netman's blog

By netman, history, 6 years ago, translation, Code
Code
Code
Code
C++ code
Java code Tutorial of Codeforces Round #390 (Div. 2)  Comments (42)
 » Auto comment: topic has been translated by netman (original revision, translated revision, compare)
 » The fastest editorial in 2017
 » Another solution of problem D. We use sweep line with events {segment_start, segment_end}. When segment starts we increase arr[pos_l]++, and when segment ends we decrease arr[pos_l]--. To find the answer, we need to check the k-th left-started segment in our array, each time for every event. If we are in pos and have segments_cnt >= k, we know that each of them has end-point >= pos, so our goal is to find k longest segments and answer is pos — po_l[k-th segment]+1. To implement arr[] we can use sparse segment tree. Code Complexity is O(NlogN + Nlog109) PS. Is it right complexity in editorial? Should it be O(NlogN + NlogR)?
•  » » Solution in editorial has such complexity, because I sort events in every iteration of binary search. I know how to improve complexity, but it's not so important :)
•  » » 6 years ago, # ^ | ← Rev. 3 →   better solution for D, which is too simpler and also much more straight to code. We know the period we want is min(ri)-max(li) between all of k periods we chose. So I sort all of the periods as {li,ri} and just for li I want k-1 periods before it which the min(ri) of them should be maximal possible. I have a set in which I keep k-1 maximum ri of previous periods. And the ans is for any i(1first ) — l[i].firs + 1); Complexity is O(NlogN) 23597706 thank you netman.
•  » » » Nice :)) the best solution !
•  » » » Can u elaborate on how are you going to save indexes of coupons after every iteration.
•  » » » » As I coded, I apply the algorithm twice. At the first one, I save the maximum intersection and then at the second one, when the answer is equal to the maximum I output the i(we are at it, now) and the elements in the set.
•  » » » » » Wow,That was simple. I was trying to update the ans in one pass and that was giving TLE. Thanks for the answer. Good solution
•  » » » It is amazing. Thank you
•  » » Can you elaborate your approach using seg. tree? I am unabble to get it.
 » Could you explain more about binary_search in D ?
 » thanks for realy good problems
 » 6 years ago, # | ← Rev. 5 →   wrong solution!
•  » » How do you handle the wildcard character in the KMP algorithm?
•  » » 6 years ago, # ^ | ← Rev. 2 →   Can you explain it please, because I don't think you can do this with just a KMP. PS: Obviously one can solve the problem in O(n2 * C) where C is the cost of solving the 1D version of the problem. So it's enough if you tell your solution for the 1D problem.
•  » » » so do you find the answer!? or I explain it?!
•  » » » » Please explain it, or provide a submission of an implementation code of it. :)
•  » » » » » 6 years ago, # ^ | ← Rev. 5 →   wrong solution!!!
•  » » » » » » Much clearer, please :(
•  » » » » » » » 6 years ago, # ^ | ← Rev. 2 →   wrong solution!
•  » » » » » » What is KMP for strings with '?' ?
•  » » » » » » » 6 years ago, # ^ | ← Rev. 3 →   Oh, I make a mistake about the statement....!!! sorry every one! thank you Um_nik
 » Loved the first problem, had to think a bit out of the box.
 » I don't wanna be a hater, but at problem A, by "dividing" I understood that the array should be divided in 2 or more arrays. "1.Array sum is not zero. In this case we can divide array into one subarray A[1... n]." That's not called dividing, because you are left with one single array. If I'm wrong, please correct me. Thanks for reading this and I hope I didn't waste your time.
•  » » Yes, you are wrong. As the problem statement point the dividing all of array into one array is correct.
•  » » Read problem description carefully.
 » 6 years ago, # | ← Rev. 2 →   I had some trouble debugging my implementation of Div2E editorial's solution, so I'll give some hints. If you build a straightforward Gz, i, j representation of Ti, j using std::bitset, shifting is reversed! This means that shift(Gz, x, y) should be implemented with b>>y instead of b<>y is not enough. Use (b<<(m-y))|(b>>y) instead. Pattern might be larger than text, so don't forget to take y modulo m. My implementation: 23653130
 » How would one go about solving D if the question was the union of all of the segments instead of the intersection?
•  » » I think a bit about it!!! And I don't think it can be solved better than O(nk). Anyone else have an idea?!
•  » » » 6 years ago, # ^ | ← Rev. 2 →   Can you share your method? The best I could think of its an O(kn^2) solution.
•  » » » » Sure! First, we sort segments and remove the segments that are inside another segments. We can simply prove they are useless. Now if li > lj then ri > rj. We arrange the segments with their li. Define dp[i][j] equal to the maximum union of j segments from 1 to ith! We consider two condition for ith segment to fill dp[i][j]: If the previous picked segment have any share range with this, then we choose the leftmost segment that have share range with this as k and simply dp[i][j] = dp[k][j-1]+(ri-li+1)-(rk-li+1). and If not we can update dp[i][j] from maximum of dp[k][j-1](k from 1 to k-1) and then dp[i][j] = mx[k-1][j-1]+(ri-li+1). Am I wrong?!
•  » » » » » 6 years ago, # ^ | ← Rev. 4 →   Ah, I missed out the dp transit optimization part, that's a neat observation.Could persistent data structure help improve the algorithm? The dp transition is always going to be shift one step to the right and add the same variable if a segment is "profitable".
•  » » » » » » 6 years ago, # ^ | ← Rev. 2 →   To be honest, I don't know about persistent data structure well! As I was thinking about it, actually, the updating is good enough to be much more optimizer! I will think about it tonight and I'll share the result(if I have any results)!
•  » » » » » » » Now I think more about it I don't think persistent data structure is a feasible data structure, as there is no way to update the next state merely from the latest state. As we have to update from both the just overlapping position and the just not overlapping position it is very hard to maintain the data structure that supports update function at every version.
 » Another greedy solution for D code.
 » 6 years ago, # | ← Rev. 2 →   My O(nlog(n)) solution using Sort and Heap for problem D (div2). 23736804 Algorithm: 0 Keep tree vars: max for intersection length, l, r for final left and right bounds, go 1 1 Sort segments by their left borders, go to 2 2 Keep Min Heap of size k to store right bounds. go to 3 3 Traversing the segments, if the heap's size is less than k just add the segment's right bound to it, then go to 3. Else go to 4 4 Compare current segment's right bound with heap's peek, then go to 5 5 If it is greater than peek, then just remove peek of the heap and add the current segment's right bound to the heap, then go to 6. Else go to 7. 6 Calculate count of goods by taking difference of heap.peek()-cur.left+1. Update max, l, r and go to 7. 7 Repeat 3 - 6 until we pass all the segments, then go to 8. 8 If heap size is equals to k, then go 9, else go 10 9 Calculate count of goods by taking difference of heap.peek()-cur.left+1.Update max, l, r and go to 10 10 List k segments that contains segments [l,r] To sum up sorting takes O(nlog(n)) traversing with heap operations also O(nlog(n)). Total time complexity is also O(nlog(n)).
 » Problem E tags contains "fft". Could someone give me a hint about that approach?
•  » »
•  » » » Thanks, it helped me a lot
 » 5 years ago, # | ← Rev. 5 →   Never mind. Solved it ;)
 » 4 years ago, # | ← Rev. 3 →   "Array sum is zero. But we know that array has non-zero elements. Then there is exists such prefix A[1... p], which sum is s and s ≠ 0. If sum of array is zero and sum of prefix is s, then sum of remaining suffix is equals to 0 - s =  - s ( - s ≠ 0). Therefore array can be divided into two parts A[1... p] and A[p + 1... n]."Can anyone explain me above these lines more easy way? What is actually meant by prefix A[1...p]? What is meant by remaining suffix? I am at beginner level in programming. It will be more helpful if anybody attach important resources on prefix and suffix of array.