### BledDest's blog

By BledDest, history, 2 years ago, ,  Tutorial of Educational Codeforces Round 27 Comments (36)
 » Can someone explain to me the solution for C mentionned above? I didn't quite get it..
•  » » 2 years ago, # ^ | ← Rev. 2 →   MY APPROACH: (Intuitive) Here we are simply sorting the start timing and end timing separately. We will maintain a count which indicates the number of TV shows we are watching at a particular moment simultaneously on both the TV's. Now, just like merge procedure of merge sort, we will maintain two counters for start timing array and end timing array separately. Now just see, if start[startCtr] <= end[endCtr] , it means we started watching one more TV show at a particular timing. So, we increment startCtr and increment the count by 1. If start[startCtr] > end[endCtr], it means we just finished watching one TV show, so we increment endCtr and decrement count by 1. At any moment, if count goes above 2, we will output "NO", because we only have 2 TV's to watch the shows.Refer my solution. http://codeforces.com/contest/845/submission/29665809 Hope it helps!
•  » » 2 years ago, # ^ | ← Rev. 2 →   The Sweep Line Algorithm is used here. It is a common algorithm. The idea is to sweep a vertical "line" left to right and analyze the event points in chronological order. In this case, event points are left and right edges of each segment.You may want to read this article for more.
 » Can someone please elucidate the solution for G ?
•  » » A very similar problem (with a more detailed editorial) can be found here XOR_Cycle
 » 2 years ago, # | ← Rev. 2 →   Where are the author's solutions??They should be there.Also the time complexity of all the problems is not mentioned.
 » 2 years ago, # | ← Rev. 2 →   for C problem, what's wrong with this 29660564, it got accepted when i modified it to 29673408
•  » » Try input 3 1 1 2 3 1 2 and then 3 2 3 1 1 1 2 the result should stay the same, shouldn't it? :)
 » Can someone explain in detail how do we find leftmost point that is not lightened by k centers of ignition?
