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.

I dont think you can view the tests on codechef.

no you dumb fuc

Which problem in your opinion was about "copy paste persistent tree"?

http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?cid=726&pid=1004

I believe there are many online judges have the totally same problem.

What was the solution to the black subgraph problem? The fastest solution I could think of involved iterating to the correct subtree size and taking 2-dimensional fft's or something along those lines.

You are talking about probably the easiest problem from this contest, right? I read this problem and 'wait, I spend 40 minutes on geometry while there was obvious DP?!' Still don't understand why so few teams solved it.

Just kidding :) Different people prefer different kinds of problems.

4 points forming rectangle (answer is NO)

it is not correct answer is "YES" in that case.

There is answer for a rectangle... and it's kinda easy. The only case without answer is when one point is inside triangle made of 3 other. I had such cases: 3 (or more) collinear points, points forming a parallelogram, other cases. It's easy to consider every of them separately, hardest thing was about "find intersection of two lines".

I tried to minimize the number of cases, so here's what I did :

If three of the points are collinear, sort them by increasing order of x-coordinate, then y-coordinate. Let's say the points are P₀, P₁, P₂ in this order. Now, we just take P₀P₃P₂ as our triangle.

Otherwise, build the convex hull of the four points. If the size is at most 3, the answer is NO. Otherwise, we have the points A, B, C, D as the vertices of a convex quadrilateral, in this order. In this case, take the lines AB, AD and the line parallel to BD passing through C as the sides of our triangle. The vertices are just the three intersection points of these lines.

Here

A similar problem to this is problem "Barricades" from Algorithmic Engagement 2007. You can find a solution in the first half of the "Looking for a challenge" book (which you can download here). The book explained why the DP is amortized from O(n³) to O(n²) (which is the same case for this problem).

I guess the estimation of time complexity for your DP is not strict.

Let T(x) be the time complexity of a DP with x nodes. If you write a DP whose time complexity is like T(L+R) = T(L) + T(R) + L*R (Somehow you can convert the tree where some vertex could have three or more children into as a equivalent binary tree), the time complexity is O(N^2) in total (N is the number of nodes) as xuanquang1999 said.

Why? Let's assume T(x) <= x^2, then T(L+R) = T(L) + T(R) + L*R ≦ (L+R)^2 = L^2 + R^2 + 2*L*R. You can find this is obviously true by comparing each term in the left side and the right side.

This fact is a little amazing. I can't understand it intuitively actually.

Straight-forward DP has complexity N^2. You can read cheater2k's very simple explanation here in Vietnamese.

That property of increasing and then decreasing doesnt hold !!

Sort the arrays a and b.

The problem is equivalent to finding the maximum matching of arrays a and b such that if m, M are the minimum and maximum value of A - B where (A, B) is a pair in the matching, then M - m ≤ 2y.

My idea is since n and m are small, I can brute force all possible (i, j) so that we pair a_i, b_j and m = a_i - b_j. For each such pair, I can find the maximum number of pairs I can still make without violating m ≤ a - b ≤ m + 2y in O(n) time by greedy.

My solution : For each position i, find the leftmost position l such that the mex of the subarray [l..i] is at most k. Note that the mex is larger than k iff all numbers from 0 to k inclusive has appeared in this subarray. Note that if [l..i] has mex larger than k, then [l..i+1] must also have mex larger than k, so the sequence of leftmost position is non-decreasing. We can compute this leftmost position for each i with the help of two pointers. Call the leftmost position for position i as L[i].

Once we build the array L, we just have to do a simple dp. dp[i] is the number of ways to divide the first i elements into subarrays satisfying the condition. dp[i] = dp[i - 1] + dp[i - 2] + ... + dp[L[i] - 1], and the latter can be computed in O(1) time if we maintain the prefix sum for dp[i].

Complexity : O(n).

Currently replay round of the contest is taking place ! You can submit there ! Or else after this contest all the problems will be added to practise section. For a problem from contest just remove the contest code from URL to go to practise version of that problem

eg https://www.codechef.com/SNEL17RP/problems/CHEFPRAD -- contest

https://www.codechef.com/problems/CHEFPRAD -- practise

Hi, We noticed that we have missed making the solutions of the elimination round private. Now we are already half way through the contest and the damage is done. Keeping into consideration of the series of events and the spirit of the competition, we are calling back the prizes (of the replay round) that were announced earlier. We shall be more diligent in our future events and we sincerely apologize for the inconvenience caused. Thank you for bearing with us.

We had the same issue , our solution got TLE and we wasted time thinking a better logic. In the end , just changed vectors to arrays(optimized the constant basically) and it passed -.-

Getting 3 * 10^8 operations in a second is not entirely unreasonable. Also, in this problem it is not easy to create test data to force this up. We had the slowest solution running in 0.23 secs.

check with a simple case like this: n=3 k=1 array=2 1 0, you are printing 3 while the answer is 2.

For this test-case

10 4

8 4 3 1 5 2 0 5 6 0

your code gives rt array as [0,0,0,0,0,0,1,1,1,2] while the correct array should be

[0,0,0,0,0,0,2,2,2,2]. When the 0 is found at i = 7 ( 1- indexed ), you are setting rt for that = lt which is 1,

but for lt=1, the mex is still = 5. So lt should be = 2 , by removing 4 ( at i = 2) also.

Hope you got it!