Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### GlebsHP's blog

By GlebsHP, history, 4 years ago, translation, ,

Hello everybody!

Today the second regular rated round based on problems of VK Cup 2016 Final Round will take place. Of course, we have created some more easy problems to fulfill the requirements of different skill levels and make the contest interesting for everyone.

The commentators of the previous announcement pointed out that I forgot to thank MikeMirzayanov for making Codeforces and Polygon so awesome. I was wrong, Mike, that's really cool :)

Scoring distribution will be published right before the start of the contest. We wish you good luck and beautiful solutions!

UPD1. Scoring for div2: 500-750-1000-1500-2000-2500. Scoring for div1: 500-1000-1500-2250-3000.

UPD2. The contest is over, congratulations to winners!

Div1:

Div2:

UPD3. I sincerely apologize for the delay with problem analysis. I was out of town for a vacation. Here it is.

• +372

 » 4 years ago, # |   -89 You also forgot to tell the main character of the problems.
•  » » 4 years ago, # ^ |   +66 There is no main character in the statements this time.
• »
»
4 years ago, # ^ |
-35

## Old driver will fire his car!Come on, become candidate master!

•  » » » 4 years ago, # ^ |   -13 DI DI...
•  » » » » 4 years ago, # ^ |   -13 di di student’s card
 » 4 years ago, # |   +16 don't forget to add codes on editorial as previous round.
•  » » 4 years ago, # ^ |   +124 LOL it should've been DONT FORGET TO WRITE AN EDITORIAL
 » 4 years ago, # |   0 =))
 » 4 years ago, # |   +19 Where are you tourist? :(
•  » » 4 years ago, # ^ |   +111 He took part in the onsite event, thus is unable to participate in this round.
•  » » 4 years ago, # ^ |   +26 Why the fixation on tourist to get top rank? It may be TooDifficuIt.
•  » » » 4 years ago, # ^ |   0 ba dum dis :P
 » 4 years ago, # |   -28 how many tasks in this problemset??!!
 » 4 years ago, # |   +135 petr now
•  » » 4 years ago, # ^ |   +34 a week of Petr
•  » » » 4 years ago, # ^ |   -22 today TooDifficuIt will be the hero :D
•  » » » » 4 years ago, # ^ |   0 I think so
•  » » » 4 years ago, # ^ |   0 The week is end.
•  » » » 4 years ago, # ^ |   +24 When You get -116 in rating after getting Rank #3 in div 1 :O
 » 4 years ago, # | ← Rev. 3 →   -33 want another Christmas tree!!
 » 4 years ago, # |   +11 Is tourist travelling？-_^
•  » » 4 years ago, # ^ |   +5
•  » » » 4 years ago, # ^ |   0 :)
•  » » 4 years ago, # ^ |   0 666
 » 4 years ago, # |   -37 New king of the iron throne of codeforces is Petr now :). tourist is busy in westores and hoping to see him to fight for the iron throne of codeforces again :P
•  » » 4 years ago, # ^ |   +17 You watch too much game of thrones.
•  » » » 4 years ago, # ^ |   -11 what's wrong in that?? It is the most amazing tv series so far i have seen. I suggest u must also watch to get something from nothing ;)
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   +10 Btw, i've watched every single episode of this show, But it didn't improve my coding skills at all. ..hmm weird, isn't it?
•  » » » » » 4 years ago, # ^ |   -8 I had never said watched it at the stack of your coding. And all the time coding is impossible even for tourist , petr too.. When i m tired and for refreshment i watched to gain my momentum again. So it helps me to back to coding..That's how it helps :p
 » 4 years ago, # | ← Rev. 3 →   +8 I'm Really surprised :DI hope I'll be Specialist :))->-> Thanks A lot <-<-
 » 4 years ago, # |   0 Guess it will be a colorful contest ;). Good luck everyone :)
 » 4 years ago, # |   0 what if mike Participated in one contest ? .. won't be great contest :p !?
 » 4 years ago, # |   +1 Wish good-luck to all. Happy Coding :)
 » 4 years ago, # |   -36 Game of codeforces throne likely to be unseen today as neither tourist nor Petr have registered so far! Can TooDifficult make it happening today?
•  » » 4 years ago, # ^ |   +9 Petr had registered.
•  » » » 4 years ago, # ^ |   0 Petr got -116 and tourist become top rank again!
 » 4 years ago, # |   +30 Scoring distribution?
 » 4 years ago, # |   +11 score distribution right before the start wow, they really meant right before the start.
 » 4 years ago, # | ← Rev. 2 →   +15 Tired of pokemon commercials.
•  » » 4 years ago, # ^ |   0 I love pokemon:D
 » 4 years ago, # |   +50 Seems like I can't concentrate on the contest with police helicopters hovering around...
