Can anyone give the tutorial for this problem
There are two possible basic cases which you need to consider here. Firstly you may start from the start node and go all the way to the end node or vice versa. And as the problem statement says you may visit any edge twice but not thrice,assume you have taken the path from start to end hence you cant visit any node twice in between them because then you will have to visit the edge thrice,therefore we discard this case. Assuming you are going to go clockwise from start to end ,you may also take a path from start in anticlockwise direction till the state where you are getting negative values as a sum. Same is the case with end node ,you may also take a path from end node in clockwise direction till the sum is negative. Combining these two situations,you overall have to subtract the maximum sum of subarray on the other side.You will also need to take the case when you will go from the end to start and hence take the minimum of these two cases to reach the final solution!
Happy Coding 
6 Likes
Do the following for going ClockWise and then CounterClockWise.
1st
Take the cost for making one full loop from start to start and then to end.
N = 5 Start = 1 End = 3
Check Path 1 2 3 4 5 1 2 3
2nd
Break the path into three parts:
- Take the cost of going CCW to a point before the end CW back to the start
- CW to the end
- CW past the end (but not too far). Cannot go on a leg of the path that was traveled in the first part. Then CCW back to the end.
2 is easy to calculate.
Build a stack that keeps track of the minimum cost for step 3 for traveling AT MOST up to a particular node on the path back up to start. It might be better not to go ALL the way up to that particular node, but you still have to check them all. Then find the cost for step 1 going to a particular node and add it to the minimum cost of step 3 of POSSIBLY going up to that particular node. Add 1 2 and 3 together.
Do it all again, but reverse all directions.
Take the min of the four possibilities.
Since the track is circular, there are two ways of getting from start->end. Let’s call it left and right, one way of going from the left-hand side of start and the other by going from the right-hand side. Store the start->end edge values in two separate arrays each for both the directions.
Then apply Kadane’s algorithm to get the max positive continuous sub-array of the left-side array and right-side array and also the sums of the left side and right side, as maxl, maxr, suml, sumr. (maxl and maxr should be >=0)
The answer will be equal to min(suml+2*(sumr-maxr), sumr+2*(suml-maxl))
Complexity: O(n)
Theory wise, there will be 8 probable paths from start->end considering both the left-side and right-side.
-
Straight from start to end
-
Go a little back from start, and then come back to start and go to end from opposite direction.
-
Go from a start to a distance little further from end and then come back to end.
-
Combination of #3 and #4 (Should be careful for overlapping case)
Each of the above will be for either of the sides, so total 8.
1 Like
you can get sum of start to end :
sum of one side(start to end) and (for other side)account minimum walk that go back from start and pass end point and return to end point with segment tree and sum whit our sum of one side(we must calculate this way for two side!) then minimum of two earned sum for two side is answer! you must earn minimum of walk that include go back from start and then pass from end point and return to end point with segment tree
Using segment trees is redundant here… segment tress are useful if we work on at some random ranges given that the array is unchanged… but here at every case the array of values is being changed… So, in fact using segment trees will degrade the performance… And it is clearly evident in your code… See… the max time that your code took to solve the toughest subtask is 1 sec… but if we just use brute force… it could easily be done in just around 0.15 sec… @ ahmadreza 1994
Same Logic ! 
This problem can be solved using DP on prefix sums. Here is my
[1].
<b>Explanation:</b>
Since the path is circular, we can reach from start to end to 2 ways. Call one path primary and other one secondary. The primary path is one which is always traversed, while from the secondary one, we either do not traverse it at all or traverse some part of it twice. (You can draw a small diagram it your notebook to understand it better). If we see again the secondary path boils down to a circular array itself, where start and end are related. We want to minimise the sum such that the sub-array chosen from secondary path have some part from start side and some from end side (may be empty as well). So How to do this?
Consider an $O(n^2)$ solution first. Consider an array of length "n". Consider left indices and right indices and calculate the prefix sums for both. The answer will be minimum over all possible combinations of left and right prefix sums. Since both can be $O(n)$ in number, number of such pairs will be $O(n^2)$.
Now we can actually store the prefix sums for forward and backward array. Then we build a dp on it, where dp[i] denotes the minimum prefix sum we get for all indices from $1 <= x <= i$. In my code dp1 is from left part and dp2 is for right part. Then 3 cases arise:
1. Either we chose only left part (dp1 in my code)
2. We chose only right part (dp2 in my code)
3. Or we chose a combination of both, making sure they do not overlap (dp1 + dp2 condition in my code)
If you still have any doubts, you can ask in comments section below.
[1]: https://www.codechef.com/viewsolution/11108564What is wrong in my code. I am getting a WA on this.
Problem https://www.codechef.com/AUG16/problems/CHEFCRUN
My Solution http://ideone.com/E5UsdS
1 Like
complexity:O(n)
difficulty:medium
u can pass 1 edge only 2 times not more then that so according to this condition u will find that for any possible path from start node to end node there is one whole side(start->end) can be clockwise or anti-clockwise such that all edges from start to end are traveled only once, example draw the line from start node to end node which will cut the circle in two half so u will find that all sides on any one half are traveled only once and the edges which are traveled twice will be on other half.
so the answer will be like this
let say,
sum of the values of all edges on right half side is Rvalue1.
sum of the values of all edges on left half side is Lvalue1.
sum of the values of edges traveled twice on right half side is Rvalue2.
sum of the values of edges traveled twice on left half side is Lvalue2.
case 1:twice traveled sides are on left side so the value will be:Rvalue1+2*Lvalue2.
case 2:twice traveled sides are on right side so the value will be:Lvalue1+2*Rvalue2.
we have multiply with 2 because they are traveled 2 times.
so answer will be min of case 1 and case 2
now, the problem is to find rvalue2 and lvalue2.
let’s see how we can find it.
we have to reach end node from start node so we can go directly on any side clockwise or counterclockwise.
But we are going twice on some sides to reduce the cost of traveling.And u will find that we can go from start node up to one node and we will back to start node by traveling twice just to reduce cost from start node only,like this we can do at end node after reaching there from one side u can go up to some extinct on other side and travel back to end node just to reduce the cost.
assume if the case 1 is giving minimum value for our case then to find Lvalue2 we will find max possible continuous sum on left side between start node and end node let say maxContSum and we will subtract it from Lvalue1 by doing this we will end up with the sum of edges that are connected to start node or end node or both depends upon maxContSum which we will travel to get -ve value from starting or/and after reaching at end node, if our maxContSum is equal to Lvalue1 then it suggests that we cant reduce the cost by going twice on left side from either start or end node(means we are not getting some -ve cost to decrease over all cost by doing this).
so the Lvalue2=Lvalue1-maxContSum(on left side).
As we can find Rvalue2.
In O(n) complexity and we won’t get TLE.
And by above method we can find correct answer.
Happy coding.
I don’t think my approach is right because my code couldn’t pass all the testcases.
This is my approach. Please help me to find the mistake in my approach.
Step 1: min1 = 0, min2 = 0;
stepsum1 = 0, stepsum2 = 0;
Step 2: find the value of min1, stepsum1, min2, stepsum2 such that min1 is the minimum sub-array sum from source to destination, stepsum1 is the sub-array sum is along the path from source to destination, min2 is the minimum sub-array sum from destination to source and sum2 is the sub-array sum is along the path from destination to source. I have calculated stepsum1,min1,stepsum2 and min2 simultaneously by comparing the edge weights.
This is the fragment of code(to make it clear),
while(true){
if(visited[dec(i,n)]||visited[j])
break;
if(v[dec(i,n)] < v[j]){
stepsum1 += v[dec(i,n)];
visited[dec(i,n)] = true;
i = dec(i,n);
}
else{
stepsum2 += v[j];
visited[j] = true;
j = inc(j,n);
}
if(min1 > stepsum1)
min1 = stepsum1;
if(min2 > stepsum2)
min2 = stepsum2;
}
step 3: ans1 = 2*(min1+min2)+sum, where sum is the total sum from source to destination other way.
step 4: Do the same other way and find ans2
Step 5: return min(ans1,ans2)
Thank you in advance…
Method:
This problem can be easily solved using Kadane’s Maximum sub-array sum algorithm.
Just calculate maximum sub-array sum from start to end (clockwise), say, MaximumSumClockwise and the normal sum from start to end again clockwise, say, SumClockwise.
Next calculate maximum sub-array sum from start to end (counter - clockwise), say, MaximumSumCounter and the normal sum from start to end again counter-clockwise , say, SumCounter.
- Take the default values of the variable storing the maximum sum to be 0. *
Now the answer is just the minimum of ( 2*(SumClockwise - MaximumSumClockwise) + SumCounter) and (2*(SumCounter - MaximumSumCounter) + SumClockwise).
Reason:
There are 2 possibilities:
1.) You go Counter Clockwise from start, come back to start go Clockwise to end, go further and then return.(You may neglect any of the extra path, if it is not profitable!)
2.) You go Clockwise from start, come back to start go CC to end, go further and then return.(You may neglect any of the extra path, if it is not profitable here too!)
Take minimum of these two paths!
The AC Solution:
https://www.codechef.com/viewsolution/11138087
4 Likes
i have solved my question similar to your approach , u can see my solution , it is easy to understand i have used vry basic concept Solution
@depakks1995: Hey, try this test-case,
Input:
1
8
-1 -1 -1 -1 -1 1 -1 -1
1 4
Correct-Output:
-11
Your Output:
-9
Reason for -11:
Path: 1->8->7->8->1->2->3->4->5->6->5->4
You only calculated maximum negative paths, So you take 1 + (-1) + (-1) as good in your case while it would be better to go around and leaving the (1).
Can someone please tell me how to solve CHEFRRUN , the link to the problem statement is https://www.codechef.com/AUG16/problems/CHEFRRUN . Please, I’ve been trying it but I haven’t been able to come up with a proper solution. I can’t ask a question because I don’t have sufficient Karma points. Thanks in advance
thanx for the help
My solution passes for the 1st subtask and for few cases in the 2nd and 3rd subtask.
Can somebody please provide me the testcase where my code fails? or any Suggestion so I can find my mistake.
Here is the link to the code :
[1]
Thank You
[1]: https://www.codechef.com/viewsolution/11110750