### VastoLorde95's blog

By VastoLorde95, history, 2 years ago, ,

Seems like HackerRank is down. Anybody from Hackerrank knows what will happen to the live contests? I mean, should we wait for 5-10 mins for the site to come back or what?

• +41

 » 2 years ago, # |   +27 Yep, down for me too. Will Codeagon be extended or postponed or something?
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 Looks like it is back up!Can't see problems yet though.
 » 2 years ago, # | ← Rev. 2 →   +5 It is working now for meI didn't see comment above...
 » 2 years ago, # |   0 Delays in the verdict caused me severe issues, I wasted a lot of time due to that and also in Counting Princess Presents, if the input graph is surely a Tree changes the problem drastically! Did I miss some line or was it understood or something? If not that was bad!
 » 2 years ago, # |   +8 In the question "Happiness of a Kingdom", in case of no special edges,the empty subset was included n (ie number of nodes) times in the answer.Any explanation for this?
•  » » 2 years ago, # ^ |   0 n graphs that contain a single node and no edges... should have been clarified.
•  » » » 2 years ago, # ^ |   +10 We had to find number of different subset of edges and not the number of different graphs.I guess the empty subset should only be included once.
 » 2 years ago, # |   0 How to solve C ? I tried a DP approach where my state is (idx , rem (remaining shops to visit)) . My pos array contains the indices of the shops which contain the item. int bought = m - rem; for(int i = idx + 1; i + rem <= pos.size(); i++) { long cost = 1L * (pos.get(i) - pos.get(idx)) * (bought == 0 ? 1 : 1L * bought * k); min = Math.min(min , cost + findOpt(i, rem - 1)) } 
•  » » 2 years ago, # ^ |   +3 Greedy. The chosen m shops should be contiguous from the list of shops that contain items.
•  » » » 2 years ago, # ^ |   0 Could you prove why taking consecutive shops work?
•  » » » » 2 years ago, # ^ |   0 Prove it by contradiction. If some shop is skipped, you can replace it with some other shop and decrease the total cost.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 But shouldn't the DP solution give the same answer . I was getting WA instead of TLEs and RTEs.
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   0 I tried DP and got a few test cases right.HereIt gives segmentation fault for rest.
•  » » » » » 2 years ago, # ^ |   0 I tried a 2-D DP too ... It didn't pass memory and time.f(i, j) be the minimum time to reach shop i having bought exactly j sweets.if(bi = 0) f(i, j) = f(i — 1, j) + j*k else f(i, j) = min{f(i — 1, j) + j*k, f(i — 1, j — 1) + (j — 1)*k}Base case — f(i, 0) = iHowever, for memory it won't pass. I was able to get past the memory problem by storing a 1-D array f(i) ... and doing j passes on it and keeping track of previous f ... which will have f(i, j — 1).It didn't pass the time limit because it is of complexity O(M*N) and both those numbers can be 1e5.Here's the code. In case you're interested. An O(n) solution is expected.
•  » » » » 2 years ago, # ^ |   +5 Finally I found the problem . HackerRank doesn't report Runtime Exceptions , they are treated as WA . So I put my code in a try block and had a infinite loop in the catch part . All the test cases which gave WA earlier now became TLE . Hence DP works but its slow and memory inefficient .
•  » » » 2 years ago, # ^ |   0 Using two pointer method ? It also depends on the position of first shop in our chosen m shops
 » 2 years ago, # |   +6 Was there some issue in the site in the middle of the contest as well (Somewhere around 2.5 hours into the contest)? The pages kept on loading for eternity. I tried on Firefox,Chrome, cleared the cache but only in the last few minutes the site functioned normally.