•  » » 4 years ago, # ^ |   0 police helicpters?
•  » » 4 years ago, # ^ |   +63 What did you do?
•  » » » 4 years ago, # ^ |   +22 Live in Munich and work near OEZ
•  » » » » 4 years ago, # ^ |   +3 The shooting was reported about an hour ago, But you commented about 90 minutes ago, wtf? Are you involved in this? :/
•  » » » » » 4 years ago, # ^ |   +22 Because police helicopters were there much earlier than any reports. And my colleague who left work a little bit earlier reported hearing shots (and hidden in nearby home)
•  » » 4 years ago, # ^ |   +258 I also couldn't concentrate on all past 30-50 contests which I participated with missiles falling around me.
•  » » » 4 years ago, # ^ |   -28 :D
•  » » » 4 years ago, # ^ |   +20 Said like a boss :D
•  » » » 4 years ago, # ^ |   +71 You deserve a special competitive medal, dude. I was really surprised with your performance in the last ACPC contest when you became second on the Arab region alone because your teammates couldn't get visa for Egypt. You live in the most dangerous city in the world where you are not sure how your tomorrow is going to be. Go on and keep competing, you are a wonderful example and inspired a lot of people! May Allah keep you all safe.
•  » » » » 4 years ago, # ^ |   +12
•  » » » 4 years ago, # ^ |   0 You forget about electricity shortage :D .
 » 4 years ago, # | ← Rev. 3 →   +9 Edit: It's too late to delete this, so I'm sorry for taking up some unnecessary space. Basically I made an incorrect assumption that I'm not sure is legal to post here during the contest.Is anyone thinking the sample test case #2 for D is incorrect possibly?Here is my understanding for the second sample test: students at 0 bus at 0 at time 0, 1 person gets on bus 2 walking students at 3 bus at 6 at time 3, 1 person on bus arrives at end 2 still walking students at 4 bus at 4 at time 4, 1 person gets on bus 1 walking students at 5, bus at 6 at time 5, 1 person on bus arrives at end 1 still walking this is already more than the answer the sample case gave.
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 I misunderstood the problem in the same way.
•  » » 4 years ago, # ^ |   0 That's how I understood it as well. Maybe we're just thinking about it wrong? But that's the only way I can see it.
•  » » 4 years ago, # ^ |   0 I think the return of the bus can be neglected.
•  » » 4 years ago, # ^ |   +5 Bus can go non-integer amount of time.
•  » » 4 years ago, # ^ | ← Rev. 3 →   +3 I still don't understand how you get that low number. The lowest I could get is:  +   +   = 3 + 1.5 + 0.75 = 5.25
•  » » » 4 years ago, # ^ |   0 I thought same at first.
•  » » » » 4 years ago, # ^ |   0 Same here.So I left it and went for E. But was too slow.
•  » » » » 4 years ago, # ^ |   0 its easy ... SPOILER (HINT) ahead . . HINT : all of them (all n) and the bus will reach destination at the same time ...think about this..
•  » » 4 years ago, # ^ |   +3 Yes, I also thought so. In fact, according to that, the time only dependes on the last guy and there are some inequalities with the others. It was so weird :c
•  » » 4 years ago, # ^ |   +20 Students can get off the bus at any point. You are assuming that students gets off the bus only at the end.
•  » » » 4 years ago, # ^ |   +10 I strongly believe that it should be mentioned explicitly to avoid those confusions. But, I understand that it is part of the contest.
•  » » » 4 years ago, # ^ |   +10 So how about the bus take a student 3 unit far everytime, shouldn't it take 4.5 time ? t x1 x2 x3 0 0 0 0 // take student 1 t x1 x2 x3 1.5 3 1.5 1.5 // take student 2 t x1 x2 x3 3 4.5 4.5 3 // take student 3 t x1 x2 x3 4.5 6 6 6 
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 I was wrong
•  » » » 4 years ago, # ^ | ← Rev. 10 →   +13 students at 0,0,0 bus at 0 at time 0, 1 person gets on bus 2 walking FOR 1.28s students at 1.28,1.28,2.56 bus at 2.56 at time 1.28, bus goes backwards FOR 0.42s students at 1.70,1.70,2.98 bus at 1.70 at time 1.70, 1 person gets on bus 2 walking FOR 1.28s students at 2.98,4.26,4.26 bus at 4.26 at time 2.98, bus goes backwards FOR 0.42s students at 3.40,4.68,4.68 bus at 3.40 at time 3.40, 1 person gets on bus 2 walking FOR 1.28s students at 6,6,6 bus at 6 at time 4.68. (Calculation is not exact, but I think it wouldn't be necessary)
•  » » » » 4 years ago, # ^ |   0 Oh, and here I thought "as well as the reversal of the bus ... can be neglected." indicate that it doesn't take any time for the bus to return, there go my first hour into the contest =.=
•  » » » » » 4 years ago, # ^ |   +3 I spend 1:00 too...(And got 150 points because of 10^-6... :( )
•  » » » » » 4 years ago, # ^ |   0 What is it supposed to mean then? "the reversal of the bus ... can be neglected." made me think it took no time for the bus to return as well.
•  » » » » » » 4 years ago, # ^ |   +6 It means that after the bus moves some distance from left to right, it can turn around and start moving from right to left in zero time. The time taken to turn around is zero.
•  » » » » » » » 4 years ago, # ^ | ← Rev. 3 →   0 OHHHHHH turning around ok got it. Thanks!
•  » » » » 4 years ago, # ^ |   +6 You can do it by using binary search on time. You know the optimal way is to make all students arrive on the same time. So, If time is set, you can calculate the 1.28s and 0.42s in my post when the time is set in 4.68s.
•  » » 4 years ago, # ^ |   0 first of all , the pupil can take the bus for not all the distance and complete it by himself ....If we think of the problem without uding the first remark , your thinking still incorrect... - student 1 : 0 — > 6 in 3s - student 2 : 1 sc 3 — > 4 + 1 sc — > 6 because you have to do the eq : t * v1 + 3 =6 — t * v2 - same for the rest
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 deleted
 » 4 years ago, # |   +3 Could you please include an explanation for Div.2 D second example?
•  » » 4 years ago, # ^ |   +7 When the bus takes some students (or maybe only 1 student) it will be more profitable if it doesn't take them to the final. Think on this a little bit and you will get the second example.
•  » » » 4 years ago, # ^ |   0 I still don't get how I decide where to leave each student then. I thought about binary search but wasn't sure on what to apply it / conditions.
•  » » » » 4 years ago, # ^ |   0 Ok see if the bus takes some student directly to the final then every peace of time after that these student will not be doing anything they will just wait on the final, but if the bus take them some distance between the final they will walk during the transportation of the other students and that will reduce the time.
•  » » » » » 4 years ago, # ^ |   +1 Ok, I drop them before the final, but how do I know how much before the final? As in, at what position to drop them?
•  » » » » » » 4 years ago, # ^ |   +3 Wait for analysis.
•  » » » » » » 4 years ago, # ^ |   +4 let maximum people bus can carry be n and total people is N. So bus can make ceil(N/n) trips. You have to drop people such that last set of people carried by bus reach final point at the same time when the rest of people reach. I thought of this logic but wasn't able to implement.
•  » » » » » » » 4 years ago, # ^ |   +13 This idea is indeed correct. It implies that all persons need to be carried the same distance d. The bus then makes s = ceil(n/k) trips from start to end. The total distance travelled by bus while carrying is then d*s, total distance in reverse is d*s - l (since we ended at distance l from the origin). Total time is then T = (2*d*s - l) / v2.Now lets take a look at a passenger. It is carried by bus for d meters, and walks distance of l - d meters. Total time is T = (l-d)/v1 + d/v2. We have two equations with unknowns T and d, we solve for T which has exactly one solution (provided that v2 > v1) and voila, we have a O(1) solution.I would say it is not particularly easy for a Div1A problem.
•  » » » » » » » » 4 years ago, # ^ |   0 Thanks for your great analysis, majk. Can you suggest a tag for this problem? Which category does this problem belong to? What are some idiom analysis used in these kind of problem?
•  » » 4 years ago, # ^ |   0 It's not productively always go to end of way by bus.
•  » » » 4 years ago, # ^ |   +1 Can you explain more? I figured out this has to be the case but couldn't use it to solve the problem. :/
 » 4 years ago, # |   0 Good contest with good problems! Hopefully everyone did well and learned a lot today. :)
 » 4 years ago, # | ← Rev. 2 →   +10 Could Div 2 E be solved by keeping count of number of childrens if a subtree that are in the 2*k vertex list. And then counting how many times an edge u-v would be used depending on something like min(count[v], unpairedLeft — count[v])?
