you can not start from every car,
e.g.
CAPACITY Array:- 3 0 0 0 1 1 2,
you can not start from first car.
can you explain the case when we do not have enough fuel to reach next car, but after sorting it is giving correct answer why???
1 Like
In question it is written that there is always at least one possible path.
I think question not well written/framed I didnât understand the question correctly even after reading it several times.
2 Likes
so that case will not happen when we do not have enough fuel ??
it is not properly mentioned in question
I think it was written , anyways I canât confirm because question is non accessible nowâŚ
The language of the question was highly unprofessional, it has already been said that I can only fill fuel up to c[i] for ith car, whereas in the solution given you will for some car exceed c[i], this is very unprofessional on setterâs part, I want a proper explanation for this shit. I could have easily solved this question if the language was more lucid and clear.
10 Likes
yes , I also feels the same , the explanation of question was very poor.
1 Like
yes, most of the people got correct answer with hit & trail / random⌠Codechef should recheck their questionâs language before holding the contest.
2 Likes
Can anyone give the proof that if we greedily buy n litres of gasoline, there will always be a car which will not run out of fuel before the complete circle?
True,
Literally Problem Statement was very poorâŚ
I have spent two hours to this problem and couldnât get itâŚ
and I lost my 5 months streak as well⌠
where in solution fuel taken is exceeding capacity?
Here we have to sort according the the cost. That is, if we sort a vector of pair of integers(c and f ), pair with less cost is before the one with more cost.
f is already per liter.
Try to do by induction.
P(m) = If we select m cars and fill xi fuel in them such that xi>0 and x1+x2+x3+âŚxm = N,then there is a way such that no car run out of fuel.
P(1), P(2) is quite obvious.
Now, Let P(m) is true
In case of P(m+1),there are two cases:
- every ith car out of these m cars has fuel such that it just reaches i+1 th car.
- There is a car i which has more fuel than required to reach i+1 th car. Select i and i+1th car and merge them , now there are m cars. According to inductive hypothesis, there is a solution to this problem, now try to prove from here that there is solution to problem with m+1 cars as well. (Its quite easy from here).
Can any1 tell whats wrong with my soln
CodeChef: Practical coding for everyone . I am using same greedy approach
1 Like
The capacity of the tank is infiniteâŚonly inital filling is limited.
This should have been mentioned in the question.
@dhruv788 I donât think so we can start from any point like f = [0,0,2,0,0,0,15] c = [1,1,1,1,1,1,5] as we cannot start from the third index .
I meant that if your sum of capacity of tank is N , then there is always atleast one node via which you can cover distance N.
oh okay, I understood it otherwise yeah its correct then