Moderator: Board moderators
What node is a "potential node"?vinay wrote:2) otherwise start with each "potential node" from 1 to n and see if sum does not become positive in between ..
Think about the linear time solution of finding maximum contigious subarray sum.vinay wrote:Could u pm me ur algo or give some idea of ur O(n) algo...
output5
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
A simple O(n^2) works fine! Dont make your program sophisticated!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
Code: Select all
I've solved the problem by initializing data at beginning of each step.I can confirm that this statement is true. However, a completely naive implementation will not work. It requires a wee bit of optimization.smilitude wrote:A simple O(n^2) works fine! Dont make your program sophisticated!
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;
}