BledDest's blog

Educational Codeforces Round 27 — Editorial
By BledDest, history, 7 years 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

Comments Comments (33)
| Write comment?
»
7 years 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..

→ Reply
  • »
    »
    7 years 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.

    → Reply
»
7 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Can someone please elucidate the solution for G ?

→ Reply
»
7 years 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.

→ Reply
»
7 years 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

→ Reply
  • »
    »
    7 years 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? :)

    → Reply
»
7 years 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?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      7 years 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.

      → Reply
  • »
    »
    7 years 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.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you so much! Great approach!

      → Reply
    • »
      »
      »
      7 years 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.

      → Reply
      • »
        »
        »
        »
        7 years 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)
        → Reply
»
7 years 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?

→ Reply
  • »
    »
    7 years 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

    → Reply
  • »
    »
    7 years 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.

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

      Thanks, it helped me to find mistake in my code :)

      → Reply
»
7 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Tutorial is not available

→ Reply
»
7 years 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?

→ Reply
»
7 years 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?

→ Reply
  • »
    »
    7 years 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.

    → Reply
    • »
      »
      »
      7 years 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...

      → Reply
      • »
        »
        »
        »
        7 years 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.

        → Reply
»
7 years 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 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.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What are those 3*k lines and columns formally?

    → Reply
    • »
      »
      »
      7 years 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).

      → Reply
      • »
        »
        »
        »
        7 years 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.

        → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain the intuition behind using Gaussian elimination in Problem G?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

В разборе задачи Экзамен по вождению, по моему ошибка: не выгодно не замечать знаки «отмена ограничения скорости» и «обгон запрещен» должно быть не выгодно не замечать знаки «отмена ограничения скорости» и «обгон разрешен»

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem D is poorly written and explained :/

→ Reply
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

$$$O(K^2.\log{N})$$$ solution for problem E: We can instead just find the leftmost, rightmost, upmost and downmost points that were not ignited, and just check that $$$max(righmost - leftmost, downmost - upmost) <= 2.time + 1$$$.

How do we find the leftmost, rightmost, upmost, downmost?

Let us consider the leftmost point, it is either in the first column, or it is a point lying just to the right of some square's (each burning point generates a square) right boundary. So we can consider for each square, and see whether its right boundary is completely covered by other squares or not. If not, then its right bound is a suitable candidate for being leftmost point. Similarly we can find the other 3 required points too.

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

problem c with cordinate compression

https://mirror.codeforces.com/contest/845/submission/255626351

→ Reply