10192 - Vacation

[howa]

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

[angga888]

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]

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

[na5ir_algo]

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]

[jackie]

I use normal DP LCS algorithm and got AC

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

[mshashi]

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

[sklitzz]

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]

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

[Solaris]

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.

Typical LCS algorithm stated in the CLRS book is enough to solve this problem.

[thinker_bd]

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]

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]

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 .

[Raiyan Kamal]

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

[Raiyan Kamal]

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

[mohiul alam prince]

Hi thinker_bd

just increase your SIZE value and get ur AC

Thanks
MAP