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.

So... Delayed 30 minutes. The contest duration will be 1:00 — 6:00 GMT.

It's with Link-Cut Tree.

Can you share your idea?

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.

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 N^th 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 N^th row, there are M·(N - 1) possibilities, you go to state (N - 2, M - 1).

Clearly it's O(N·M).

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

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

https://en.wikipedia.org/wiki/Eulerian_number

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.

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 ¯_(ツ)_/¯

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.

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

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.

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).

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.

Can someone tell the problem?

My idea

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

A perhaps unexpected solution?

Lol if you don't know, how can we?

I think it is almost the same with APIO 2007 Backup.

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.

Right after https://www.ioi-jp.org/camp/2018/2018-sp-tasks/index.html becomes available?

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.

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 S_i denote the set of valid values with i-th bit equal to 1. Then, query S_i and S_i' 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.

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.