dolphinigle's blog

Codeforces Beta Round #87
By dolphinigle, 13 years ago, In English
Welcome to Codeforces Beta Round #87!

The mysterious author of today's match (which turns out to be me) have prepared seven problems for you (five in each division). Since I can't spoil you any of the problems yet, for now I can safely say that I like all of today's problems. The problem statements are wonderfully crafted (and translated) with the help of both RAD and Delinur and they are now very easy to read. My hope is that you will like them as well :).

There will be .png images in some problems, so make sure your browser can support them. You may want to check if you can see the image in the Time to Raid Cowavans problem (authored by Alex_KPR).

And also a warm thanks to it4.kp for testing the problems (for the fourth fifth time I might add - he tested 4 of my SRMs already :) ) together with RAD, and to MikeMirzayanov and the entire Codeforces team for the great system and this opportunity! Indeed it is through this website that I receive my current internship offer :).

So from Kraków I wish everyone and the Codeforces' server good luck and stay strong :).

===

The match has ended! Thank you for participating - I enjoyed it :). Here's the Editorial for this match.

The top three of the Division1 solves all five problems! They are followed by al13n and kcm1700 who solved 4 problems in approximately one hour. Congratulations!

Division 1:
2. Petr
3. Egor
4. al13n

In division 2, we have exactly 5 persons who solved all 5 problems, the fastest solved all five problems within 1 hour 4 minutes! Congratulations!

Division 2:
1. kyrka
3. Skird
4. ts10

I hope I can author other set next time here. Till we meet again.

Final rants

If I could turn back time, I would change the following:
1) Swap problem D1-D and D1-E
2) modulo 1,000,003 becomes modulo 1,000,000,007
3) N^2 solutions means N >= 4,000
4) Time limit should be made for Java, not Python...

Lesson learned. And the N^3 solutions which pass turn out to be beautiful after I see them (all of them implements different algorithm after I read them more carefully). Not to mention there's 3 passing N^2 solutions. Okay, I'm content now :) - apologies for my rants yesterday.

=== stale rants below ===

Oh, after the coding phase, you may want to visit this post again.

Guess what? It's starting! Rawr! I'm honored that it broke the maximum number of participants so far - thank you guys :).
Link to standings:

Now that the match is over...
I owe division 2 apologies for making D2-D too easy. Sorry - I didn't see that coming.
Anyway, while you're busy waiting for scores to pop up in your respective division summary, here you go! Editorial for this match.

I don't know, I hope all N^3 solutions in D fail. Otherwise I owe you guys another apology. I'll be more evil with constraints next time :)
Okay, so a big apology from me for letting a N^3 solutions to pass D1-D. It didn't cross my mind that N^3 = 2000^3 would run under 2 seconds. I'll make sure not to make things like this happen again in my matches :( - 5000 here I come.
  • Vote: I like it
  • +5
  • Vote: I do not like it

Comments Comments (55)
| Write comment?
13 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Since "from Krakow now", could you please include in future contests some problems about Ijon Tichy and possibly other Stanisƚaw Lem's heroes? ;-)
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    You're too late, this is my last month in Krakow :)
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      I believe such a mighty problemist could create two or three contests during one month! Ok, it was almost joke, never mind! :-)
      → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Thanks for mentioning me, but I didn't deserve it this time.
The only thing I did was comparing the difficulty of two problems. I didn't even read the other ones. So, this is definitely not testing :)
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Will the strange illustrations appear!?

→ Reply
13 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

