Dinar_Gumirov's blog

Invitation to APIO 2018 Open Contest
By Dinar_Gumirov, 7 years ago, In English

Hello everyone!

Innopolis University (Innopolis, Russia) will organize the Asia-Pacific Informatics Olympiad (APIO) 2018. APIO is an IOI-like competition for delegations within the South Asian / Western Pacific region. The official contest will be held online from 12th to 14th of May, with students competing at contest sites within their own country or area.

We invite everybody to take part in APIO 2018 Open Contest from 15th to 17th of May 2018!

You can start the contest at any time, from 00:00 on May 15, 2018 till 00:00 on May 17, 2018 (UTC+0). The contest will run for five hours, it will be proposed to solve 3 tasks.

The supported languages are C11, C++14 and Free Pascal. Task statements will be available in English, Chinese (Simplified), Chinese (Traditional), Hebrew, Japanese, Korean, Mongolian, Russian, Thai, Turkish and Vietnamese, with many thanks to the leaders of the respective delegations for providing task translations. You can find additional information on the official site APIO2018. Unfortunately, clarifications will not be available during the open contests.

Problems prepared by niyaznigmatul, qwerty787788, budalnik, izban, PavelKunyavskiy, pashka.

In order to take part in APIO 2018 Open context, please register via link.Registration will be closed on 14th of May. Once registrations close, you will get a username and password to log in to the contest site by email.

Olympiad will be held via contest management system PCMS2.

Looking forward to your participation!

APIO 2018 Organizing Committee

UPD: We have good news: if you want you can continue to solve problems until 24th of May. But the result will be unofficial and we won't count your new submits in the scoreboard.

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

»
7 years ago, # |
← Rev. 2   Vote: I like it +15 Vote: I do not like it

Will you publish an Editorial after end of the Olympiad?

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

    Organizing Committee won't publish an editorial after the end of the Olympiad. We will publish the tasks, tests and author's solutions on APIO2018 website.

    I will give a link for the Olympiad materials here.

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

Will test data be available after contest? Hopefully this year won't be like the last :P

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

    Everything will be allright:)

    We will publish the Olympiad materials until 20 of the May

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

looked for this types of challenges..thanks :D

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

Hello, I've already registered 2 days ago. But until now, I didn't get username and password for the contest. Are user and password will be given after registration closed?

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

    Hi, you will get a username and password after the registration closes. I think,we will send all necessary information at 7-8pm(UTC +3).

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

Can those who gave APIO discuss scores if not solutions?

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

So what about the unofficial results?

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

Unofficial results?

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

I'm having a few questions about my solution. Can I post them here now?

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

