Hello Codeforces!↵
↵
Japanese Olympiad in Informatics Spring Camp 2017 will be held from Mar. 19 to Mar. 25.↵
↵
There will be four online mirror contests during the camp. ↵
↵
- day1 : [Mar. 20 (00:30 — 05:30 GMT)](https://www.timeanddate.com/worldclock/fixedtime.html?day=20&month=3&year=2017&hour=00&min=30&sec=00)↵
- day2 : [Mar. 21 (00:30 — 05:30 GMT)](https://www.timeanddate.com/worldclock/fixedtime.html?day=21&month=3&year=2017&hour=00&min=30&sec=00)↵
- day3 : [Mar. 22 (00:30 — 05:30 GMT)](https://www.timeanddate.com/worldclock/fixedtime.html?day=22&month=3&year=2017&hour=00&min=30&sec=00)↵
- day4 : [Mar. 23 (00:30 — 05:30 GMT)](https://www.timeanddate.com/worldclock/fixedtime.html?day=23&month=3&year=2017&hour=00&min=30&sec=00)↵
↵
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 this year.↵
↵
There might be unusual tasks such as output-only tasks, optimization tasks, reactive tasks and communication tasks, just like International Olympiad in Informatics (IOI).↵
↵
Details are available in [contest information](http://cms.ioi-jp.org/joi-sp-2017/index-en.html).↵
↵
Good luck and have fun!↵
↵
↵
**UPD1:**↵
↵
We will use [CMS](https://cms-dev.github.io/) (customized version) on our server to hold the contests. The registration URL will be announced just before the first contest.↵
↵
Providing English statements is our first trial for this year, so there aren't past English problems. If you try past problems with Google Translate, you can get them from [here](https://www.ioi-jp.org/camp/index.html).↵
↵
**UPD2:**↵
↵
Registration is available now.↵
↵
- Contest page : http://cms.ioi-jp.org/contest/↵
- Ranging : http://cms.ioi-jp.org/ranking/↵
↵
**UPD3:**↵
↵
The contests are over. The judge is open now. You can submit your codes in the contest page.↵
↵
Unofficial Simple Editorial:↵
↵
- cultivation: East and West wind have almost the same effect. You don't have to consider the order. The essential value is the sum of the number of east and west wind. The candidates of this value are $O(N^2)$. You can easily calculate how many north wind and south wind needed to fill each column. The number of the essential columns are $O(N)$. So you can solve this by $O(N^{3} log N)$ or $O(N^3)$ with precalculate.↵
- port facility: Let's assume the containers nodes and make edges between the nodes which can't put on the same area. If this graph is bipartite, The answer is 2^(#connected compornent). Otherwise, the answer is $0$. First, count the connected component. Sort containers and use Segmenttree, then you can BFS with $O(N log N)$. You can check wheather the graph is bipartite by just simulating the transportation.↵
- sparklers: The first insights are you can do binary search the answer $v$, no two persons don't have to burn sparklers simultaneously and burning sparklers looks like an interval. If you can merge $[l,r-1]$ or $[l+1,r]$ and $( X_r - X_l ) / v \le ( r - l ) T$, then you can merge $[l,r)$. You can do some greedy algorithm to check you can merge $[0,n)$↵
- arranging tickets: Open the circle at point 0. You can use binary search by determining the answer $m$. You don't have to flip the interval $[a, b]$, $[c, d]$ such that $a < b < c < d$. So Filipped interval share some point t. Let's determin t and the number of flipped interval n. Actually, the candidate of $n$ is $m$ or $m-1$, the candidate of $t$ is leftmost and rightmost argmax $a_i$. You can greedily determin flipped intervals. ↵
- broken device: Divide bits into groups of size 3. There is a code of 3bits that translate 2 bit if intact, 1bit if 1 bit lost, 0 bit if more bits lost.↵
- railway trip: If you make edges to adjacent greater stations, It looks like a tree. You can use doubling to answer queries quickly.↵
- coach: Sort refilling points by $S_{i} mod T$ and passengers by by $D_i$ together. Each adjacent refilling points can purge passengers between them from the back. You can do DP and you can fasten DP by convex hull trick.↵
- long mansion: Let Llink_i be the rightmost $j$ s.t. $j \le i$ and $c_i$ is in $A_j$. Rlink_i is alike. Then JOI-kun can't go out from $[ l, r ]$ iff $Llink_r < l$ and $r < Rlink_l$. Let $Lret_r$ be min{ l | Llink_r < l and r < Rlink_r }. Then JOI-kun can't go from L to R iff there exists $r$ s.t. $L <= r < R$ and $Lret[r] <= L$. You can use segtree to speed it up.↵
- natural park: Let's consider the case of tree. You can add node one by one. First, you can determin wheter the node connects currect tree directly. If Yes, Number the tree nodes BFS order, then you can binary search which node connects the node directly. If No, binary serch a node between this node and the current tree, and solve recursively. In the case of general graph, you can solve with almost the same solution.↵
- abduction 2: Memoize. If you speed up finding the street with sparse table, you can get AC. Time complexity analysis is a little complicated. This margin is too narrow to contain. If you want to know, you shold read the Japanese editorial slide.↵
- city: Index the nodes by euler-tour order. Encode nodes by pair of the id and interval length. Sum of the number of the descendants of each nodes are at most 18 N. So most of the lengths are very small. Representing length like $1.05^n$ ( if you can't, add dummy nodes ) is very efficient in this case.↵
- dragon 2: Sort points by the angles from X. sweep them by the angle. Use segtrees or BITs to manage current points by the order of the angle from Y. You can now answer queries efficiently. Sqrt decompose queries by the size, you can solve with $O(N sqrt Q log N)$↵
↵
Japanese Olympiad in Informatics Spring Camp 2017 will be held from Mar. 19 to Mar. 25.↵
↵
There will be four online mirror contests during the camp. ↵
↵
- day1 : [Mar. 20 (00:30 — 05:30 GMT)](https://www.timeanddate.com/worldclock/fixedtime.html?day=20&month=3&year=2017&hour=00&min=30&sec=00)↵
- day2 : [Mar. 21 (00:30 — 05:30 GMT)](https://www.timeanddate.com/worldclock/fixedtime.html?day=21&month=3&year=2017&hour=00&min=30&sec=00)↵
- day3 : [Mar. 22 (00:30 — 05:30 GMT)](https://www.timeanddate.com/worldclock/fixedtime.html?day=22&month=3&year=2017&hour=00&min=30&sec=00)↵
- day4 : [Mar. 23 (00:30 — 05:30 GMT)](https://www.timeanddate.com/worldclock/fixedtime.html?day=23&month=3&year=2017&hour=00&min=30&sec=00)↵
↵
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 this year.↵
↵
There might be unusual tasks such as output-only tasks, optimization tasks, reactive tasks and communication tasks, just like International Olympiad in Informatics (IOI).↵
↵
Details are available in [contest information](http://cms.ioi-jp.org/joi-sp-2017/index-en.html).↵
↵
Good luck and have fun!↵
↵
↵
**UPD1:**↵
↵
We will use [CMS](https://cms-dev.github.io/) (customized version) on our server to hold the contests. The registration URL will be announced just before the first contest.↵
↵
Providing English statements is our first trial for this year, so there aren't past English problems. If you try past problems with Google Translate, you can get them from [here](https://www.ioi-jp.org/camp/index.html).↵
↵
**UPD2:**↵
↵
Registration is available now.↵
↵
- Contest page : http://cms.ioi-jp.org/contest/↵
- Ranging : http://cms.ioi-jp.org/ranking/↵
↵
**UPD3:**↵
↵
The contests are over. The judge is open now. You can submit your codes in the contest page.↵
↵
Unofficial Simple Editorial:↵
↵
- cultivation: East and West wind have almost the same effect. You don't have to consider the order. The essential value is the sum of the number of east and west wind. The candidates of this value are $O(N^2)$. You can easily calculate how many north wind and south wind needed to fill each column. The number of the essential columns are $O(N)$. So you can solve this by $O(N^{3} log N)$ or $O(N^3)$ with precalculate.↵
- port facility: Let's assume the containers nodes and make edges between the nodes which can't put on the same area. If this graph is bipartite, The answer is 2^(#connected compornent). Otherwise, the answer is $0$. First, count the connected component. Sort containers and use Segmenttree, then you can BFS with $O(N log N)$. You can check wheather the graph is bipartite by just simulating the transportation.↵
- sparklers: The first insights are you can do binary search the answer $v$, no two persons don't have to burn sparklers simultaneously and burning sparklers looks like an interval. If you can merge $[l,r-1]$ or $[l+1,r]$ and $( X_r - X_l ) / v \le ( r - l ) T$, then you can merge $[l,r)$. You can do some greedy algorithm to check you can merge $[0,n)$↵
- arranging tickets: Open the circle at point 0. You can use binary search by determining the answer $m$. You don't have to flip the interval $[a, b]$, $[c, d]$ such that $a < b < c < d$. So Filipped interval share some point t. Let's determin t and the number of flipped interval n. Actually, the candidate of $n$ is $m$ or $m-1$, the candidate of $t$ is leftmost and rightmost argmax $a_i$. You can greedily determin flipped intervals. ↵
- broken device: Divide bits into groups of size 3. There is a code of 3bits that translate 2 bit if intact, 1bit if 1 bit lost, 0 bit if more bits lost.↵
- railway trip: If you make edges to adjacent greater stations, It looks like a tree. You can use doubling to answer queries quickly.↵
- coach: Sort refilling points by $S_{i} mod T$ and passengers by by $D_i$ together. Each adjacent refilling points can purge passengers between them from the back. You can do DP and you can fasten DP by convex hull trick.↵
- long mansion: Let Llink_i be the rightmost $j$ s.t. $j \le i$ and $c_i$ is in $A_j$. Rlink_i is alike. Then JOI-kun can't go out from $[ l, r ]$ iff $Llink_r < l$ and $r < Rlink_l$. Let $Lret_r$ be min{ l | Llink_r < l and r < Rlink_r }. Then JOI-kun can't go from L to R iff there exists $r$ s.t. $L <= r < R$ and $Lret[r] <= L$. You can use segtree to speed it up.↵
- natural park: Let's consider the case of tree. You can add node one by one. First, you can determin wheter the node connects currect tree directly. If Yes, Number the tree nodes BFS order, then you can binary search which node connects the node directly. If No, binary serch a node between this node and the current tree, and solve recursively. In the case of general graph, you can solve with almost the same solution.↵
- abduction 2: Memoize. If you speed up finding the street with sparse table, you can get AC. Time complexity analysis is a little complicated. This margin is too narrow to contain. If you want to know, you shold read the Japanese editorial slide.↵
- city: Index the nodes by euler-tour order. Encode nodes by pair of the id and interval length. Sum of the number of the descendants of each nodes are at most 18 N. So most of the lengths are very small. Representing length like $1.05^n$ ( if you can't, add dummy nodes ) is very efficient in this case.↵
- dragon 2: Sort points by the angles from X. sweep them by the angle. Use segtrees or BITs to manage current points by the order of the angle from Y. You can now answer queries efficiently. Sqrt decompose queries by the size, you can solve with $O(N sqrt Q log N)$↵
