452 - Project Scheduling

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

Moderator: Board moderators

User avatar
@ce
Learning poster
Posts: 71
Joined: Mon May 28, 2012 8:46 am
Location: Ranchi, India

Re: 452, Why WA

Post by @ce » Sat Jun 29, 2013 6:59 am

@brianfry713...thank you.
-@ce

kev_yu
New poster
Posts: 3
Joined: Sun Dec 29, 2013 8:46 am

Re: 452, Why WA

Post by kev_yu » Sat Jan 04, 2014 6:13 am

I don't understand why I get TLE my algo should run with O(V+E) time complexity. I have test the the test case given here and got it right. First I run topological sort with DFS then DP bottom up

Here is my code

Code: Select all

#include <iostream>
#include <cstdio>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <math.h>
#include <bitset>
#include <stack>

#define INF 800000010
using namespace std;

typedef pair<int,int> ii;
typedef vector<int> vi;
typedef pair<int,ii> iii;
typedef vector<iii> viii;
typedef vector<ii> vii;


vi topo;
int dist[110];
bool visited[110];
vii AdjList[110];

int xtr[4]={0,0,1,-1};
int ytr[4]={1,-1,0,0};
int maksimum(int a,int b)
{
	if (a>b)
	{
		return a;
	}
	else
	{
		return b;
	}
}

void toposort(int u)
{
	visited[u]=1;
	for (int i=0;i<AdjList[u].size();i++)
	{
		int S=AdjList[u][i].first;
		if (!visited[S])
		{
			toposort(S);
		}
	}
	topo.push_back(u);
}

int main()
{
	int TC,maks;
	int u,v,weight;
	char inp,term;
	scanf("%d",&TC);
	getchar();
	getchar();
	for (int b=1;b<=TC;b++)
	{
		if (b!=1) printf("\n");
		
		//Inisialisasi
		for (int i=1;i<=60;i++)
		{
			AdjList[i].clear();
		}
		for (int i=1;i<=60;i++)
		{
			visited[i]=0;
			dist[i]=0;
		}
		maks=0;
		inp=getchar();
		while ((inp!='\n'))
		{
			//printf("%c\n",inp);
			u=(int)inp-64;
			getchar();
			scanf("%d",&weight);
			term=getchar();
			AdjList[u].push_back(ii(u+30,weight));
			if (term!='\n')
			{
				inp=getchar();
				while ((inp!='\n') && (inp!=EOF))
				{
					v=(int)inp-64;
					AdjList[u+30].push_back(ii(v,0));
					inp=getchar();
				}
			}
			if (inp==EOF)
			{
				break;
			}
			else
			{
				inp=getchar();
			}
		}

		//topological sort
		for (int i=1;i<=60;i++)
		{
			if (!visited[i])
			{
				toposort(i);
			}
		}

		for (int i=topo.size()-1;i>=0;i--)
		{
			int cur=topo[i];
			for(int j=0;j<AdjList[cur].size();j++)
			{
				int S=AdjList[cur][j].first;
				int we=AdjList[cur][j].second;
				dist[S]=maksimum(dist[S],dist[cur]+we);
			}
		}
		for (int i=31;i<=60;i++)
		{
			if (maks<dist[i])
			{
				maks=dist[i];
			}
		}
		printf("%d\n",maks);
	}
	return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 452, Why WA

Post by brianfry713 » Thu Jan 16, 2014 12:31 am

It looks like you figured it out.
Check input and AC output for thousands of problems on uDebug!

kaushik_acharya
New poster
Posts: 17
Joined: Thu Jul 28, 2005 3:05 pm
Location: Bangalore, India

Re: 452, Why WA

Post by kaushik_acharya » Fri Mar 21, 2014 8:07 pm

Got RE.
Here's my code: http://ideone.com/f4nz44

Have done DFS based topological sort like others have mentioned in this thread.
Have also tested the code with the 100 test cases put by Brian Fry.

Wondering where could I have gone wrong.
My experience with Fraudster khari

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 452, Why WA

Post by brianfry713 » Fri Mar 21, 2014 10:57 pm

Try changing your tokenize function. It throws a RE if there is a trailing space on a line. I used sscanf().
Check input and AC output for thousands of problems on uDebug!

kaushik_acharya
New poster
Posts: 17
Joined: Thu Jul 28, 2005 3:05 pm
Location: Bangalore, India

Re: 452, Why WA

Post by kaushik_acharya » Sat Mar 22, 2014 6:34 pm

brianfry713 wrote:Try changing your tokenize function. It throws a RE if there is a trailing space on a line. I used sscanf().
@brian,
Thanks a lot. I didn't realised that the input lines can have trailing spaces.
I made a change on my tokenize function to check for reaching end of string.
My experience with Fraudster khari

vsha041
New poster
Posts: 35
Joined: Wed Feb 12, 2014 10:04 am

Re: 452, Why WA

Post by vsha041 » Sun May 11, 2014 12:39 pm

Thanks for the test cases Brian Fry. For this problem it requires some work to create testcases.

anando_du
New poster
Posts: 10
Joined: Sun Mar 01, 2015 3:11 pm

Re: 452 - Project Scheduling

Post by anando_du » Mon Jan 04, 2016 5:49 pm

Test cases are too weak i think ... My AC code produces output 0 for
1

A 42
This case

hasan169
New poster
Posts: 1
Joined: Sun Apr 03, 2016 1:23 pm

Re: 452 - Project Scheduling

Post by hasan169 » Sun Apr 03, 2016 2:21 pm

i have checked all the inputs of U debug but still getting WA.... can anyone give me special testcase
here is my code https://ideone.com/ZXxfQy

Post Reply

Return to “Volume 4 (400-499)”