10887 - Concatenation of Languages

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

Moderator: Board moderators

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

Re: 10887 - Concatenation of Languages WA

Post by brianfry713 » Sat Sep 14, 2013 10:02 pm

hpjhc, try reading line by line so your code can handle empty strings.
Check input and AC output for thousands of problems on uDebug!

sampad74
New poster
Posts: 29
Joined: Wed Jun 18, 2014 3:57 pm
Location: Bangladesh

Re: 10887 - Concatenation of Languages

Post by sampad74 » Tue Jul 22, 2014 1:35 pm

I got TLE.Here is my code,please help me to make my program fast.Thanks in advance.

Code: Select all

#include<stdio.h>
#include<string.h>
int main(void)
{
    int t,i;
    scanf("%d",&t);
    for(i=1;i<=t;i++)
    {
        int m,n;
        scanf("%d %d",&m,&n);
        char a[m][20],b[n][20],c[m*n][40];
        char e[1];
        int j,k,l=0;
        gets(e);
        //for(j=0;j<m;j++) scanf("%s",a[j]);
        for(j=0;j<m;j++) gets(a[j]);
        //for(j=0;j<n;j++) scanf("%s",b[j]);
        for(j=0;j<n;j++) gets(b[j]);
        for(j=0;j<m;j++)
        {
            for(k=0;k<n;k++)
            {
                strcpy(c[l],a[j]);
                l++;
            }
        }
        //printf("\n%s %s %s\n",c[0],c[1],c[2]);
        l=0;
        for(j=0;j<m;j++)
        {
            for(k=0;k<n;k++)
            {
                strcat(c[l],b[k]);
                l++;
            }
        }
        //printf("\n%s %s %s %s %s %s\n",c[0],c[1],c[2],c[3],c[4],c[5]);
        int count=0;
        for(j=0;j<(m*n);j++)
        {
            for(k=(j+1);k<(m*n);k++)
            {
                if(!strcmp(c[j],c[k])) count++;
            }
        }
        //printf("\n%d\n",(m*n)-count);
        printf("Case %d: %d\n",i,(m*n)-count);
        //printf("\n%s %s %s\n",c[0],c[1],c[2]);
    }
    return 0;
}


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

Re: 10887 - Concatenation of Languages

Post by brianfry713 » Tue Jul 22, 2014 7:31 pm

Read this thread for ideas. What is the complexity of your code, is it O(M * M * N * N)?
Check input and AC output for thousands of problems on uDebug!

Zyaad Jaunnoo
Experienced poster
Posts: 122
Joined: Tue Apr 16, 2002 10:07 am

Re: 10887 - Concatenation of Languages WA

Post by Zyaad Jaunnoo » Sun Sep 07, 2014 1:10 am

brianfry713 wrote:hpjhc, try reading line by line so your code can handle empty strings.
Do we really have empty strings in the input set?

The problem statement says that the strings are formed by lower case letters only (a to z).
You can assume that the strings are formed by lower case letters (‘a’ to ‘z’) only, that they are less than 10 characters long and that each string is presented in one line without any leading or trailing spaces.
Confused about this one. :-?

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

Re: 10887 - Concatenation of Languages WA

Post by brianfry713 » Mon Sep 08, 2014 8:58 pm

Zyaad Jaunnoo wrote: Do we really have empty strings in the input set?
Yes
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 108 (10800-10899)”