Integers in your solution are going out of bounds, a simple long long datatype will do. 
CodeChef: Practical coding for everyone : Your solution with long long datatype.
Python 3-time complexcity O(n^2)
T=int(input())
for i in range(T):
N=int(input())
f=list(map(int,input().split()))
res=0
summ=0
for j in range(1,N):
summ=f[j-1]-1
if(summ<0):
break
else:
f[j]=summ+f[j]
res=res+1
if(f[j]==0):
break
if(res==N-1):
res=res+f[N-1]
print(res)
There is a simpler proof by contradiction.
Let b_i=q_i-1. Then we have \sum_1^N b_i=0, and at any moment in time from 2 to N the amount of fuel in the car we pick prior to stealing gasoline from the car we have just reached will be equal to the sum of b_i for that car and all the cars we have stolen gasoline from along the way.
So all we need to prove now is that there exists such an index i that all the partial sums from that index going clockwise are non-negative.
Let us call an arc from i to j (clockwise) good if all the partial sums of b_k starting from i along that arc are non-negative. We need to prove that there exists an index i such that a full circle from i to i clockwise is a good arc.
Assume that it is not so. Consider a set of all the good arcs. It is obvious that if two good arcs have a non-empty intersection than their union is also a good arc, so there will be a set of non-intersecting maximal good arcs such that every good arc is a sub-arc of one of those arcs, and if each of the maximal arcs is extended by one the sum of b_i along it will be negative (and they still will not intersect). But since the total sum of b_i is 0 there must exist a positive b_i outside of those arcs, which is a contradiction.
Thats what f[i] was for right?
What would have been your approach if instead of choosing any car we had to start with the first car? Will it still be doable using greedy or will it DP?
Ok. Appreciate the feedback.
Can you explain in more simpler terms?
Hi,
Can someone please help me in finding what is wrong with my code?
I have run test cases but they all seem to pass, still I am getting wrong answer.
If someone can provide test case where I am failing it would be helpful.
Code:
#include
using namespace std;
#define llu long long int
long int f[200001];
long int c[200001];
long int ans[200001];
int main() {
int t;
cin>>t;
int n;
// your code goes here
while(t--){
cin>>n;
for(int i=0;i<n;i++){
cin>>f[i];
if(f[i]>n){
f[i]=n;
}
}
for(int i=0;i<n;i++){
cin>>c[i];
ans[i]=1000000001;
}
for(int i=0;i<n;i++){
for(int j=i;j<i+f[i];j++){
//cout<<"i "<<i<<" f[i] "<<f[i]<<" j "<<j<<" ";
int k=j%n;
//cout<<"k "<<k<<" ans[k] "<<ans[k]<<"\n";
if(ans[k]>c[i]){
ans[k]=c[i];
}
}
}
llu ans2=0;
for(int i=0;i<n;i++){
ans2+=ans[i];
}
cout<<ans2<<"\n";
}
return 0;
}
Just a minor change: The problem links are broken for Div-1 and Div-2 contest. It should be LTIME instead of LTM
1 Like
can anyone please explain this line!!
vector order(n);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int a, int b) {
return cost[a] < cost[b];
});