e-maxx's blog

Codeforces Beta Round #34 (Div. 2)
By e-maxx, 9 years ago, translation, In English,

Welcome all to the next Codeforces Format round!


In this round I will replace Artem Rakhov in his usual role of contest administrator: Artem have set out to America to take part in TopCoder Open Algorithm onsite. Good luck, Artem!


The contest has ended, results.

User a4461497 has won the contest, while among first-division users - kuniavski was the first who solved all 5 problems.


All tests to the contest problems:

C, D, E


Thanks to Michael Mirzayanov and Julia Satushina who helped to prepare this round.
 
 
 
 
  • Vote: I like it
  • +46
  • Vote: I do not like it

Comments Comments (32)
9 years ago, # |
  Vote: I like it +23 Vote: I do not like it
Good luck to Artem!
→ Reply
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it
Actually,I like acm/icpc rules more...
→ Reply
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it
Prob. A,B,C,D are easier than the previous Round 2 contest problem set. However E seems very interesting. Thanks.
→ Reply
  • 9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it
    Yeah, I finished the set in 45 minutes this time, while I still haven't figured out the last problem from the previous set!

    Problem E in this contest was almost identical to the easy problem in TopCoder SRM 458 (the problem here has a more complicated collision formula, but that doesn't really change the problem, as the exact formula is given in the problem statement anyway). edit: actually, it looks like this problem was a little different after all. Still, it looked very familiar at the time. Maybe my mind was playing tricks.

    On the whole, I thought the previous set was a lot more inspired.  But I hope this was just an outlier and that future rounds will be more interesting again.

    To RAD.: best of luck in Las Vegas!
    → Reply
9 years ago, # |
  Vote: I like it +2 Vote: I do not like it
I think it's easy . Why don't it have dynamic programing ?
→ Reply
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it
hi. could you tell my what's  Artem Rakhov's username at Topcoder?
→ Reply
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it
what is the test case 13  of problem A???
→ Reply
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Can You please tell me what is stack size  here?
Or where is the rule page about this at all?
My recursive program in D gets Runtime error in test 19.And very same iterative program get accepted.I guess It is due to stack overflow.
→ Reply
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Can anybody explain the solution to Problem D ?
→ Reply
  • 9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Once the graph is a tree, you can construct it just by the information of the parents of the nodes, and then do a bfs from r2 to get the parents when that is the root.
    → Reply
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it
What are test 12, test 22 and test 26 of problem C?
→ Reply
  • 9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    You can download the tests in the part for round #34 in home page
    → Reply
9 years ago, # |
  Vote: I like it -6 Vote: I do not like it
I also want to know what are test14 of problemC.Anyone can help?
→ Reply
  • 9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    1000,1000,1000,1000,1000,998,998,1000,1000,1000,1000,999,999,1000,1000,1000,999,1000,997,999,997,1000,999,998,1000,999,1000,1000,1000,999,1000,999,999,1000,1000,999,1000,999,1000,1000,998,1000,1000,1000,998,998,1000,1000,999,1000,1000,1000,1000,1000,1000,1000,998,1000,1000,1000,999,1000,1000,999,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,998,1000,1000,1000,998,1000,1000,998,1000,999,1000,1000,1000,1000
    → Reply
  • 9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Maybe your array is too small,and that's my problem
    Actually  ,you can download the tests in the part for round #34 in home page

    → Reply
    • 9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
       After setting my array a little bigger, i got AC and i found what my problem was.Thanks a lot!
      → Reply
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I think #34 is easier than #32 or #31.
→ Reply
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Can anyone tell me the idea for the problem E?

Thanks.
→ Reply
  • 9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I just read the problem, and I think we can just simulate it. We keep finding the time at which the next collision occurs ( minimum of next collision time of all pairs ) and update the positions of all the balls after that. I guess this should be fine with the given constraints. Are there going to be so many collisions that this might lead to TLE ? If not, can some one give a rough proof. Thanks.
    → Reply
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I can't understand Problem D. What mean numbers in the second row and how to construct a tree ;o
→ Reply
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it
The numbers in the second row are nothing but the parent cities of the cities 1 to n, except for city r1. You may construct the tree using an adjacency list.
→ Reply
  • 9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Thank you, but how for example the tree looks like if the input is:
    Input:
    6 2 4
    6 1 2 4 2
    And how to know what value is i for each p(index)?
    Maybe my question is dumb, but i really can't imagine this. :/
    → Reply
    • 9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      for the above input,
      City   parent City (p index)
      1        6
      3        1
      4        2
      5        4
      6        2
      City 2 has no parent since its the root..  (assign the parents sequentially to the cities from 1 to n, when city r1 comes do not assign any parent to it..)

      The tree (Adjacency List) would look something like this:
      1 :  6 -  3
      2 :  4 -  6 
      3 :  1
      4 :  2 -  5 
      5 :  4
      6 :  1 -  2 
      Hope this makes things clear.. :)
      → Reply
    • 9 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it
      It could be represented this way -
       __2__
      |         |
      6        4
      |         |
      1        5
      |
      3
      → Reply
    • 9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Now I get it. Thank you
      → Reply
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it
hi
→ Reply