Hackerrank Question

general
1

Question https://www.hackerrank.com/contests/w38/challenges/a-time-saving-affair
Solution https://www.hackerrank.com/contests/w38/challenges/a-time-saving-affair/submissions/code/1308726348

Please let me know what is wrong in this code.

2

Your Implementation of was absolutely correct but the reason for some failing cases was the following block of code:

  node x = nodes[nn.dest].get(i);
  if(dist[nn.dest]+x.dist< dist[x.dest] )
  {
          dist[x.dest] = dist[nn.dest]+x.dist;
          if((dist[nn.dest])/k%2==1){
              long r = (dist[nn.dest]%k);
              dist[x.dest] += k-r;
          }
          node xx = new node();
          xx.dest=x.dest;
          xx.dist=dist[x.dest];
      queue.add(xx);
   }

You are adding the extra waiting time only after you have considered that the current path is shorter than the path , What I mean to say is that you are not adding the extra waiting time before putting elements in your queue.

Let us consider an example , suppose you reach a node at time t = 4 and the weight of the edge that you will be traversing is just 1 unit. Now suppose that the traffic light is red at t = 4 when you reached the node , but since you do not consider the extra waiting time during the if(dist[nn.dest]+x.dist< dist[x.dest] ) statement , your code fails on some cases

I modified your code , check it.
I just did the following modification to your code:

         long tempp = 0;
         if((dist[nn.dest])/k%2==1){
             long r = (dist[nn.dest]%k);
              tempp += k-r;
         }
           if(dist[nn.dest]+x.dist + tempp < dist[x.dest] )
           {
            dist[x.dest] = dist[nn.dest]+x.dist + tempp;

                node xx = new node();
                xx.dest=x.dest;
                xx.dist=dist[x.dest];
                queue.add(xx);
           }
          
        }

Since we now consider the extra waiting time in the variable tempp , It passes all the cases where it failed.
I hope I was Able to help you , you can check a neat implementation of this question in c++ here.
Thank You !

3 Likes
3

I got it thnx