MikeMirzayanov's blog

By MikeMirzayanov, 12 years ago, translation, In English

Hello

We've scheduled Codeforces Testing Round #4 on January, 3 15:00 (UTC). It will be non-rated event, just to test system before important Codeforces Round #100. The round duration is 1 hour and it will contain just two problems. I do not promise something interesting and exciting, but as a small warm-up will be nice :)

I'll be glad to see you on the round,
MikeMirzayanov

The testing is successfully completed. Thank you for participation. I hope you like this sprint.

Announcement of Codeforces Testing Round 4
  • Vote: I like it
  • +92
  • Vote: I do not like it

»
12 years ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it
I have one point in the testing round. At min 32 after i submitted B problem , I didn't get an response from the system for like a min. then all the sudden the system said pretests passed.  
»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it
What's the idea behind problem B? 
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    anyone ?
    how to do problem B ?
    • »
      »
      »
      12 years ago, # ^ |
      Rev. 2   Vote: I like it +5 Vote: I do not like it

      Try googletranslate russian version.

      binpoisk == binary search, lol

    • »
      »
      »
      12 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      After running the DP version of Floyd-Warshall (similar to exponentiation by squaring), you can check if a positive cycle of length K exists in O(N^3.logN) time by combining matrices for maximum distances <=2^U.

      Knowing this, running a binary search from 2..N for the cycle length can also run in O(N^3.logN) time if the operations are ordered correctly.

»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I got stuck in problem B just now, but after read the article I figure out it :)