bro, it says that u can fill fuel up to f[i] for a car. and this is not the first time this has happened, look at the questions of codeforces and Atcoder how lucid are they and they even make NOTE for such trivial details. I appeal to the CodeChef admin, please take care of such, though I would point out in long challenges such ghastly mistakes are not there.
https://www.codechef.com/viewsolution/39875539
The solution satisfies all sample test cases but gives WA. Can anyone tell me whatâs wrong with the code?
i think you misunderstood my question, i want explanation for why?? part
i am definitely not going to drive in my life.
Change int cost to long long int cost
1 Like
what is wrong in my code .
The car can refuel itself anytime by spending coins
and bcz of this I have 5 WAâs in Q1 and 4 WAâs in Q2 
There is no penalty in lunchtime contest.
Thank you @avikrit_10, it worked. I wanted to know why that happened.
So what I did earlier long = int * int, what you suggested was long = int * long, so is it that in order to make sure result is of long type one of the value should be long. and also int * int will give answer of type int. Am I correct? I also tried (long)carrycap*cost; and that also worked so I think type casting back to long was necessary.
I donât think that the editorial (unlike the video editorial) really tries to explain why the condition is sufficient, that is why we can always pick a car that can drive the full circle without running out of gas.
1 Like
Am i the only one who thought that this was a DP problem?
1 Like
There is stronger fact - if we have exactly N litres of gasoline, there exist only one car we can start with and amount of fuel at every moment will be non-negative. It can be easily proved by induction on number of cars - if we have n+1 cars with n+1 litres of gasoline there exist two cars that we can âmergeâ into one and situation will become n cars and n litres where condition is satisfied.
Proof by induction :-
Number of cars or length of track is N
[SEE THE EXAMPLE AT THE END IF YOU DONâT UNDERSTAND THE PROOF AND THEN READ THE PROOF]
Base :-
- Any one car with exactly fuel n , so we can start at this car and travel n units with this car basically to the initial point or exactly one time around the track.
K Number of cars with total sum of fuel n :-
- Consider k number of cars placed at some position at circular track of length n and the sum of fuel of all this cars are exactly n [ no two cars should be placed at same position].
- Now the trick is to find the possible placement of cars such that we can not reach any other car from the starting car.
For example â consider this :- let the first car is at the position 1 , (postion p is the point where the car number p was present in our orginal problem) , and it has fuel f1 , so we can reach 1 + f1 positons from the fuel of this car , so letâs place next car at 2 + f1 , and now if car 2 has f2 fuel we can reach 2+f1+f2 and lets place third car at 3+f1+f2. In this type of placement we are not wasting any postions and the last car is placed at k + f1 + f2 ⌠+ fk-1 = k + n - fk and this final car can travel form k + n - fk +1 to k where we can guarantee that there exists at least one car form which we can reach k ( k > fk) or the placement is not possible because there was already another car (k = fk) or from car k we can travel to 1 (k < fk ) meaning no matter where we place this last car there exists at least one car form which we can reach another car.
- Now we realize that there is no possible way to place all cars such that we can not reach another car for the fuel of previous car. Another way to say this is there is atleast one pair of cars exist such that we can reach second car from first car with the first car fuel alone.
- Now the another trick is consider the case of k cars with total fuel n , and we know there exits atleast one pair , consider this pair and replace this two cars by another car at the positon of first car with the fuel of sum of this two cars.
This replacement of pair of cars with new car doesnât change our objective , because in the first case we are saying if we reach the first car we can get f1 fuel and if we reach second car we can get f2 fuel , but we know we can reach the second car with f1 fuel so , replacing the first car and second car with a car at first car position with fuel f1+f2 saying we can travel f1+f2 if we reach first car.
-
Now we have k-1 cars with the same total fuel of n , so we can guaranteed to find the another pair of cars. And do the step 4.
-
By doing this repeatedly we finally get 1 car at some position , this is the position where we can start our trip.
EXAMPLE :-
Consider the track of length of 6
Take 3 cars at position 1 5 6 with fuel 3 2 1
- from 1 we can travel upto 4 [ 1 - 2 - 3 - 4]
- from 5 we can travel upto 1 [5 - 6 - 1]
- from 6 we can travel upto 1 [ 6 - 1]
So there is atleast one pair of cars exist such that we can reach second car from first car with the first car fuel alone.
In this example there is three pairs , cars (2 ,3) , cars (2 , 1) and cars (3 , 1)
now take any pair letâs take cars (2 ,3) and combine.
Now we have a cars at positions 1 and 5 with fuel 3 and 3
- from 1 we can travel upto 4 [ 1 - 2 - 3 - 4]
- from 5 we can travel upto 1 [5 - 6 - 1 - 2]
here we have only one pair (2,1)
Combine them we left with one car at position 5 , which was our starting position for our initial problem.
If Something wrong with the proof let me know.
3 Likes
yes absolutely correct
What should be the answer for this test case?
1 1 2
1 10 1
setters solution gives 3 but shouldnât it be 11? (as you canât fill more than fi litres)
the answer is 3 -
from car 1 you take 1 unit of fuel it cost 1 coin
from car 3 you take 2 units of fuel it const 2 coins
you start travelling with car 3 , you have 2 units of fuel so you can reach 1 and 2, when you pass 1 you take the 1 unit of fuel so after reaching 2 you have 1 unit fuel left so using that you travel to 3 completing the one trip.
1 Like
I canât understand why day by day question clarity and test case explanation is decreasing in codechef
i am the one who got 90points in the contest
not able to find why the solution is working for 90points
can any tell why sorting the pair is working i mean proof
HELP NEEDED
Well I thought a different version for this question ans thus not able to solve it. But Can anyone suggest a possible soln. for it?
I thought the max tank capacity for a certain car is limited by fr[i], thus it canât have more than that fuel. If someone knows a possible soln. to solve it then plz present.