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 t then each value ai, bi, ci will drop to 0 exactly once, and more specific for t equal to k - ai, k - bi, k - ci respectively. From here we reduced it to a sweep line problem.
Consider the problem as having 3n points (arrays a,b and c) on an array of size 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 the sum 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*t because 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 O(NLog(N)) 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.
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 value in 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 taskor 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 if f[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.
.
Can you explain your solution?
.
Can you share you code ? Very interesting approach
.
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(N2·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