11093 - Just Finish it up

All about problems in Volume 110. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

11093 - Just Finish it up

Post by vinay » Mon Sep 11, 2006 3:50 pm

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...

Thanks in advance... :lol:
If I will myself do hashing, then who will do coding !!!

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

Post by Cho » Mon Sep 11, 2006 5:19 pm

O(n^2) algorithm runs in 1.6s??
Mine is O(n), but it takes 1.555.

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

@cho

Post by vinay » Mon Sep 11, 2006 5:33 pm

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 !!!

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

Re: 11093 - just finish it up

Post by Cho » Mon Sep 11, 2006 6:56 pm

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

Post by StatujaLeha » Mon Sep 11, 2006 8:33 pm

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.

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

Post by Cho » Mon Sep 11, 2006 8:42 pm

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

Post by StatujaLeha » Mon Sep 11, 2006 8:49 pm

Cho wrote:If you start at station 4, you have to go back to station 4 to finish the lap.
Thanks, I have understood.

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

Re: 11093 - just finish it up

Post by vinay » Tue Sep 12, 2006 6:40 pm

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

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

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 :P
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

Post by kp » Tue Sep 12, 2006 10:40 pm

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

Post by ytsejam » Thu Sep 14, 2006 6:43 pm

Can someone post some test cases?
I'm having some trouble getting AC !

User avatar
smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

Post by smilitude » Sat Oct 07, 2006 3:22 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
Location: Bangladesh
Contact:

Post by mrahman » Tue Oct 10, 2006 1:37 pm

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?

Thanks in advance

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

Post by StAnger » Thu Sep 17, 2009 9:14 pm

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.

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

Re: 11093 - Just Finish it up

Post by uDebug » Tue May 27, 2014 12:24 pm

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!

Find us on Facebook. Follow us on Twitter.

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

Re: 11093 - Just Finish it up

Post by unreleased » Tue Mar 24, 2015 2:50 pm

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;
}

Post Reply

Return to “Volume 110 (11000-11099)”