I'd like to invite everybody to participate in HourRank 12 on HackerRank. It'll start tomorrow at 19:30 PM MSK.
It's my first HourRank but I've prepared problems for HackerRank several times. I also used to prepare problems for Codeforces long time ago.
There will be three problems and one hour to solve them. Contest will be rated and top-10 contestants on the leaderboard will receive amazing HackerRank T-shirts!
I'd like to thank wanbo for testing the problems, it's always a pleasure to work with him. I hope you will enjoy the problems and some of you will solve everything.
Scoring will be: 20-40-80. Editorials will be published right after the contest.
Good luck!
Why uwi has penalty 42:00 in the leaderboard while his last submission was at 30:08?
I find problemset pretty interesting. Thanks !
It looks it would be better to have four tasks and that last task should be on level between current second and first. In lot of previous rounds gap between first two problems is too big for many coders :)
Can someone discuss the approach for this problem: https://www.hackerrank.com/contests/hourrank-12/challenges/fair-cut
I understood uptill the the pseudo polynomial solution part but after that its very hard someone please explain the editorial !
I couldn't even understand the pseudo polynomial solution....I couldn't make any dp condition....could you explain how pseudo polynomial solution works?
I also find it very hard to understand, but I took some notes out, and I wish anybody can help us arrive at a convincing conclusion;
1 — Since the array is sorted, then as we advance alpha, we're sure all array elements are less than a[alpha+1]. Why is that useful to calculate the cost?
2 — The first solution, uses 3d array dp[alpha][beta][gamma], but is gamma really unique? What values does it take? it's the sum of all items with Li, sorted, and in increasing order. does uniqueness even matter?
3 — We have only two cases; take it, or leave it = Li or Lu.
4 — There's also a tricky short-cut used in ((beta . a[alpha+1] — gamma))
notice that the cost function is sum over i sum over j of |ai-aj|
but what if we leave a[alpha+1] .i.e. give it to Lu, then we have to loop and subtract all items with Li from a[alpha+1]
but how many items with Li, that's beta, and what is the sum of their values, it is gamma = a[alpha_i] for all i in I (with Li)
so the whole expression is just a[alpha+1] — a[0] + a[alpha+1] — a[1] + a[alpha+1] — a[2] ... so on as long as these items are with Li.
5 — The other case is simple if you just multiply alpha-beta by a[alpha+1] and follow similar logic to convince yourself that it literally translates to sum over subtracting every item with Lu from the new item given to li
My question is how could any body come up with such sophisticated logic in less than one hour and implement it too? I wish I could reach this level one day :)
To be honest, that solution is a bit overkill for the problem and I thought that the problem will be harder.
I'd like to explain another way to come up with practically the same dp. Let's sort the numbers and look at each gap between consecutive numbers. The length of the gap ai + 1 - ai will be caclulated in the final answer with coefficient A·B + C·D where A is the number of Li's integers among {1, ..., i}, B is the number of Lu's integers among {i + 1, ..., n}; C is the number of Lu's integers among {1, ..., i} and D is the number of Li's integers among {i + 1, ..., n}. It's clear that C = i - A, D = (n - i) - B.
Then if we have dp state (i, j): we have arranged the first i integers and j of them we have given to Li. Then it's easy to find A, B, C and D for the gap between i and i + 1. Then the function we calc with our dp is contribution of gaps before element i to the final answer.
This makes me feel better, I almost implemented a similar solution. Here if you're interested, please let me know if I'm wrong:
https://github.com/thecortex/C-Practice-2016b/blob/master/Li%20Lu%20Fair%20Cut/src/Li%20Lu%20Fair%20Cut.cpp
Forgive me for the left couts for dumping variables.
I don't think that is correct because you are calculating the function after you've fixed everything, but your memoisation doesn't corresponds to the actual information you need to calculate the function (which is actually the whole arrangement), that's why you may choose wrong arrangement with the same characteristics (n and k) because you are picking up some arrangement, calculate the function for it and then you don't calculate anything for different arrangements with the same characteristics. What you should do is to calculate the function step by step (with gap contributions I described) when you are deciding to pick or not to pick the element. That is very important because you will be able to know which state is better.
We consider each element independently, and find the coefficient it will contribute to final answer. After sorting the numbers , the states current position and number of elements in Lu's set. , it is simple adding the number of elements less than the current number and subtracting the bigger ones of the other set , (remember the array is sorted) .
For each element in the array , you'll have 2 cases , either put in Set A , or Set B. Now for each case , the unfairness value that will be added in the answer has to be included. Just calculate the number of elements it'll be greater than or smaller than and then accordingly add into the answer. You'll have to sort the array beforehand so as to determine whether the current element's contribution will be positive or negative. See Code for clarity.
When you're adding the number to set B you used — ret = A[pos]*present — (K — sizeA)*A[pos].
A[pos]*present is clear to me — since you need A[pos] present number of times to subtract it with all the number in set A so far... But then you also need the sum of all the numbers in set A so far...
How is (K-sizaA)*A[pos] doing the job?
Please let me know if I'm making a mistake
(K — sizeA) is the number of elements that will go from [pos + 1 ... n] into setA , so , only for these many elements we will mark A[pos] contribution , if we take pairs of a[i] belonging in [pos + 1 , n ]. Also since A[pos] will be smaller than those , hence a negative sign. We are taking each elements contribution in the total unfairness value. So we don't need the sum of all number in A .
How were we supposed to know that the last task had binary scoring before submitting it?
I saw standings at one moment and saw I need a little more points for top 10. I submitted code and I got AC on some tc, I said Yeah I have t-shirt !!! :D After one minute I realized it was 'mosa' ( as we call it in Serbia :D ).
Does 'mosa' mean tricked ? In Kannada (Indian , south indian i.e) mosa means cheat!
Yeah :) It is very interesting, I thought it is something invented by local guys :D
This greedy O(nlogn) solution gets full score on the second problem for some reason:
Wow, I haven't thought about such greedy. I've tried to find counterexample for this but haven't succeed. The main assumption you make is that except one or two integers in the center we should arrange integers symmetrically. If that's true, everything is correct. But I don't know how to prove it either. Could anybody prove of disprove this?
Yes, the assumption is that if k > n - k, then it is optimal to give the smallest and the greatest number to Li, otherwise we should give them to Lu. The sum of distances between amin , amax and some subset S of the other integers
only depends on the size of S, so we can simply increase the answer, remove amin and amax from the set and repeat the procedure.
To prove that the assumption is correct, we could argue that if k > n - k and amax belongs to Lu, then we could always get a better answer by switching amax with the greatest integer that belongs to Li. Let b be the the greatest integer belonging to Li. If we instead give b to Lu and amax to Li, the answer will decrease by (amax - b) * (k - 1) and increase by at most (amax - b) * (n - k - 1), so our answer will be better. A similar argument can be made for amin. Im not sure if this is clear enough but Ive convinced myself at least :).
Yeah, sounds good for me. That's a very nice solution!
can you explain for this example 5 3 1 3 5 7 8 here if i take li is {1,3,8} or {1,7,8} ans is 20 but for this {1,5,8} ans is 18
I saw that rating system got updated, but there is no Hourrank 12 ratings on it yet? Will it get updated eventually?
Something really strange is happening with rating on hackerrank currently. Can we expect some big post about changes in rating system?
They sent emails about that.
"First, we changed how we calculate algorithms contest scores by transitioning from Bayesian Approximation based algorithm to the Elo Rating System.
Second, we also removed Ad Infinitum contests from the algorithms leaderboard and created a mathematics leaderboard with a separate rating."
I didn't get this email. Last time I got anything about new rating system was 2nd of June. And this description doesn't explain anything. They don't have invariants like codeforces do. So, it is hard to understand, if there rating is at all working properly.
Hello @tunyash .. My rating in hackerrank werent updated after the contest. They still stand the same. Please look into the matter. Thanks