10252 - Common Permutation

[midra]

thank you so much!!
I finally understand!

Byee!

[sumankar]

Midra,

Good, now can you remove the code

[mooseelkdog]

Can't seem to figure out why I get a wrong answer to this problem, I find the common letters to the words, and output the multiples of each letter occuring in both words, I output blank lines for neither word having common letters and for a blank input of the second word, IS IT POSSIBLE TO HAVE AN INITIAL BLANK LINE INPUT?

Thank you

[mooseelkdog]

for clarity I am posting my sample input:

<blank line>
icky
pretty
women
walking
down
the
street
meningitis
frontal
yelp
<blank line>
verbatim
greater
prettywoman
walkingdown
inging
singing
ab
ba
ab
cd
cat
bat

and my output generated:

<blank line>
e
nw
et
nt
<blank line>
aert
anow
ggiinn
ab
<blank line>
at

for extra clarity, <blank line> signifies carriage return

thanks again

[tetuya]

Hi mooseelkdog.
Your output is same with mine.
you may have other wrong code.

[noren]

I'd say that case matters. After I added tolower() I got accepted. There must be something wrong either in the spec, or in the testdata. However you can print the letters in lowercase. Just convert the indata to lowercase.
/johan

[Arm.Turbo]

My outputs for all tests from this board the same with AC solutions. I try to use tolower() but it's WA anyway. What's the problem?

Code: Select all

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>

int main ()
{
   char tmp1[1024];
   char tmp2[1024];
   char ttmp1['z'-'a'+1];
   char ttmp2['z'-'a'+1];
   int j, sl1, sl2, k;

   #ifndef ONLINE_JUDGE
   freopen("Debug/input.txt", "r", stdin);
   //freopen("Debug/output.txt", "w", stdout);
   #endif

   while(1)
   {
      if (gets(tmp1) == NULL)
         break;
      if (gets(tmp2) == NULL)
         break;
      sl1 = strlen(tmp1);
      sl2 = strlen(tmp2);
      for (j = 0; j < 'z'-'a'+1; j++)
      {
         ttmp1[j] = 0;
         ttmp2[j] = 0;
      }
      for (j = 0; j <sl1; j++)
      {
         ttmp1[tolower(tmp1[j])-'a']++;
      }
      for (j = 0; j <sl2; j++)
      {
         ttmp2[tolower(tmp2[j])-'a']++;
      }
      for (j = 0; j < 'z'-'a'+1; j++)
      {
         if (ttmp2[j] < ttmp1[j])
            ttmp1[j] = ttmp2[j];
      }
      for (j = 0; j < 'z'-'a'+1; j++)
      {
         for (k =0; k < ttmp1[j]; k++)
         {
            printf("%c", j+'a');
         }
      }

      printf("\n");
   }
   return 0;
}


[burgerman]

I try to use tolower() but it's WA anyway.

Your problem is not upper-case input. The following code should cause a floating point exception should any uppercase letters occur:

[cpp]char c
if (c >= 'A' || c <= 'Z'){
int x = 6 / 0; //will cause fpe should a character from A to Z be encountered
}[/cpp]
and none occurred when I tried it.

Your problem would probably be found in the statement,

The input file contains several cases, each case consisting of two consecutive lines.

