Rubanenko's blog

December Cook-Off
By Rubanenko, 10 years ago, In English

CodeChef invites you to participate in the December Cook-off 2014.
Time: 21st December 2014 (2130 hrs) to 22nd December 2014 (0000 hrs). (IST — +5:30 GMT) — Check your timezone.

Details

Registration: Just need to have a CodeChef user id to participate.

New users can register here.

Problem Setter: Rubanenko

Problem Tester: ddldyj237

Russian Translators: vadimmm & Rubanenko

Editorialist: fchirica

Mandarin Translator: MinakoKojima

It's my third CodeChef Cook-Off. The contest is quite balanced and I think that this contest will bring you something new and unusual. Don't be afraid of being creative! As always I'd love to hear from you after the competition is over.

Special thanks go vadimmm for discussing the problemset.

Don't forget that top ten contestants will receive CodeChef T-shirts!

UPD

Contest has started with some lagging and delays. I'm sorry for that and, unfortunately I could do nothing with it.

Strongest active ACM ICPC Belarus competitor kostya_by takes the lead! uwi has two penalty submissions in margin.

uwi submits the last problem from the first try and wins the contest!

dreamoon_love_AA seemed to be trying to do the same as he does on codefoces these days, but the problems were too easy, so he didn't succeed and accidentally solved all of them. Congratulations!

By the way, it seems that I forgot to say that you should be not only creative, but attentive as well..:)

I'm sorry that the problemset was too easy for some contestants. Problem RRPLAYER turned out to be known and easy. As you will see from the editorials, I had more complicated(and I thought cool) solution. I'm really sorry and probably won't set public contests in future :(

  • Vote: I like it
  • +75
  • Vote: I do not like it

»
10 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

Bump: starts in a minute! Hopefully I won't need the "Keep calm and spam F5" pic...

UPD: Okay, too late for pics anyway.

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

    Your hopes are shattered ! -_-

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

    I am getting 502 bad gateway.

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

    Seems like you will :D

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

    accidently pressed F4 instead of F5 :P

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

    Thanks for that reminding; original announcement had wrong timeenddate link, so i was sure that it is still almost an hour left to the beginning, when i saw your message few minutes after contest has started:)

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

I can't download the CodeChef.

Does somebody have the same problem?

UPD: All works!

→ Reply
»
10 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Strongest active ACM ICPC Belarus competitor kostya_by takes the lead!

Sad news for tourist...

→ Reply
»
10 years ago, # |
  Vote: I like it +18 Vote: I do not like it

I really did not like your sense of humor : 107 + 7

But other problems were interesting especially "Jam". I used parralel binary search. What was the intended solution?

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

    There is an easier n1.5 approach. What data structure did you used to use to do the binary search?

    If one implements something that allows to add progression and ask for minimum over the entire array, then he does not need binary search at all.

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

      i've used 2 fenwicks that allows me to update range and query an index.

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it -8 Vote: I do not like it

        By the way, did you do something special to avoid overflows? Since x, y <  = 109, applying first, say M / 2 updates would cause an overflow.

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

          No, i did not noticed it exceeds 1019. It looks like test-data has not got this kind input right?

          → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it +14 Vote: I do not like it

          I have to mention that problem statement says that x, y <  = 105.

          There are also lot of other problems with this statements in this contest — indexes in statement of Matrix Again were fixed at some moment late after contest start, and input format of problem Jam still does not say anything about line with values of B[i] :) And also limitation 0 <  = l, r <  = N looks a bit strange. Thanks for a contest, but please prepare better statements next time.

          → Reply
»
10 years ago, # |
  Vote: I like it +13 Vote: I do not like it

I had O(N·logN·logM) solution for RRJAM. It seems like some AC solutions have that complexity too. Was there some special case for that problem that caused my solution to run infinitely? I ran a couple of big tests and it seems like it should pass in time. (In fact, I had 2 solutions with that complexity, one with parallel binary search, and the other with persistent lazy segment tree, and both TLE)

Solution link: http://ideone.com/01kXO2

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    My solution with persistent segment trees (and the same time complexity as yours) got accepted, so I don't think it was intended to get TLE.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

First Cook-Off where I solved all the problems :) Don't know if I have improved or your problems were easy :P

→ Reply
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

"Problem RRPLAYER turned out to be known and easy."

I did not know the problem, but it was rather easy to see the pattern between answers for different n's.

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to use dp solution for n equals 3000. My dp implementation has precision problems when n approaches 3000.

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

    You were allowed to have 10 - 1 relative error. So for 3000 answer is about 25000 and it was ok to output 23000.

    → Reply
»
10 years ago, # |
  Vote: I like it +13 Vote: I do not like it

The problems were indeed easier than usual — you can see that by the larger than usual number of contestants who solved all of them (and the speed with which they solved all the problems). But it was a good contest. I don't think that the fact that the problems were easier is a good reason to stop setting public contests in the future.

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain a dp solution to RRPLAYER (other than the one described in the editorial)? According to the editorial one needs to pre-compute values but many solutions didn't do that.

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I just become stupid in the first hours that think problem Servers is a very very hard problem and try to use some strange method to solve it...

→ Reply