Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

# | User | Rating |
---|---|---|

1 | tourist | 3438 |

2 | moejy0viiiiiv | 3288 |

3 | W4yneb0t | 3218 |

4 | LHiC | 3196 |

5 | TakanashiRikka | 3178 |

6 | Petr | 3163 |

7 | Um_nik | 3150 |

8 | izrak | 3109 |

9 | ershov.stanislav | 3105 |

10 | mnbvmar | 3018 |

# | User | Contrib. |
---|---|---|

1 | rng_58 | 179 |

2 | tourist | 171 |

3 | csacademy | 170 |

4 | Petr | 162 |

5 | Swistakk | 158 |

6 | Errichto | 156 |

7 | Zlobober | 152 |

7 | matthew99 | 152 |

9 | zscoder | 139 |

10 | Endagorion | 138 |

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial of Educational Codeforces Round 27

↑

↓

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/22/2017 14:42:51 (c3).

Desktop version, switch to mobile version.

User lists

Name |
---|

Can someone explain to me the solution for C mentionned above? I didn't quite get 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!

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

Where are the author's solutions??

They should be there.

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

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

Try input

and then

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.

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= [c_{1},c_{2}, ...,c_{k + 1}]Notice that

c_{1}= 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 10^{9}, 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 timet, the leftmost position an initially enlightened cell at (r,c) will be able to reach is (r,c-t). Therefore, columnc-t- 1 may have one unenlightened cell. So we check for that column if that is the case. Let's do this for the remainingkinitially enlightened cells (c_{2},c_{3}, ...,c_{k + 1}), so we have a total ofk+ 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

cif it has one unenlightened cell? Let's iterate over every initialized enlightened cell (there arekof them). For each of them, at a timet, you want to know the range of cells from columncit 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 isc' -t. Ifc' -tis at or left toc, 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 propagatedtunits to the left, every of thosetcolumns covered will also covertcells up and down. Store the range [l,r] this initialized enlightened cell spanned for columncin a list. Repeat for the rest of thek- 1 enlightened cells.Now the only remaining step is, sort the list by

l, in case of tie, byr. 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 ifcellscovered<height_{grid}. 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 columncended 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.

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.

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.

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·

Klines and 3·Kcolumns are relevant, so coordinate compression can be used followed by anO(K^{2}) 2D partial sums based approach.What are those 3*k lines and columns formally?

Let (

x_{1},y_{1},x_{2},y_{2}) be a rectangle you want to update, then you only mainly care about {x_{1},x_{1}- 1,x_{2}+ 1} and {y_{1},y_{1}- 1,y_{2}+ 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 {

x_{1},x_{2}+ 1} and {y_{1},y_{2}+ 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.