(tolower may even cause further problems, depending on the judge's implementation)

[midra]

Why this qsort function doesn't work

[mohiul alam prince]

hi
i have changed ur code and got AC
but u have to understand what were the problems in your code

MAP

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int funcion(const void *a,const void *b){
return *(char*)a-*(char*)b;
}

int main()
{
  char a[1002],b[1002],x[1002];
  int i,j,len1,len2,ind;
  while(gets(a)){
     gets(b);
     if ( strlen(a) == 0 || strlen(b) == 0 ){printf("\n");continue;}
      for (i=0;i<=ind;i++)  x[i]=0;
      len1=strlen(a);len2=strlen(b);
      ind=0;
      for(i=0;i<len1;i++)
          for(j=0;j<len2;j++){
              if(a[i]==b[j]){
                  x[ind]=b[j];             
                  b[j]=0;
                  ind++;
                  break;
              }
          }
        x[ind] = NULL;
        qsort(x,ind,sizeof(x[0]),funcion);
        printf("%s\n",x);
  }   
  return 0;
}


[Kentaro]

Important Edit: A straight LCS-based solution worked like a charm and I've finally gotten AC for this problem. But I wonder what was wrong with this program?

The Programming Challenges judge accepts my program just fine, which seems to work exactly according to the problem specification (it assumes it is working with 0-1000 lowercase letters in each string and is correct for every single test case I could throw at it) but the UVa judge won't accept it.

I think the UVa judge is playing a terrible trick on all of us and I'm trying to get to the bottom of it...

Code: Select all

#include <iostream>
#include <string>
#include <algorithm>
#include <cctype>
using namespace std;

const bool DEBUG = false;

int main() {
   string word1, word2;
   while (getline(cin, word1) && getline(cin, word2)) {
      
      if (DEBUG) {
         cout << "First line is: " << word1 << endl;
         cout << "Second line is: " << word2 << endl;
      }
      
      // Sort the letters in each word
      sort(word1.begin(), word1.end());
      sort(word2.begin(), word2.end());
      
      // Make sure that the shortest word is word1
      if (word1.size() > word2.size()) {
         string temp = word1;
         word1 = word2;
         word2 = temp;
      }
      
      if (DEBUG) {
         cout << word1 << endl;
         cout << word2 << endl;
      }
      
      int w1_place = 0;
      int w2_place = 0;
      int w2_last = 0;
      while (w1_place < word1.size() && w2_last < word2.size()) {
         if (word1[w1_place] == word2[w2_place]) {
            cout << word1[w1_place];
            w1_place++;
            w2_place++;
            w2_last = w2_place;
         }
         else {
            if (w2_place < word2.size()) w2_place++;
            else {
               w1_place++;
               w2_place = w2_last;
            }
         }
      }
      cout << endl;
   }
}


Edited to remove some extra emoticons that appeared in the post.
Another fixes a minor issue in the code. I didn't submit the code with any syntax errors, but I have been changing it a lot trying to get AC, so in revising the code and reverting it back again I've made some small mistakes.

[AhlyM]

hi programmers.
This code take compiler error i need someone to tell me where is the error?

Code: Select all

program str (input,output);
uses strings;
type
   arr=array of char;
var
   x,y,r,z:arr;
   s1,s2:string;
   i,l1,l2,b,g,c,v,s:integer;
function bubble (r:arr;s:integer):arr;
var
   i,j:integer;
   t:char;
begin
     for i:= 1 to length(r) do
     begin
          for j:= 1 to length(r)-1 do
          begin
               if r[j] > r[j+1] then
               begin
               t:=r[j];
               r[j]:=r[j+1];
               r[j+1]:=t;
               end;
          end;
     end;
     bubble:=r;
end;
begin
     while not eof(input) do
     begin
     c:=1;
     s:=1;
     readln(s1);
     readln(s2);
     l1:=length(s1);
     l2:=length(s2);
     setlength(x, l1);
     setlength(y, l2);
     setlength(r, 0);
     setlength(z, 100);
     for i:=1 to l1 do
     begin
          x[i]:=s1[i];
     end;
     for i:=1 to l2 do
     begin
          y[i]:=s2[i];
     end;

     if l1>l2 then
     begin
          for g:=1 to l1 do
          begin
               for v:=1 to l1 do
               begin
                    if y[c]=x[v] then
                    begin
                         z[s]:=x[v];
                         s:=s+1;
                         break;
                    end;
               end;
               c:=c+1
          end;
     end
     else
     begin
     for g:=1 to l2 do
          begin
               for v:=1 to l2 do
               begin
                    if x[c]=y[v] then
                    begin
                         z[s]:=y[v];
                         s:=s+1;
                         break;
                    end;
               end;
               c:=c+1
          end;
     end;
     setlength(r, s);
     for b:=1 to s do
     begin
         r[b]:=z[b];
     end;
     r:=bubble(r,s);
     for b:=2 to s do
     begin
          write(r[b]);
     end;
     setlength(z, 0);
     setlength(r, 0);
     setlength(x, 0);
     setlength(y, 0);
     writeln;
     writeln;
     end;
end.


[mosaick2]

Actually, I can't understand what's wrong in my method.
Who can give advice to me?

Code: Select all

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int CHARSIZE = 26;

void checkMap(char *lCase, int *map);

int main()
{
   char lCase1[1000] = {0,};
   char lCase2[1000] = {0,};
   int map1[CHARSIZE] = {0,};      // for masking flags.
   int map2[CHARSIZE] = {0,};      // for masking flags.

   do {
      /* Clear */
      memset(map1, 0x00, CHARSIZE*4);
      memset(map2, 0x00, CHARSIZE*4);
      memset(lCase1, 0x00, 1000);
      memset(lCase2, 0x00, 1000);

      /* Input */
      cin.getline(lCase1, 1000);
      cin.getline(lCase2, 1000);

      /* Processing */
      checkMap(lCase1, map1);
      checkMap(lCase2, map2);

      /* Output */
      for(int i=0; i < CHARSIZE; i++)
      {
         if((map1[i] >= 1) && (map2[i] >= 1)) {
            int small = (map1[i] > map2[i]) ? map2[i] : map1[i];
            for(int j=0; j < small; j++)
               printf("%c", i+97);
         }
      }
      cout << endl;

   } while(!cin.eof());

   return 0;
}

void checkMap(char *lCase, int *map)
{
   int ix=0;
   while(lCase[ix] != 0)
   {
      switch (lCase[ix])
      {
         case 'a': map[0] += 1; break; case 'b': map[1] += 1; break;
         case 'c': map[2] += 1; break; case 'd': map[3] += 1; break;
         case 'e': map[4] += 1; break; case 'f': map[5] += 1; break;
         case 'g': map[6] += 1; break; case 'h': map[7] += 1; break;
         case 'i': map[8] += 1; break; case 'j': map[9] += 1; break;
         case 'k': map[10] += 1; break;case 'l': map[11] += 1; break;
         case 'm': map[12] += 1; break;case 'n': map[13] += 1; break;
         case 'o': map[14] += 1; break;case 'p': map[15] += 1; break;
         case 'q': map[16] += 1; break;case 'r': map[17] += 1; break;
         case 's': map[18] += 1; break;case 't': map[19] += 1; break;
         case 'u': map[20] += 1; break;case 'v': map[21] += 1; break;
         case 'w': map[22] += 1; break;case 'x': map[23] += 1; break;
         case 'y': map[24] += 1; break;case 'z': map[25] += 1; break;
      }
      ix++;
   }
}


[Amir Aavani]

try to change
char lCase1[1001] = {0,};
char lCase2[1001] = {0,};
In checkMap, you go till a 0 is meeted, what if the inputs string's length are exactly 1000. you missed the trailing 0.

[mosaick2]

try to change
char lCase1[1001] = {0,};
char lCase2[1001] = {0,};
In checkMap, you go till a 0 is meeted, what if the inputs string's length are exactly 1000. you missed the trailing 0.

I've got your advice.
I think It's also my mistake.
But, I got TLE until now.
I think I have the other problem in my code.