10192 - Vacation

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

Moderator: Board moderators

howa
New poster
Posts: 6
Joined: Sat Jun 12, 2004 8:13 am

Post by howa » Sat Jun 12, 2004 11:13 am

No............
I still got WA............................>.<
help

User avatar
angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

Post by angga888 » Sat Jun 12, 2004 11:27 am

howa wrote:No............
I still got WA............................>.<
So strange... :-? I have modified your program and submitted it.
It got AC.

This is the only change in your program:
[pascal]var
a,b:string;
cost:array[0..2000,0..2000] of longint;
i,j,k,n:longint;
begin
k:=0;
while not eof(input) do
begin
inc(k);
fillchar(cost,sizeof(cost),0);
readln(a);
if a='#' then exit;
readln(b);
...
end.[/pascal]

howa
New poster
Posts: 6
Joined: Sat Jun 12, 2004 8:13 am

Post by howa » Sat Jun 12, 2004 11:34 am

Oh sorry~
I deleted the readln(b) carelessly ==;
Thanks~~~! :D :)

na5ir_algo
New poster
Posts: 2
Joined: Sat Jul 10, 2004 11:27 am

10192 vacations i got WA

Post by na5ir_algo » Sat Jul 10, 2004 11:54 am

if i put !cin.eof() in most outer while loop it will give me Time limit Exceed Error
and if i put ture in most outer while loop it will give me wrong answer please tell me whats the problem with my program.

Code: Select all

[cpp]
#include <iostream>

using namespace std;

int main (void)
{
	const short maxlength = 100;
	char text1[maxlength] = {'\0'};
	char text2[maxlength] = {'\0'};

	short check = 0;
	short stext1 = 0;
	short stext2 = 0;
	short countcase = 0;
	short j = 0;
	short i = 0;
	short visit1 = 0;
	short visit2 = 0;

	while(true)
	{
		countcase++;
		check++;
		cin.getline(text1, maxlength);

		if(text1[0] == 35)
			break;
		if(text1[0] == 35)
			break;		

		cin.getline(text2, maxlength);

		if(text2[0] == 35)
			break;
		if(text2[0] == 35)
			break;


		for(i = 0; text1[i] != '\0'; i++)
			stext1++;

		for(i = 0; text2[i] != '\0'; i++)
			stext2++;		

		j = 0;
		short i = 0;
		visit1 = 0;
		visit2 = 0;

		while(i != stext1 && j != stext2)
		{
			if(text1[i] == text2[j])
			{
				i++;
				j++;
				visit1++;
			}
			else if(j < stext1-1)
			{
				j++;
			}
			else if(i < stext2-1)
			{
				i++;
			}
		}
		
		j = 0;
		i = 0;

		while(i != stext1 && j != stext2)
		{
			if(text1[i] == text2[j])
			{
				i++;
				j++;
				visit2++;
			}
			else if(i < stext1-1)
			{
				i++;
			}
			else if(j < stext2-1)
			{
				j++;
			}
		}

		if(visit1 == 1 && visit2 == 1)
		{
			cout<<"Case #"<<countcase<<": you can visit at most "<<visit1<<" city."<<endl;
		}
		else if(visit1 >= visit2)
		{
			cout<<"Case #"<<countcase<<": you can visit at most "<<visit1<<" cities."<<endl;
		}
		else if(visit2 > visit1)
		{
			cout<<"Case #"<<countcase<<": you can visit at most "<<visit2<<" cities."<<endl;
		}

	}

	cout<<endl;

	return 0;
}
[/cpp]
-A-S-D-F-G-H-J-K-L-

jackie
New poster
Posts: 47
Joined: Tue May 04, 2004 4:24 am

Post by jackie » Sat Jul 24, 2004 5:25 am

I use normal DP LCS algorithm and got AC

BTW you should output "cities" although the answer is 1.

mshashi
New poster
Posts: 5
Joined: Sat Jul 31, 2004 1:35 pm
Location: IIT Kanpur
Contact:

WA in 10192

Post by mshashi » Tue Aug 03, 2004 6:58 am

I am using the normal longest common subsequence algorithm for this problem but I am getting wrong answer. Can anybody tell me about some special input/output for this problem, for which my program may not be working ???
Try try try ........... again :-)

sklitzz
New poster
Posts: 32
Joined: Fri Dec 03, 2004 5:19 pm

10192 WA problem

Post by sklitzz » Fri Feb 18, 2005 10:33 am

I think the algorithm is ok, but I still get WA?!

Code: Select all


//Vacation( 10192 ACM )

#include <stdio.h>
#include <string.h>

#define MAX 101

char s1[MAX], s2[MAX];

int lcs()
{
	int i, j;
	int dp[MAX][MAX] = { 0 };
	int len1 = strlen( s1 ), len2 = strlen( s2 );
	
	for( i = 1; i <= len1; ++i )
		for( j = 1; j <= len2; ++j )
		{
			if( s1[i] == s2[j] ) dp[i][j] = dp[i-1][j-1] + 1;
			else if( dp[i-1][j] >= dp[i][j-1] ) dp[i][j] = dp[i-1][j];
			else dp[i][j] = dp[i][j-1];
		}
	return dp[len1][len2];
}

