VastoLorde95's blog

HackerRank down?
By VastoLorde95, history, 7 years ago, In English

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?

  • Vote: I like it
  • +41
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +27 Vote: I do not like it

Yep, down for me too. Will Codeagon be extended or postponed or something?

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

It is working now for me

I didn't see comment above...

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

→ Reply
»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    n graphs that contain a single node and no edges... should have been clarified.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      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.

      → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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))
}
→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Greedy. The chosen m shops should be contiguous from the list of shops that contain items.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Could you prove why taking consecutive shops work?

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Prove it by contradiction. If some shop is skipped, you can replace it with some other shop and decrease the total cost.

        → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      But shouldn't the DP solution give the same answer . I was getting WA instead of TLEs and RTEs.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        I tried DP and got a few test cases right.

        Here

        It gives segmentation fault for rest.

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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) = i

          However, 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.

          → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        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 .

        → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Using two pointer method ? It also depends on the position of first shop in our chosen m shops

      → Reply
»
7 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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.

→ Reply