•  » » 4 years ago, # ^ |   0 Do you mean problem E?
•  » » » 4 years ago, # ^ |   0 Yes sorry
•  » » » 4 years ago, # ^ | ← Rev. 4 →   +8 Any ideas about this solution by ainta? It pairs university i with university i+k on the Euler tour.It makes sense intuitively, but why is this correct?
•  » » 4 years ago, # ^ |   0 can you elaborate your approach. ?
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 I tried to explain it better here. That unpairedLeft should have been 2*k only.
•  » » » » 4 years ago, # ^ |   0 Can you explain the correctness ? What if that particular edge isn't included in the 'best' solution ? Like 2 nodes in the subtree of v pair among themselves ?
•  » » » » » 4 years ago, # ^ |   0 This was the same reason why i couldn't submit this during the contest. However thinking now, lets suppose that we have choice to go through the edge u-v or pair 2 vertex in subtree of v (name them as a and b).Assume we pair a and b directly. Distance b/w a and b would be depth[a] + depth[b] — 2*depth[lca(a, b)]. Notice lca(a, b) is always in subtree of v, so we can reduce the subtracted term 2*depth[lca(a, b)] to 2*depth[v] if we consider using the edge u-v and also depth[v] <= depth[lca(a,b)] Hence choosing the edge u-v will always maximize the answer
•  » » » » » » 4 years ago, # ^ |   0 To what are you comparing depth[a] + depth[b] — 2*depth[lca(a,b)] ??
•  » » » » » » » 4 years ago, # ^ |   +3 If we pair a and b, addition to answer would be depth[a] + depth[b] — 2*depth[lca(a,b)]However if we don't pair them directly, but pair each of them to other vertex on other side of u, then addition to answer would atleast be depth[a] + depth[b] — 2*depth[v] + 2 (the 2 for edge u-v)
 » 4 years ago, # |   +20 Many thanks to GlebsHP for a nice round.
 » 4 years ago, # |   +1 My code fails for pretest 11 for problem C .ANY idea? http://codeforces.com/contest/701/submission/19344527
•  » » 4 years ago, # ^ |   +1 I failed the same test, I am very curious. Seemed like an easy problem
•  » » 4 years ago, # ^ |   0 isn't it "baacdabc"?
•  » » » 4 years ago, # ^ |   0 mine is giving is 4
•  » » 4 years ago, # ^ |   0 I found a counterexample for mine. 6 abcaab My solution says 4 but correct solution is 3.
•  » » 4 years ago, # ^ |   +5 Your code finds some interval, not necessarily the shortest one. Consider an example: 8 abcaabbc Your code will first move l from 0 to 4, leaving r=7, and then stop on "abbc" getting 4 whereas the returned value should be 3 (the first three letters "abc").
 » 4 years ago, # |   +12 Beautiful Div1-B. The problem seem impossible at first, but after you switch your point of view (from vertex to edge), it become very easy.
•  » » 4 years ago, # ^ |   0 would you mind explaining a little bit why?
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +3 For each edge, we want to count how many time it is used in the maximal sum, and that number equal the min of university count for the subtree from each vertex of that edge.
 » 4 years ago, # | ← Rev. 3 →   0 Because there is no hack in Div2-B, can we consider Div2-B's pretest is system tests?UDP: I know the answer now. The author may add some more tests.
 » 4 years ago, # |   0 Implemented a solution for Div2-D using ternary search optimization, really nice problem, unfortunately my solution works but it is too slow i didn't even submit it (a lot of recursive calls going on). Curious to see what the real solution is :D
•  » » 4 years ago, # ^ | ← Rev. 3 →   +36 A O(1) mathematical formula exists.T = el / (ev1 + v2 - v1)
•  » » » 4 years ago, # ^ |   +6 Can you explain your formula?
•  » » » » 4 years ago, # ^ | ← Rev. 3 →   +62 Let us try to make all people reach the end at the same time. So every person has to travel by bus(at most once, as given in statement) by the same amount of time. So, let distance travelled by every person in bus be P. If bus picks up some people at point A and they disembark at point B, then it needs to travel (v2 - v1) / (v2 + v1) * P(let this be equal to Y) back to get to other left people, because they would have travelled some distance on foot with speed v1. Let Z denote the number of trips bus has to make, it is equal to ceil(n / k). Therefore we have a relation, bus goes forward Z times, and goes back by the amount Y, Z - 1 times. Add these up, and they should equal L. That is, Z * P - (Z - 1) * Y = L. So we can find P now. Once we know P, we can find the answer easily.
•  » » » » » 4 years ago, # ^ |   0 Could you, please, explain Y = P  ×  a bit more?Why do you divide by v2 + v1?
•  » » » » » » 4 years ago, # ^ |   0 Take a paper and pencil, draw a line segment AB of length P. Now we will imagine that bus goes from A to B, leaves children at B and then returns and meets other children who started from A at some point C on the line segment. Time at which they both meet will be equal. So equate time( = distance travelled/ speed ) of both and you will get the formula.
•  » » » » » » 4 years ago, # ^ |   0 Time for bus to travel from A to B and return back to meet students who travel on foot (at point C) is Time for bus to travel from A to B is Hence, time for bus to return from B to C is , which equals to .Therefore, DistanceBC  =  t * v2  =   * v2  =
•  » » » » » 4 years ago, # ^ |   0 Thanks a lot, very clear idea!
•  » » » » » 4 years ago, # ^ |   0 I understood everything before this equation Z * P - (Z - 1) * Y = L. How is the difference(or sum, since its written sum above) equal to L?
•  » » » » » » 4 years ago, # ^ |   0 Z = ceil(N / K).As everyone reaches the end at the same time, we have to make exactly Z trips in the forward direction. Naturally, when the bus goes forward the last time, it should reach the end point with all children and it won't go back. Therefore trips that bus makes going back is Z - 1. Therefore, bus goes Z times forward and Z - 1 times back. We have to subtract them and it should equal L. Try drawing it on paper, by making exactly ceil(N / K) trips forward and ceil(N / K) - 1 trips back.
•  » » » 4 years ago, # ^ |   +1 a simple mathematical formula:d = [(n-1)/k]+1 ans=l/v2*((d*2.0-1.0)*v2+v1)/(v2+(d*2.0-1.0)*v1);
•  » » » » 4 years ago, # ^ |   0 Can you explain it?how to understand? thank you
 » 4 years ago, # |   0 Isn't div 2 D binary search on time ? But can anyone layout the conditions ? Same as div 1 A.
