RAD's blog

Codeforces Beta Round #29 (Codeforces format, Див. 2)
By RAD, 14 years ago, translation, In English
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 Mirzayanov, Dmitry Matov, Gerald Agapov and Nickolay Kuznetsov, thank them for that.

Happy Recruiter's Day,
Artem Rakhov

  • Vote: I like it
  • +9
  • Vote: I do not like it

Comments Comments (51)
| Write comment?
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
what is test case 11 for problem B??
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Is the following a valid test for problem A?
3
2 6
5 3
8 -6
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it
    Yes
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Then I think the answer is "YES" and submission no 115151 produces "NO". But it has passed the final tests.
      → Reply
      • 9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        interesting.. seems can't find the submission "You don't have access to view this submission"

        → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
What is test case 6 for problem D?? thx
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    8
4 3
1 4
8 5
7 6
3 5
7 3
4 2
2 6 8
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
What's the 14th test of problem E........
I got wa on it
Guys who failed system on E were TLE in majority。。。

→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
What is a test case #14 for problem C? Judge reported "Runtime error", but I don't see why.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Oh, don't worry.
    Now I see, that I just used too little constant in array declaration. What a silly fail. :-)
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
What is B-pretest1 and answer?
PE when I use C#
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    pretest1 = sample test1
    May be you output "," instead of "." ?
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
what's test case 3 for problem c?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    3
458744979 589655889
248228386 824699605
458744979 824699605

    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
What is pretest 4 for problem C? I don't know why I get a representation error.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    4
90104473 221011623
18773664 221011623
90104473 74427905
74427905 186329050

    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
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?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    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.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      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 :)
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        nice and easy solution. Thank you.
        → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        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.
        → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          As we all know,BFS travel every state in ONE step, so when reach the goal state, the step is  minimum.
          → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        nice and easy solution. Thank you.
        → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
What's the 12th test of problem B ?
I got WA on it .
Thanks !
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    2 1 1 1 1000

    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      а какойо ответ должен быть? У меня выводит 2.00000
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it
        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 .

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

What's test 19 in problem B?

→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    1000 1 1 1 1

    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      how about the 28th test ?
      Thanks !
      → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Thank you :)
      → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      My code outputs 1999.000000 and I think it's right.
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        No, the answer is 1001
        → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          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...
          → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          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.
          → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
What's test 5 in problem C?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    772 467 142 356 889

    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Problem C.....maybe you got a mistake
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it 
        6
        264896923 2497658
57071588 447086061
2497658 483723090
57071588 264896923
158310110 483723090
158310110 72866107
        → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
In Problem B : 

In this case 5 4 3 1 1. Why the answer is 2.33333333
I think it should be 2.66666667.


→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    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
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
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 ?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I got AC. Had not written a return statement and the behavior of function was undefined.
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
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.
→ Reply