Hello everyone!

I would like to invite you to participate in January Circuits '18. It's a long contest that will start on Jan 20, 9:00 PM IST (check you timezone). Contest will run for 9 days.

The problemset consists of 7 traditional algorithmic tasks of various difficulties and 1 approximate problem. For traditional algorithmic tasks, you will receive points for every test case your solution passes — so you can get some points with partial solutions as well. For the approximation task, your score depends on the best solution in the contest so far. Check contest page for more details about in-contest schedule and rules.

I'm the setter of the problemset and Kmcode is the tester. I would like to thank HackerEarth admin trytolearn for his help.

As usual, there will be some nice prizes for the top five competitors:

- $100 Amazon gift card + HE t-shirt.
- $75 Amazon gift card + HE t-shirt.
- $50 Amazon gift card + HE t-shirt.
- HE t-shirt.
- HE t-shirt.

GL & HF.

Please elaborate the approach for Arrays Problem. The editorial is not clear.

Which part you don't understand?

How are we sorting the 3 arrays, what is m in the second line? Like let's say that first, we are sorting the 3 values for each index viz a[i]<=b[i]<=c[i] and then we are sorting the complete array from 1 <= i <= N. But we can be sure that after this if array a is sorted array b and c will also be sorted. And is it possible to solve the question using Binary Search over the answer with the complexity O(N*logN*logK)?

I don't understand how you use binary search, the thing you need to observe that if you consider and try all possible

tthen each valuea_{i},b_{i},c_{i}will drop to 0 exactly once, and more specific fortequal tok-a_{i},k-b_{i},k-c_{i}respectively. From here we reduced it to a sweep line problem.Consider the problem as having

3points (arrays a,b and c) on an array ofnsize k(0 indexed). Now for t = 0 to t = k-1 we have to move each triple(a[i],b[i],c[i] for i in 1 to n) to the next position on this array and take minimum of the largest triple's sum (a[i] + b[i] + c[i]) after each iteration of moving t.Consider the case where none of the 3*n points you are moving, cross k array's boundary. In such a case all triples' sum as well as maximum triple's sum will

increase by 3(one for each a,b and c). The only place where the sum decreases is when the points cross the k array's boundary, in which case thesum drops by k.So we can simulate this problem with the help of a multiset which has all the sums initially, we also store after how many movements will a point hit the boundary(simply k — value of point) which gives us an idea after how many iterations of t should a particular triple's sum be reduced by k.

Then we do the following : We iterate over t in 0 to k and find which triple gives the current maximum sum . We add to this value

3*tbecause the sum would have ideally increased by this value had the points not hit the boundary of k array. We also check if some point hits the boundary in this step then reduce corresponding triples' sum by k and reinsert the correct value in the multiset. This algorithm is.O(klog(N))In fact we can reduce this to

by observing that we needn't iterate over all values of k but the chance that a particular triple will no longer be that with maximum sum only occurs when a point of the arrays a,b or c hits the boundary. For other values of k our maximum sum and corresponding minima doesn't change.O(NLog(N))I am unable to understand the how will you keep track and update each of the values in multiset (para 2). Can you please explain the approach for this problem?

The point to notice is that we

don't update each valuein the multiset when we move one step on k array since we know that unless some point turns around at the boundary(moves from k-1 to 0) the ordering of sums (a[i] + b[i] + c[i]) remains the same.As an examples suppose we had 3 sums viz <3,5,7> then on moving t steps ahead the values will be <3+t,5+t,7+t> however suppose a[3] (the one contributing to 7) hits the boundary at next step now the values will be <3 + (t + 1), 5 + (t + 1), 7 + (t + 1) — k >. We can do away by just updating the '7' value since other than that the ordering of sums remains constant and we know which iteration we are working on (t here) so we just add that to the current maximum value extracted from multiset.

Thanks for your reply. I understood the approach :)

Were the test cases really weak in

`Classic task`

or was there some observation making so many brute solutions optimal?No, it's just that the tests were weak :(, I'm really sorry for it, I made sure that for the big set and my brute gave me TLE doing

f[get(i)] =get(j) and didn't expect the adding of an additional iff[i]! =f[j] to fit the solution in TL.P.S. I'm going to add stronger tests in the practice, of course the solutions won't be rejudged.

Is hashing the main idea of this problem? I have a

O(NlogNlogN) solution with some tricky lines and it passed.EDIT : I did not realize that Editorial was available.

Can you explain your solution?

Let

get(u) be the index of connected component which hasuas one of its vertices.The main idea is to skip all the edge such that

get(u) =get(v).For a set of edges (

l,r), letfind(l,r) be the smallestxsuch thatx<landget(x)! =get(r-x+l) and we will add this edge into our DSU.We can easily see that

find() can only be accessed at most 2N+Mtimes.If we have all

get(u) for allufrom 1 toN, we can use Binary Search + Hashing to find x inlogN. But after each time we add an edge into DSU, there's some vertices which itsget() will be changed. So we need to store the hashing array as a Segment Tree, so that we can perform queries inlogN.Beside, if we use Small-to-Large technique for our DSU, each vertice's

get() will be changed for at mostlogNtimes.So, we have

NlogNchange query and (2N+M)logNupdate query.Time complexity :

O((N+M)logNlogN).Can you share you code ? Very interesting approach

You can find it here.

for problem "Road" i wrote a recursive dp solution. Here is the code. But the solution gives TLE in many test cases. Is this because of stack overflow or the complexity of the recursive dp? Also, how can I convert recursive dp into an iterative one if stack overflow is the problem?

Your complexity is

O(N^{2}·K) which is too much, see editorial, there is described how to optimise it.Is there any recursive solution for this question?

No, it won't fit in ML.

i just did it recursively with some tweaks in the previous version of the code. Here is the code with AC