•  » » 4 years ago, # ^ | ← Rev. 3 →   +3 I was thinking that you should drop them off at a point b such that the time remaining after you drop them off multiplied by the walking speed of kids is equal to the remaining length.http://codeforces.com/contest/701/submission/19348156
•  » » » 4 years ago, # ^ |   0 Yes. I solved it like that by fixing time using binary search.
•  » » » 4 years ago, # ^ | ← Rev. 3 →   0 Div2D/Div1A: Can anyone explain what is wrong with this approach?2 groups of walkers, front and back. In the beginning all pupils are in the back group. Then the bus picks k pupils and moves them to x distance from the goal (binary/ternary search for best x). This group is now the "front group". Both groups walk continuously. The front group stops walking when they reach the goal. As long as there are pupils in the back group, the bus keeps moving pupils from the back group to the front group.
•  » » » » 4 years ago, # ^ |   0 I think the best distance x depends on the time remaining so the drop off point wont be the same for all the kids
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 Right. The front group is continuously walking, so the drop off point won't be the same for all pupils. In my previous comment "x" refers to the first drop off point.
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 I give up. Got as far as test #9. If anyone has an idea of where this rounding error comes, I would love to know: http://codeforces.com/contest/701/submission/19350779edit: nevermind, solved it
 » 4 years ago, # |   0 Anyone please explain the 2nd test case of Problem D (Div-2). In which way the ans is 4.7142857143 . My calculated ans is 5.6666664444 :( .
•  » » 4 years ago, # ^ |   +3 5.666644 was coming only if you assumed bus will always reach towards the end of destination. Answer could be reduced if the bus leaves those k persons somewhere in between
•  » » 4 years ago, # ^ |   0 I think the optimal strategy is for the bus to drop them somewhere in the middle and let them walk to the final destination.In real life this makes no sense, but you want to optimize the time of everyone getting to the final destination.I don't know the formula though.
•  » » 4 years ago, # ^ |   +8 ans is 33/7.0 and theres a O(1) formula
 » 4 years ago, # | ← Rev. 4 →   +4 WTF with DIV2 A? Almost all people in my friend list have it wrong on system tests :O Edit: Seems it is fixed now! phew :D
•  » » 4 years ago, # ^ |   +5 Div2 A with N <= 100000 would've been fun.
 » 4 years ago, # |   +11 Haha, is there anyone notice a small bug in the very first seconds of system testing? All of the accepted submissions are shown to be hacked!
 » 4 years ago, # |   0 Is there anything particular about Div1,B testcase 10 or is it just a large test case? I'm pretty sure my code was O(n) and I couldn't think of any exceptions.19346020
•  » » 4 years ago, # ^ |   0 I can't find any exceptions too... How about changing recursive function to loop? If It still gets TLE, then it will have an exception.(I'm just saying that recursive depth 200000 is dangerous)
•  » » » 4 years ago, # ^ |   0 I resubmitted without using std::pair and going threw only one dfs. I think the complexity was the same but the use of stl, etc. just increased the time constant a lot. Thanks for the help19367422
 » 4 years ago, # |   -15 I think problem setters should not add unnecessary character set like in Div2 C. Either keep a-z or A-Z , but why both? >( ..
•  » » 4 years ago, # ^ |   +4 Why not both?
•  » » » 4 years ago, # ^ |   0 Increases the implementation not the complexity of the problem?
 » 4 years ago, # |   +57 Am I the only person who understood the sequence: "...reversal of the bus, take place immediately and this time can be neglected" that it takes 0 time to reverse (go backwards) no matter how long? I know that it would mean a very strange bus, but I lost 25 minutes before noticing it :(
•  » » 4 years ago, # ^ |   +4 I interpreted it the same way. Although I probably wouldn't have been able to do it even if I had interpreted it correctly :P.
•  » » 4 years ago, # ^ |   0 WTF!! I came to know now!!
•  » » 4 years ago, # ^ |   0 So ... what does it mean in the end ?
•  » » 4 years ago, # ^ |   0 :D
 » 4 years ago, # |   0 how to solve div 2b?
•  » » 4 years ago, # ^ |   +10 Denoted by x the number of rows where no rook is placed, denoted by y the number of columns where no rook is placed. Answer = x*y.
•  » » 4 years ago, # ^ | ← Rev. 13 →   +9 In total (in the beginning) there are n * n cells.These n2 cells can be viewed as n rows of cells and n columns of cells.When we place a rook, it destroys completely 1 row and 1 column. Let's keep 2 arrays which will tell us, whether the row/column was destroyed or not:bool destroyedRows[100000];bool destroyedCols[100000]; After you place the first rook at cell (r0, c0), we can destroy row and column like that:destroyedRows[r0] = true;destroyedCols[c0] = true; The amount of alive rows decreases like that:long long cellsLeft = n * n;cellsLeft -= n; // for destroyed rowcellsLeft -= n; // for destroyed columncellsLeft += 1; // because row and column intersect at point where rook stands If you place the next rook at cell (r0, c1), you cannot destroy the row r0 the second time.That is why you should first check whether it was already destroyed:if (!destroyedRows[r0]){    destroyedRows[r0] = true;    cellsLeft -= n;} The final idea is to accumulate the amount of destroyed rows and destroyed columns till the current rook.Imagine that you have already processed i - 1 rooks. Now, the i'th rook wants to destroy the row ri and the column ci. If the row ri hasn't been already destroyed, you should destroy it now. But some cells on that row ri where previously destroyed by i - 1 rooks before the current rook. When they (previous rooks) were destroying there's columns, they also crossed the row ri! How many times did they cross the row ri? Well, they should have crossed it when they destroyed their's columns and we should just keep track of the number of columns destroyed (which is  ≤ n - 1). We will use this number to add back the amount of destroyed columns:...destroyedRows[ri] = true;cellsLeft -= n;cellsLeft += destroyedColumnsCount; // add back cells that were already destroyed before That is the general idea. The rest is implementation detail... =)
•  » » 4 years ago, # ^ |   +1 I think the basic idea is quite easy. Initially, number of rows(n) = number of columns(m) = nThen there are only 4 cases:1. if you have not visited the row and the column both visit them and reduce them, n-- & m-- output: cout<<(n*m-(n+m-1));2. if you have not visited the column visit and reduce the column size, m-- output: cout<<(n*m-n);3. if you have not visited the row visit and reduce the size, n-- output: cout<<(n*m-m);4. if you have visited both the row and column, there is nothong to do output: cout<
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Here is my approach :)For each query, you have to find number of cells on the board which do not have their row number and column number equal to any of the positions of the rooks placed uptill then. Actually, I did it by solving its complement, i.e. number of cells on the board which have their either their row number or column number or both not equal to any of the positions of the rooks placed and then subtracting this answer from the total number of cells.Maintain two sets for rows and columns. Denote them by r and c. Total cells -> (n*n)Cells which their row equal to any of the rooks and column not equal to that of any -> (n-size(c))*size(r)Cells which their column equal to any of the rooks and row not equal to that of any -> (n-size(r))*size(c)Cells which their row not equal to any of the rooks and column not equal to that of any -> (n-size(r))*(n-size(c))Therefore Answer = (n*n) — (n-size(c))*size(r) — (n-size(r))*size(c) — (n-size(r))*(n-size(c))On further simplification, this turns out to be, Answer = n*n — size(r)*n — size(c)*n + size(r)*size(c)Answer = (n-size(r)) * (n-size(c))Here is my solution: Code
 » 4 years ago, # |   +10 can rating fall over 100? I think mine will...
