10192 - Vacation

[ability]

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]

same problem here

after changing scanf by gets i got ac

[Sultan_Dhaka]

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]

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]

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

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

[sun_kuet]

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]

Try a different problem.

[mrxy56]

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]

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

[dibery]

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.

[emrankdr]

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]

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

[TryCatchMe]

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
sadas

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!