10252 - Common Permutation

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

Moderator: Board moderators

Post Reply
Amir Aavani
New poster
Posts: 30
Joined: Wed Oct 23, 2002 6:53 am

Post by Amir Aavani » Mon Apr 03, 2006 10:59 am

I think your program get SigSeg somewhere and so, it got TLE. Try to replace memset with a for loop which set all the elements of an array. I am not sure about how memset in C/C++ do.

Fali
New poster
Posts: 8
Joined: Fri Jul 15, 2005 4:00 am

10252 - Common permutations

Post by Fali » Tue Jun 27, 2006 7:22 am

Why WA, so weird, please help me with this problem.

Here is my code:

Code: Select all

/*
  Common Permutation, Uva 10252
  Nephtali Garrido
*/
#include <cstdio>
#include <iostream>
using namespace std;

char v1[1000],v2[1000],x;
int cuan1[29],cuan2[29],c,c2;

int main()
{   while(cin>>v1>>v2)
    { for(c=0;c<29;c++)
       cuan1[c]=cuan2[c]=0;
      for(c=0;v1[c]!='\0';c++)
       cuan1[v1[c]-'a']++;
      for(c=0;v2[c]!='\0';c++)
       cuan2[v2[c]-'a']++;
      for(c=0;c<29;c++)
      { x=c+'a';
        if(cuan1[c]>=cuan2[c])
         for(c2=0;c2<cuan2[c];c2++)
          printf("%c",x);
        else
         for(c2=0;c2<cuan1[c];c2++)
          printf("%c",x);
      }
      printf("\n");
    }
    return 0;
}
If anyone knows why i got WA, please help me

j_hines
New poster
Posts: 5
Joined: Mon May 24, 2004 6:09 pm

Post by j_hines » Thu Jul 13, 2006 3:56 am

not sure if this will help, but i solved this problem a long time ago ... you can look at my source code if you want, it's at http://itnoise.com, you have to register though to see the solution repository. There are quite a few solutions there, and you can upload some of yours too if you like, it's a resource for students who are practising to participate in programming competitions.

cheers

marco_dick
New poster
Posts: 2
Joined: Tue Aug 01, 2006 6:34 am

Post by marco_dick » Tue Aug 01, 2006 7:20 am

I have used "division by zero" method, and I can conclude that the strings a and b contain ONLY LOWERCASE character. Also, there can be blank line as a or b.

However, after making corresponding changes to my program, I am still getting WA. I use the method of counting frequency, stated by IIUC GOLD.

I just wonder is the algorithm wrong, or there is something really tricky.

User avatar
dust_cover
New poster
Posts: 23
Joined: Tue Sep 12, 2006 9:46 pm

getting WA for 10252! PLZZZZZZZZ help

Post by dust_cover » Sun Oct 22, 2006 8:38 pm

I have chked all the test cases from previous discussions
Also add the capital letter case & blank space
but still getting WA. plz HELP!

Code: Select all

removed after AC!
Thnx in Advance!
Last edited by dust_cover on Mon Oct 23, 2006 10:03 pm, edited 1 time in total.
i wanna give it a try....

sakhassan
Experienced poster
Posts: 105
Joined: Sat Mar 11, 2006 9:42 am
Location: cse,DU

Post by sakhassan » Sun Oct 22, 2006 9:09 pm

dust cover


pls chk for this input


pretty woman
walking down
ur output is

*anow (* stands for space)
i think u got ur problem ;)

User avatar
dust_cover
New poster
Posts: 23
Joined: Tue Sep 12, 2006 9:46 pm

Post by dust_cover » Sun Oct 22, 2006 9:21 pm

hi corrected it. But still WA
input--

Code: Select all

pretty woman
walking down
qwe
   
pretty
women
output

Code: Select all

anow

e
can someone ac telle me whether my output is right?
i wanna give it a try....

User avatar
dust_cover
New poster
Posts: 23
Joined: Tue Sep 12, 2006 9:46 pm

Post by dust_cover » Mon Oct 23, 2006 10:10 pm

Hello sorry i had the problem with my Array size
And I checked that no need to consider the Capital letter or blank space
Which is clearly stated in the problemset. i used the ASCII value from 97 to 122 & got AC!
And there is no such data in Judge Input also

--thanx :D
i wanna give it a try....

JoongHo
New poster
Posts: 2
Joined: Wed Jul 19, 2006 9:29 am

10252 (TLE) Help me!!

Post by JoongHo » Mon Jan 01, 2007 10:16 am

Who can give advice to me?

-------------------------------------------------------------------------------------

/*
No. 10252 Common Permutation
*/

#include <iostream>
#include <string>

using namespace std;