•  » » 4 years ago, # ^ |   0 T.T...
 » 4 years ago, # |   +8 I started trying problem A after I read it I couldn't understand the second sample, so I decided to move to B, after I solved it I went to read C, I figured out the solution quickly:apply max flow considering all edges capacity equal to 1, if it's more than 2 then output -1 otherwise try out to remove each edge which became saturated and for each of them find bridges and pick best bridge on the path between s and t of course there's some corner cases to handle.wow very easy idea I decided to code it although I have bridges and max flow codes beforehand it took me a full hour to code it, after passing all samples I submitted it and got WA after fixing some bugs I still got WA the contest ended but I didn't solving anything except B, if I knew coding C is overkill I would have returned to solve A instead :(
•  » » 4 years ago, # ^ |   0 I had the same solution to C as yours, but little bit simpler — you don't have to compute maxflow. If for every "deleted" edge, there is no path from s to t consisting only bridges, then we print  - 1.I didn't code it, but it's O(m2). Isn't it too slow?
•  » » 4 years ago, # ^ | ← Rev. 3 →   +64 I had a solution that didn't need flows and works in .Get a path from s to t. If none exists, print 0.This path will consist of at most n-1 edges. Now for each edge in this path, remove it from the graph and construct the bridge tree of the remaining graph. If s and t are in the same block int the bridge tree then removing this edge is of no use to us. Bridge Tree can be constructed in If s and t are in different blocks find the minimum weight edge on the path from block of s to block of t in the bridgeTree. Now you have two edges, compare their weigths with the current minimum and update accordingly.Add the removed edge back to the graph and repeat.Took too much time debuggin but oh well :/ 19347868
•  » » » 4 years ago, # ^ |   0 Nice!
 » 4 years ago, # |   +2 div 2 D anyone ?
 » 4 years ago, # |   +1 thanks Physics for div2 D ))
•  » » 4 years ago, # ^ |   +10 let maximum people bus can carry be n and total people is N. So bus can make ceil(N/n) trips. You have to drop people such that last set of people carried by bus reach final point at the same time when the rest of people reach.I thought of this logic but wasn't able to implement. Am I thinking right?
•  » » » 4 years ago, # ^ | ← Rev. 4 →   0 Yes, right idea. You can get it if you go to the frame of reference, where students are stationary. We can solve it by solving equation system.
 » 4 years ago, # |   0 Any idea for pretest 11 for div2-c
 » 4 years ago, # |   0 Overflow in B anyone?
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Overflow case is already present in pretest 3
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 I have a case of what I think is an overflow at testcase #31. Its a negative number, and a huge test case, so its the first thing that came to mind.edit : Its a case of unsigned integer overflow.
•  » » 4 years ago, # ^ |   0 Yes, Mine :(
 » 4 years ago, # |   +1 Was I the only one who thought "reversal" in Div2 D means "traveling" back to the students after the drop-off? Bad me. :(
 » 4 years ago, # | ← Rev. 2 →   0 Why the system testing is stuck at 100% ?? We have been seeing this for the last few contests !! Please fix this issue! :(
 » 4 years ago, # |   0 Getting WA in test case 31 in Div2 B. Can anybody give any insight why? Thanks! :)Solution
•  » » 4 years ago, # ^ |   +1 row.size() and col.size() are returned as unsigned ints, and in the worst case multiplying them can make them overflow. Type cast them into (long long)! :)
•  » » 4 years ago, # ^ |   0 i too had similar solution....failed because size function returns unsigned int :(
 » 4 years ago, # |   +47 petr now
•  » » 4 years ago, # ^ | ← Rev. 2 →   +26 Rank 3 and -116 O.o .. WOT
•  » » » 4 years ago, # ^ |   +2 because he was in rank 1
 » 4 years ago, # |   +11 When will be editoral?
 » 4 years ago, # |   0 Any hints on how to solve div 2 C ??
•  » » 4 years ago, # ^ | ← Rev. 2 →   +3 I used cumulative sum + binary search on window length approach. But it can be solved using two pointers technique. Hope this will help.
•  » » » 4 years ago, # ^ |   0 How to binary search here?
•  » » 4 years ago, # ^ |   +2 You can solve it by method of two pointers.
•  » » » 4 years ago, # ^ |   0 Can you explain How?
•  » » 4 years ago, # ^ |   +6 It can be solved using 2-pointers technique.We keep 2 pointers : left and right, which indicate that currently we're working with the houses(string) with indices [left, right].Also, we maintain an array to keep a count of all the pokemon's(letters) that we've caught so far, and a variable min, to keep the minimum substring length which includes AT LEAST 1 pokemon of all types.Then, inside a loop for left which goes from 0 to n — 1 (n = length of the string), we run another loop and increment right and add the pokemon at index right, until we don't have AT LEAST 1 pokemon of all types or right becomes equal to n. At this point, we update our min variable if the current substring [left, right] includes all pokemons and it's length is less than min. Then, we decrease count of the pokemon at index left and then increment left.Again, we check and update our min if needed.We do this inside a loop for left as stated above. Since right goes from 0 to n — 1 once and also left`, the total complexity is O(n).
•  » » » 4 years ago, # ^ |   0 I dont understand how the complexity of your algo is O(n). If i am not wrong it is a nested loop. right ??
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   +5 You're wrong, because both pointers only move forward, which means that the complexity is O(n).UPD: We don't move right pointer everytime from left, we keep its' position saved.
•  » » » » 4 years ago, # ^ |   +5 No, right is initialised only once, outside the first loop, and inside it is only incremented. We never reinitialise it or decrement it. So, right goes from 0 to n — 1. And the other loop is for left, which also goes from 0 to n — 1. Hence, O(n).You can refer to my code : 19349919P.S. : I actually initialised right to -1. I hope it's clear now. :)
•  » » » 4 years ago, # ^ |   0 I tried something like that , but it's O(n^2)?...here is my code that took TLE;
•  » » » » 4 years ago, # ^ |   0 Actually you are setting your right variable to n — 1 multiple times and then are iterating it down to i for 0 <= i < nso, for i = 0, you have n — 1 loops, for i = 1,you have n — 2 loops and so on.. So your worst case time complexity is O(n^2).You need to increment both your left and right variables from 0 to n just once. if you still don't get exactly how it's working let me know, I'll explain :)
•  » » » » » 4 years ago, # ^ |   0 ok, thanks !!
•  » » 4 years ago, # ^ | ← Rev. 3 →   +1 Move across the string recording the last position of each character that occurs in the string. Once you have seen each letter at least once, each time you move take the difference of the biggest last position and the smallest last position. The smallest such difference is your answer. This is worst case O(52*n).
•  » » 4 years ago, # ^ | ← Rev. 2 →   +3 Binary Search + Segment Tree Problem-CI don't like 2-pointers
•  » » » 4 years ago, # ^ |   +1 that's just wrong man...
•  » » » » 4 years ago, # ^ |   0 i know
•  » » » 4 years ago, # ^ |   0 two pointers much simpler than seg tree+binary search.
•  » » » » 4 years ago, # ^ |   0 ofcourse , but I was bored a little bit and I had the seg-tree code ready just the final touch
 » 4 years ago, # |   +42 upset..I got rank 10 too but not on the winners' board..Orz
 » 4 years ago, # |   +15 rest in pepperoni petr :'(
 » 4 years ago, # |   0 Hi, can anyone tell what may be the cause of this error in the Div.2 task A? 19333396
