### joisino's blog

By joisino, history, 11 months ago, ,

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.

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
•

 » 11 months ago, # |   +109 This is too early for me, will contest be avaliable after it ends?
•  » » 11 months ago, # ^ | ← 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.
 » 11 months ago, # |   -147 ....................../´¯/) ....................,/¯../ .................../..../ ............./´¯¯/'...'/´¯¯·¸ ........../'/.../..../....../¨¯\ ........('(...´...´.... ¯~/'...') .........\.................'...../ ..........''...\.......... _.·´ ............\..............( ..............\.............\... 
 » 11 months ago, # | ← Rev. 2 →   +15 Is there a reason why Java submissions aren't allowed?
 » 11 months ago, # |   +31 The contest will start in 15 minutes but why isn't the registration open?
•  » » 11 months ago, # ^ |   +15 So... Delayed 30 minutes. The contest duration will be 1:00 — 6:00 GMT.
•  » » » 11 months ago, # ^ |   +15 When will the registration be open?
•  » » » » 11 months ago, # ^ |   +15 It is already running.
 » 11 months ago, # |   +33 How to find rectangle-avoiding shortest distance between two segments?
 » 11 months ago, # | ← Rev. 2 →   +15 Is the solution for task construction with HLD ? How to solve this task?
•  » » 11 months ago, # ^ |   +11 It's with Link-Cut Tree.
•  » » » 11 months ago, # ^ |   +36 I have an O(nlognlogn) with binary lifting and segment tree
•  » » » » 11 months ago, # ^ | ← Rev. 2 →   0 Can you please give more detailed explanation and maybe your implementation?
•  » » 11 months ago, # ^ |   +2 Can you share your idea?
•  » » » 11 months ago, # ^ |   0 After seeing 300iq idea i realized that my approach is wrong :/
•  » » 11 months ago, # ^ |   +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.
•  » » » 11 months ago, # ^ |   +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.)
 » 11 months ago, # |   +6 How to solve B?
 » 11 months ago, # |   0 How to solve C?
•  » » 11 months ago, # ^ | ← 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 4·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).
 » 11 months ago, # | ← Rev. 3 →   +33 I was only able to solve B in Day1, so here it is Day1BPick any half-line from (0, 0) (better random, to avoid collinear case). Now you should find a cycle that crosses such line odd times. It can be solved by Dijkstra or Floyd-Warshall. Be careful for implementing line segment intersection.Some cute test cases that helped me so much : TC1 (N = 1)1 10 -100 11 100 11 Answer is 62. (Try this for every 4 direction) TC2 (N = 8)8 10 9 11 11 9 -9 -11 -11 -9 9 -11 11 -9 -9 11 -11 9 11 11 11 11 -11 -11 -11 -11 -11 11 -11 11 11 -11 11 -11 Answer is 72.
•  » » 11 days ago, # ^ |   +3 Can you tell how you discovered this solution and why we make odd intersection count?
•  » » » 11 days ago, # ^ |   +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.
 » 11 months ago, # |   -16 How to solve D?
 » 11 months ago, # | ← Rev. 2 →   -8 Where can we see and submit problems now? EDIT: Found it, it did not load for me for whatever reason.
 » 11 months ago, # | ← Rev. 2 →   +16 Will today's contest be delayed?UPD: No. The contest will start in about 10 minutes.
 » 11 months ago, # |   0 How to solve Worst Reporter 3?
•  » » 11 months ago, # ^ | ← 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
 » 11 months ago, # |   0 How to solve A from day2 ?
•  » » 11 months ago, # ^ |   0
•  » » » 11 months ago, # ^ | ← Rev. 5 →   0 Can you explain the intuition behind this? (how can i solve for 100/100 without OEIS?)
•  » » » 11 months ago, # ^ |   0 So we just insert n and n - k in eulerian number formula and that's it?
 » 11 months ago, # |   +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.
•  » » 11 months ago, # ^ |   +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.
 » 11 months ago, # |   +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
•  » » 11 months ago, # ^ | ← 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 ¯_(ツ)_/¯
•  » » » 11 months ago, # ^ |   +8 Then it's all good. sigh
 » 11 months ago, # |   +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) * something2In other word, is it possible to solve A without access to Google or OEIS?
•  » » 11 months ago, # ^ | ← Rev. 3 →   -48 Yes. This link may help you!Edit: This doesn't answer the question. You can still use the same idea to find a generating function though. This link is an example.
•  » » » 11 months ago, # ^ |   +6 That is for linear recurrence, not 2D recurrence.
•  » » » » 11 months ago, # ^ |   -9 Oh true. I completely misread the question. Oops
 » 11 months ago, # |   +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.
•  » » 11 months ago, # ^ |   +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
•  » » 11 months ago, # ^ |   +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.
•  » » » 11 months ago, # ^ |   +15 The problem is not about difficulty but about posing a very well-known problem which have resources in OEIS and Wikipedia
•  » » » 11 months ago, # ^ |   -39 For problems like this one can always look at the generating functions of the rows of A.
•  » » » 11 months ago, # ^ |   +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.
 » 11 months ago, # |   +7 I wonder how many JOIs there are in the JOI logo...
 » 11 months ago, # |   +31 Is is possible that you leave server open for another week so we can upsolve problems (after camp)?
 » 11 months ago, # |   0 How to solve task 2 "Bitaro" ?
