BledDest's blog

By BledDest, history, 5 weeks ago, In English,
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
 
 
 
 
  • Vote: I like it  
  • +68
  • Vote: I do not like it  

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain to me the solution for C mentionned above? I didn't quite get it..

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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!

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    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.

»
4 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

Can someone please elucidate the solution for G ?

»
4 weeks ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

Where are the author's solutions??

They should be there.

Also the time complexity of all the problems is not mentioned.

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

for C problem, what's wrong with this 29660564, it got accepted when i modified it to 29673408

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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? :)

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain in detail how do we find leftmost point that is not lightened by k centers of ignition?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I cant even understand why we have to find exactly leftmost(

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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.

  • »
    »
    4 weeks ago, # ^ |
    Rev. 3   Vote: I like it +1 Vote: I do not like it

    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.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you so much! Great approach!

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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)
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone tell me the solution for B. Do we need to find all lucky tickets till 999999?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
4 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

Tutorial is not available

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can anybody elaborate on the sweep line approach to find the leftmost point?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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...

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          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 :)

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
»
4 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

For problem E there is no need for line sweeping. One can realize that only K lines and K columns are relevant, so coordinate compression can be used followed by an O(K2) 2D partial sums based approach.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What are those 3*k lines and columns formally?

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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).

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        Also, caring about {x1, x2 + 1} and {y1, y2 + 1} is enough if the compressed indices represent ranges rather than single coordinate values.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

why can't i see the test cases?? its been 9 days the contest is over

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please give a more detailed solution of problem F.