RAD's blog

Codeforces Beta Round #42 (Div. 2, Codeforces format)
By RAD, 14 years ago, translation, In English
Good evening

Yesterday evening the Saratov university delegation returned from St. Petersburg, from the ACM-ICPC NEERC 2010/11 World Programming Championship semi-finals. If you haven't seen the final standings: 4 Saratov teams received diplomas, and we (Saratov SU 2) advanced to the finals. Saratov SU 1 was also among those, who advanced, that's pretty cool for their first time, but didn't advance because of the limitation "only one team from one university".

Also we have prepared a Div. 2 round. Thanks for prompt assistance to Edvard Davtyan, Gerald Agapov and Maria Belova.

Good luck!
Artem Rakhov and Codeforces team


Unfortunately, the discrepancy between author’s solution and statement of problem E was detected. We bring our apologies to all the participants. All solutions that have not been Accepted previously were rejudged. Thanks to member xcr for detection of the issue.
  • Vote: I like it
  • +27
  • Vote: I do not like it

Comments Comments (30)
| Write comment?
14 years ago, # |
  Vote: I like it +1 Vote: I do not like it
Someone can paste the Pretest #6 for the problem D?
I can't figure what is the problem with my solution...
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Try 1 2 and 1 4
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      He means pretest?
      1 2 and 1 4 are used for hack.
      → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      У меня бага в 1 4 оказалась. Айайай как обидно, что во время контеста не догадался его вбить.
      → Reply
14 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it
/ a.out 
1 2
0
1 1
1 2
1 1

./a.out 
1 4
1
1 4 1 1
1 1
1 2
1 3
1 4
1 1


→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Try these tests: 4 4 , 4 5 , 5 4 , 5 5 (all the rest cases).
    → Reply
14 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it
I wonder if it wouldn't be better to have a possibility to lock the problem and start hacking without passing pretests, even without submiting it.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    I think it wouldn't be better, because in your case contestant can use 2 accounts: one for stealing solutions from another, second - for submitting stolen solutions. Now for getting solutions from competitors, even cheater have to write solution which passes pretests
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
How do I prove for problem D that when both n and m are odd, we can't find a required path without using teleporting gates?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Well, let's look at board painting. Every turn we change color of cell, in which king stays. So, for odd n and m cell at n*m turn will be black. n*m+1 turn must follow us to (1,1), which is also black. So we're used to place at least one gate.
    → Reply
    • 6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      In the above comment, the board painting refers to visualizing the board as a chess board with the cell at (1, 1) being colored black.

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

    Another way to prove this is by noting that the graph is bipartite.

    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Give me 23 test for E, please
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it
    Big random test with 99 cars, and 100 segments for each car.
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
What's final test 25 at problem D? Thanks..
→ Reply
  • 14 years ago, # ^ |
    ← Rev. 8   Vote: I like it 0 Vote: I do not like it
    I don't know. But I can assure you that if your code passes the following types of inputs, it should pass all the inputs,
    odd even
    even odd
    even even
    odd odd
    1 2
    2 1
    thanks to HackSon.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      I think "1 even" and "even 1" are not precise enough...
      1 2
      2 1
      1 M
      N 1
      where N, M > 2.
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        it's unnecessary to check "1 M" and "N 1" when N or M odd since it same as "odd odd"
        → Reply
    • 14 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it
      I have it done more complicately, so it's giving me Time exceeded.. but i think it should handle it for every 1<=n, m<=100
      → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    99 99
    → Reply
14 years ago, # |
  Vote: I like it +6 Vote: I do not like it
Hi to codeforces team

why you don't put test case's and problem's(in PDF) after each contest ?

it's usefull for every one ....

thanks for attention
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Congrats on making into the finals!! 9 Problems done, that is pretty impresive.
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Today I participated "out of competition". I have 2 questions:

-My solution got hacked by another div1 contestant. So....does this mean I'm able to hack any other div1 competitors? Cause I didn't see any one in my "room".

-Am I able to see the case that got me hacked during competition?

Thx in advance
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    To see other "out of competition" contestants in your room you should check box, that doing it (in top right corner).
    Hack protocols availible at "Hacks" tab by link in "Verdict" column.
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    If you participate 'out of competition', then when you enter the contest you appear in room number 1 instead of the room you were assigned to. (It's a bug.) To move into your room, select it from listbox in top right corner, it's marked with a star.
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Can anyone explain me problem C, I couldn't program it and ended up getting -2, how about a contest analysis after every contest?
→ Reply
  • 14 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it
    Let C[i] = # of integers in A1...AN s.t. Ak = i (mod 3)
    Then answer = C[0]/2 + min(C[1], C[2])
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    Previous explanation is for problem B. As regards C you just have to pair numbers a, b when:
    a % 3 = b % 3 = 0 or a % 3 = 1 and b % 3 = 2. In such cases (a + b) % 3 = 0.
    → Reply