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
vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:

11093 - Just Finish it up

Post by vinay »

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

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

Post by Cho »

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

Post by vinay »

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

Post by Cho »

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 »

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

Post by Cho »

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 »

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

Post by vinay »

[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 »

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 »

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

Post by smilitude »

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 »

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 »

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

Post by uDebug »

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 »

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)”