goryinyich's blog

Codeforces Round #102
By goryinyich, 13 years ago, In English

Hi there!

I'm the author of today's CF round.

During the round you'll again assist far away kingdom citizens in solving their everyday problems.

I want to thank Artem Rakhov for invaluable help during the round preparation, Maria Belova for translation of the problems, Mikhail Mirzayanov for excellent CF system and all participants for not leaving this event without your attention.

More AC verdicts and high rating to all of you! gl & hf

UPD: Round is finished. Congratulations to winners and awardees in both divisions!

Div-1
3. Egor
6. Coder
8. neal
9. WXYZ
10. whhone

Div-2
2. songlj

UPD: Round editorial is published. Russian version will appear soon.
  • Vote: I like it
  • +90
  • Vote: I do not like it

»
13 years ago, # |
  Vote: I like it -14 Vote: I do not like it
Thanks for preparing this round! Good luck to all the participants :-)
→ Reply
»
13 years ago, # |
← Rev. 2   Vote: I like it -13 Vote: I do not like it

Hi Sergei!

Thank you for your round. This event help me to rest and relax of boring examinations. I suppose that the problems is good and I'll get enjoy of this round.
→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it
    And to practise english a little bit :)
    → Reply
»
13 years ago, # |
  Vote: I like it -7 Vote: I do not like it
Thanks for the preparation! It's your efforts that will give us a meanful night (in my nation) !
→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    orz npc                                                                                                        langren...
    → Reply
»
13 years ago, # |
  Vote: I like it +59 Vote: I do not like it
+5 mins. Why? :) The contest is running away from us D:
→ Reply
»
13 years ago, # |
  Vote: I like it -9 Vote: I do not like it
Maybe the contest is scared :)) Anyway,good luck everybody :D
→ Reply
»
13 years ago, # |
  Vote: I like it +3 Vote: I do not like it
A very mathematical round. Thanks just as much.
→ Reply
»
13 years ago, # |
  Vote: I like it +68 Vote: I do not like it
A and C are implementation problems.
Have seen B before and D is based on known idea which was used in IPSC 2010 task K.

I expected more from this author.
→ Reply
»
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it
Am I the only one who wrote the complicated DP for problem C (div 1)?
→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it
    ... which wasn't quite right? You are not the only one.
    → Reply
    • »
      »
      »
      13 years ago, # ^ |
      ← Rev. 2   Vote: I like it +8 Vote: I do not like it

      I compared the maximum number of T-shape thing with tourist's solution. All my answer was correct. I hope my printing the board was correct too :(

      Edit: final test passed :D

      → Reply
    • »
      »
      »
      13 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Разве не работал перебор?

      Вроде простая динамика, ну немного более техническая, чем обычно.

      Why not DP?
      It was a rather simple one, though a bit more technical than usual.
      → Reply
  • »
    »
    13 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    Am I the only one who wrote the compilacated code for problem C (div 1) and didn't even pass pretest? :( http://mirror.codeforces.com/contest/142/submission/1040136

    → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I wrote the complicated DP too..
    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      and my solution is fast enough to solve n=m=9
      → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        My solution is fast enough to run all 81 possible test case in 1s :)

        May be the limit should have been min(m,n) <= 9, max(m,n) <= 20 ?

        → Reply
        • »
          »
          »
          »
          »
          13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          My DP solution is a little bit special. It will get TLE when max(m,n)<=20.  
          → Reply
»
13 years ago, # |
  Vote: I like it -14 Vote: I do not like it
Very fast System testing today.Its making up for the 5 mins delay in the start of the round.
I liked this round....Was logical and mathematical one...........:)
→ Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Can someone please point out why my solution to problem A (div2) in Python kept getting runtime error on pretest 1, even though it ran fine on my side. I had to re implement the exact same solution in C++ to get it AC. Darn! Here is the code: #
→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it
    Ghm. Maybe I misunderstand something, but sys.exit(1) looks strange. Return code 1 means runtime error in any programming language.
    → Reply
    • »
      »
      »
      13 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      Ah damn. I think you are right. What a silly oversight.

      Thanks.

      → Reply
»
13 years ago, # |
  Vote: I like it -33 Vote: I do not like it
wow! Greatest contest i've ever seen! I think this was a record for Div 2 to have ~2000 registered people! Thanks Codeforces
→ Reply
»
13 years ago, # |
  Vote: I like it +10 Vote: I do not like it
Editorial please
→ Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
i realize a useful "cut case" technique which sometimes works (like problem C this time) by reading others' codes...=D

  1.         // "useful" technique XD
  2.         if (clock() - start > 2.7*CLOCKS_PER_SEC) return;

(this technique was once used by my team in an acm-icpc regional contest too.)
→ Reply
  • »
    »
    13 years ago, # ^ |
    ← Rev. 2   Vote: I like it -7 Vote: I do not like it

    You can improve this even more.

    clock() function and floating-point comparison aren't the fastest operations.

    We usually use something like

    1. const int MAX_ITER = 80000000;
    2. int curIter;

    4. void solve(int x, int y){
    5. ...
    6.     if(curIter > MAX_ITER)
    7.         return;
    8.     curIter++;
    9. ...
    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      in the regional contest experience i mentioned above, we used exactly the method you suggested: count number of iterations in the searching function
      this worked well since our machine was (theoretically) identical to the judge machine
      (e.g., we found that 1,000,000 iterations ~= 1 second, the number of test cases <= 10, and there is 10 second time limit, so it should be save to set MAX_ITER = 1000000)

      while this method is also practical. however, in Codeforces/SRM/...etc contest, it may be a bit less convenient to "estimate" MAX_ITER, since the environment setting is a bit different. 
      → Reply
    • »
      »
      »
      13 years ago, # ^ |
      ← Rev. 2   Vote: I like it -10 Vote: I do not like it

      It seems to me that it's greater to use clock(), but not as mentioned above, but somehow like this:

      const int ITER = 1000;

      const float MAX_TIME = 2.8;
      int iter = 0;

      ...
      if (!(++iter % ITER))

        if ((float)clock() / CLOCKS_PER_SEC > MAX_TIME)

          return;

      ...


      It's better because we don't know, how much iterations our algorithm can do in time-limit; in my variant it will work exactly MAX_TIME (+/- EPS), and won't slow much because we check time only each ITERth iteration.

      → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it -10 Vote: I do not like it
        When iterations where answer exists work immediately, and time-limit cut-off need only for last iteration where no answer exist, there is no need for any optimization.
        → Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Can you please post the tutorial for this round?!
→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

this submission shouldn't have passed it was missing a case and I added it here

here a test case:

12 5
20 10
8 9

the output should be -1, but it outputs

5 7
2 3
→ Reply