Hello Codeforces community!
I am glad to announce that HackerRank 101 Hack 42 will be held on 18th Oct 2016 at 16:30 UTC. You can sign up for the contest here. Though what's priceless is solving interesting problems and the thrill of competition, prizes make the competition fierce. Top 10 performers will get a HackerRank T-shirt.
The contest will consist of 5 problems with variable scoring distribution. We have tried our best to prepare a nice problem set. Hopefully everyone will enjoy. Also, you'll be able to enjoy the detailed editorials written by the setter.
Good luck and have fun!
Who is the setter this time around?
Is this correct for the earlier version of 4th problem ?
I solved E in O(n × log3(n)) and it passed TL. Problem statement for D was totally wrong for 70 minutes of contest. Strange contest.
Was there any notification that D's statement changed?
I didn't see any notifications. Just was checking comments for every 5 minutes.
I've noticed "turned off" change into "toggle" after problem statement refresh.
Then, after some time, the "(1)" appeared in notification icon at the top.
I also got 100 in E with log^3, I thought it would get at most 50. I wonder what was the purpose of the second subtask if this passes everything.
Can you explain your log**3 approach ? Editorial isn't clear.
Say we want to solve the problem for indices from L to R. Denote with P the index of the largest element between those indices. Now for every interval [i;j] (L<=i<=P<=j<=R, i!=j), it is true that max[i..j] is on index P. So we want to count how many such intervals we have so that A[i]*A[j]<=P. And when we are done, we recursively solve the problem for intervals [L,P-1] and [P+1,R]. In order to count the number of those intervals [i,j], we can use the following slow approach: For every i from L to P, count how many numbers from P to R are less than or equal to A[P]/A[i]. Well, once we have fixed i, we can find the number of those j indices in log^2 (actually log is possible), it is a known task — http://www.spoj.com/problems/KQUERYO/ (my solution for this problem is really fast actually, see ranking, so this may have helped to pass the time limit here :D).
Well, now the only thing we need to do is to see if the interval [L,P-1] is shorter than [P+1,R]. If it is, then fix i among [L,P-1] and count the proper indices j. If it is not, then fix j among [P+1,R] and count the proper indices i. And this is in total O(NlogN) divide and conquer, if we always choose the shorter interval.
Thanks , I got it now . Btw , for the spoj problem did you do something other than merge-sort tree ?
Nope, just a merge sort tree with fast input and I simply allocated arrays for each node, instead of vectors and used hand-written binary search instead of lower_bound/upper_bound.
Is there any meaningful time difference between malloc(n * sizeof(int)) and vector<int>(n)?
That wasn't a cool move, ffao, why did you code such a fast solution :D
I guess it depends on what meaningful time difference means to you. I took my fastest solution (0.06s), changed the struct to the following piece of code and submitted a few times and it worked in 0.10-0.11s:
I just had a mergesort tree written here and I wanted to test if it was correct, I had no idea it was fast :)
0.05 isn't a significant difference for most problems, but when solving problems with tight time limits I'll definitely keep this in mind!
Can you please share your code ?
Yes, sure! The struct tree_node as well as the functions merge_them, build_tree, update_tree and query_tree are pretty much what I used for KQUERYO, I just copied them from there.
I meant for the hackerrank question :P
That was the code for the hackerrank question, I just pointed out what part I used to solve KQUERYO.
I'm guessing they didn't want log^3 to pass, but didn't actually check if it passed or not. Separating solutions by one log is really hard anyway, I don't know why they still try.
Maybe that's right. This came to my mind but it seemed like a bad attempt :D
1) Will the round be rated?
2) What is "BIT" in "can solved offline using BIT" in E-problem's editorial?
BIT is binary-indexed tree.
I guess, it's rated, since "Ratings will be updated soon, please wait!" is written on contest page.
"Ratings will be updated soon, please wait!" could be just a robot's message :)
In problem E, why does iterating over the smaller segment doesn't time out?
About problem D, if you have a loop that takes k time and a loop that takes n/k time, then the complexity is O (n), not O (nk). I'm guessing the statement wasn't the only part of this problem that was rushed...
For E problem.I wrote N*log(N)*log(N) solution but it give TLE.Pls help find my mistake.I used ordered set and divide conquer. Here is my code.
I was initially using a sparse table in problem E, that took O(NlogN) memory, that caused MLE. However, all this time, HackerRank's judge showed me the verdict Wrong Answer.
After the contest, I used a segment tree, that takes O(N) memory, and guess what, my solution passed. Why doesn't HackerRank provide a verdict like MLE ? Is giving wrong answer the right way to deal with this? This made me really angry after the contest.
When one creates an online judge, the first thing one should deal with is small things like various verdicts. This is really stupid from HR.
How do you know that it was MLE if Hackerrank showed you WA for all the cases? Could there be some bug in your sparse table code which resulted in WA?
My code passed the first 10 test cases and got a score of 52 initially when I used a sparse table . The final verdict was WA
How does this mean that your actual verdict wasn't WA?
Please check for urself. Just declare an array of size 5 × 105 × 18 to any of ur AC code, and the next thing u will see is WA !
This code gets AC in the contest's first problem. I created a long long array of size 5*1e5*18, as you said and the code passed the test cases.
I also used sparse table (along with persistent segtree) but my code successfully passed, without any MLE!!
AND i never heard of any segtree using O(n) memory.. i am curious does something really exist?
In 4th problem, why the theory that no button should be pressed twice works?Proof!
Pushing a button twice is the same as not using it at all
Sorry, i meant if some bulb is switched off , why can't we press the button corresponding to it. I get what you meant, but i'm not able to understand this claim "If button i is pressed, then no button in the inclusive i-k,i+k range will be pressed".
I have an alternative (albeit harder to implement) approach for problem E:
We will be using D&C approach. Let's now consider a segment [l...r) ans fix m = (l + r) / 2. We will recurse for [l...m) and [m...r) and, after that, calculate the answer for
and 
.
Now, let's suppose the maximum value lies on the right segment. Then, we could sort the left segment decreasingly by value A[i] and sort right segment decreasingly by value max[m...j] / A[j].
Now, we can impose the constraint A[i] * A[j] ≤ max[m...j] by an algorithm similar to merging sorted arrays, with the two pointer approach. Let's also not forget about the other constraint, created by out supposition: max[i...m) ≤ max[m...j]. This can be solved by keeping a data structure of your choice (I used BIT).
The other case is solved similarly, with some extra care for double-counting.
No arguing, the other solution is easier to understand and write. And it's a nice trick to remember.
Code is here. I had to parse input data in order to squeeze it within time limits. Sneaky and overcomplicated, but rather fun nonetheless.