Блог пользователя VastoLorde95

HackerRank down?
Автор VastoLorde95, история, 7 лет назад, По-английски

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
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

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

→ Ответить
»
7 лет назад, # |
← Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

It is working now for me

I didn't see comment above...

→ Ответить
»
7 лет назад, # |
  Проголосовать: нравится 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!

→ Ответить
»
7 лет назад, # |
  Проголосовать: нравится +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?

→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +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.

      → Ответить
»
7 лет назад, # |
  Проголосовать: нравится 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))
}
→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Could you prove why taking consecutive shops work?

      → Ответить
      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

      → Ответить
      • »
        »
        »
        »
        7 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        I tried DP and got a few test cases right.

        Here

        It gives segmentation fault for rest.

        → Ответить
        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится 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) = 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.

          → Ответить
      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится +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 .

        → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      → Ответить
»
7 лет назад, # |
  Проголосовать: нравится +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.

→ Ответить