Noam527's blog

By Noam527, history, 20 months ago, In English,

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

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

»
20 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

  • »
    »
    20 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    What is your strategy to pick high points from B?

    • »
      »
      »
      20 months ago, # ^ |
      Rev. 2   Vote: I like it +5 Vote: I do not like it

      I had many cases. I managed to convert some to others to shorten my work, but still there were many left. I believe my solution is optimal, because for all cases the polygon I build has 0 points inside (besides the case where a = b = 0, where I'm not sure if what I did was optimal but it seems so).

      I'll probably share it, later though.

      Edit: I got most of the tests right, on all others I recieved "Invalid number of segments of some type"... I guess I need to bugfix now :P

      • »
        »
        »
        »
        20 months ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        Seems you got 30) Can you please now eleborate your solution?

»
20 months ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve paprike?

»
20 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
20 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Results are available!

»
20 months ago, # |
  Vote: I like it -17 Vote: I do not like it

Can C be solved with antipodal points and segment tree?

»
20 months ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve C,D?

»
20 months ago, # |
  Vote: I like it +12 Vote: I do not like it
Spoiler
  • »
    »
    20 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Can you explain much about Coordinate Compression?

    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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

  • »
    »
    20 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

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

      Spoiler
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    20 months ago, # ^ |
    Rev. 4   Vote: I like it +5 Vote: I do not like it

    fixed

  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How can I deal with the error 'The response parameter is missing' when I'm registering. Thanks.

    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It seems it is because we use reCAPTCHA for registering :( I cannot find a good way to avoid it.

»
20 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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.