### yutaka1999's blog

By yutaka1999, history, 3 years ago,

Hello Everyone!

The 19th Japanese Olympiad in Informatics Final Round Online Contest will be held on February 9. (01:00 — 05:00 GMT).

The contest duration is 4 hours. There are five problems, which are the same as the 19th JOI Final Round. Problem statements will be provided both in Japanese and English.

The registration page will be announced 30 minutes before the contest start.

You can see details in the contest information page.

• +124

| Write comment?
 » 3 years ago, # |   0 Auto comment: topic has been updated by yutaka1999 (previous revision, new revision, compare).
 » 3 years ago, # |   +10 [Reminder] The contest will begin in 30 minutes!
 » 3 years ago, # |   0 Is the idea for D finding $O(N)$ interesting edges to test naively or is there a different way?
•  » » 3 years ago, # ^ |   +10 That's what I've done. O(M log M) ideaSince interesting edges lie in the shortest path tree of 1 or n, some smarts like this can be used to optimize?
•  » » » 3 years ago, # ^ |   0 How to solve the mentioned problem from JAG Practice Contest?
•  » » » » 3 years ago, # ^ |   +18 Google translating this may help
•  » » 3 years ago, # ^ | ← Rev. 2 →   +10 If you're still interested, I have a solution in $\mathcal{O}(n^3 + m\log m)$ (or $\mathcal{O}(n^3 + m)$, negligible). It passed on oj.uz in 96ms, so it's probably a fine (not too tight) solution: SolutionAs expected, for each edge we will compute the minimum path from 1 to n and backwards, if this edge was reversed. Let's focus just on the path from 1 to n. First, we run dijkstra (or floyd warshall) to find the shortest path on the given graph, let this path be $(v_1, \dots , v_k)$, where $k \leq n$. We will then run 2 floyd warshall's: $D_{i,j}$ denotes the minimum path from $i$ to $j$ on the given graph, $D'_{i,j}$ denotes the minimum path from $i$ to $j$ on the given graph, but without any of the edges on the minimum path found by dijkstra.For each edge $(u, v)$ with cost $c$, that is not on the minimum path: if we decide not to use it, then it is best to go on the minimum path we found (as it's just like removing the edge from the graph). If we decide to use it, then we can safely use the value $D_{1, v} + c + D_{u, n}$ (and compare it with the minimum path); even though $D_{1, v}$ might use the edge unflipped, if it did then the resulting value will be larger than the minimum path. Same with $D_{u, n}$.For each edge $(v_i, v_{i+1})$ with cost $c$, on the minimum path: if we decide not to use it, then, if we view the path as one that begins at $v_1$, ends at $v_k$ and sometimes leaves the minimum path (then returns), then we can claim it leaves the minimum path exactly once (it can't leave less since the minimum path is not a path after the flip):First, for all $x < y$, we won't leave the minimum path at $v_y$ and return at $v_x$; depending on whether $y \leq i, x \leq i < y, i < x$, we can get rid of one of these vertices (and this detour around the minimum path), and instead use a part of the minimum path (while the path still doesn't use the flipped edge). So now we know that all those jumps around the minimum path just cover contiguous, disjoint segments of edges in the minimum path. So any jump around a contiguous segment which doesn't contain the flipped edge can be replaced with that segment in the minimum path.This yields the simple solution: for each $1 \leq l \leq i, i+1 \leq r \leq k$, we consider the path with cost $D_{1,v_l} + D'_{v_l, v_r} + D_{v_r, n}$. We do this in $\mathcal{O}(k^2)$ for each edge on the minimum path, so $\mathcal{O}(k^3)$.And let's not forget, if we decide to use the flipped edge on the minimum path: well actually it will never be optimal: take any such path, and right before you use the flipped edge to go from $v_{i+1}$ to $v_i$, just instead use $D_{v,n}$, which is guaranteed to be shorter.So it's a very light cubic complexity.My submission (which is not meant to be readable, just for reassurance: https://oj.uz/submission/201505
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 I'm very late, but there is a lemma that somehow works (utility is significantly reducing coding time): The number of edges (u,v) with weight w [reversed to (v,u)] where dist(1,v) + w + dist(u,N) < dist(1,N) OR dist(N,v) + w + dist(u,1) < dist(N,1) is O(N). Is there a reason for this or is it just weak test data?
 » 3 years ago, # |   +14 You can solve all problems here: https://oj.uz/problems/source/477
 » 3 years ago, # |   +33 Btw, problems were very nice. It will be good for preparing the IOI. Thanks to the author!
•  » » 3 years ago, # ^ |   +89
 » 3 years ago, # |   -8 I submited my solution and i got 100/100 points but for my current score is 0 and in ranking it is 0 points, what is going on?
 » 3 years ago, # |   +5 How to solve problem 5 — Fire ?
•  » » 3 years ago, # ^ |   0 Please somebody, i can't understand the codes.
•  » » 3 years ago, # ^ |   +13 Basic Idea: For each index $i$ let $prev[i]$ denote the largest index less than $i$ such that $a[prev[i]] > a[i]$ (-1 if does not exist). Build the forest $prev[i] \rightarrow i$. Solve the queries offline and build the tree from left to right. Note that the nodes in the forest are labelled in dfs-order. For each edge in the forest, label it with the absolute difference in values (in array $a[]$) of its endpoints. Then, you can write the answer to a query as the sum of edge weight multiplied by min(subtree size of the child of the edge + some constant, T) where $T$ depends on query. This can be handled using several fenwick trees.Here's my submission: link
•  » » » 3 years ago, # ^ |   0 thanks i will try to understand
•  » » 3 years ago, # ^ |   0 My Solution is not the same as zscoder, but hope you understand it :) click
•  » » » 3 years ago, # ^ |   0 Hm cool , you post solutions only to relativelly difficult problems? or to easy ones too?
•  » » » » 3 years ago, # ^ |   0 I very recently (read: a week back) started posting solutions. So ill just post the ones which i have solved, which ranges from easy to hard.
 » 3 years ago, # |   0 Can someone explain me the solution of problem C?
•  » » 3 years ago, # ^ | ← Rev. 3 →   +18 1) Note that at any moment the set of visited cities is equal to some circular segment.2) You may assume that at any moment you are currently in one of the ends of that segment.Using these observations, we can solve the problem in $O(n^2 \cdot T)$ time using $dp_{l,r,where,time}$, where $l \ldots r$ denotes the circular segment of currently visited cities and $where$ is $0$ if you are currently at $l$ and $1$ if you are currently at $r$, and $time$ is the current time, and the value of this DP is the largest number of stamps that you can collect.After that, you can optimize this DP by changing the state of DP and the value, to optimize $O(n^2 \cdot T) \to O(n^3)$.Final DP will be $dp_{l,r,where,cnt}$ is the minimum time in which it is possible to be in the state $(l,r,where)$ as described before and collect $cnt$ stamps.
•  » » » 3 years ago, # ^ |   0 Thanks 300iq!!!