•  » » 4 years ago, # ^ |   +6 sum/n is not necessarily an integer but sum/(n/2) is.
 » 4 years ago, # |   +3 In recent rounds I have seen a glitch in the standings. When the system testing starts all queued submissions turned to failed. May be it's not a big deal but I wonder why this is happening?NB: The round was great. I'm looking forward to seeing so many rounds like this one. Thanks for the round :)
 » 4 years ago, # |   0 can anyone explain the approach to Div2C?
•  » » 4 years ago, # ^ |   0
•  » » 4 years ago, # ^ |   0 Go through the sequence and push symbols into the queue one by one. When it contains all types of symbols, this means you found a subsequence that satisfies problem statement. Now you can crop it from the beginning to make it as short as possible — just delete front symbol from the queue while it still contains all types of symbols. When done, check if this snippet is the shortest that you found so far. To continue searching, just remove first symbol from the queue (it should miss one type of symbol now) and continue pushing them from the given sequence. All the procedures can be performed quickly using STL structures like queue and set.
•  » » 4 years ago, # ^ |   0 I will explain my solution (binary search + sliding window) at first, its obvious the answer is the size of some contiguous subsequence that have all types of pokemons.if you try every range with size 1, then every range with size 2, .. until have range with all types of pokemons you can get the answer. but this is to slow which takes O(n^2).so you should do binary search on the size of the range, which takes O(n*log(n)). http://codeforces.com/contest/701/submission/19338973
 » 4 years ago, # |   0 approach for div2E ?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +36 Find a node such that all subtrees have <= K universities. Answer is sum of all depths. Complexity : O(N).
•  » » » 4 years ago, # ^ |   0 Nice explanation, thanks!
•  » » » 4 years ago, # ^ |   0 It took me a couple of minutes to figure your comment out, but this is beautiful.
•  » » » 4 years ago, # ^ | ← Rev. 3 →   0 I tried finding a node such that it has exactly K on one side. Can you figure out my solution fails? Your node will also have this property. 19342855
•  » » » » 4 years ago, # ^ |   0 I think you meant K and not K / 2 ? Also, there may not be a node such that exactly K nodes lie in one subtree.
•  » » » » » 4 years ago, # ^ |   0 Yes, but there is always a node which has a subset of sub-trees having exactly K nodes and exactly K in other subset when the tree is rooted at this Node.In un-rooted definition , if we remove this node all the components have <=K nodes.Is anything wrong in this hypothesis?
•  » » » » » » 4 years ago, # ^ |   +3 What if the subtrees have the following count of nodes : 2,2,k-3,k-1 ?
•  » » » » » » » 4 years ago, # ^ |   0 Thanks. So close yet so far from the solution. :)
•  » » » 4 years ago, # ^ |   0 Could you more explain the algorithm?
•  » » » 4 years ago, # ^ |   0 can you prove that such node is optimal choice?
•  » » » » 4 years ago, # ^ |   0 Yes. When we choose such a node, we know that each subtree has <= K universities. For a university in any one subtree, we have two choices : To pair it with a university in a different subtree or to pair it with a university in the same subtree. You can see that pairing universities among different subtrees maximises the answer, which is what is required!
•  » » » » » 4 years ago, # ^ |   0 Thanks, got it.
•  » » » » » 18 months ago, # ^ |   0 how will you prove that it always give maximum sum
•  » » 4 years ago, # ^ |   +15 Suppose there is a edge u->v and there are count[v] vertices that are in subtree of v and also in the 2*k list, then the edge u-v would be used (added) in the answer min(count[v], 2*k — count[v]) times only since we can always select min(count[v], 2*k — count[v]) pairs such that one is from each side of the edgeLink to submission
 » 4 years ago, # |   -20 my last 3 cf was horrible,thanks to the author to give sliding window problem which boost up the rating a lot.hahhahhaha
 » 4 years ago, # |   0 Div2D: What is the significance of "In order to avoid seasick, each of the pupils want to get into the bus no more than once"? I can't think of a case where shuttling a student more than once would be useful.
•  » » 4 years ago, # ^ |   +5 For example, let there be three students, but let the bus carry only two simultaneously. Intuitively, a good solution would carry each of the subsets {1, 2}, {1, 3} and {2, 3} on the bus for the same duration. However, this is impossible given the constraint.
•  » » » 4 years ago, # ^ |   0 Because the bus takes time to drive back the constraint doesn't matter. Makes the problem easier though, otherwise you'd have to figure out yourself that it doesn't matter...
•  » » » » 4 years ago, # ^ |   0 It does matter. I think the point in Gassa's example is that without the constraint we never have to drive a half-empty bus. So the bus is always driving at 100% capacity.
•  » » » » » 4 years ago, # ^ |   +6 It's impossible to drive the bus at 100% capacity if there's 2 seats and 3 pupils. The bus will always have to drive back to get the last pupil and drive at 50% capacity.
•  » » » » » » 4 years ago, # ^ |   0 Right, when the bus is driving BACKWARDS it's always empty.When the bus is driving FORWARDS we have a capacity problem. Without the constraint we could always drive forwards with 100% capacity. With the constraint we might sometimes have to drive a half-empty bus. In Gassa's example, we might first drive {1, 2} and then drive {3}. Even though we have room for 1 more passenger, we can't take anyone, because 1 and 2 have already been to the bus and we have no-one else we could take.
•  » » » » » » » 4 years ago, # ^ |   +6 'The constraint' meaning 'each of the pupils want to get into the bus no more than once', even without the constraint the bus cannot always drive forwards with 100% capacity. There's no better solution without this constraint, just like you stated in your original comment.
•  » » » » » » » » 4 years ago, # ^ |   0 Read Gassa's example again, it's very short and it illustrates the problem perfectly. It has the bus always driving forwards with 100% capacity. Add the constraint and the capacity drops.
•  » » » » » » » » » 4 years ago, # ^ |   +6 After reading Gassa's example again (and again) I still don't understand. Could you give me an example of how the bus will always drive forwards with 3 pupils and 2 seats?
•  » » » » » » » » » 4 years ago, # ^ |   0 I wasn't able to construct an example. I may have been wrong about the capacity thing.Let's say we shuttle {A,B} for some distance. Now we have to shuttle {C} for the same distance on its own. We can't shuttle A with C at this point, because A is ahead of C.So now I'm back to square 1, wondering what's the significance of the constraint in the first place.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +3 This looks impossible even without the constraint. How does the carrying of each of the subsets {1, 2}, {1, 3} and {2, 3} looks like? Do they need to travel backwards with the bus? Does it add efficiency?
•  » » » » 4 years ago, # ^ |   0 I wasn't able to construct a speedup example so far.My point is a bit different: when the constraint is there, it is irrelevant whether or not it's possible to get faster without it. So this investigation happens after the contest, not when solving the problem. Which is a good thing, especially if there is indeed no faster solution without the constraint.
 » 4 years ago, # |   -40 Who else has noticed that tourist has become top on the rank table even without participating!?
