Xellos's blog

COCI 2013/14: Round #3
By Xellos, 10 years ago, In English

I'm surprised there's no blog post to this... just so nobody misses it:

Round 3 of Croatian Open Competition in Informatics takes place at this time today, and lasts 3 hours.

You can log in to the contest site at evaluator.hsin.hr, or register an account there if you don't have one already. Make sure to select the right contest from the list when logging in — it's not HONI, but COCI.

Everything related to the contest should be posted here in a few weeks' time (except the solutions, it seems).

Feel free to discuss the problems here after the contest is over.

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

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

Isn't KOLINJE solvable in linear?

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

    Yeah, it should be, and easily. I don't know why the constraint on N is so low. Maybe preparing people for FB Hacker Cup and its fake constraints :D

    I failed most tests on it, though — because I didn't write long long instead of int once. Punishing such silly mistakes excessively is the main unfairness of contests without feedback...

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

How to solve 6th problem?

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

Is the idea of the sixth problem to maintain a set of slopes (convex hull method) to find the nearest covered points to the left and right of each building?

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

    My idea involved keeping a convex hull of a decreasing sequence of buildings seen so far, from which one of those points can be directly extracted. But it should work with a structure for set of slopes as well, since it's not much different.

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

Test are very simple on KOLINJE!

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

Anyone know how to you solve 5th problem?

I could wait for the official solutions, but yeah they're a bit slow with them.

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

    Suppose that you're counting the "difference" of 2 numbers, X and Y. How many times will the i-th digit of X be equal to x? And how many times will that digit of Y be equal to y? You can count that (it's actually the same result for X and Y if x = y), and from it count how many times will you count |x - y| into the result. Loop that over all x, y and i.

    How to count how many numbers in the interval [A, B] have x as the i-th digit? That interval is the difference of [0, B] and [0, A - 1], and so are the answers, so let's just take A = 0. Well, if the part of the number before the i-th cipher is strictly smaller than in B, we can choose all digits from i + 1 to last position to be anything from 0 to 9; it can't be larger, and if it's equal, the part of the number after the i-th position must be  ≤  to that in B. Using modular arithmetic, it's not hard to count it using this.

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

repetition

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

The full results are up in the system.

→ Reply