rprudhvi590's blog

By rprudhvi590, history, 5 weeks ago, In English,

Chef likes to play with graphs a lot. Today he created a graph in the following way. He first lays down N nodes in a circle. The nodes nodes are numbered from 1 to N , in the clockwise order, i.e. the node 2 is followed by 1, 3 is followed by 2, and 1 is followed by N . There is an edge between each adjacent pair of vertices, so there are total N such edges. Each edge has an integer associated with it (may be negative).

we will be given start and end then we have to find minimum cost for going from start to end

link:https://www.codechef.com/problems/CHEFCRUN

Input: 5

-5 100 100 100 2

1 5

Output:

-8

Explanation Chef goes from 1 to 2 by incurring a cost of -5. Then from 2 to 1 using the edge second time and incurring cost of -5 again. Now, he can not use the edge between 1 and 2 again, as he has traversed the edge already twice. Now he will go from node 1 to node 4 by paying a cost of 2. Total sum of costs incurred is -5 + -5 + 2 = -8. This is the minimum possible cost that Chef can have

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

»
5 weeks ago, # |
Rev. 7   Vote: I like it +8 Vote: I do not like it

Imagine that all of the edges are stored in arr (the weight of the edge is stored). Create an array with size N in order to keep the prefix-sum. Then do this:

if (l > r) swap(r, l);
int sum = 0;
for (int i = 0; i < n; i++) {
  sum += arr[i];
  preSum[i] = sum;
}

Then for each query print(min(preSum[l — 1] + preSum[r], TotalSum — preSum[l — 1] — preSum[r])). TotalSum is the sum of all the edges' weights. r and l are the nodes that we want to find the path between.
I hope it helped.
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Remember, it is not a complete solution but the main idea is the same...

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    well there is one more condition here since the edges can be negative weighted and also we can visit each edge twice then we can simply traverse the edge back and forth so we add (2*weight) to our ans,in case the edge weight is negative our ans gets reduced by (2weight)

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, as you said it is easy to handle it when we have negative edges and we can visit them twice. Just multiply negative values by 2.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by rprudhvi590 (previous revision, new revision, compare).

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by rprudhvi590 (previous revision, new revision, compare).