Hello Everyone!
Japanese Olympiad in Informatics Spring Camp 2019 will be held from Mar. 19 to Mar. 25.
There will be four online mirror contests during the camp.
 day1 : Mar. 20 (01:30 — 06:30 GMT)
 day2 : Mar. 21 (01:30 — 06:30 GMT)
 day3 : Mar. 22 (01:30 — 06:30 GMT)
 day4 : Mar. 23 (01:30 — 06:30 GMT)
The contest duration is 5 hours and there are 3 or 4 problems in each day. Problem statements will be provided both in Japanese and English.
There might be unusual tasks such as outputonly 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!
UPD: The link to the contest page is added. Schedule is updated.
Auto comment: topic has been updated by yutaka1999 (previous revision, new revision, compare).
Good Luck Coders ;)
Will there be mirrors after contest? The timezone isn't good for European programmers :(
since koosaga will make virtual participation to day 1 or day 2 of JOI spring camp , so I think there will be a mirrors after the contest.
I think it won't be a mirror but just an analysis mode of the contest with all problems available.
Unfortunately, there won't. But you can upsolve after the contests.
They traditionally opened judge servers, as far as my memory goes.
And, as my name is called, I'll also advertise it here: https://codeforces.com/blog/entry/66014
Will the japanese team be selected based on these 4 contests?
Definitely! The team will be selected practically just with the spring camp results.
I will participate in it and very looking forward to it :)
P.S. I, of course, want to compete even with open contestants, so I am really looking forward to seeing many open contest participants and I definitely recommend to participate. It's really a highquality contest.
good luck!
Good luck! And who are the other participants? :)
There are twentyone participants in JOI Spring Camp.
I don't list up because there are lots, but the list is available here in Japanese.
Four of them are participants (Japan 1 or 2 Team) of IOI 2018. It includes Masataka Yoneda (E869120) who got gold medal in IOI, and Hirotaka Yoneda (square1001), Koichi Namekata, and Yasutaka Hiraki.
But we still can't expect who will qualify... Final Round Winner and Runnerup was not IOI 2018 participants.
Auto comment: topic has been updated by yutaka1999 (previous revision, new revision, compare).
where is site and registration form?
They will eventually be on https://contests.ioijp.org/joisp2019/indexen.html.
A link to the registration page will appear on this page about 30 minutes before the beginning of the contest.
And the contest begins in about 35 minutes:
March 20, 2019 to March 23, 2019 10:0015:00 +0900 (JST) 01:0006:00 (UTC/GMT)
Edit: this is going by what is on the contest site, there is discrepancy with the blog...
But the time is 00:30 in the blog..
Sorry for the delay.
Today's contest will start in 01:30 in UTC, one hour after the initial plan.
still nothing
Why the contest site is still to be announced?
Will the lecture materials be available?
I'm curious that how did people solve problem "Meetings"? I heard many (at least three types) solutions, so I expect that many people solved in different ways.
Can you describe some solutions?
I've solved this contest in analysis mode, and it was really hard to push my solution to get OK (because it makes ~$$$41\,000$$$ queries)
I solved during contest, finally around 39100 queries (as I remember) in 17ary tree worst case.
First, if we ask $$$query(0, x, y)$$$, we get LCA of $$$x$$$ and $$$y$$$ when the root is $$$0$$$.
The first subproblem is that, assuming the graph is line graph and one edgepoint is $$$0$$$, find the graph in $$$O(V \log V)$$$. We can do it easily because we can simply sort by distance from zero because $$$LCA(x, y)$$$ will be $$$x$$$ iff $$$d(0, x) < d(0, y)$$$.
Then, let's return to main problem. Supposing that we fix $$$x$$$ and we ask $$$query(0, x, i)$$$ for all $$$i$$$, the set $$$S$$$ of return value will be all vertices in path from $$$0$$$ to $$$x$$$. We can get the order of path by solving subproblem. This routine takes $$$O(V + S \log S)$$$.
Then, thinking about distinguishing return value of $$$query(0, x, i)$$$, we can separate into the same problem for subtree. It works well if we decide the value of $$$x$$$ randomly.
I submitted this solution first and got 78 points with about 44000 queries, but doing somewhat optimization I got 100 points. E869120 has much more efficient algorithm (about 22000 queries, possibly more than expected solution), so I hope that he will write the solution there.
My randomised solution which gets ~25k queries on worst case 17ary tree:
Pick a random vertex as root. We will solve the problem recursively. We will pick a random vertex and find all vertices that belong to the path from the root to this random vertex by simply iterating over all vertices in this recursive call and doing a $$$query(root, randv, w)$$$. If the result of this query is $$$w$$$ we know that $$$w$$$ belongs to the path. If that's not the case we will add $$$w$$$ to a temporary set $$$S_{result}$$$.
After that we can find the order of the vertices on this path easily in expected $$$O(n \log n)$$$ with a "quick sort"like approach (pick a random vertex and divide the path into to new paths — one to the left of the vertex and one to the right).
Well finally we run the recursion with root equal to every vertex on the path and set of vertices equal to $$$S_v$$$, where $$$v$$$ is the vertex on the path.
I solved it during online contest. My solution works in about ~22k queries on 17ary tree(I'm not sure it is the worst case).
At first, there are tree with two nodes, 0 and 1. and there is an edge between them. from 2 to n1, we will add a node to tree. To add a node $$$u$$$, we can use centroid decomposition on current tree. Let the centroid of the tree is $$$m$$$. There are $$$k$$$ child of $$$m$$$, $$$v_1$$$, $$$v_2$$$, ..., $$$v_k$$$. Assume that the size of subtree is nonincreasing order, $$$Subtree(v_1)> ... > Subtree(v_k)$$$. Ask query $$$(u, v_1, v_2)$$$. If the answer is $$$u$$$, then $$$u$$$ is on the path from $$$v_1$$$ to $$$v_2$$$ and we can find the location of $$$u$$$ by one more query: $$$(u, v_1, m)$$$. If the answer is $$$v_1$$$, we can restrict the range to $$$Subtree(v_1)$$$, so we can do centroid decomposition on $$$Subtree(v_1)$$$ recursively. The case of $$$v_2$$$ is similar. If the answer is $$$z$$$, a totally unknown node, then make an edge between $$$u$$$ and $$$z$$$. $$$z$$$ is on the path from $$$v_1$$$ to $$$v_2$$$, so we can handle it similarly. If the answer of the query is $$$m$$$, then just move to query $$$(u, v_3, v_4)$$$, .. and so on. If the process is finished and can't find the location of $$$u$$$, then add an edge $$$(u, m)$$$.
18*18*8>2000, so I think 9+9+4 query is enough to last insertion. Also, former insertions needed smaller number of query.
After some hour struggling to solve Meetings problem, I suddenly realized that this problem is very similar to This Problem in CSAcademy, which I solved it before. The only difference between two problem is the constraints of input tree. (Meetings : max degree <= 18, CSAcademy problem : trees are generated with RNG) I copypasted my previous code and it gave me 100 points.
I'm not blaming the problem setters, (There are way too many problems in the world, and it is very hard to avoid the coincidence) but I just feel sad that I became more stupid than last year...
i woke up 4:00 am because of this contest and the contest started after 1.5 hour. So can someone tell me when is the second contest exactly ?
I don't know but I expect that it is 90 minutes after contest (10:30 — 15:30 UTC+9), because such information is written in contest information page.
How to solve day 1 naan?
I solve the small subtasks by a greedy approach but the numbers grow quickly and exceed the limit for the last subtask with the same solution.
I've used some __int128 + hack that if you want to make a fraction (A, B) with $$$B > 10^9$$$, just convert it to fraction
((A * 10^9 + B — 1) / B, 10^9).
Break the naan evenly(by happiness) into N pieces for each person.
Call p(i,j) as the position of the jth cut for the ith person The B of p(i,j) should be N*v<=2e8
Repeat j from 1 to N, take the smallest p(i,j) out of the remaining people and stop considering i afterwards
It is easy to see that it works (its just a slight modification to the greedy)
Has Day2 started yet? Or is it delayed
it starts in 13 minutes
how to solve day2 first problem antennas?
If it's not hard, could you please add all previous day's problems in the analysis session? yutaka1999
It should be OK now.
Could you please tell me what or in a better way, where is the analysis session you mentioned? :D
https://cms.ioijp.org/
Ahaa, Thanks!
Does this link works? (connects too long on my browser)
How to solve d2p1? To me, it seems the hardest problem in day 2..
BTW, p2 and p3 were interesting, too. Great contest!
It was hard but I guess not the hardest. Though hard to explain.
For each query $$$[L, R)$$$ I find $$$i, j$$$ $$$(L \leq i < j < R)$$$ which both can see each other and $$$H_i  H_j$$$ is maximum. (To solve the whole problem reverse the array and run this again)
In this way $$$i$$$th antenna can communicate with antennas in $$$[i+A_i, i+B_i+1)$$$ so make it two event. Add this antenna at $$$i + A_i$$$ and remove it at $$$i+B_i+1$$$. Set $$$c_i$$$ to $$$h_i$$$ if this antenna is present now and $$$inf$$$ otherwise. Set $$$d_i$$$ to currently maximum difference value $$$H_j  H_i$$$.
Now sweep from left to right and process events. After processing events till $$$j$$$, the answer for every queries $$$[l,j)$$$ is $$$min(d_l, d_{l+1}, .., d_{j1})$$$. Also for the $$$j$$$th antenna and every antenna $$$k$$$ which $$$j  B_j \le k \le j  A_j$$$ update $$$d_k$$$ to $$$max(d_k, c_k  H_j)$$$ (notice that if $$$k$$$th antenna is not present then $$$c_k$$$ is $$$inf$$$ and $$$d_k$$$ doesn't change).
We can implement changes to array $$$c$$$ and $$$d$$$ using segment tree with lazy propagation. So it's done in $$$O(nlgn)$$$ time complexity.
At "antenna k which j−Aj≤k≤j−Bj", shouldn't it be j−Bj≤k≤j−Aj ?
Yup. My mistake, thanks!
Will there be editorials in English after the camp has ended?
How to solve dishes from day 2?
I got 74 points in contest, and there was a little typo. I upsolved it.
Let $$$X[i]$$$ be maximum $$$j$$$ that satisfies $$$A[1]+A[2]+...+A[i]+B[1]+B[2]+...+B[j] \le S[i]$$$. Likewise, $$$Y[i]$$$ be maximum $$$j$$$ that satisfies $$$A[1]+A[2]+...+A[j]+B[1]+B[2]+...+B[i] \le T[i]$$$.
Put a blue point in $$$(i, X[i])$$$ with score $$$P[i]$$$ and red point in $$$(Y[j], j)$$$ with score $$$Q[i]$$$.
Order of steps can be represented by a path from $$$(0,0)$$$ to $$$(n,m)$$$ in lattice graph. $$$(i,j)$$$ means you already have done $$$i$$$ steps of IOI Donburi and $$$j$$$ steps of JOI curry.
For a path, the whole score of process is (sum of scores of blue points above or on the path) + (sum of scores of red points below or on the path).
It can solved directly with segment tree and lazy propagation in $$$O((N+M) log (N+M))$$$ time, but there are something to handle, so I tried to make it easier.
For each red point in $$$(x,y)$$$ with score $$$q$$$, make it blue and change its location to $$$(x+1,y1)$$$ and change its score with $$$q$$$. After this process, only blue point remains and the problem becomes easier. After calculate answer, you should add $$$q$$$ for each red point. Then you can get the same answer with original problem.
Only bluepoint problem can be solved by segment tree. Time complexity : $$$O((N+M) log (N+M))$$$ .
Is there a way to solve task "examination" from day 1 without 2D binary indexed tree?
use MO's algorithm
Can you elaborate a little bit? I don't really see how MO's algorithm is related to this problem.
you just put pointer 1 on A and pointer 2 on B, and maintain a BIT on a+b values
Then you just do like how you do it on regular Mo's
It can be solved by (CDQ) divideandconquer.
Sort all students and queries together by one of the 3 parameters. Recursively divide them into halves according to that parameter.
For each subproblem obtained from above, consider only students in one half, only queries in another half. Resort them together by one of the two remaining parameters. Then handle each of them by operations on a segment tree based on the last parameter.
you can use ordered_sets in segment tree.
Interesting solutions. Thanks.
Here is my method :
Represent students as points $$$(x, y)$$$ where $$$x = S_i$$$ and $$$y = T_i$$$.
In subtask 2, we want to know the number of such points in $$$Q$$$ infinite rectangles covering all points $$$(x, y)$$$ with $$$x \geq X_i$$$ and $$$y \geq Y_i$$$. Sort students/points by decreasing $$$S_i$$$. Sort rectangles by decreasing $$$X_i$$$ and process them in this order, adding step by step "new discovered points" in a 1D segment tree on ordinates.
After adding all "new points discovered with $$$x \geq X_i$$$", do a Range Sum Query on $$$[Y_i ; +\infty[$$$ to know the answer for this rectangle. Final complexity is $$$O((N+Q+Y_{max}) \log Y_{max})$$$.
Subtask 3 : Thinking on paper, we see that we're now querying the intersection of an infinite triangle and an infinite rectangle. I count the number of points in the "big triangle" and I substract the number of points in the "little triangle" below the rectangle. I use two segment trees, one on $$$T_i$$$ values, other one on $$$S_i + T_i$$$ values. It needs two different passes with different sorting. There are some rectangles which should be treated as in subtask 2 instead (when $$$Z_i$$$ is useless).
Substask 4 : I used dynamic segment tree, it's slow but it pass the TL.
Code : https://oj.uz/submission/102091
I got a solution:
Lets divide our queries into 2 types : a+b>=c and a+b<=c
\
\
\"This area is what we want"
\
\
 "limit A"
\
\"limit C"
"limit B"
and this is equal to area X — area Y
\
\
\"Area X"
\
 "limit A"
\
\
\"limit C"
\"Area Y"
\
\
\

\
\"limit C"
"limit B"
And it's easy to find Area X and Area Y(same technique as you find the answer for type 1)
I did manage to approach the problem till this point but I don't know how to go further. So we need compressed 2D BIT? Can you share your code so that I can learn from it?
no just sweeping line and 1DBIT( or treap or anything else)
for example, to get the size of Area X, you put all points satisfying limit A into your data structure, and ask how many of them is above limit C.
Someone asked me how to solve transportation. I'll leave it here.
No algorithm other than Dijkstra solves the problem even in $$$B = 0$$$, so it should be related. Dijkstra algorithm is inductive, which starts from the knowledge of $$$dist[0] = 0$$$ (Nearest vertex of 0 is 0 itself) and find the secondnearest, thirdnearest, and so on.
If both of them know the distance for $$$k$$$nearest vertex, how can they find which is $$$k+1$$$nearest? Usually, they are adjacent to some found vertex, but you don't have full information so it's not guaranteed. However, it turns out that one of two has a correct answer, which means, If they know the $$$k$$$ nearest vertex correctly, and they just relaxed to their best knowledge, then one of them has the answer. This fact is not hard to prove.
Now, you should communicate to know which is the $$$k$$$nearest vertex. Both should compare their candidates, and pick the one which gives smaller distance. You can do like this:
20 + 0 + 1 + 20 + 11 + 1 = 53. Also, initial stage requires 1 bits to wake A up.
Here goes the key idea: You don't need to spend 20 bits for distance. The distance for the new candidate will either be infinite or less than $$$maxDist + 500$$$ (when $$$maxDist$$$ is the maximum overall currently found distances). Thus you can just send the delta of distance (511 if its infinity).
9 + 0 + 1 + 9 + 11 + 1 = 31. Initial stage still requires 1 bits to wake A up.
Some constant optimization.
And you get WA cause you spend 58001 bits. Just prune somewhere. I pruned the first phase of distance sending.
Also, transportation is a cool innovation because now we can see, there can be a lot of problems like on distributed code jam at IOI format :)
We can improve the solution further by randomization into $$$(9*1.5+1+11)N=25.5N$$$ bits.
How?
Every round, we flip a coin to determine A or B send first. If A is sent first, and it's already less than B, we don't need to send B anymore. The expectation is $$$9+1+9*0.5$$$.
Ohh... that’s a nice trick (and a good alternative to constant optimization)
Поставь "Класс по братски"
Hi everyone, let's raise my contribution please))
what is solution for problem 1 or problem 2?
I assume you are talking about Day 3. Q1: Centroid Decomposition.
Choose a centroid, and assume you pick nodes from subtress of at least 2 children from it, or you pick the node itself.
Then you can do greedy, greedily pick the node that descreases the cost most. By some smalltolarge, you can compute the costs in O(size*lg).You then update the answer of [1,size], so solving a subtree is O(size*lg), and overall complexity is O(N*lg^2)
I think you need special handle for E=1, but shouldn't be trouble. For E>=2 we only pick leaves actually, but i don't see how to use that.
Q2: Simple DP.
Note that there exists a optimal solution that does all "set range" before "flip range". Also, all "set range" do not overlap itself, and same for all "flip range".
Consider that you have x "set ranges" and you have to open/close range for y "flip ranges". Then the cost is x+ceil(y/2).
Run DP from left to right, maintain dp[i][j], which is the minimum x+y you can do, for prefix i,
j=0: no "set ranges" are opened
j=1: You have opened a range for "set range to 0" and haven't closed it
j=2: You have opened a range for "set range to 1" and haven't closed it
Then you can do transition, as following:
I tried the best to explain :)
i got it, Thanks.
I have came up with solution of "Designated Cities" similar to you (greedy, with centroid decomposition $$$O(n \log^2 n)$$$), but there was more better solution explained by maroonrk in the editorial time of onsite contest. It was a geniuslike solution.
First, think about the query of $$$E = 2$$$. It can be solved by DP in $$$O(n)$$$. Then, realize that the designated cities of optimal solution for $$$E \geq 3$$$ completely includes the optimal solution for $$$E = 2$$$. Therefore, it means that greedy will work after we determined two vertices when $$$E = 2$$$. The time complexity is $$$O(n \log n)$$$.
how u r able to come up with such complex solutions
Problems from Day 3 are all available here: https://oj.uz/problems/source/378
How to solve Day4 Q1?
Sort by $$$C$$$. Let $$$F(i, j)$$$ be a max. possible cost obtained from interval $$$i, j$$$ (paying exactly $$$2(C_j  C_i)$$$ for circular tour). Let $$$opt(i)$$$ be the maximum $$$j$$$ such that $$$F(i, j)$$$ becomes maximum.
You can prove that $$$opt(i) \le opt(i+1)$$$, and you can calculate $$$F(i, j)$$$ in $$$O(\log N)$$$ using persistent segtree, thus you can use D&C optimization to solve the problem in $$$O(N\log^2 N)$$$.
How to prove that opt(i) <= opt(i+1)?
In fact you can solve it without persistent segtree. Using that fact, that if you will store two pointers at the current segement, and will move it during the D&C (and maintaining two sets, classic) it will be $$$O(n \log^2 n)$$$
Yes, I solved just like that and it is similar to IOI 2014 — Holiday.
How to solve day 4 Q3? My divideandconquer solution only gave me 40 points.
Erasing an element also provides your some information. So you don't need to erase everything in the set when you solved $$$[l, r]$$$ and want to solve $$$[l, mid]$$$ and $$$[mid+1, r]$$$.
You want to split some set into two halves. If one of them is full, you don't need to make a query to know which set it belongs to. To avoid hacks, random shuffle the set before making queries.
Do not set $$$mid = (l+r) / 2$$$, try something like this: $$$mid = l * ratio + r * (1  ratio)$$$.
My code
What is the reason not using 0.5 as $$$ratio$$$?
The real reason is $$$T(n) = T(x) + T(nx) + n + \min(x, nx)$$$.
With some careful implementations and dirty optimizations, we can make it into about $$$9.705 * 10^5$$$ queries for $$$n=43000$$$ and $$$9.952 * 10^5$$$ queries for $$$n=44000$$$.
My code
I'm not sure what the cause is, but when I download https://cms.ioijp.org/dataset/day4data.tar.gz and extract the file, the following error pops out:
Maybe your download was corrupted? It is working fine for me. Try redownloading.
It works now, probably the files were fixed
Please add them quickly. I am waiting for you to complete so that I can update OI Checklist :D
It would take some time to complete, because there are too many unusual problems this year and they cannot be automatically uploaded. I expect 24 weeks.
Its Ok. I just needed the links to update the list. Thanks. :)
Links are finalized, you may use them :)
Will there be editorial for all the problems?
What is the team that will go to IOI?