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

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

Hello Everyone!

Japanese Olympiad in Informatics Spring Camp 2018 will be held from Mar. 19 to Mar. 25.

There will be four online mirror contests during the camp.

The contest duration is 5 hours and there are 3 to 4 problems in each day. Problem statements will be provided both in Japanese and English.

There might be unusual tasks such as output-only tasks, optimization tasks, reactive tasks and communication tasks, just like International Olympiad in Informatics (IOI).

The contest site and registration form will be announced about 30 minutes before the contest.

Details are available in the contest information page.

We welcome all participants. Good luck and have fun!

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

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

This is too early for me, will contest be avaliable after it ends?

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

    Yes. We will open the judge server as analysis mode during the contest intervals (06:30 — 23:30 GMT).

    In addition to that, we will distribute contest materials, such as problem statements, solution codes, input data and output data, in the web page after the camp.

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

Is there a reason why Java submissions aren't allowed?

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

The contest will start in 15 minutes but why isn't the registration open?

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

How to find rectangle-avoiding shortest distance between two segments?

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

Is the solution for task construction with HLD ? How to solve this task?

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

    It's with Link-Cut Tree.

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

    Can you share your idea?

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

    I didn't post my idea since I didn't have the opportunity to submit solution (I was at camp during the actual contest so I couldn't code and submit my solution back then). Now that it's on oj.uz and I just passed it there I'll describe my solution. It's a bit sketchy since I didn't write a formal proof.

    We'll first read the entire tree and perform HLD on it so that each path is now a union of chains. Then, for each chain, we'll store the values in the chain naively, however we group consecutive equal terms together, so if there are C consecutive occurences of v, instead of storing C copies of v, we just store a pair (C, v).

    For each query, we can just naively go through each chain and store the compressed value-frequency pair in a vector and count the number of inversions in the vector using the standard solution, where V is the size of the vector. For each update, we go through the related chains and update the corresponding parts of the chain (for all chains except the last, we'll just clear the entire chain and replace it with (sz, v), where sz is the size of the chain.)

    The idea is that the number of pairs you actually consider should be amortized linear or around , so the solution works quite fast. I think it's provable by considering some cost function.

    Here's my submission.

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

      The proof can be done by HLD. Denote light edge as an edge which reduces the subtree size into half, and heavy otherwise. Call the edge “separator” if their each endpoint have different number.

      Every query passes the light edge at most lgN times. This is reasonably small, so it’s okay even if they are all separators.

      For heavy edges, they are the separator if the previous query was from the parent’s light edge. This means that O(sum of separator heavy edge) = O(sum of light edge). So this is also nlgn. Thus, we have only nlgn separators. I think the worst case can be achieved by playing in binary trees (although I didn’t really tried)

      Note that this explains why Link-cut tree operates in O(nlg^2n) operation. (After solving, I found that this is the exact proof that Tarjan & Sleator gave.)

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

How to solve B?

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

How to solve C?

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

    Order the points in decreasing order of x and let dp[N][M] be the answer for (N, M). Because of ordering we'll consider only the Nth row at transition. You have the following cases:

    1. Put two points with the equal row, there are possibilities to choose the columns, you go to state (N - 1, M - 2).

    2. Put any direction on any column, there are M possibilities to do this, you go to state (N - 1, M - 1).

    3. You don't put anything on this row and go to state (N - 1, M).

    4. You choose two points with equal column such that one of the rows is the Nth row, there are M·(N - 1) possibilities, you go to state (N - 2, M - 1).

    Clearly it's O(N·M).

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

I was only able to solve B in Day1, so here it is

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

    Can you tell how you discovered this solution and why we make odd intersection count?

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

      My solution was inspired by well-known "point-in-polygon" test. The point lies in polygon iff it intersects the polygon segment odd times. In this problem we want to fix the location of (0, 0) inside the polygon. This means we want to intersect the polygon segment odd times.

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

How to solve D?

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

Where can we see and submit problems now?

EDIT: Found it, it did not load for me for whatever reason.

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

Will today's contest be delayed?

UPD: No. The contest will start in about 10 minutes.

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

How to solve Worst Reporter 3?

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

    For the first guy, the table of movements is like (-1 , 0) , (D1 — 1 , Dn) , (2*D1 — 1 , 2*D1) ... (k*D1 — 1 , K*D1) ( where (x,y) denotes the position and time respectively) , note that from the second guy we can create the same table using the fact that " k*D1 — 1 + 2 >= D2 + 1 " -> k >= ceil(D1/D2) using the first table again and repeat this we can find that the second table is (-2 , 0) , (D1*ceil(D2/D1) — 2 , D1*ceil(D2/D1)) , ... ( k*D1 * ceil(D2 / D1) — 2 , k*ceil(D2 / D1)). We can do this recusivly and see that the i-th table looks like : (-i , 0) , (f(i) — i , f(i)) , ..., (k*f(i) — i , f(i)) , where f(i) = f(i-1) * ceil(D(i) /f(i-1)) and f(1) is D1 , now we can binary-search for every query the answer using the fact that the position increases with the i , and that we can know the position of the i-th guy in time t using only f(i) , Code

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

How to solve A from day2 ?

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

How to get a good score on Road Service?

I got 48 by doing dfs order and then adding an edge from 1 to every th vertex in the dfs order.

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

    Notice that a star graph has extremely low cost. I dissected the tree into K+1 small trees where the radius of each small tree is small. Then I build a star graph with the centres of the small tree. I scored 89. I think dissecting the tree wisely (maybe dp) can get a higher score because I only used greedy.

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

By the way, are we allowed to use google? I tried to find the first problem and succeeded, of course. However, when I went to submit it, there were only 2 seconds left which wasn't enough so deep inside I hope we were not supposed to use google and this kinda justifies everything :D

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

    I think not because in the CMS page it says that the rules is the same from the spring camp, but i don't speak japanese and can't read the spring camp rules, so i don't really know ¯_(ツ)_/¯

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

Is there a general method to deal with solving 2D recurrence?

A(i, j) = A(i - 1, j) * something1 + A(i - 1, j - 1) * something2

In other word, is it possible to solve A without access to Google or OEIS?

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

Day2A is really pointless (just like other two problems). After I found the recurrence I was sure that it will be in OEIS. So I stopped solving it, as it wasn't worth bothering more.

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

    For solving it with use of the internet we don't even need to find recurrence. The Second sample tells us "I'm not a famous number oeis me" and it is really enough. https://oeis.org/search?q=1310354&language=english&go=Search

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

    I don't know if Japanese students have access to Internet while doing the contest like us. If not, problem A is actually quite hard if you don't know about Eulerian number before.

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

      The problem is not about difficulty but about posing a very well-known problem which have resources in OEIS and Wikipedia

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

      For problems like this one can always look at the generating functions of the rows of A.

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

      The students do not have access to the Internet at all. One student solved it during the contest by finding the property somehow (I was curious, but I didn't understand his explanation). Anyway I don't think it's a really good problem personally, though.

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

I wonder how many JOIs there are in the JOI logo...

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

Is is possible that you leave server open for another week so we can upsolve problems (after camp)?

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

How to solve task 2 "Bitaro" ?

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

    Sqrt decomposition.

    If number of friends which won't come are — run the naive O(N) dp.

    Else we notice that in the furthest cities from a city, there is at least one which is not blocked. Well then we can simply store the furthest cities for each city.

    The overall complexity will be either if you carefully choose the comparison constant (we have because we merge the furthest cities with sorting).

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

    We precompute the longest distances for each vertex in time.

    For each query, if , we can solve it easily, otherwise we can use brute force in O(m) time.

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

    Can someone tell the problem?

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

How to solve Airline Route Map?

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

    My idea

    Spoiler

    I now got AC, and fixed the problem which caused RE

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

    A perhaps unexpected solution?

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

How to solve day3 C?

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

Problem "airline_route_map" has some solutions with 12 more vertices, when you can only transfer an UNDIRECTED graph (And I did in this way).

But actually, the problem doesn't shuffle the direction of your edges, so it is easier to solve it by transferring a "DIRECTED graph". And it needs only 11 more vertices.

UPD: according to azneyes 's solution above, only 1 more vertex is needed by transferring a "DIRECTED graph"

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

I have a long and complicated O(n4) solution for "Security Gate". It got 73 after the contest. Maybe we can squize it into TL, about 9s for the maximum test case. Code here

How to solve this problem in O(n3)?

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

Is "Candy" just greedy maintaining a set of components (i , i + 2 , ... , i + 2*k) ?

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

How to solve A from day 4 ?

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

How to solve Day4 C?

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

When will the official solutions be published?

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

Is the judging server down?

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

Will the tests be available after the contest?

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

Which four are selected for the Japanese ioi team ?

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

When the problems will be uploaded at ojuz?

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

Can someone please tell me how to solve day 4 interactive task Library? I find the problem very interesting but I can't solve it.

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

    I solved it in the following way: you want to find all the pairs of adjacent values (there are N-1 of them). When querying a set {s1, s2, ..., sN} out of which you already know some relations of adjacency, you can say whether there is some extra relation of adjacency between them. So what you can do is to find the pairs of adjacent values in increasing order of the maximum of the pair, in the following way. First, find the smallest i so that {1, 2, .., i} has at least an adjacency relation among them. By the minimality of i, you know i is part of that adjacency relation. Then you can binary search the greatest j so that {j, j+1, .., i} has at least one adjacency relation and then, from the maximality of j, you get that j and i are adjacent. So you have 2 binary searches for determining each adjacency relationship, which leads to an overall of O(NlogN) operations, precisely, 2NlogN.

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

    Here's my solution :

    Suppose we query a set S and its complement S' (with respect to some contiguous segment [l, r]). Then, if one of the answers is bigger, we know that the first and last element of the segment [l, r] is in the set with the larger answer. Otherwise, the first and last element of the segment are in different sets.

    For each i, let Si denote the set of valid values with i-th bit equal to 1. Then, query Si and Si' for each i. Thus, if we let x, y denote the value of the leftmost and rightmost element in the current interval respectively, we can find in queries. Let .

    Let V be the set of valid values such that if , . With a binary search, we can use another queries to find the value of one end of the interval from V. Finally, we get the values of x and y, but don't know which is which. Just query one of them with the element before the interval to determine this.

    We used queries to determine the positions of 2 elements, so this works in the limits (in fact the bound is not tight since when the interval is smaller, the binary search takes less queries).

    See my code for more information.

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

      Thank you very much.

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

      zscoder , radoslav11

      after looking ur ideas and thought process , sometimes i think that you both being red coder developed so high and intutitive ideas to solve complex problems ..

      it symbolizes that ur level is very high .. but main question is , if your level is that much then what would be the level and mind powers of tourist and legend Petr

      hmm .. out of my reach even to think that

      kya vijju bhai sahi kahe na vijju123

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

What is the intended solution of Day2A?

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

i know it's late now but can anyone tell me how to solve Day 4 problem 2 Mergers ? Here is the link

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

    Observe that if the tree is separable, there exists atleast one edge such that there is no state which appears in both subtrees resulting from the deletion of that edge. Let's call all these edges "bad".

    For all edges $$$(u, v)$$$ that are not bad, merge $$$u$$$ and $$$v$$$ into one node. You have a resulting tree now such that all edges are bad. You can perform operations of the form: take any two nodes $$$u$$$ and $$$v$$$, colour all edges on the path from $$$u$$$ to $$$v$$$. Using minimum number of these operations, we need to colour all the edges of this new tree.

    It is easy to see that each leaf node of this new tree will be included in atleast one operation in order to colour its parent edge. Hence, the minimum number of operations needed is $$$\lceil\frac{leaf}{2}\rceil$$$, where $$$leaf$$$ is the number of leaves in the condensed tree.