•  » » I cant even understand why we have to find exactly leftmost(
•  » » » When you find leftmost and rightmost; you have largest difference inx axis between two non-lightened points. If that distance is less or equal to 2*x where x is answer in binary search then we can put k+1 th point of ignition in center and cover both rightmost and leftmost point. Same goes for topmost and bottommost point.
•  » » 2 years ago, # ^ | ← Rev. 3 →   First, let's enumerate the columns of interest, because we believe that we may find a cell that has not been enlightened in them. Let's call this set of columns C = [c1, c2, ..., ck + 1]Notice that c1 = 1, since it's the leftmost column in the grid and there's a chance there is at least one empty cell. As for the rest of the columns of interest, we cannot try every single other because the width of the grid can be up to 109, so we should reason about which columns we should pick. Notice that if, when we are doing our binary search and we are evaluating if it's possible to enlighten the whole grid at a time t, the leftmost position an initially enlightened cell at (r, c) will be able to reach is (r, c - t). Therefore, column c - t - 1 may have one unenlightened cell. So we check for that column if that is the case. Let's do this for the remaining k initially enlightened cells (c2, c3, ..., ck + 1), so we have a total of k + 1 columns to try for the leftmost one. The same way idea can be applied to the rightmost column, top and bottom rows.How to check for a column c if it has one unenlightened cell? Let's iterate over every initialized enlightened cell (there are k of them). For each of them, at a time t, you want to know the range of cells from column c it is responsible for enlightening. Let's say that initialized enlightened cell is at (r', c'). The leftmost cell it's going to be able to enlighten is c' - t. If c' - t is at or left to c, it's obviously going to reach it, and what vertical range does it cover in this column? It's going to be [r' - t, r' + t], because as fire propagates in one direction, it's going to be propagating in the rest of the directions, so if it propagated t units to the left, every of those t columns covered will also cover t cells up and down. Store the range [l, r] this initialized enlightened cell spanned for column c in a list. Repeat for the rest of the k - 1 enlightened cells.Now the only remaining step is, sort the list by l, in case of tie, by r. Calculate the total range it covers by keeping track of the last endpoint covered so as to avoid counting some segment more than once, and check if cellscovered < heightgrid. If that is the case, there was at least one unenlightened cell in that column.
•  » » » Thank you so much! Great approach!
•  » » » Hey, now I realised that there might be some corner cases for this. For example, what if all k initial points lie in first column? Then leftmost column without lightened cell MAY be right to all k of these points.
•  » » » » Yes, I omitted that detail. Let's say you initialize left = width, right = 0. For every column of interest, update them accordingly if column c ended up having an unenlightened cell: left = min(left, c) right = max(right, c)
 » Could someone tell me the solution for B. Do we need to find all lucky tickets till 999999?
•  » » Maybe there is more clever solution, BUT YOU CAN find all lucky numbers til 999999. see my solution on profile. Its literally 6 foor loops from 0 to 9.Complexity is 1 milion which passes easily, so why think clever if u can brute haha
•  » » What I did was the following: Assume WLOG that the sum of the first three digits is less than the sum of the last 3. Let the difference between the halves be d. You want to increase the sum of the first half and/or decrease the sum of the second half so that d = 0. If you have a digit, x, in the first half, you can use that the decrease d by (9 — x). Similarly, if you have a digit, y, in the second half, you can use that digit to decrease d by y. So, just put all (9-x)s and ys into a list, sort, and greedily subtract the largest values until d <= 0.
•  » » » Thanks for the solution brother. Its an efficient way to check whether to decrease sum by changing the left part, increase by changing the right part or change element from both the sides.
•  » » » 9 months ago, # ^ | ← Rev. 2 →   ya
 » Tutorial is not available
 » can anybody elaborate on the sweep line approach to find the leftmost point?
 » For question D, I have written the solution following exactly the same steps as mentioned in the editorial (and coincidentally, the same variables!). However, I am getting WA in testcase 8. Can someone please help?
•  » » When a new speed limit sign comes, you also have to check if he is speeding. For example, if he goes with 50, at 60 speed limit, and 40 speed limit sign comes, you don't check it, though he is speeding.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   For every iteration, in the beginning, I am checking if the current speed is greater than the speed at the top of the stack. As long as this condition holds (and the stack is not empty), I pop the stack values and increment c. I am doing this in the beginning instead of doing it after the the code for type=3. So if a new speed limit of 40 comes, i push it and in the next iteration check whether sp is greater than the stack.top value...
•  » » » » Yes, but you change the speed before checking it. Imagine this test case: 4 3 60 1 50 3 40 1 30 Your code prints 0, but he was speeding with 50 at 40 sign.
•  » » » » » 2 years ago, # ^ | ← Rev. 2 →   Okay, I got it. I thought that if he passes a speed limit and then changes his speed, it won't be a violation. So if the current speed is 50 and the sequence is like: 3 40 1 35 I am accepting it as I thought that he had looked at the speed limit sign and then decreased his speed accordingly. That approach was wrong. Thanks for your help! Accepted now :)
•  » » » Link of my code is https://www.ideone.com/7UrJob
 » For problem E there is no need for line sweeping. One can realize that only 3·K lines and 3·K columns are relevant, so coordinate compression can be used followed by an O(K2) 2D partial sums based approach.
•  » » What are those 3*k lines and columns formally?
•  » » » Let (x1, y1, x2, y2) be a rectangle you want to update, then you only mainly care about {x1, x1 - 1, x2 + 1} and {y1, y1 - 1, y2 + 1}. Check out my code for more details (the one submitted after the contest has the tightest bounds on arrays, so it's a better choice).
•  » » » » Also, caring about {x1, x2 + 1} and {y1, y2 + 1} is enough if the compressed indices represent ranges rather than single coordinate values.
 » why can't i see the test cases?? its been 9 days the contest is over
 » Can someone please give a more detailed solution of problem F.
 » I dont think the explanations of the question in problem D is clear. He is saying that every sign cancels out the previous signs of its kind but in " his point of view " he remembers. SO there is no clear explanation of "His point of view ".
 » Can someone explain the intuition behind using Gaussian elimination in Problem G?