Hi,
I came across this problem but I am unable to get: 1. how is the graph built 2. time loop meaning cycle? 3. the hint — each pair of pastures is connected by at most one road in each direction. 4. what is the approach ?
Can someone explain this problem to me in a more detailed and simpler way?
I think the editorial did its part but I am not able to do mine! : (
Auto comment: topic has been updated by disha00 (previous revision, new revision, compare).
Auto comment: topic has been updated by disha00 (previous revision, new revision, compare).
ek aisa graph banao jisme sari ndes reverse jae with the weight they are coming and then * last node to front node with negative of v[n-1]
this is the observation i had try to have your ideas on this thing may help u , if not just letme know
Hi If I am correctly getting your approach, if we caluclate cost of one round from start to end and then reverse traverse- what is the condition to stop? since negative weights hai toh cost <0 hoti jayegi, ek hi reverse round lagana hai?
Hey @disha00, Let me try. So the “graph” is mostly a way to think about the problem, you don’t actually build a huge graph with all pastures. The key is that when you sort the values, the differences between consecutive values behave like edges, and the solution just counts how often each such “edge” is used in all paths. And for the question next to that, “Time loop" or "cycle” just means you can move around and eventually come back to where you started. For solving the problem you don’t simulate these loops, you only need how many times each edge (difference between sorted elements) is included in the shortest paths between pairs. Moving next, “At most one road in each direction between a pair of pastures” simply means there are no multiple parallel edges between the same two nodes. So between any two pastures you can have 0, 1 (one direction), or 2 (both directions) edges, but not more than that. And for the last question, the intended solution would be roughly... Sort the array of values... look for the differences a[i] -a[i-1] ...For each such difference, count how many pairs of nodes use this gap on their shortest path, which can be computed using prefix/suffix counts and a formula (obv)... then multiply each difference by its count and sum everything up. Feel free to ask about anything that you didn't get. Also, if you want, I can write the exact formula and a concrete example to make it more clear. hope that helped ;)
Ohhk, getting the hang of it now thanks