Yes, everyone is invited to participate in the mirror contest

We hope you will all enjoy the contests. Good luck!

Good luck! hf

I will prefer if its posted only after the mirror contest gets over

The scoreboard is not live due to the online nature of the contest, but publicly available after the end of each contest on both competition days (see the update)

I solved servers using centroid decomposition. We need to add weights to the edges of tree. If $$$"S a b"$$$ was $$$i$$$-th query the weight of $$$(a,b)$$$ will be $$$i$$$. Then by the time of $$$i$$$-th query we know that $$$b$$$ contains chunk $$$a$$$ if and only if the path from $$$a$$$ to $$$b$$$ has increasing weights and the last edge on the path has weight less than $$$i$$$. So now we can solve this problem offline using centroid decomposition and some data structure like fenwick tree, which will make the total complexity $$$O(nlog^2n)$$$

We will publish solution outlines at some point on the official website. However, that might only be in a few days — we will announce it here once that happened. Until then, you have the opportunity to continue trying to solve the problems on your own ;-)

In problem Servers, I come up with the following idea:

If server a stores data chunk d, then there should be an increasing path form node d to node a if we add weighted edges to the graph (tree), where weights are just the query indexes.

Now Q type of queries can be solved using binary lifting if we build the tree offline and we can check whether these two nodes are in the same component using DSU.

This increasing path idea maybe can be applied to C type off queries. I don't know exactly how, but the idea is the number of servers that contains chunk d is the number of nodes that has an increasing path from d

I only got 70 on watchmen but here is my method.

We denote the length of the path on the henchmen on vertex $$$a$$$ as $$$ped[a]$$$. For each vertex $$$v$$$ with a watchmen on it, we will duplicate it $$$ped[v]$$$ times, the $$$i$$$-th duplication stores the minimum time such that residue modulo $$$ped[v]$$$ is $$$i$$$. We denote this $$$w[v][i]$$$.

Now we will just have to figure out how to draw edges such that we reduce the number of edges.

Firstly, for vertices that are duplicated, we draw edge with weight $$$1$$$ from $$$w[v][i]$$$ to $$$w[v][(i+1)\%L]$$$. This just means staying at that edge. We also draw edges to the adjacent vertices in the henchmen's path (with conditions about not getting noticed). The number of additional edges here is $$$O(l^2)$$$.

For edges that connect a vertex without henchmen to a vertex with henchmen (there are $$$O(M)$$$ of these), we have to split this into $$$2$$$ parts. Say $$$a$$$ is the vertex with the henchmen and $$$b$$$ is the vertex without. For edges go $$$a \to b$$$, we make a new node, $$$a'$$$ that is the minimum time over all $$$w[a][i]$$$. Then connect $$$a'$$$ to $$$b$$$. We only have to create $$$a'$$$ once, so the number of additional edges here is $$$O(l^2)$$$. For edges that go $$$b \to a$$$, we want to connect $$$b$$$ to all $$$w[a][i]$$$ but this will create $$$O(Ml)$$$ edges, so we reduce this number by connecting only $$$2$$$ edges. One of them has weight $$$1$$$, which is going into $$$a$$$ immediately, and the other is we wait for the henchmen to pass and go into the node. This is equivalent because we have edges from $$$w[a][i]$$$ to $$$w[a][(i+1)\%L]$$$.

Now for the interesting part, the edges that connect the vertices where there are $$$2$$$ different henchmen, note that there are $$$O(l^2)$$$ such pairs. We make this edge directed first. So the edge is $$$a \to b$$$. Suppose $$$w[a][i]=t$$$, then we can reach $$$w[a][i]$$$ at time $$$t+ped[a]$$$ by going around a cycle. When we want to update $$$w[b]$$$ from $$$w[a][i]=t$$$ we want to update $$$t+1,t+1+ped[a],t+1+2ped[a],\ldots$$$ but this will take add a $$$O(l^4)$$$ to our complexity. So we add a "hidden layer" $$$w[h]$$$ of size $$$ped[b]$$$ between $$$a \to b$$$. $$$w[a]$$$ connects directly to the hidden layer. The hidden then has edges from $$$w[h][i]$$$ to $$$w[h][(i+ped[a])\%ped[b]]$$$ which allow us to only add $$$O(l^3)$$$ to our complexity. This has to be sped up for 100 points but I am not sure how.

Using Dial's algorithm (I assumed the answer is always less than $$$10^7$$$), we have a $$$O(N+M+l^3)$$$ algorithm.

My implementation is here

Unfortunately not right now. We currently prepare the servers for the live contest tomorrow. We may enable analysis mode tomorrow after the day-2 contest for both contests.

Analysis mode is now enabled for both contests.

Sorry, it should work now!

What's the link for day 2?

Please wait a few more minutes, we are currently setting up the contest.

Edit: It should work now :)

+1 The problems are really nice

I also got 80 and I don't think it is possible to get 100 due to the bounds on n,d = 2*10^6, unless you are able to optimize the inner dp to run on O(n) instead of O(n*log(n)). Actually I think they made the bounds that high to stop lagrange from getting 100 pts, because there is another more efficient solution described in the analysis that does not involve lagrange.

I did.

At first I was working with the alien trick approach too. But then I was trying to solve the d-parameter-less version with good complexity, and the greedy approach clicked. In fact, it's not the only problem. I vividly remember getting alien-trick-rolled in few other problems- (a) get a vibe and verify the function is convex (b) think about the parameter-less version, get a greedy approach to solve that (c) but wait, I can use this greedy approach in the actual problem :v

Can somebody describe the process in detail, since I noticed that you can't do the standard trick. At least for me, I get a problem when C(l) is > d where C(l) is the minimum number of mattresses for an optimal solution where a cost of a mattress is l. I saw some codes use the formula:

if(C(l) > d) r1 = dp(l) — l*C(l) r2 = dp(l+1) — (l+1)*C(l) answer is r2 + (r1-r2)*(d-C(l+1))/(C(l)-C(l+1))

where l is the biggest cost for a mattress such that C(l) >= d

Can someone give an explanation. Thank you in advance

Sorry for the delay, but most of the committee members were a bit to exhausted to get to that right away :-) The test data is now on the website, ready to be uploaded to another online judge. Note, however, that the managers used for the interactive tasks rely on the German fork of CMS, so they might need some tweaking to get them running on another judge system.