int main()
{
	int i = 0;
	while( gets( s1 ) && gets( s2 ) && ++i )
		printf( "Case #%d: you can visit at most %d cities.\n", i, lcs() );
		
	return 0;
}

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Fri Feb 18, 2005 2:07 pm

You should do something like make sure s1 is not "#".. I think.. just in case..

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Location: Dhaka, Bangladesh
Contact:

Post by Solaris » Fri May 20, 2005 9:22 pm

First of all,

Input:
aaab
abaaa

Output:
Case #1: you can visit at most 3 cities.

Well the post of 'infancy' really puzzled me for a while and to get the output as 2 cities I modified normal LCS (Longest Common Subsequence) and removed any repeatation of cities. But the OJ gave WA. :P

Typical LCS algorithm stated in the CLRS book is enough to solve this problem. :-?
Where's the "Any" key?

thinker_bd
New poster
Posts: 22
Joined: Thu Jun 09, 2005 1:44 am

10192 TLE : though i did dp solution but got TLE Help please

Post by thinker_bd » Tue Jul 05, 2005 8:11 pm

10192 though i did dp solution but got TLE Help he please.my code is following. please say why i got TLE .

Code: Select all

#include <stdio.h>
#include <string.h>

#define SIZE 100

char X[SIZE],Y[SIZE];
int c[SIZE][SIZE];
int i,j,m,n;

int LCSlength() 
{
  m=strlen(X);
  n=strlen(Y);
  
  for (i=1;i<=m;i++)
	  c[i][0]=0;
  
  for (j=0;j<=n;j++)
	  c[0][j]=0;
	
  
  for (i=1;i<=m;i++)
	{
		for (j=1;j<=n;j++) 
		{
			if (X[i-1]==Y[j-1])
				c[i][j]=c[i-1][j-1]+1;
			
			else if (c[i-1][j]>=c[i][j-1])
				c[i][j]=c[i-1][j];
			
			else 
				c[i][j]=c[i][j-1];
			 
		}
	}
  return c[m][n];
}


int main() 
{
	int t_case=0;
	freopen("10192.txt","r",stdin);
	while (gets(X)!=NULL) 
	{
		t_case++;
		if(X[0]=='#')
			break;
		gets(Y);
		int len=LCSlength();
		printf("Case #%d: you can visit at most %d cities.",t_case,len); 
		printf("\n");
	}
	return 0;
}

thinker_bd
New poster
Posts: 22
Joined: Thu Jun 09, 2005 1:44 am

10192 TLE : though i use DP solution i got TLE help PLZ

Post by thinker_bd » Tue Jul 05, 2005 8:41 pm

10192 TLE : though i use DP solution i got TLE help PLZ. my code is following

Code: Select all

#include <stdio.h>
#include <string.h>

#define SIZE 100

char X[SIZE],Y[SIZE];
int c[SIZE][SIZE];
int i,j,m,n;

int LCSlength() 
{
  m=strlen(X);
  n=strlen(Y);
  
  for (i=1;i<=m;i++)
	  c[i][0]=0;
  
  for (j=0;j<=n;j++)
	  c[0][j]=0;
	
  
  for (i=1;i<=m;i++)
	{
		for (j=1;j<=n;j++) 
		{
			if (X[i-1]==Y[j-1])
				c[i][j]=c[i-1][j-1]+1;
			
			else if (c[i-1][j]>=c[i][j-1])
				c[i][j]=c[i-1][j];
			
			else 
				c[i][j]=c[i][j-1];
			 
		}
	}
  return c[m][n];
}


int main() 
{
	int t_case=0;
	freopen("10192.txt","r",stdin);
	while (gets(X)!=NULL) 
	{
		t_case++;
		if(X[0]=='#')
			break;
		gets(Y);
		int len=LCSlength();
		printf("Case #%d: you can visit at most %d cities.",t_case,len); 
		printf("\n");
	}
	return 0;
}

Raj Ariyan
Learning poster
Posts: 70
Joined: Sat Feb 05, 2005 9:38 am
Location: Gurukul

>>>>>

Post by Raj Ariyan » Mon Jul 11, 2005 7:17 am

Hi Thinker,
I cant understand why u use i,j,m,n variable as a global variable. I think u know clearly that how global variable initialize. This is the reason for ur TLE. Just cut those line and paste it in your LCS() function. Another thinks u will get RTE after modifying this. So also change the size. Use SIZE 1000 instead of SIZE 100. Good Luck :D .
Some Love Stories Live Forever ....

Raiyan Kamal
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
Location: Bangladesh
Contact:

Post by Raiyan Kamal » Thu Jul 14, 2005 10:29 pm

We are supposed to discuss problems of Voluem 3 here, not 101.

Raiyan Kamal
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
Location: Bangladesh
Contact:

Post by Raiyan Kamal » Thu Jul 14, 2005 10:51 pm

No need to make size 1000. I got AC using 105.

User avatar
mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

Post by mohiul alam prince » Tue Aug 02, 2005 12:00 pm

Hi thinker_bd

just increase your SIZE value and get ur AC :)

Thanks
MAP

Post Reply

Return to “Volume 101 (10100-10199)”

Who is online

Users browsing this forum: No registered users and 1 guest