So it seems that the online mirror has ended. How to solve 2nd and how to get 1st (I know how to do but it won't be fast enough for last subtask).

Also what's wrong with following solution for 3rd: Compress to bcc. If there is a bridge add esge between the two components. If there is a articular point, split the component such that the AP becomes a new component. Now we have 3 cases — the free vertices are in the same component, 2 vertices are in the same component and all 3 vertices are in different components. This can be done with a couple of DFS-es on the compressed tree. This solution passed for 66 points. Did anyone get AC with a similar idea.

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

    why do you need to split on AP btw? because.. in any case.. after creation of a bridge tree, there will be no case that is not eliminated by the bridge tree but eliminated by the AP-splitting. What i mean is.. if S,F where on different sides of AP then its all good. And even if they are on the same side, We can still go form S, through the AP(which is taken to be C) and then to F, without revisiting. if we were indeed revisiting, then that means there was only one path.. which is again a bridge, and so that case is already eliminated by the bridge tree.

    Please correct if wrong.

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

    Sorry for my poor English

    2nd problem can be solved in the following way: First, consider how to solve subtask 4(all circles have the same radius R): We can divide the Cartesian plane by square with R*R. Then, for each circle i that has not been removed yet, let's denote the circle i in block x_i, y_i. Other circles which might be removed by circle i must be in block ( x_i ± 2 , y_i ± 2 ).

    Now, let’s try to solve the whole task. Let’s denote one operation as: one circle i remove other circles in blocks ( x_i ± 2 , y_i ± 2 ). First, let’s sort the circles by the radius. Let’s divide the Cartesian plane with R = r_max. Then do the operation. If the operation had be done more than 1024 times and now the current r * 100 <= r_max. Then we set r_max = r and divide the Cartesian plane with new radius r_max again. The source of parameter 1024 and 100 is found during the contest. (If the parameter 1024 is changed to 3000 or more, it will TLE on test 88).

    I got AC on 2nd problem by the above method.

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

    Instead of dividing into R*R blocks, we can divide blocks using logs.

    Assume that at first, we have one big block, with coordinate [0,0] to [2^32, 2^32]

    At each query, we can just divide each block into 2*2 smaller block until the side of each block is as small as possible but still bigger than current R. The rest of the solution is same as yp155136's one.

    Please note that the division step can be done quickly using bitwise operator, combined with the idea of radix sort (base 2)

    By using this method, we do not need to find the "magic" value for each division.

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

    For Prob C, I got AC with an idea similar to radoslav11, however, I connect every nodes in one BCC to a virtual nodes so that I need to do DFS just one time.

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

As I said above, I have a few questions about my solution for the 1st problem.

During the contest, I came up with a O(N * log * log) solution with a segment tree where each of its node is a set. And I known that my solution was much slower than the author's one but 5 seconds for time limit made me believe that it would pass.

But not as I expected, my solution was only able to pass N < 60000 subtasks and got TLE with others. So I accepted that my solution was too slow and tried to solve the two first N < 300000 ones in O(Nlog).

And again, I got TLE. But what make me confused is I passed only one of them.

So I want to ask if the test cases for the first N < 300000 was weak and why a simple O(Nlog) solution with segment tree can not pass the problem in 5 seconds time limit. Thanks for reading.

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

    What was your approach?

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

      First of all, sorry for my poor English.

      I sorted both the stores and queries in increasing order of the year.

      In a simple approach, for each of K types of stores, we'll maintain a set of the stores and we only need to binarysearch for its closest store in the set for each query.

      Let's call the set K closest stores of K different type to the position x is s(x). Now we'll have to maintain a segment tree which can maintain min(s(x)) and max(s(x)).

      If K = 1, it would be easy to insert and delete stores from by just implementing a lazy propagation segment tree.

      If we only delete stores, we can use a max-min segment tree.

      But for the last subtask, since we only need to know the min(s(x)) and max(s(x)), for each node p on segment tree which covers the range [L, R], we'll maintain a set of stores T(p) such that if a store r is in T(p) then r is also in s(i) with every L <= i <= R. We can easily see that we don't need to perform lazy updates on this segment tree. For each inserting and deleting update on range [X, Y], we should stop going deeper inside subtree p if X <= L <= R <= Y and perform the update on T(p). Then for each asking query of postion x, we can calculate the answer with every node p such that L <= x <= R.

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

        You can actually remove the set, using 2 priority queues and 2 vectors to keep the things you should erase. This way it should be much faster. Thanks btw.

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

          Actually, I thought about that during contest, using priority queue for pair < position, the index of the store >. But since I was not able to pass the O(Nlog) one, I gave up the contest.

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

When'll the organizing committee publish the dataset ?

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

Shouldn't a N*root(N) solution pass for 30 points in problem 2? I tried it but somehow got TLE.
Code: https://pastebin.com/kC1u1tEv

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

    Just imagine when vec.size()>=blocksize happens all the time. This is pure n^2.

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

As usual, all the tasks are ready for judging: https://oj.uz/problems/source/326

Thanks for authors providing a Polygon package, it was really helpful! We hope we could also able to upload APIO 2017 too.

UPD: We mistakenly uploaded tests wrongly (slightly wrong), and we rejudged every solution. Maybe your score has been changed. Sorry for the inconvenience caused.

→ Reply