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

ability
New poster
Posts: 2
Joined: Sun Apr 27, 2008 8:49 pm

### Re: 10192 - Vacation

Hi Farnak,
Error is at line#33 in the code. See here:
>>if (line1[i-1] == line2[j-1])

Index for both the strings starts at 0 and ends at len-1, and so it should be [i-1] and [j-1]. U hvn't checked the first characters of both the strings.

subzero
New poster
Posts: 26
Joined: Mon Aug 15, 2005 5:21 am

### Re: 10192 - Vacation

same problem here

after changing scanf by gets i got ac
There is no knowledge that is no power.

Sultan_Dhaka
New poster
Posts: 2
Joined: Wed Nov 02, 2011 8:26 am

### Re: 10192 - Vacation

I have submitted the following code which seems to me correct but I got Run-time eror . Can any one tell me where is the bug ??

#include<iostream>
#include<string>
#include<cstdio>
using namespace std;

int LCS(string a , string b)
{

int m,i,j,n,c[100][100];
m=a.length()-1;
n=b.length()-1;
for(i=1;i<=m;i++)
c[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( a.at(i)==b.at(j) )
c[j]=c[ j - 1] + 1 ;
else if (c[ j ] >= c[ j - 1] )
c[j] = c[ j ] ;
else
c[j]=c[j-1];
}
}
return c[m][n];
}

int main()
{
int test=0;
string a,b;
while(cin>>a && a.at(0)!='#' && cin>>b)
{
++test;
printf("Case %d: you can visit at most %d cities\n",test,LCS('1'+a,'1'+b));
}
return 0;
}

fryzito
New poster
Posts: 2
Joined: Wed Nov 23, 2011 3:38 am

### Re: 10192 - Vacation

I recommend not to use

