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

tea
New poster
Posts: 2
Joined: Thu Oct 03, 2002 5:38 pm

10192 - Vacation

Post by tea » Thu Oct 03, 2002 6:48 pm

do we ouput 1 city or 1 cities?

thx

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

Post by Ivan Golubev » Thu Oct 03, 2002 9:25 pm

Output "cities" in all cases.

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

Post by Larry » Tue Nov 12, 2002 5:36 am

I think this is just the longest common substring, but I can't get my DP to work.. is there any trick cases or am I using the wrong approach?

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

Post by Larry » Tue Nov 12, 2002 5:41 am

Nevermind. I return dp[x-1][y-1] which didn't work for x or y = 0. Got AC now.

off_algos
New poster
Posts: 29
Joined: Wed Nov 13, 2002 11:37 am
Location: india

i think the judge made a mistake

Post by off_algos » Wed Jan 08, 2003 7:02 pm

in the question the soln is obviously the the longest common substring

but if i compare
{
if(strlen(mother)!=strlen(father))
while(1);
gives me a timelimit exceeded
without it my code is running in 0:00:002 time but produces WA
heres is m code
can u help me

Code: Select all

#include <stdio.h>
#include <string.h>
char a[102],b[102];
int tbl[102][102];
int main()
{
    int i,j,na,cno=0,x,y,z,nb;
    while(scanf("%s%s",a,b)==2)
    {
	na=strlen(a);
	nb=strlen(b);
	for(i=0;i<na+1;i++)
	{
	    tbl[i][0]=0;
	}
	for(j=0;j<nb+1;j++)
	{
	    tbl[0][j]=0;
	}
	for(i=0;i<na;i++)
	    for(j=0;j<nb;j++)
	    {
		x=tbl[i+1][j];
		y=tbl[i][j+1];
		z=tbl[i][j]+1;
		if(a[i]==b[j])
		{
		    tbl[i+1][j+1]=z;
		}
		else
		{
		    tbl[i+1][j+1]=x>y?(x>z-1?x:z-1):(y>z-1?y:z-1);
		}
	    }
	printf("Case #%d: you can visit at most %d cities.\n",++cno,tbl[na][nb]);
    }
    return 0;
}

WanBa
New poster
Posts: 14
Joined: Mon Apr 28, 2003 11:21 am

Post by WanBa » Mon Apr 28, 2003 11:43 am

father: abca
mother: abda
according norm DP , the answer is 3.,however,the true is TWO.
destiny conditioned by past

infancy
New poster
Posts: 4
Joined: Thu Oct 09, 2003 1:55 pm

10192 help plz, Is norm dp enough for this problem??

Post by infancy » Thu Oct 09, 2003 2:11 pm

I used norm dp to try to solve this problem, but I find it difficult to deal with the case like this:
aaab
abaaa
since in my program, I find the lcs first, then deal with the duplicated ones. so, in the case above, I got 1 instead of 2. I guess in this problem we should get 2 as the answer.
so would someone please tell me how to solve such kind of problem??
Thank you!!! :roll:

Syed Mubashshir Husain
New poster
Posts: 9
Joined: Wed Apr 02, 2003 10:28 am

10192

Post by Syed Mubashshir Husain » Sun Oct 19, 2003 7:54 am

hello

WanBa said
"
father: abca
mother: abda
according norm DP , the answer is 3.,however,the true is TWO. "

It is totally wrong. I accpeted 10192.

40366
New poster
Posts: 4
Joined: Wed Jan 07, 2004 9:42 am

10192 run time error

Post by 40366 » Tue Jan 20, 2004 6:41 am

Code: Select all

# include<iostream>
# include<string>
# include<vector>
bool find_(vector<char> &A,int i,char s)
{
	for(int j = 0;j <= i;j++)
		if(A[j] == s)
			return true;
	return false;
}
int main()
{
  vector<char> A,B;
  char c;
  int count = 1;
  while(cin.get(c))
  {
	if(c == '#')
		break;
	while(c != '\n')
	{
		A.push_back(c);
		cin.get(c);
	}
	cin.get(c);
	while(c != '\n')
	{
		B.push_back(c);
		cin.get(c);
	}
	int **C = new int *[A.size()];
	int i,j;
	for(i = 0;i < A.size();i++)
	{
		C[i] = new int[B.size()];
		if (find_(A,i,B[0]))
			C[i][0] = 1;
		else
			C[i][0] = 0;
	}
	for(i = 0;i < B.size();i++)
		if(find_(B,i,A[0]))
			C[0][i] = 1;
		else
			C[0][i] = 0;
	for(i = 1;i < A.size();i++)
	{
		for(j = 1;j < B.size();j++)
		{
			if(A[i] == B[j])
				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];
		}
	}
	cout << "Case #" << count <<": you can visit atmost " << C[A.size() - 1][B.size() - 1] <<  " cities.\n";
	A.erase(A.begin(),A.end());
	B.erase(B.begin(),B.end());
	for(i = 0;i < A.size();i++)
		delete []C[i];
	delete []C;
	count++;
  }
  return 0;
}

zizi
New poster
Posts: 7
Joined: Fri Jan 30, 2004 4:51 am

Post by zizi » Wed Mar 10, 2004 10:00 am

so,what is the output for
aaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaa

thanks

User avatar
alu_mathics
Learning poster
Posts: 55
Joined: Sat Jan 24, 2004 9:30 pm
Location: Chittagong
Contact:

Post by alu_mathics » Wed Mar 10, 2004 1:02 pm

input:
aaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaa
WanBa said
"
father: abca
mother: abda
#
output:
Case #1: you can visit at most 8 cities.
Case #2: you can visit at most 0 cities.
Case #3: you can visit at most 9 cities.
cuii e

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

10192

Post by howa » Sat Jun 12, 2004 8:18 am

[pascal]var
a,b:string;
cost:array[1..2000,1..2000] of longint;
i,j,k,n:longint;
begin
while a[1]<>'#' do
begin
inc(k);
fillchar(cost,sizeof(cost),0);
readln(a);
if a[1]<>'#' then
readln(b);
if a[1]<>'#' then
begin
for i:=1 to length(a) do
for j:=1 to length(b) do
if a=b[j] then
cost[j]:=1+cost[i-1][j-1]
else
begin
cost[j]:=cost[j-1];
if cost[i-1][j]>cost[j] then
cost[j]:=cost[i-1][j]
end;
writeln('Case #',k,': you can visit at most ',cost[length(a)][length(b)],' cities.');
end;
end;
end.[/pascal]
Please help me~ :oops:

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

Post by angga888 » Sat Jun 12, 2004 8:42 am

Your algorithm seems ok, maybe you can try this:
[pascal]while not eof(input) do
begin
...
readln(a);
if a='#' then exit;
readln(b);
...
end;[/pascal]
Hope it helps :wink:

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

Post by howa » Sat Jun 12, 2004 10:24 am

Thanks~
But i still got WA >_<

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

Post by angga888 » Sat Jun 12, 2004 10:50 am

Oops... :o I forgot to tell you about the array.
The index should start from 0.
[pascal]cost:array[0..2000,0..2000] of longint;[/pascal]
Btw, 2000 is too big, isn't it?

Now it should be AC :D

Post Reply

Return to “Volume 101 (10100-10199)”