•  » » 4 years ago, # ^ |   -19
 » 4 years ago, # |   +1 can someone explain me the process to solve div1 D? i was thinking mo's algorithm but can't figure out the calculations. please help :(
•  » » 4 years ago, # ^ |   +17 By mo's algorithm, you can know the occurance of each number in the query interval [L, R], and also you can know which kinds of occurance has appeared. Since , the number of different occurance is no more than . So you can use pair < occ, cnt >  instead of only occ to represent a node in priority queue. And every time you pick up a node from the top, you can simply do this : occ *= 2 and cnt /= 2, if cnt is odd then you should split it. The whole algorithm is about .
•  » » » 4 years ago, # ^ |   0 thanks :D nice explanation :)
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +8 Did someone actually fit this exact complexity in TL though? This last part (with priority_queue or w/e else) seems a bit too slow for me, I spent quite some time trying to make it work (I've heard the solution, but I'm really curious if it can be passed in )
•  » » » » 4 years ago, # ^ |   0 The priority queue can be replaced by two queues. And this whill be .
•  » » » » » 4 years ago, # ^ |   0 How do you bound number of Huffman's vertices? Is it surely ? Won't it be multiplied by some small nonconstant factor?
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 I made it work. The only part which is beyond n sqrt(n) is the sorting — I perform O(n) sorts on an array of length O(sqrt(n)), which works really fast. Other than that everything else is O(n sqrt(n)).Oh, and using a custom list implementation instead of std::list resulted in a 20x speedup :D
 » 4 years ago, # |   +3 can someone help me out im getting WA in #17 test case in DIV2-C 19356617
•  » » 4 years ago, # ^ |   0 It can be solved using binary search. map all the characters and store an array dp. where dp[i][j] represents the number of occurrences of the ith character from index 1 to j. Then run a loop from 1 to n and for each i find out the lowest index r, greater than i where each character occur at least once. the complexity is O(n log n), so it easily passes. there might be two pointer solution but, binary search seemed easier and safer to me.
•  » » 4 years ago, # ^ |   0 can anyone help me in finding whats wrong in my code?
•  » » 4 years ago, # ^ |   0 Line 28: r<=n is causing problem.You have to stop the loop when r hits n, remember to care of the cases where string[n-1] is part of the optimal solution.
•  » » » 4 years ago, # ^ |   0 thanks a lot....finally got accepted
 » 4 years ago, # |   0 What about the Tutorial ? why didn't you post Problems analysis till now !!?
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 The author is busy with Pokeman Go.
 » 4 years ago, # | ← Rev. 2 →   +11 When will we read the anlysis of the problems?
 » 4 years ago, # |   0 where is the editorial?
•  » » 4 years ago, # ^ |   0 it was eaten by the author:D
 » 4 years ago, # |   0 In C, I'm finding the closest occurence of each character (both immediate left and immediate right) Then using two pointers, one pointer increases until no character on the right, and other decreases until no character on the left. Getting WA on test11. help.https://ideone.com/Wy4E3x
 » 4 years ago, # |   0 My approach on Div2E/Div1B, not necessarily correct, maybe I just slither through the system test cases.Step 1:Set a node which is only connected by an edge as the root of the tree.Step 2:DFS from this node, for each subtree count it's amount of university inside the tree. Select the minimum among all the nodes which has at least k university. (This is probably the node which every pair in the optimal solution will past... I say PROBABLY because I don't have a strong prove for this, but I can't think of a counter case.)Step 3:DFS from this node, the answer is the sum of this tree. My submission: http://codeforces.com/contest/700/submission/19363132A kinda similar question I would recommend to try out: http://codeforces.com/problemset/problem/685/B
 » 4 years ago, # |   0 Any tips on Div2F/Div1C? Cycles in the graph seems to be a huge obstacle in the problem.
•  » » 4 years ago, # ^ |   +25 For simplicity assume that there is no multi-edge nor self-loop (they can be handled in the beginning).First idea: brute force — remove every edge and look for bridges between s and t and find the best option. Iit can be done with standard dfs with low fuction, but -supposing you start if from s — you also need to remember if there is t in the subtree you've just visited. Complexity: O(m^2)Better idea: take a path P between s and t (if it doesn't exist — output 0 0). Observation: At least one edge from P must be removed. As the path contains at most n edges, we get O(n*m) which easily fits the limits.
•  » » » 4 years ago, # ^ |   0 Hope you don't mind that I'm asking, but how do you get O(n*m)? I'm only able to get O(n*(n+m)). After I remove and edge from the path I have to redo the DFS and this leads to O(n*(n+m)).
•  » » » » 4 years ago, # ^ |   0 Yeah, but n<=m so it is fine to write O(m) instead of O(n+m). Of course I also have the same complexity as you.
•  » » » » » 4 years ago, # ^ |   0 Thank you. I haven't written complexities in this manner before because I always tought that it is much clearer what kind of algorithm we have used. If we write n*(n+m), it is clear that we are doing a DFS each time. If we write only n*m it is not so clear. Again, thank you!
 » 4 years ago, # |   +17 dude , where is the editorial ?
 » 4 years ago, # |   +12 How long we wait for the editorials??
 » 4 years ago, # |   +1 Will Editorial be published this time? Waiting...............
 » 4 years ago, # |   +8 Editorial will be published soon, I guess. Another question is "when is the next round?"
 » 4 years ago, # |   +32 why does pairing node i and i + k after sorting according to dfs start time work in div1B?
 » 4 years ago, # | ← Rev. 2 →   0 Hints for E and F div 2 ?