void quick_sort (char a[], int n)
{
char v, t;
int i, j;
if (n > 1)
{
v = a[n-1];
i = -1;
j = n-1;
while(1)
{
while(a[++i] < v);
while(a[--j] > v);
if (i >= j) break;
t = a;
a = a[j];
a[j] = t;
}
t = a;
a = a[n-1];
a[n-1] = t;
quick_sort(a, i);
quick_sort(a+i+1, n-i-1);
}
}


int main()
{
char input1[1001], input2[1001], result[1001];
int inputLen1, inputLen2, resultLen, k, L, i, j;

while(!cin.eof())
{
k = 0;
// Array Clear
for (L = 0; L < 1001; L++)
input1[L] = 0;

for (L = 0; L < 1001; L++)
input2[L] = 0;

for (L = 0; L < 1001; L++)
result[L] = 0;

// String Input
cin.getline(input1, 1000);
cin.getline(input2, 1000);

// String Length Check
inputLen1 = strlen(input1);
inputLen2 = strlen(input2);

for (i = 0; i < inputLen1; i++)
{
for(j = 0; j < inputLen2; j++)
{
if (result[k] == 0 && input1 == input2[j])
{
result[k] = input1;
input2[j] = NULL;
j = inputLen2;
}
}
if (result[k] != 0)
k++;
}


quick_sort(result, k);

for(int r = 0; r < k; r++)
{
cout << result[r];
}

cout << endl;
}

return 0;
}

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Thu Jan 04, 2007 5:20 pm

Dont open a new thread if there is one already. Check the following thread...
http://online-judge.uva.es/board/viewto ... ight=10252
Ami ekhono shopno dekhi...
HomePage

mpi
New poster
Posts: 46
Joined: Fri Nov 03, 2006 7:53 pm
Location: Madrid

this problem can't be that difficult

Post by mpi » Wed Mar 21, 2007 7:25 pm

I've tried it hundreds of times but always get WA. I'm getting tired of this silly problem, it's too straightforward to worth doing it. My approach is based on counting the frequencies of characters in the two input strings, handling empty lines too. Here is my short code for this problem:

Code: Select all

#include <stdio.h>
#include <string.h>
#define MAXLEN 1000

char cadena1[MAXLEN+2], cadena2[MAXLEN+2], permutacion[MAXLEN+1];
char letras1[256], letras2[256];
int len1, len2;

int main()
{
    int i, j, k;
    int min;

    while (gets(cadena1) && gets(cadena2)) {
        len1 = strlen(cadena1);
        len2 = strlen(cadena2);
        for (i = 0; i < len1; i++) letras1[cadena1[i]]++;
        for (i = 0; i < len2; i++) letras2[cadena2[i]]++;

        for (i = 'a', k = 0; i <= 'z'; i++) {
            min = (letras1[i] < letras2[i]) ? letras1[i] : letras2[i];
            for (j = 0; j < min; j++) {
                permutacion[k++] = i;
            }
            letras1[i] = letras2[i] = 0;
        }

        permutacion[k] = '\0';
        printf("%s\n", permutacion);
    }

    return 0;
}
Thanks in advance!

mpi
New poster
Posts: 46
Joined: Fri Nov 03, 2006 7:53 pm
Location: Madrid

Oh my gO_od!

Post by mpi » Wed Mar 28, 2007 3:10 pm

OK, i've just found the subtle mistake that was spoiling my code and hence my results, notice the difference:

Before:

Code: Select all

for (j = 0; j < min; j++) 
    permutacion[k++] = i;
After:

Code: Select all

for (j = 0; j < min; j++) 
    permutacion[k++] = (char)i;
Sometimes i feel a bit embarrassed :oops:

User avatar
kana
New poster
Posts: 19
Joined: Mon Mar 13, 2006 6:03 pm
Location: dhaka

Post by kana » Mon Sep 03, 2007 8:11 am

i'm getting PE!!! can anyone help?

Code: Select all


Last edited by kana on Wed Sep 12, 2007 9:31 pm, edited 1 time in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Wed Sep 05, 2007 4:09 am

Read the description again.
Each string is on a separate line and consists of at most 1000 lowercase letters
So, there can be blank strings.

Code: Select all

    if(l1 == 0) 
        continue; 
So, you dont need this line.

Hope it helps.
Ami ekhono shopno dekhi...
HomePage

himanshu
New poster
Posts: 17
Joined: Mon May 15, 2006 12:24 pm
Location: Hyderabad, India
Contact:

Can it have two answers

Post by himanshu » Sat Oct 20, 2007 8:09 pm

If several x satisfy the criteria above, choose the first one in alphabetical order.
Can this problem have two answers or that is just to confuse the extra cautions.

Thank You,
HG

Post Reply

Return to “Volume 102 (10200-10299)”