•  » » 11 months ago, # ^ | ← 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).
•  » » » 11 months ago, # ^ |   +3 Using merge sort can avoid .
•  » » » » 11 months ago, # ^ |   +8 for this problem,I think nth_element() function is a good choice...
•  » » 11 months ago, # ^ | ← 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.
•  » » » 11 months ago, # ^ |   0 mlgn is a typo, right?
•  » » » » 11 months ago, # ^ |   0 fixed.
•  » » 11 months ago, # ^ |   0 Can someone tell the problem?
 » 11 months ago, # |   0 How to solve Airline Route Map?
•  » » 11 months ago, # ^ | ← Rev. 2 →   +5 My idea SpoilerWe assume that N <= 511. Make 12 additional nodes : 0 ~ 9 : connects with every node that have i-th bit on in it's number 10 : connects every non-additional node (degree N) 11 : connects every node beside 10th additional node (degree N + 10) Also, make an edge that connects i-th additional node to (i+1)th additional node, for 0 ≤ i ≤ 8. 11st node have degree N + 10, which is the highest. (Other node can have at most 8 + N-1 + 2 adjacent node, because they have at most 8 bits on) Thus, Bob can find that node. After that, Bob can easily find 10th node too. After that, Bob can also find the set of 0~9th node, which is tied in the length-9 chain.0th node's degree is always greater than 9th node for N ≥ 3, so you can tell every node's number in the chain. Now, it's easy to retrieve full information in graph.Now, if N >= 511, there can be a node that have at most 9 bits on. However, we can always relabel such node to another number with at most 8 bits on. Because there are only 11 such numbers with 9 bits on, in range 0 ~ 1023. I now got AC, and fixed the problem which caused RE
•  » » » 11 months ago, # ^ |   0 Thanks :)
•  » » 11 months ago, # ^ |   +86 A perhaps unexpected solution? SpoilerI solved with only 1 extra vertex ...For all given edges make sure A_i < B_i and swap if not. Send all edges to Bob. Add extra vertex N. If edge (v, v+1) does not exist send it and also send (v, N). Also send (N - 1, N)On Bob's side, run topological sort to recover the permutation that shuffled the vertices. The order is unique due to extra edges sent. If (v, N) is an edge than (v, v+1) was an extra edge so we don't include these in output.
 » 11 months ago, # | ← Rev. 2 →   +10 How to solve day3 C?
 » 11 months ago, # | ← 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"
 » 11 months ago, # |   +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 hereHow to solve this problem in O(n3)?
•  » » 11 months ago, # ^ |   -38 Lol if you don't know, how can we?
 » 11 months ago, # | ← Rev. 2 →   +1 Is "Candy" just greedy maintaining a set of components (i , i + 2 , ... , i + 2*k) ?
 » 11 months ago, # |   +8 How to solve A from day 4 ?
•  » » 11 months ago, # ^ |   +9 I think it is almost the same with APIO 2007 Backup.
 » 11 months ago, # |   +1 How to solve Day4 C?
 » 11 months ago, # |   +31 When will the official solutions be published?
 » 11 months ago, # |   +4 Is the judging server down?
 » 11 months ago, # |   0 Will the tests be available after the contest?
 » 11 months ago, # |   +16 Which four are selected for the Japanese ioi team ?
•  » » 11 months ago, # ^ |   +14 Japan 1 Team: WA_TLE [1st], 193s [2nd], Kmcode [3rd], Hoget157 [4th] Japan 2 Team: E869120 [5th], square1001 [6th], Pulmn [7th], hirakich1048576 [8th] Japan is the host country of IOI 2018, so Japan can elect 2 teams. One is official, and the other one is unofficial.
•  » » » 11 months ago, # ^ |   +13 Congratz, can we find the full scoreboard somewhere?
 » 11 months ago, # |   +27 When the problems will be uploaded at ojuz?
•  » » 11 months ago, # ^ |   +33 Right after https://www.ioi-jp.org/camp/2018/2018-sp-tasks/index.html becomes available?
•  » » » 11 months ago, # ^ |   +10 You can submit “batch” problems here: https://oj.uz/problems/source/312 We are working for library and airline_route_map right now. We are not sure whether we will open road_service or not (probably we would)
•  » » » » 11 months ago, # ^ | ← Rev. 2 →   +20 library is ready too: https://oj.uz/problem/view/JOI18_libraryWe implemented our version of grader and interactor because it seemed the given grader was too easy to exploit (for example, it seemed possible to rewind the standard input) If you find any bugs while evaluating your submission, please report us.
•  » » » » 11 months ago, # ^ | ← Rev. 2 →   0 sorry, my mistake
•  » » » » 11 months ago, # ^ |   0 airline_route_map` is partly ready now: https://oj.uz/problem/view/JOI18_airlineWe checked that the grader/interactor works correctly on the unexpected solution and two independent full score solutions. However, the model solution gives WA [12] or WA [14]. I tried to investigate what's going on, but we can't find any evidence that our grader is wrong. If you have your accepted/partly accepted solution, we would be really appreciated if you submit your code and check if the score is consistent. Thanks in advance :)
 » 11 months ago, # | ← 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.