By RAD, 10 years ago, translation,
Today in Russia it's not just the 20th of september, it's Recruiter's Day. In Azerbaijan – Oil Industry Worker's Day, and in Belarus – Customs Officer's Day. But for us it's another good day to arrange the round. Welcome to Codeforces Beta Round #29 (Div. 2, Codeforces format)!

Helped with preparation of the round: Mike MirzayanovDmitry MatovGerald Agapov and Nickolay Kuznetsov, thank them for that.

Happy Recruiter's Day,
Artem Rakhov

• +9

 10 years ago, # |   0 what is test case 11 for problem B??
•  10 years ago, # ^ |   +13 2 1 1 1 1
•  10 years ago, # ^ |   0 ans???my comes 2.000000
•  10 years ago, # ^ |   0 3.0000000
•  10 years ago, # ^ |   0 o... :(
 10 years ago, # |   0 Is the following a valid test for problem A?32 65 38 -6
•  10 years ago, # ^ |   +13 Yes
•  10 years ago, # ^ |   0 Then I think the answer is "YES" and submission no 115151 produces "NO". But it has passed the final tests.
•  10 years ago, # ^ |   0 this is valid.. and output definitely "YES", but how he/she passed??? :o
•  5 years ago, # ^ |   0 interesting.. seems can't find the submission "You don't have access to view this submission"
 10 years ago, # |   0 What is test case 6 for problem D?? thx
•  10 years ago, # ^ |   0 8 4 3 1 4 8 5 7 6 3 5 7 3 4 2 2 6 8
 10 years ago, # |   0 What's the 14th test of problem E........I got wa on itGuys who failed system on E were TLE in majority。。。
•  10 years ago, # ^ |   +3 The 14th test is just big test with n=500 and m=1000
•  10 years ago, # ^ |   0 What is the optimal length of the test #14?3Q~
•  10 years ago, # ^ |   0 4
 10 years ago, # |   0 What is a test case #14 for problem C? Judge reported "Runtime error", but I don't see why.
•  10 years ago, # ^ |   0 Oh, don't worry. Now I see, that I just used too little constant in array declaration. What a silly fail. :-)
 10 years ago, # |   0 What is B-pretest1 and answer?PE when I use C#
•  10 years ago, # ^ |   0 pretest1 = sample test1May be you output "," instead of "." ?
 10 years ago, # |   0 what's test case 3 for problem c?
•  10 years ago, # ^ |   0 3 458744979 589655889 248228386 824699605 458744979 824699605
 10 years ago, # |   0 What is pretest 4 for problem C? I don't know why I get a representation error.
•  10 years ago, # ^ |   0 4 90104473 221011623 18773664 221011623 90104473 74427905 74427905 186329050
 10 years ago, # |   0 what's the solution for the last problem?it's obvious that if the shortest path in the graph has even numbers of nodes, than that's a solution.. but what to  do if that is not the case?
•  10 years ago, # ^ |   0 I managed to get AC in practice using Dijkstra's algorithm.You can represent each state as (x1, y1), where x1 and y1 are the location of the two guys. Then you can transition from (x1, y1) to (x2, y2) at a cost of 1 if there exists edges (x1, x2) and (y1, y2). Ensure that x2 != y2. Thus, you begin with (1, n), and terminate at (n, 1). Since each transition is equally weighted, a normal queue is sufficient.My solution was fairly sketchy since I got TLE using some C++ STL, but it passed with time 800ms when I manually implemented them. I'm wondering if there are more efficient solutions.
•  10 years ago, # ^ |   +1 Yes, there are. Since the edges have weight 1 (actually, equal weight in general) you don't need to use Dijkstra (and use BFS instead). The state in the bfs is the current nodes of the two persons and who moved last (in order to make the solution linear in the number of edges we need to realize there is no need to move them both at the same time). So we end up with a state[500][500][2], i.e. [node1][node2][who], where node1 is the current node of person 1, node2 is the current node of person 2, and who is 0 or 1 depending on who moved last. We run a standard BFS which should not allow the node1 == node2 when who == 0 (i.e. after the move of the second one). Ending state is when node1 == n, node2 == 1, who == 0. You can figure out details further yourselves :)
•  10 years ago, # ^ |   0 nice and easy solution. Thank you.
•  10 years ago, # ^ |   0 That's a much better representation of states. I've updated my solution and now it passes with time 110ms.Sorry about the confusion; I meant BFS instead of Dijkstra. Basically a Dijkstra without checking to see if the new distance is lower.
•  10 years ago, # ^ |   0 As we all know,BFS travel every state in ONE step, so when reach the goal state, the step is  minimum.
•  10 years ago, # ^ |   0 nice and easy solution. Thank you.
 10 years ago, # |   0 What's the 12th test of problem B ?I got WA on it .Thanks !
