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

Автор Noam527, история, 9 лет назад, По-английски

Hey!

I am not related to the organization of this competition, however there doesn't seem to be any blog post regarding it (and there's not much time left), which is unfortunate so that's why I'm writing this :).

Today (in approximately 4.5 hours, 14:00 UTC) starts this year's COI — Croatian Olympiad in Informatics. The contest is open and the registration page is here (while this page contains a redirect to the registration, along with their past problemsets).

The competition should be close to IOI style; It seems to contain ~4 problems and from what I understood, has a duration of 5 hours. A big difference is that there is no full feedback during the contest: every submission is only tested on the samples provided during the contest (I would expect them to change this format for COI but it doesn't seem to be the case).

Good luck! Let's discuss the problems and the solutions here after the contest ends :).

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

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

I put all my time into B (after finishing A though it might be wrong/have corner cases, as I did not prove it)... so my score wouldn't be high but I had a lot of fun. Hopefully I'll get something high on B (hopefully there won't be bugs...).

Regarding C and D, I'd like to know how people solved C (for 100 points). As for D, I still want to think about it.

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

How to solve paprike?

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

Deleted. I thought B was finding max area polygon. Stupid..

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

Results are available!

»
9 лет назад, скрыть # |
 
Проголосовать: нравится -17 Проголосовать: не нравится

Can C be solved with antipodal points and segment tree?

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

How to solve C,D?

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +12 Проголосовать: не нравится
Spoiler
  • »
    »
    9 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +3 Проголосовать: не нравится

    Can you explain much about Coordinate Compression?

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

      Our circular arcs (let’s just say “queries” from here) have at most O(n+q) distinct endpoints — where the rewards decrease or increase. This means we don’t have to consider all real numbers but a query’s endpoints, or any point arbitrarily close to them.

      So if we consider all queries offline, we will use coordinate compression in those endpoints, which can be represented with vectors from origin — essentially a integer pair, that can be compared with angular sorting.

      In my code, I used some tricks to ease implementation. Code

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

    What do you mean by "(numbers < i && !jPx) i (numbers < i && jPx) (numbers > i)" in problem D?

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

      I think it's better to attach my code doing that part :

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

    sorry to bother, Can you explain how do we greedy in pA :(((

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

You can submit all problems here: https://oj.uz/problems/source/311

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

Problem B (Pick) Super ad-hoc problem. Many cases have a polygon that does not have any inner points. Find a base shape type 1~4. Grow to the right using a. Grow to the up using b, c, and d.

Type 0: a, b, c, d = 0, 0, 2r, 2s. c and d are positive. Corner case that is given sample input 2.

Type 1: a, b, c, d = 2p, 2q, 2r, 2s. a and b are positive.

Type 2: a, b, c, d = 2p, 2q, 2r, 2s. a and c are positive.

Type 3: a, b, c, d = 2p, 2q, 2r + 1, 2s + 1. a, c, and d must be positive.

Type 4: a, b, c, d = 2p + 1, 2q + 1, 2r + 1, 2s.

Otherwise, swap(c, d). It is mirrored problem with a line x = 0. More otherwise, swap(a, b). It is mirrored with a line y = x. I think there is no polygon for remaining cases, but I don’t have proof.