Rubanenko's blog

Invitation to the July Cook-off 2014 on CodeChef
By Rubanenko, 10 years ago, translation, In English

CodeChef invites you to participate in the July Cook-off 2014.
Time: 20th July 2014 (2130 hrs) to 21st July 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: msh_shiplu

Russian Translator: Witalia

Editorialist: PraveenDhinwa

Mandarin Translator: gediiiiiii and MinakoKojima

It's my second CodeChef Cook-Off. I believe this round is more interesting than my first one and hope you'll enjoy it! I think almost every problem can be solved by almost everyone, so everybody has a chance to place in top ten and win a T-shirt from CodeChef.

Problem statements are dedicated to Ukrainian National Team at IOI — Scorpy, NegaTeeF, seland and Omelianenko. I had a pleasure to help them with preparing for the IOI and they invented a nice solution for one of the problems in this contest! I'd also like to thank vadimmm for discussing and sharing ideas about the problemset.

UPD Contest is starting in 15 minutes!

UPD I'm completely sorry for having this endless testing queue. Hope none of you is disappointed because of it.

As you will see from the editorials, every problem has at most 50-60 lines neat solution. I'd love to hear from you about your impressions, especially your solutions for RRDAG and RRTREE. I also wonder whether there exists O(N2) solution for RRFRNDS. During the setting process I tried to invent such solution, but eventually ended up with O(N3) solution with constant optimization.

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

»
10 years ago, # |
  Vote: I like it +15 Vote: I do not like it

It was a great round, thx for preparing problems. But trouble with long testing was annoying.

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

    Round is not ended, it is prolonged for 1 hour. However, there are some problems with connection.

    Edit: Now everything is OK.

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

    Thanks, but you have about 35 minutes to submit all the problems!

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

Finally I solved "Friends".)) Thanks for this great round!

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

I solved Friends with bitsets, pls disqual me.

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

    I guess almost everybody did, since it was intended solution :)

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

      Oh my god! O;

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

      Oh come on, so jury doesn't have a proper solution for it. Why did you decide to have n=2000 then? It kills some of the bitset solutions (e.g. with Java's built-in bitsets), and does not kill others. If you wanted O(n3) to pass, you should've made the constraints way smaller.

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

        Hmm, my java solution based on built-in bitsets passed.

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

          Well, obviously if it's close to TL, it depends on luck. That's why general guidelines are "TL >= max(2 * time of jury java solution, 3 * time of jury C++ solution)". Just for the record, my TL solution is here.

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

            Problem in your solution is that you use O(n^3) memory instead of O(n^2)...

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

              It doesn't. At any point of time it is O(n2) memory, allocating bitset n2 times shouldn't consume much additional memory because GC/allocator implementations are smart. And I bet identical code in C++ would pass (and you wouldn't say that it uses n^3 memory, even though it allocates O(n) memory n^2 times). Besides, locally it was quite fast.

              Btw, do you know a way to solve the problem with Java using only built-in bitsets (i.e. BitSet or BigInteger) without allocating n^2 bitsets (and without accessing internals of bitsets, of course)?

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

                I agree about c++ solution:)

                Just don't create BitSet s inside your cycles (create it once and clear it inside loop and OR it with g[i]) and also you can optimize your solution in 2 times (you can look only on pairs with i < j).

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

                  Yes, yes, I know that it can be optimized a lot, it is far from being optimal :) I'm just saying that n=2000 is too much for intended O(n3) solution, and the TL is quite tight.

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

                  Maybe you are right and I'm sorry for this issue. I implemented bitset myself for this problem and set two times my running time as TL. Since it was ACM-style contest, I hope you wasn't affected very much :(

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

        All my solutions are written in Java and have at least two times margin.

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

      My O(N3) (see my code, it's so simple that I don't need to explain it) passed.

      UPD: I know I shouldn't be asking anymore and just take it as trolls being strong on CF, but I'll ask anyway: why the downvotes?

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

        I hate the concept of downvote. I only downvote when something is out of context. Otherwise either I upvote or left it as it is.

        I also dont know why you got so many downvotes :(

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

    Wow, till now I was sure that this is intended solution))

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

Don't know whats wrong with my submission for Friends ! O(n^2) gets TLE! but other people's O(n^3) doesn't :(

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

I wonder what's the jury soultion for "Present for Andrii". My (accepted) solution is O(n3) (with bitsets), but I hope jury has smth with proper asymptotics. Is is solvable without finding transitive closure? Or did jury implement O(n2.5) madness for it? (if so, I wonder whether it is faster than bitsets?)

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

    There is a neat O(N2) solution.

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

      Oh, nice! Why did you give such a small N then? Your solution would work for n=10000, which kills all transitive-closure-finders like me.

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

        Because either input or output would be quite massive then. It's also almost impossible to upload more than 8 MB file on CodeChef...

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

          You could've asked to compute hash of the output; and give graph not as a matrix, but as a list of arcs (which doesn't help bitset solutions).

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

            Good idea. I wish you helped me with preparing this contest T_T

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

This was something like "bitset round".

It seems that hardest 3 problem have bitset solution.

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

    Only one intended solution requires bitset.

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

      No offense. It was fun. Sometimes i feel good when intended solution was not bitset but mine was :).

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

    For me, it was an "additional factor of N in complexity" round. I had that for the 3 non-trivial problems. In short: WAT.

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

Long queue building up in the middle of the contest, testing completely nuked and contest extended: commemorating IOI 2013 day 1? :D

Just too bad this Cookoff couldn't be on 8th...

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

Thanks for editorials, this time they are well written and easy to understand)

→ Reply