while ((gets (str1) & & str1 [0]) & & (gets (str2) & & str2 [0]) & & str1 [0]! = '#' & & str2 [0]! = '#') {

but only

while (gets (str1) & & gets (str2) & & str1 [0]! = '#') {

kumar_utpal
New poster
Posts: 2
Joined: Thu Dec 15, 2011 9:49 am

### 10192 - Vacation(runtime error) . can't find any solution..

#include <cstdio>
#include <sstream>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>
#include <stack>
#include <list>
#include <iostream>
#include <fstream>
#include <numeric>
#include <string>
#include <vector>
#include <cstring>
#include <map>
#include <iterator>
#include <bitset>

using namespace std;

string s1,s2;

int LCS()
{
string s3;
s3+=" "+s1;
s1=s3;
s3=" "+s2;
s2=s3;
int a=s1.size(),b=s2.size(),i,j;
if(b<a)
{
swap(s1,s2);
swap(a,b);
}
int c[a];
for(i=0;i<b;i++)
c[0]=0;
for(i=0;i<a;i++)
c[0]=0;
for(i=1;i<a;i++)
{
for(j=1;j<b;j++)
{
if(s1==s2[j])
c[j]=c[i-1][j-1]+1;
else
c[j]=max(c[i-1][j],c[j-1]);
}
}
return c[i-1][j-1];
}

int main()
{
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
int k;
k=1;
while(1)
{
getline(cin,s1);
if(s1=="#")
break;
getline(cin,s2);
cout<<"Case #"<<k<<": you can visit at most "<<LCS()<<" cities."<<endl;
k++;
s1.clear();
s2.clear();
}
return 0;
}

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

### Re: 10192 - Vacation

The end of input occurs when the first sequence starts with an "#"character (without the quotes).

See what happens to your program if the the last line is:
#a
Check input and AC output for thousands of problems on uDebug!

sun_kuet
New poster
Posts: 12
Joined: Wed Mar 27, 2013 4:28 pm

### 10192 - Vacation - SE .Plz help

Code: Select all

#include<iostream>
#include<vector>
#include<string>
#include<cstdio>
using namespace std;
int main()
{
int lcs[105][105];
string s1,s2;

for(int k=1;;k++)
{
cin>>s1;
if(s1[0]=='#') break;
cin>>s2;
for(int i=0;i<=100;i++)
lcs[i][0]=0;
for(int j=0;j<=100;j++)
lcs[0][j]=0;
for(int i=1;i<=s1.size();i++)
for(int j=1;j<=s2.size();j++)
{
if(s1[i-1]==s2[j-1])
lcs[i][j]=1+lcs[i-1][j-1];
else
{
if(lcs[i-1][j]>=lcs[i][j-1])
lcs[i][j]=lcs[i-1][j];
else lcs[i][j]=lcs[i][j-1];
}
}
cout<<"Case #"<<k<<": you can visit at most "<<lcs[s1.size()][s2.size()]<<" cities."<<endl;
}
return 0;
}

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

### Re: 10192 - Vacation - SE .Plz help

Try a different problem.
Check input and AC output for thousands of problems on uDebug!

mrxy56
New poster
Posts: 1
Joined: Sun Aug 11, 2013 6:50 pm

### HELP!!!10192 Vacation------WHY TLE!!!

It's a LCS problem,I think I am absolutely right.But why TLE!!!Please help me!Thank you very much!!!
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int d[1010][1010];
char a[1010],b[1010];
int dp(int i,int j){
if(i<0||j<0) return 0;
int &ans=d[j];
if(ans>0)return ans;
if(a==b[j])
{
ans=max(ans,dp(i-1,j-1)+1);
}
else ans=max(ans,max(dp(i,j-1),dp(i-1,j)));
return ans;
}
int main(){
int len1,len2,count=0;
while(fgets(a,1010,stdin)!=NULL){
if(a[0]=='#')break;
fgets(b,1010,stdin);
if(a[0]=='\n'||b[0]=='\n') {printf("Case #%d: you can visit at most 0 cities.\n",++count);continue;}
memset(d,0,sizeof(d));
len1=strlen(a);
len2=strlen(b);
printf("Case #%d: you can visit at most %d cities.\n",++count,dp(len1-2,len2-2));
}
return 0;
}

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

### Re: HELP!!!10192 Vacation------WHY TLE!!!

I tried changing some parts of your code and got Submission Error, so try a different problem. See:
http://uva.onlinejudge.org/index.php?op ... 1&Itemid=1
Check input and AC output for thousands of problems on uDebug!

dibery
Learning poster
Posts: 76
Joined: Sat Feb 23, 2013 4:16 pm
Location: Taiwan, Taipei
Contact:

### Re: 10192 - Vacation

A sample input:

Code: Select all

ff

#
Output:

Code: Select all

Case #1: you can visit at most 0 cities.
Case #2: you can visit at most 0 cities.
I was careless enough to output only a 0 and got WA for many times.
Life shouldn't be null.

emrankdr
New poster
Posts: 2
Joined: Mon Dec 22, 2014 9:40 am

### Re: 10192 - Vacation

Why my code is returning compile error after submission? Please help.

My code is given below:

Code: Select all

import java.io.IOException;
import java.util.Scanner;
public class Main {
public int lcs(String str1, String str2) {

int l1 = str1.length();

int l2 = str2.length();

int[][] arr = new int[l1 + 1][l2 + 1];
int i, j = 0;
for ( i = l1 - 1; i >= 0; i--) {

for ( j = l2 - 1; j >= 0; j--) {

if (str1.charAt(i) == str2.charAt(j)) {
arr[i][j] = arr[i + 1][j + 1] + 1;
} else {
arr[i][j] = Math.max(arr[i + 1][j], arr[i][j + 1]);
}

}

}
return arr[0][0];
}

public static void main(String[] args) throws IOException {
Scanner sc= new Scanner(System.in);
int Case=0;
while (sc.hasNext())
{
String str1 = sc.nextLine();
if (str1.equals("#"))
{
break;
}
String str2 = sc.nextLine();
Case++;
LongestCommonSubsequence obj = new LongestCommonSubsequence();

int result = obj.lcs(str1, str2);

System.out.println("Case #" +Case+": "+ "you can visit at most "+result+" cities.");
}
}
}

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

### Re: 10192 - Vacation

Check "My Submissions" for the reason for your compile error.
http://uva.onlinejudge.org/index.php?op ... e&Itemid=9

Code: Select all

Main.java:40: error: cannot find symbol
LongestCommonSubsequence obj = new LongestCommonSubsequence();
^
symbol:   class LongestCommonSubsequence
location: class Main
Main.java:40: error: cannot find symbol
LongestCommonSubsequence obj = new LongestCommonSubsequence();
^
symbol:   class LongestCommonSubsequence
location: class Main
2 errors
Check input and AC output for thousands of problems on uDebug!

TryCatchMe
New poster
Posts: 15
Joined: Fri May 30, 2014 12:09 am

### Re: 10192 - Vacation

Ok, this problem was a pain. I got WA 10 times before I got ACC due to I/O mistakes. If you got WA on this problem it is most likely due to I/O and not your LCS algorithm... and yes basic LCS is enough for this problem. Here is some I/O:

Code: Select all

abcd
caabd
a     b
b     a
a   b
a b
aaaaaaaaaaaa
aaaa
bbbbbbb
bbbbbbb

xyzt   23423
2312 2323
#asfdasdas

Remember, the first sequence begins with # ends the input. Note, the input sequences for case 6 are a single blank followed by the newline character. Cities may be represented using spaces as the directions say.
Here is the output:

Code: Select all

Case #1: you can visit at most 3 cities.
Case #2: you can visit at most 5 cities.
Case #3: you can visit at most 3 cities.
Case #4: you can visit at most 4 cities.
Case #5: you can visit at most 7 cities.
Case #6: you can visit at most 1 cities.
Case #7: you can visit at most 5 cities.
Hope this helps!