In what SRM's you were a problemwriter?
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Thanks a lot. Hope to have a great contest (and great translations :D)
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
And again, I'd compete, if time of start of round was later, then standard 19:00.
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Toastman may appear in the statements.
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
err.. Excuse me but what is the SRMs by the way? (I'm really sorry if it's inappropriate to ask like this)
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I'd like to compete, but its right on my lunch time.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Damn auto correct
    http://www.codeiforces.com
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I tried to submit a solution for practice in past contest but it was taking so long for judging.. I'm afraid this will happen in contest also.. Any solution for this, admin ?
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I think this happens because the server is rebooting before each contest. I may be wrong though.
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Your problems are usually nice and make the competitors think more rather than just coding. I was eagerly waiting for you to be an author of one the codeforces round. Thank you dolphinigle
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
In all problems today we should return only one number (both Div1 & Div2) (:
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Clear statements, useful pictures, and nice problems! I enjoy this match  very much. Thanks, dolphinigle .
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Great problemset. I'm just wondering about the solution of Div 1 C, that kind of tasks always confuses me.
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
How to solve DIv2 prob 2. I have no clue whats the best way ?
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    The answer is the number of wolfs, which have at least 1 neighbour pig. Since there is only one step in the task, and a wolf can eat at most one pig, it doesn't matter which to choose, and because no pig has more than one neighbour wolf, there can't be a fight over the same pig between multiple wolves as well.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Ahh..  did not notice that thing and whole time I was thinking , whether by mistake I have opened division 1 problem B.
      → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Despite the fact that I wrote bad today, this contest seems me really good: there was solved and interesting problem. In my opinion, it would be great to see similar contest every time. 
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Не могу не привести цитату из "Криминального чтива": English, ****! Do you speak it?!
    Но вообще согласен, контест действительно хороший и интересный.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Макс, откуда ты знаешь??? Ты ведь его не писал.
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Читал условия, смотрел решения.
        → Reply
        • 13 years ago, # ^ |
          ← Rev. 3   Vote: I like it 0 Vote: I do not like it

          На самом деле, часто впечатления от контеста после того, как прочитал условия и решения, сильно отличаются от тех, которые были бы, если бы прочитал условия и после этого 2 часа решал:)

          P.S. после публикации сообщения язык поменять никак?.. Жаль.
          → Reply
          • 13 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            Безусловно, но не всегда же удается написать тот или иной контест.
            → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
The editorial available right after the match is by itself a reason to call it wonderful.
Nice problems, too.
Kudos to dolphinigle and to the others problem setters!
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
The best thing I liked about the contest was the inages supporting the test cases.Made easier for us to visualize then..Good contest overall:)
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Yep, images were nice and cute :3
    But anyways, after I read the problem pictures didn't make much sense to me, because problem text was composed that good.
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I liked round, because there were not any longlongs, and output was as easy, as possible - one number.
Liked statements, they were simple, understandable and short. Thanks to writer
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Imo pretests for Div1 D are too weak. Wasn't easy to solve it, and a few seconds before the end I understand that I've missed some special case.
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Damn, I didn't know that dolphinigle was going to be the author today. Otherwise I wouldn't have missed it.
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
B: I misread the man in the problem can always flip his direction.
C: I misread the top-most side and the bottom-most side are connected. I thought so after seeing the figure in the examples.

...orz
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I was comfortable with today's problem set. Thanks to author.
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Many Many Thanks to dolphinigle for such a wonderful problemset :)
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
"The top three of the Division1 solves all three problems"
didn't you mean five? Topcoder has a very big influence on dolphinigle, I guess. :)
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    My bad :). Thanks for catching that - fixed.

    Yeah I'm used to write summaries to Topcoder's Editorial and that's pretty much the catch-line ;)
    → Reply
13 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

I came across an awkward issue when viewing source code during the contest.The pop-up window had a top-down/vertical scroll bar if needed, but never have a left-to-right/horizontal scroll bar. This brought about a knotty problem that I was NOT able to see those code out of right side of the pop-up window. I tried to view a few submissions and the issue happened all the time, I had to give up hacking. So it is probably a BUG.

Anyone else in the same situation? How to solve it?       
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Good problemset!I think this contest is organized very well!
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Link to test case 12 of D2-D/D1-B, Lawnmower:
http://www.mediafire.com/?v7hdvddcbqnbaqv
→ Reply
13 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Well, I think my solution, despite being O(N3), is ok to pass as it is more complex than original (and it can pass in O(N2logN) if I would use FFT to multiply polynoms) :)
→ Reply
  • 13 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    It's sort of relieving to hear this from a Java coder - my biggest concern was that C++ coders gained significant advantage due to C++'s inherently fast speed. Also the extra effort the coders who had working N^2 solutions (shik, ivan.popelyshev, and (I think) watashi for example).

    I'm not going to let this happen again next time :). Though I'm quite happy with how beautiful the passing solutions for current D, it's still pretty evil to ask for that kind of solution. 

    P.S. To be honest I'm not aware how to solve this problem with polynoms at all :)
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      I post my solution in editorial as comment (with no proof because I did not have one :) )
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Cool, thanks! It's in the russian forums by the way
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Ooops, I thought I double checked to post it in English and still...
          → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
D1--D  is a so fantastic problem!!!!
I love it so much! Really elegent! THX
→ Reply