Блог пользователя Xellos

Автор Xellos, 11 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +40
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

Isn't KOLINJE solvable in linear?

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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...

»
11 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

How to solve 6th problem?

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

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?

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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.

»
11 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Test are very simple on KOLINJE!

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Anyone know how to you solve 5th problem?

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

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    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.

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

repetition

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Как решалась задача PAROVI ? Никакая идея не пришла в голову. И пожалуйста, по возможности на простом языке можно объяснение, так как я начинающий?

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Сверху предлагают на английском.

»
11 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

The full results are up in the system.