The admin preferred not to reveal number of problems.

additional information:

1- the contest will have ACM rules.

2- multiple machines for one team is allowed.

I think thats pretty good, congrats mate. :)

Both. You can see solutions in Java and C++ for different problems.

But we can see solutions of other people...

You can discuss the problems now. The editorials will be provided after the reply round.

Hints:

1. Calculate the eulerian tours of both trees

2. Now the problem is like finding intersections of prefixes

It's like a euler tour on trees technique. First, So we keep starting and ending time of each node in the first tree. Now, when we are doing dfs on the second tree, so while visiting a particular node say x, we will add 1 to all the nodes who are in the subtree of x in the first tree, i.e add 1 to all the nodes whose starting time  >  start[x] and ending time  ≤ end[x] [Remember start[x] and end[x] are for the x in the dfs of first tree]. We can do this with BIT, and when we're done with dfs of x in second tree, we will reverse the operations i.e. add  - 1 to the above stated nodes for x. So, answer for a particular node i will value of 1's added to start[i].

I have a little different approache for the task. We can calculate eulerian tours for both trees, than we will have four different times for each node : (start1, end1), (start2 , end2) — coming and leaving times for both trees. Now let's represent each node as point in the plane with coordinates x=start1 and y = start2. We have n points in total. Also we can represent recetangle with left-bottom point (start1, start2) and right-up point (end1,end2) for all nodes x. All points (nodes) in the recetangle will have x as ancestor in both trees.

Now we need to do inverse task — calcualte amount of recentagles which contains certain point and this is known problem.

How do we get such information man? Did you solve the question previously? Just Curious.

Yes, it is the exact same question.

The editorial for problem RIN at this link : http://discuss.codechef.com/problems/RIN

has the same test case which is provided as the sample test case in https://www.codechef.com/SNCKEL17/problems/SPCLN.

Any comments from admins? For me it seems the author of yersterday's problem simply copied it from cgy4ever's problem. And it may have ruined the selection of onsite teams.

UPD Now having noticed the output format "print the average sum rounding to two digits after decimal point" I'm 100% sure that problem copying is the case. Haven't seen such an impudent copying of the problem in official competition before.

Submit on Codeforces

Suppose at time moment t the queue contains people with arrival times b₀, b₁, ... b_n - 1. If b₀ ≤ t then first customer in queue will be served now, otherwise if b₁ ≤ t + 1 then first customer will be moved to the end of queue and second will be served now, ..., if b_n - 1 ≤ t + n - 1 and b_i > t + i for all 0 ≤ i ≤ n - 2, then n-th person will be served now and all others will be moved to the end of queue, preserving their order.

If b_i > t + i for all 0 ≤ i ≤ n - 1, then in seconds from t to t + n - 1 inclusive everybody gets moved to the end of queue and situation just repeats at moment t + n.

So, what happens with queue? If , then everything comes full circle and t is increased by n. Otherwise, we need to find the leftmost position j, such that b_j - j ≤ t, process customer at that position and move everybody before that position to the end of queue (preserving order).

How many full circles will happen (let's call this number k)? If (if M ≤ t then k = 0), then exactly full circles will happen. To simulate them, just increase t appropriately.

Now only the case when M ≤ t bothers us and we want to find smallest j such that b_j - j ≤ t quickly. To do this, let's keep queue in implicit treap and in each vertex remember minimum value of b_i - i in its subtree. Idea of remembering something that changes when we do operations on tree sounds kind of dangerous, but actually it is completely ok in this case. When we do merge and split we just need to do an update operation to some vertex (where info is no longer correct, but info for it children is up to date), we need to just decrease minimum in right subtree by 1 + (size of left subtree) and b_i - i for root is just b - (size of left subtree). So this kind of information can be keeped while we do basic merge and split by length operations.

To find smallest j that b_j - j ≤ t, just do tree descend and check whether minimum of b_i - i in subtree is still less than t. After that serve this customer, delete him and move all customers that stand before to the right (by splitting them out from the left and merging them on the right).

https://www.codechef.com/snackdown/2017/prizes Any team within Top 300 will get it

Hints:

• Calculate for each element how many times it will contribute in the final answer.
• Try to find some kind of reccurance relation which will help in calculating the contribution of each element using the contribution of the next element.

https://www.codechef.com/snackdown/2017/prizes Any team within Top 300 will get it

sum[i] = sum[i-1] + dp[i];
dp[i] = ( dp[i-1]-sum[i-2] ) * ar[i] + sum[i-2] + dp[i-1] + ar[i] * pow(2, i-1);
ans = dp[n-1];

complexity : O(n).

Binary search + max flow inside it

The constraints for this problem are tricky somehow. Especially when you first think of Max Flow. Create n versions of each node. Each node will have an extra copy for every time second. and for each edge u->v add it for all nodes [u][s] -> [v][s+1] where s is a second ranging from 1 to n. I think most people got AC with binary search, but you can throw throw out binary search and add edges to the sink representing each second while going on and after adding each layer call your augmenting path function. I think this runs in K * N * M. But in particular it's kind of impossible to force maxflow algorithms to reach worstcase.

We can create a new graph where each node (i, j) represents that we are on node i at time j. Now when we are creating edges , we should create edges from a nodes (u, t) to (v, t + 1) if (u, v) edge exists in our original graph. So, our initial problem is transformed into finding the edge disjoints paths in our new graph which is a standard problem. Now we can binary search on minimized maximum length by creating a graph in which the nodes are stated as above and t is the length we want to check. To check for a particular length, we'll need to check if the total disjoint paths in our new graph  ≥ k and change the limits of binary search accordingly.

There is no need in persistent segment tree. We need to store vector in each vertex of segment tree and do binary search.