•  10 years ago, # ^ |   0 2 1 1 1 1000
•  10 years ago, # ^ |   0 Thanks. I've managed to find my code error.Though, I'm getting WA on test #28 now.Could you tell me the test please ?Best regards !
•  10 years ago, # ^ |   0 а какойо ответ должен быть? У меня выводит 2.00000
•  10 years ago, # ^ |   +1 On the 12th test case I got 1002.( I cannot understand russian but I assumed you might have asked what's the correct answer for the 12th test case . If I was wrong, I'm sorry .
10 years ago, # |
0

### What's test 19 in problem B?

•  10 years ago, # ^ |   0 1000 1 1 1 1
•  10 years ago, # ^ |   0 how about the 28th test ?Thanks !
•  10 years ago, # ^ |   0 1000 999 1 1 1000
•  10 years ago, # ^ |   0 I've found my error and managed to got AC.Thanks !
•  10 years ago, # ^ |   0 Thank you :)
•  10 years ago, # ^ |   0 My code outputs 1999.000000 and I think it's right.
•  10 years ago, # ^ |   0 No, the answer is 1001
•  10 years ago, # ^ |   0 I think he walks the first second then he stops for a red sign for 1 sec. then walks for 1 more second to reach the next index at the sign of red again and so on...
•  10 years ago, # ^ |   0 Ouch! I misunderstood the problem statement... I thought there are traffic lights each d meters :|Seems the problem is easier than I've expected... but it's strange to pass 18 test cases while I assumed that there are traffic lights each d meters :-?Anyway, thanks RAD a lot. I have got AC finally.
 10 years ago, # |   0 What's test 5 in problem C?
•  10 years ago, # ^ |   0 I got PE on it
•  10 years ago, # ^ |   0 772 467 142 356 889
•  10 years ago, # ^ |   0 Problem C.....maybe you got a mistake
•  10 years ago, # ^ |   0 6264896923 2497658 57071588 447086061 2497658 483723090 57071588 264896923 158310110 483723090 158310110 72866107
•  10 years ago, # ^ |   0 I think I got a Wrong Answer not PE..The answer I got is 72866107 0 0 0 0 0 0
 10 years ago, # |   0 In Problem B : In this case 5 4 3 1 1. Why the answer is 2.33333333I think it should be 2.66666667.
•  10 years ago, # ^ |   +3 He first moves 3 units ( with t1 = d1 / v = 1 second ). The traffic light changes color.He now waits t2 = 0.66667 seconds from the semaphor's red light.After t2, he instantly accelerates to v = 3 m/s speed, catches the changing color right when passing through the traffic light and makes t3 = d2 / v = 2/3 = 0.66667 seconds until reaching the destination.Total time spent: T = t1 + t2 + t3 = 1 + 0.6667 + 0.667 = 2.333
•  10 years ago, # ^ |   0 I thought t2 should be 1 second. Why he waits 0.66667 sec. Traffic light alternate turns red and green in 1 second.
•  10 years ago, # ^ |   0
•  10 years ago, # ^ |   0 Consider the car being at d1 = 3 m from A. You have alredy spent t1 = 1 sec to reach here. You currently are d2 = 1 m ahead the traffic light. Take into consideration the problem statement: "But if it approaches the traffic lights at the moment when the green light has just turned on, it can move."So, why wait 1 second for the red light to change and then reach the traffic light ( when is't green ) in 0.333 sec totaling a 1.333 ( for the distance between 3 and 4 ), when you can wait 0.6667 out of 1 sec from it's red light and then, reach the traffic light ( in 0.333 sec ) right in the moment when it changes to green, being in the above mentioned problem case.( Please excuse my empty post. Don't know what happened. I've posted the answer but there was probably an error in the system receiving it ).
 10 years ago, # |   0 I keep getting WA on Test 2 in Problem D  on the judge. Is not test case 2 the second sample test case specified in the problem ?  I get correct answers on the samples.  Can anyone tell me what Test case 2 is ?
•  10 years ago, # ^ |   0 I got AC. Had not written a return statement and the behavior of function was undefined.
 10 years ago, # |   0 There's some place where I can get the inputs and outputs of the problems?I'm getting WA at Test 13 in problem D, and couldn't figure out where my solution fail.
 10 years ago, # |   0 Can someon explain me problem C - Mail Stamps. I don't understand what is actually the problem which needs to be solved.