Allanur's blog

COCI contest #4
By Allanur, 10 years ago, In English

This contest will be on saturday (20.12.2014) at 14:00 GMT/UTC.

The fourth contest of the Croatian Olympiad in Informatics takes place.

You can login/register here(no registration for contest is required).

For more information this and this.

Good Luck to everyone :)

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

»
10 years ago, # |
  Vote: I like it -13 Vote: I do not like it

Looking forward to it :)

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

Hello I'm new to COCI. Is it allowed to submit the solutions online to previous contest for practice?

Thanks

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

    You can find previous contests testdata, solutions and tasks here.

    Each contest's practice mode is available after the contest.

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

      Can I practice a task from a previous contest (e.g. contest #3) on evaluator?

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

I'm getting "You're not allowed to log in from this location." when I try to login. Ideas why?

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

    You must change HONI to COCI in registration

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

    Check the contest bar. It should be coci not honi.

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

It would be fabulous if COCI uses full feedback (Like USACO) :)

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

What were approaches to E (SABOR) and F (STANOVI)? I couldn't come up with anything short of brute force for E, and got nothing for F.

Edit: I meant nothing short of brute force for E, apologies.

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

    Note on brute-force for D: you can prove that it's always beneficiary to use superpipe powers, since you need to pass at least 1 liter through every pipe. So, either bottom-up DP or simulation with binary search should work.

    I got precision errors though, perhaps the whole task was actually to avoid that.

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

      binary search? exist test where answer is 10^500

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

        They announced that the answer can be up to 2e9 only.

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

          Oh, that's quite sad. I reached that problem and I had a minor headache, so when I thought that I had to code long double numbers, I just gave up on the whole contest :P

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

    My solution for E: First select a random party for each MP. Then find a MP who has more than two connections to MP's in the same party and change this MP's party, and repeat this until everything is ok. I got full points, no idea why this works :D

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

      Let T be the number of edges uv that u and v has the same color. Each time you change the color of some vertex, T is decreased by at least one so you find a correct solution after at most M changes

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

      I do the same thing, but I get TLE in the 10th test case. Can you give me some hints to make my code run faster? Thanks!

      Here is my code: http://ideone.com/FQtOdy

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

        My code: http://pastebin.com/fFrZ0SmY

        I think there are two major differences:

        • I process the MP's in random order (array h contains a random permutation of the numbers)
        • my code can change several parties during one round
        → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    U can use greedy on D Easily Excuse me for my naive code http://paste.ubuntu.com/9581807/

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

Why this O(N logN) solution Exceeded Time Limit This

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

    It would be O(N logN) if you delete a element from the set for constant number. While you're decreasing some index, you're also increasing other. That's why, this is not O(N logN).

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

My overall feeling is that this was the weirdest COCI I've ever written.

2nd task: Am I missing some really easy solution here? I don't understand why this is second task, considering 3rd or 4th.

3rd task: max(sum, 2*max). It was actually nice to prove that and I liked it, but at the same time this was so easy to guess that I feel that many didn't even bother to prove it.

4th task: Again, it's clear that since we need to deliver amount of water >= 1.0 to each note, that using superpipe powers is always beneficiary. From here it's trivial bottom-up DP or binary search with simple simulation. Just need to avoid precision errors. Why N <= 1000? Why restrictions on water to each node >= 1.0? These simplify things too much in my opinion. Easier than 2nd task (unless I'm missing something there).

5th task: I liked this task, but as already mentioned here, looks like it was vulnerable to random approach without actually solving task.

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

    The third task was actually a simplified version of a recent CodeChef problem: http://www.codechef.com/NOV14/problems/SEAORD

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

      I see. I wouldn't mind if they just required to output any order as well, which would require to at least think of why it's max(sum, 2*max).

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

    5th task is a bit different version of one of the most known Math problems. The solution is quite elegant, but there is already the same at timus and one of Sereja's rounds at CF.

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

    2nd task: This task was tricky. The idea is very simple, but there are lots of things that you can mess up. Just simulate the game and pay attention to the last steps of the game.

    4th task: N <= 1000 because N <= 100000 doesn't make the problem harder, does it? Yeah, this one seemed pretty straightforward, doesn't deserve the 4th spot.

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

    in second task the players don't play optimally they just do the steps mentioned in the statement so this is just a simulation problem.

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

      Sure, however there are many things to mess up in simulation. Hence, I believe it was a lot harder to code than 3rd or 4th problem. Unless there is some clever solution which can avoid all this stuff.

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

        In my solution, I just coded up binary search on the point at which a player loses. I thought this got rid of some unneeded casework. My code isn't the most concise, but I had relatively few problems dealing with tricky cases. Here is my code for reference: http://ideone.com/nmp1PH

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

        Not so many things: http://ideone.com/HkkDuR

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

        There's nice short solution (<500 Bytes): http://ideone.com/208cQF Got full score (80pts) with this code.

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it +21 Vote: I do not like it 
          printf("%sko\n%d %d\n",a<=b?"Slav":"Mir",N[i],N[j]);

          That's amazing :)

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

Last problem can be solved easily with simple dp. There are N.M.16 states. Since you just need to remember width, height and for each edge out or in (24). To calculate each state one can silmply divide current rectangle with horizonal or vertical segments. So overall complexty is O(N316).

PS:I dont understand why this problem was 6th problem. I would not give it even 4th level. What do you think?

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

    Last problem can be solved easily with simple dp.

    Yes it's simple but why it's correct? Can you prove it?

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

      We are not going any state that has all 4 edges are "in". We have 2 options to decide whether divide our rectangle to smaller ones or do not divide at all. If we are not dividing then answer for that state equals (width * height - K)2.

      Solution found from above procedure obviously guarantee that every rectangle has at least a window at the end. Also every end state that fulfills the conditions are handling too. So answer can not be less then the solution we found.

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

        You have to prove in some optimal solution, exists a vertical line with length equal to m or a horizontal line with length equal to n. You are using this fact in your solution while dividing the table into smaller ones.

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

          Now i understand where you are coming from :) To be honest, i did not noticed this until you told me. I did not thought about it much but it seems like when there is not any of the "huge" lines you described above, it's impossible to make every rectangle has a window.

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

            Well, I don't think so! You can reach that target without the 'huge' lines but that case won't be optimal.
            It looks hard to prove!

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

              Could you give an example of splitting which has not got any huge lines and every rectangle has a window?

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

                Sorry... I was wrong. Your idea is correct! I proved it using induction. Now everything makes sense! :)

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

I read statement of CESTA 20 mins and did not understand, why this problem first and only 50 pts? I can solve it only with hashing/suffix array. Now i see my code got 0 pts, and we need to shuffling, not shifting digits :D

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

    I can't tell whether you're being serious or not...

    If you are, then I can tell you it is just trivial maths. Notice that number must be multiple of 3 at the beginning (before reshuffling) and must have a zero after shuffling.

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

      He misread the problem statement. He thought that we are only allowed to shift, not shuffle.

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

Could anypony describe solutions to Sabor and Stanovi?

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

    For Sabor, assign a party to each member, any assignment will do. Next, we will "fix" this assignment. For a person who has more than 2 opponents from the same party, we flip his party . Doing this will guarantee that the number of invalid people goes down by at least one. Hence, if we repeat this process, not only will the number of invalid people go down until 0, but the complexity will also be bounded by the number of people.

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

And when the COCI Contest #5?

→ Reply