## 11093 - Just Finish it up

Moderator: Board moderators

vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:

### 11093 - Just Finish it up

I solved it in 1.6 seconds...
My algo...

1) see if total sum of qi-pi > 0 return " not possible...
2) otherwise start with each "potential node" from 1 to n and see if
sum does not become positive in between ..
3) the moment u find the first i satisfying (2) print i..

Can it be made faster by some nice idea incorporated or its just fine...

My algo seems to be O(n^2) ...
Is there any O(n) algo possible, may be by adding some greedy aproach...

If I will myself do hashing, then who will do coding !!!

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong
O(n^2) algorithm runs in 1.6s??
Mine is O(n), but it takes 1.555.

vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:

### @cho

I have explained my algo...
Isn.t it O(n^2)...

because in case there is a solution possible .. I start from each node and see I don't encounter any state where my sum (qi-pi) from that node becomes positive..
This in worst case goes on for all n stations .. so O(n^2)...

Could u pm me ur algo or give some idea of ur O(n) algo...

btw I used scanf and printf, may be that caused some improved time..
If I will myself do hashing, then who will do coding !!!

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

### Re: 11093 - just finish it up

vinay wrote:2) otherwise start with each "potential node" from 1 to n and see if sum does not become positive in between ..
What node is a "potential node"?
vinay wrote:Could u pm me ur algo or give some idea of ur O(n) algo...
Think about the linear time solution of finding maximum contigious subarray sum.

StatujaLeha
Learning poster
Posts: 91
Joined: Tue May 31, 2005 2:01 pm
Location: Russia
I don't understand one thing.
First example:
5
1 1 1 1 1
1 1 2 1 1
Why I cannot finish lap from station 4? I can get 1 gallon of petrol at station 4. It's enough to go to station 5. At station 5 I can get 1 gallon of petrol and finish lap.

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong
If you start at station 4, you have to go back to station 4 to finish the lap.

StatujaLeha
Learning poster
Posts: 91
Joined: Tue May 31, 2005 2:01 pm
Location: Russia
Cho wrote:If you start at station 4, you have to go back to station 4 to finish the lap.
Thanks, I have understood.

vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:

### Re: 11093 - just finish it up

[quote="Cho"]
What node is a "potential node"?
[quote]

potential node is one for which qi-pi is <=0

well I have found the linear time algo...
Let me give it a try....

I think the judge's data isn't strong enough to differantiate between a O(n^2) and O(n) algo...

Checking that the total sum of qi-pi over all stations wasn't >0 so that the solution existed was enough ...
That I had done and so acc in 1.6 seconds
If I will myself do hashing, then who will do coding !!!

kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia
I solved it in O(n) as follows:

1. Starting from any station (let's call it START) and trying to finish the lap. If it's possible then goto print answer, else let's say I couldn't get from p to p+1.

2. Starting from p+1 and trying to finish lap. (I don't need to look for the path starting from intermediate stations!).

It repeats until path is found or p+1 > START. Thus it's O(n).

ytsejam
New poster
Posts: 3
Joined: Tue Aug 01, 2006 5:27 pm
Can someone post some test cases?
I'm having some trouble getting AC !

smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am
input
5
9
1 3 1 4 2 1 2 3 2
2 2 1 3 1 3 1 1 1
5
2 6 7 1 1
3 7 1 1 1
6
1 8 9 6 4 1
9 1 1 2 3 2
7
13 1 2 1 3 1 2
1 2 3 1 14 3 1
6
1 2 3 4 1 4
12 3 2 1 2 1
5
3 4 4 5 6
2 1 1 14 1
output
Case 1: Possible from station 2
Case 2: Possible from station 3
Case 3: Possible from station 2
Case 4: Not possible
Case 5: Not possible
Case 6: Possible from station 5
A simple O(n^2) works fine! Dont make your program sophisticated!
fahim
#include <smile.h>

mrahman
New poster
Posts: 25
Joined: Mon Oct 24, 2005 9:45 am
Contact:
Thank you smilitude for your test input.

I solved it using kp's method. But why this is O(n). Can anyone explain. Is there anyother method to solve this problem?

Sorry for my poor english
Practice Makes a man perfect

StAnger
New poster
Posts: 3
Joined: Tue Sep 08, 2009 11:15 pm

### Re: 11093 - Just Finish it up

I don't understrand why my code get WA.
Could some one take a look at my code?

Code: Select all

``I've solved the problem by initializing data at beginning of each step.``

uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

### Re: 11093 - Just Finish it up

smilitude wrote:A simple O(n^2) works fine! Dont make your program sophisticated!
I can confirm that this statement is true. However, a completely naive implementation will not work. It requires a wee bit of optimization.

Also, in the test case above, be sure to change the number of cases to 6 (from 5).
Check input and AC output for over 7,500 problems on uDebug!

unreleased
New poster
Posts: 16
Joined: Sun Nov 10, 2013 7:41 pm

### Re: 11093 - Just Finish it up

query: why WA??
is the idea wrong??

Code: Select all

``````//Mr. WA its for you//
//This may contaminated by WA//
//Aph you see ke y WA ....its not cypher//
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <iterator>
#include <map>
#include <set>
#include <sstream>
#include <utility>
#include <bitset>

#define mx 100000
#define INT 2147483647

#define D   double
#define L   long
#define LL  long long
#define ULL unsigned long long
#define SS stringstream

#define isc1(a)      scanf("%d", &a)
#define isc2(a,b)    scanf("%d%d", &a, &b)
#define isc3(a,b,c)  scanf("%d%d%d", &a, &b, &c)
#define llsc1(a)     scanf("%I64d", &a)
#define llsc2(a,b)   scanf("%I64d%I64d", &a, &b)
#define llsc3(a,b,c) scanf("%I64d %I64d %I64d", &a,&b,&c)

#define f(a,n)  for(a=0; a<n; a++)
#define all(a)  a.begin(), a.end()
#define ms(arr) memset(arr, 0, sizeof(arr))
#define cl(a)   a.clear()
#define sz(a)   a.size()

#define sc scanf
#define pf printf
#define pu push_back
#define pb pop_back
#define vc vector
#define mp make_pair
#define fi first
#define se second
#define pip pf("pip.....\n")

using namespace std;

int main()
{
// freopen("input.txt", "r", stdin);
//clock_t start = clock();
int a,b,c=1,d;
string str, str1, str2;
int tst, tst2,avl[123456], need[123456], temp[123456], pos;
LL sum1, sum2, sum3;
isc1(tst);
while(tst--)
{
ms(avl); ms(need); ms(temp);
pf("Case %d: ", c++);
isc1(tst2);
sum1=sum2=0;
for(a=0; a<tst2; a++)
{
isc1(avl[a]);
sum1+=avl[a];
}

for(a=0; a<tst2; a++)
{
isc1(need[a]);
sum2+=need[a];

temp[a]=avl[a]-need[a];

}

if(sum1<sum2)pf("Not possible\n");
else
{

for(a=0; a<tst2; a++)
{

if(b==tst2){break;}
b=pos=a; sum3=0;
if(temp[a]>=0)
{
while(sum3>=0 && b<tst2)
{sum3+=temp[b++];}//cout<<b<<endl;}
}

}

pf("Possible from station %d\n", pos+1);
}

}

//start = clock()-start;
//pf("\n%lf sec", start/(D)CLOCKS_PER_SEC);
return 0;
}
``````