•  » » 4 years ago, # ^ |   0 E and F div 2 = 7. That's all I can tell about that :(However, you can check out these hints: E and F.
•  » » 4 years ago, # ^ |   0 Hint for F: Let find any path P from S to T: O(M + N). The length of P will be less or equal to number of vertices. Try to remove any edge in P: O(N). For each removed edge in P find all bridges in resulting graph: O(N + M). Check if removing the bridge will disconnect S from T (it is possible at O(1)). Don't forget to check special cases: 1) There is no path from S to T. 2) Removing some edge in P disconnectes S from T. So this solution will work at O(N * (N + M)).
•  » » » 4 years ago, # ^ |   0 How did you check if deleting an edge would disconnect S from T? I did this while building dfs tree: if recursive DFS on edge has found T and that edge is a bridge, then account it.
•  » » » » 4 years ago, # ^ |   0 I did it exactly the same as you did
 » 4 years ago, # | ← Rev. 6 →   +19 D solution:Note these observations: The total time is set by the worst kid travel time. The optimal solution doesn't need to make the bus go to L on each trip. It may leave kids in half way and go left to take another kids. The optimal solution should end in L on the last trip. Proof by contradiction: If we don't end in L on the last trip, then we are leaving kids half way at speed V1, that could go at speed V2. Such proof do not apply to the other trips because time is set by the worst kid. The kid we are helping is the worst kid only in the last trip. Each kid will travel at speed V1 some time, and travel some time at speed V2 until it reaches L. If a kid travels more time at V2 and less time at V1 it will always be faster. the proportion t2 - t1 defines the kid's time to target. V1 * t1 + V2 * t2 = L If we increase V2 time of some kids, then we are reducing V2 time of other kids, Some kids are traveling more time at the bus than others. So, now I want to prove that in an optimal solution all kids must travel the same V2 time. I will do this again by contradiction. Imagine, that we have an optimal solution where two kids travel at different V2 times and one of them is the worst kid (if not all kids reach target at the same time, then there should be one or more kids to call the worst kid). Then we can always improve the worst kid travel time by increasing it's V2 time and reducing the V2 time of other kids. Improving the worst kid travel time implies improving total solution time, and as we reduced V2 time of kids that are not the worst, they don't affect the total solution time. So this is only valid if there are kids to be called the worst, and kids that are not the worst. We have just proved that any solution where the kids V2 times are not equal can be improved, this means it is not optimal. So the optimal solution must make all kids to travel the same time at V2. So now the solution is simpler. All bus trips with kids must always last the same and we could compute a growing F(x) = y where x is V2 time, that is bus trip time, and y is the position where the bus end in last trip. You need to see that if x (aka V2 time) is bigger then the bus travels more time to the right, so Y will be bigger. As F(x) is a growing function, then we can binary search x until we find F(x) = L, and the bus last position is L. This is the only solution with all V2 time equal that end in L, this means, it is a valid solution. AS all other valid solutions don't have V2 times equal, they are not optimal, what means F(x) = L computed by binary search is the optimal solution to the problem. As the statement do not ask for x (aka V2 time) we should do the extra calculation of the travel time, but if we compute the F(x) = y we can easily compute F(x) = t where t is the total bus traveling time, or another option is to compute V1time = t1 using V2time = t2 and t = t1 + t2 (note that all kids reach target at the same time as the have the same t1 and t2!) I recommend in binary search to use fixed number of iterations. It is the simpler solution, and we avoid the use of EPS (if you don't know what it is ignore this last comment). Code: F(x) = t manual calculation 19373739 F(x) = t based on v1t1 + v2t2 = L 19374507
•  » » 4 years ago, # ^ | ← Rev. 4 →   0 In the second test. Why can't I take each pupil on the bus per 3 meters?let (p1, p2, p3) positions of the pupils it = 1.5 — (3, 1.5, 1.5) — p1 in the bust = 3 — (4.5, 4.5, 3) — p2 in the bust = 4.5 — (6, 6, 6) — p3 in the bustotal 4.5
•  » » » 4 years ago, # ^ | ← Rev. 5 →   0 You are ignoring Bus return time. Bus can not teleport from one kid position to another instantly. You need to add to your calculations meeting time from the bus going left and the kids going right." as well as the — reversal of the bus, take place immediately "The reversal is the time to the bus to flip, not the time to the bus to return to search for more pupils.Your example of V2 time = 1.5s (3 meters) would bet = 1.5 — (1.5,1.5,3)te = (3-1.5)/(2+1) = 0.5t = 2 — (2 , 2 , 3.5)t = 3.5 — (3.5 , 5 , 5)te = (5-3.5)/(2+1) = 0.5 t = 4 — (4 , 5.5 , 5.5)t = 5.5 — (7 , 7 , 7)You end in position 7, so you need to reduce V2 time.
•  » » » » 4 years ago, # ^ |   0 You are right, I misunderstood the problem statement. Thanks a lot.
 » 4 years ago, # |   -34
 » 4 years ago, # |   0 Any ideas on how to solve Div2F/Div1C?
•  » » 4 years ago, # ^ |   +3 Find any path from S to T. Try to remove each edge of the path, In the resulting graph try to remove each bridge. This solution complexity is O(N * (N + M))
 » 4 years ago, # |   +40 waiting for the editorial and next context ...
 » 4 years ago, # |   0 Why does python submissions for div2 problem E gets runtime error in test 11? n is 200000 and my code: http://codeforces.com/contest/701/submission/19425329
•  » » 4 years ago, # ^ |   +3 I know nothing about Python, but it seems that you are not using 64-bit integer to store the results: Test case 11 is the first case where you need long long to store the answer. If Python has RE when there is overflow then this is probably your answer.
•  » » » 4 years ago, # ^ |   +3 There is no overflow in Python. Python's integers can store any number.
•  » » 4 years ago, # ^ |   +3 The RTE is because of recursion depth limit reach in your case. This happens mostly with me I used to switch to c++ with same logic!
•  » » » 4 years ago, # ^ |   0 Thanks! How do you overcome the problem or how to increase the depth limit?
 » 4 years ago, # |   0 Hi all,I am a beginning programmer who aspires to compete competitively in contests like USACO and the IOI. I know Java and Python fluently. I have found several programming websites like this one, and I am having a very hard time solving the most basic problems. (The code compiles fine, but I seem to bump into runtime errors.) Does anybody know a good coach? Does anybody know the best way to start? Thanks, Pimaster314
 » 3 years ago, # |   0 11