LashaBukhnikashvili's blog

COCI 2012/2013 Contest #3
By LashaBukhnikashvili, 12 years ago, In English

Hi to everybody....

Today will be another round of COCI.

Those wishing to participate can enter/register here.

To LogIn choose COCI 2012/2013 — Contest #3.

Good luck to all in advance...

UPD: Here are results.

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

Comments Comments (44)
| Write comment?
»
12 years ago, # |
  Vote: I like it +2 Vote: I do not like it

How solve problem D (AERODROM) ???

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

    you can view my O(N*T) solution where T=LOG(10^18)

    I use binary search for finding answer of 1-10^18 interval (10^18 max ans size in my opinion :D) I think this is correct,I will know in a few minutes

    UPD: This is correct.

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

    It isn't hard. Binary search in answer. I suppose you can easy understand my code: Aerodrom

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

    For M<300 000 I hope priority_queue (keeping in it Tk*how_many_people_occupy_it) solution works.

    → Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Individual results update!

UPD: My score is 350(50+80+100+120)

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Is problem F(PROCESOR) a graph problem?

I'm sorry if this question is really stupid :(

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

    Yes, it is 2-SAT problem. But memory limit is realy stupid.

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

      Can you explain more why problem F is 2-SAT problem? Thanks

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

      Why is it 2-SAT? You have a graph (32*N vertices) with edges which demand either different numbers on endpoints or the same. You can just DFS/BFS it to enumerate each connected component and since each component can be easily inverted — you can take the most significant vertice and assign 0 to it at the start of DFS/BFS.

      The only challenging point is to get it into memory limit.

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

        And you can get into memory limit by making 2 optimizations:

        1. While you have 32*E edges, don't store 32*E edges, store just E, which I will call multiedge. Since every multiedge generates exactly one edge for each vertice in the given register, we can decode it while doing DFS/BFS.

        2. Use BFS, since it haven't got any overhead from recursion. Hence you only need 2 3.2M element arrays — one of char for storing assign bits (and simultaneously checking if we have been in that vertice) and one of int for the BFS queue.

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

          We can use non-recursive DFS as well.

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

            But why? BFS is meant to be non-recursive, while in DFS you would have to store a lot more information about each vertice to be able to emulate recursion. So it might not pass in ML either, or I am missing something.

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

              I don't understand. Can't we just change queue to stack?

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

                Yeah, but you still need more information, like the pointer of what neighbor of that vertice we are currently analyzing.

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

                  Why? I always wrote non-recursive BFS and DFS with the only difference of queue and stack. Or do you mean some specifics of your solution for this problem?

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

    Yes, you can use a modified Union-Find.

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

I had a bug in task 6 , when I finded it, the cotest ended :( This is my corrected code.

UPD: my score is 453

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

    You still have 64 points — you got MLE.

    Sorry, I don't mean to be rude, but your comment easily suggests that you claim that you have full solution to 6th task.

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

My score is 490(50+80+100+120+140+0). I couldn't find any solution on the last problem T.T

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

Weak tests in problem AERODROM My solution fails test:

30 1000
1 1 1 1 ... 1 1 1

but passes systests. Have anybody the same bug?

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

    Not only that — shouldn't you have long long overflow in this case?

    100000 whatever
1 1 1 ... 1 1 1
    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, and in my test I have overflow too.

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

        Well, luck is on your side then. :) Maybe they haven't thought of this specific error, while generating the test, although I thought that this could be the place where many could fail. But as it depends on binary search values, and from a quick look you have a little bit different binary search from what I usually see people writing (either not changing middle value at all when assigning it, or changing but only in one case, not in both), maybe you got away with this for that reason.

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

    My solution is similar to your, but I set the bound to 2e18, and it fails on systests (105/120). Our solutions have the same bug, but I have less points than you have. It seems strange.

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

      I'm lucky today. I think it's impossible to catch all bugs using 8 tests.

      → Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 3   Vote: I like it +9 Vote: I do not like it

    Imho, it's very bad idea to test solutions on less than 10 test cases (for example, today's task "malcolm" has only 5 tests)... Then I see so few tests, I remember informatics olympiads in my school, where we always have 5 tests, and almost everything passes them ;)

    PS and, ofc, I have the same bug as tunyash in aerodrom, but my solution gets full score...wtf

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

Why am I getting "SIGABRT" while I am not using any assert method out there?

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

    It seems that it is Memory Limit Exceeded.

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

      Then why? Isn't HERKABE supposed to be solved using trie? so keeping 3000 int-s and err... up to 3000*3000 nodes (which consists of two int-s one vector).

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

        I also submitted a solution with trie, but got lots of MLE. In the end you can do it by sorting the strings, and counting recursively, simulating you've got a trie.

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

          I solved that by sorting the strings, but I don't know why it works in time. I just used strcmp to sort. Here's the code

          Is just STL sort is fast to sort strings?

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

            Does this solution passed from all the test cases? It seems wrong at the following: 6 aa aa ab ab a a

            The correct answer should be 12 while this program outputs 6. I also used same technique as you, it seems that each function GetResult with unique parameter set corresponds to each node of the trie with which participants tried to solve this problem with. Therefore, our solutions seem to be base on creating this trie implicitly. :)

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

              "The names are distinct and given in no particular order."

              So, that test case isn't valid. :)

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

32MB is a ridiculously small memory limit...

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

This is the first time I participated to COCI, so I want to know when they usually publish results.

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

    A few days after the contest but no more than a week.

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

The results are up!

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

    As i thought, when I saw the problems after the contest — many guys with maximum score.

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

is there any way to log in there now?

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

when is the next round of this contest ?

→ Reply