726 - Decode

[flavio]

Hi people...

I need some help...
I have been trying this question about a week...

I really don't know what is the problem!
Could anybody help me!?

Here is my C code:

Code: Select all

#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdio.h>

#define MAX_CHAR 256
#define MAX_LINHA 800

void zeraArrayInt(int array[], int size) {
   int i;
   for (i = 0; i < size; i++) {
      array[i] = 0;
   }
}

void zeraArrayChar(char array[], int size) {
   int i;
   for (i = 0; i < size; i++) {
      array[i] = 0;
   }
}

void ordenaArray(char array[], int freq[], int size) {
   int i, j;
   for (i = 1; i < size; i++) {
      for (j = size -1; j >= i; j--) {

         if (freq[array[j]] - freq[array[j - 1]] > 0) {
            char aux = array[j];
            array[j] = array[j - 1];
            array[j - 1] = aux;
         }

      }
   }
}

int main() {

   int i, cont;

   char conversor[MAX_CHAR];

   int knownFreq[MAX_CHAR];
   int encodedFreq[MAX_CHAR];

   char knownOrdem[MAX_CHAR];
   char encodedOrdem[MAX_CHAR];

   char linha[MAX_LINHA];

   char *texto[400000];
   int nLinhas;

   zeraArrayChar(conversor,MAX_CHAR);

   zeraArrayInt(knownFreq, MAX_CHAR);
   zeraArrayInt(encodedFreq, MAX_CHAR);

   zeraArrayChar(knownOrdem, MAX_CHAR);
   zeraArrayChar(encodedOrdem, MAX_CHAR);

   /* calcula as frequencias do texto conhecido */
   cont = 0;
   while (strlen(gets(linha))) {
      for (i = 0; i < strlen(linha); i++) {
         char ch = linha[i];
         if (ch < 'a') ch = ch + 32;
         if (ch >= 'a' && ch <= 'z') {
            if (knownFreq[ch] == 0) {
               knownOrdem[cont++] = ch;
            }
            knownFreq[ch]++;
         }
      }

   }

   /* calcula as frequencias do texto codificado */
   cont = 0;
   nLinhas = 0;
   while (gets(linha) != NULL) {
      texto[nLinhas] = (char *) malloc(MAX_LINHA);
      strcpy(texto[nLinhas++], linha);

      for (i = 0; i < strlen(linha); i++) {
         char ch = linha[i];
         if (ch < 'a') ch = ch + 32;
         if (ch >= 'a' && ch <= 'z') {
            if (encodedFreq[ch] == 0) {
               encodedOrdem[cont++] = ch;
            }
            encodedFreq[ch]++;
         }
      }

   }

   /* ordena arrays */
   ordenaArray(knownOrdem, knownFreq, cont);
   ordenaArray(encodedOrdem, encodedFreq, cont);

   /* faz mapeamento */
   for (i = 0; i < cont; i++) {
      conversor[(char)encodedOrdem[i]] = knownOrdem[i];
   }

   /* processa texto */
   for (i = 0; i < nLinhas; i++) {
      char *aux = texto[i];
      int j;
      for (j = 0; j < strlen(aux); j++) {
         if (aux[j] >= 'a' && aux[j] <= 'z') {
            aux[j] = conversor[aux[j]];
         } else if (aux[j] >= 'A' && aux[j] <= 'Z') {
            aux[j] = conversor[aux[j] + 32] - 32;
         }
      }

      printf("%s\n", aux);
   }

}


Input and output are welcome...

Thanks in advance...
Hugs

[Raiyan Kamal]

I tried to compile and run your code on my computer using VC++, but it crashed. Something wrong with your code or is it my computer ? Anyways, here are some test cases

case1:

Code: Select all

the quick brown fox jumped over the lazy dog.

thE quicK browN foX jumpeD oveR thE lazY doG.

Code: Select all

thE quicK browN foX jumpeD oveR thE lazY doG.

case2:

Code: Select all

the quick brown fox jumped over the lazy dog.
the lazy brown dog jumped over the quick fox. ;)

thE quicK browN foX jumpeD oveR thE lazY doG.
the quick brown of R jumped ovex THE lazy do G :(

Code: Select all

thE quicK browN foX jumpeD oveR thE lazY doG.
the quick brown of R jumped ovex THE lazy do G :(

case3:

Code: Select all

the quick brown fox jumped over the lazy dog.

abc ??? any idea ???

Code: Select all

eod ??? eua thre ???

case4:

Code: Select all

123abbccc654987the remaining letters are gone :O

the quick brown fox jumped over the lazy dog

Code: Select all

tne qbmod iravk haw sbjpec auer tne fgyx cal

case5:

Code: Select all

[O ] <- this is our national flag. I love BANGLADESH
bangladesh is our motherland. we love her. this is our flag -> [O ]

[O ]**[O ] xyz (1+2)^3=9 xyz xyz xyz xxx yyy zzz ppp ppp qqq

Code: Select all

[S ]**[S ] aol (1+2)^3=9 aol aol aol aaa ooo lll eee eee iii

[flavio]

Well... my program ran only the first and second cases correctly... The case 3 is a little confusing...
The letter 'Y' maps to 'A' and I don't know why. Look at my table for case 3:

Frequencies in KNOWN text:
a = 1
b = 1
c = 1
d = 2
e = 4
f = 1
g = 1
h = 2
i = 1
j = 1
k = 1
l = 1
m = 1
n = 1
o = 4
p = 1
q = 1
r = 2
t = 2
u = 2
v = 1
w = 1
x = 1
y = 1
z = 1

Frequencies in ENCODED text:
a = 3
b = 1
c = 1
d = 1
e = 1
i = 1
n = 1
y = 1

(ordering them... I've got:)

KNOWN sorted:
4 = e
4 = o
2 = t
2 = h
2 = u
2 = r
2 = d
1 = q
1 = i
1 = c
1 = k
1 = b
1 = w
1 = n
1 = f
1 = x
1 = j
1 = m
1 = p
1 = v
1 = l
1 = a
1 = z
1 = y
1 = g

ENCODED sorted:
3 = a
1 = b
1 = c
1 = n
1 = y
1 = i
1 = d
1 = e

Making the mapping:
e <=> a
o <=> b
t <=> c
h <=> n
u <=> y
r <=> i
d <=> d
q <=> e

A mapped the most frequently letters each other as the problem said.
But I think that the problem is my ordering algorithm.
What is this algorithm idea? I really don't know

I thought that only character in ENCODED text could map to character in KNOWN text.. but it doesn't happen in case 4.

The leter 'K' in "quick" maps to 'D' in which doesn't exist in KNOWN text:
"123abbccc654987the remaining letters are gone :O"


Could you help me? I'm getting crazy...
Thanks in advance!

[Raiyan Kamal]

my ordering is like this :

Code: Select all

If two chars have different frequency
   then they are ordered accordig to the frequencly.
else ( they have same frequency )
   they are ordered lexicographically

To arrange according to frequency, the char with higher frequency comes before the char with lower frequency. For example, if 'x' appears 3 times and 'k' appears 2 times, then 'x' comes before 'k'.

I used the ASCII values of the chars to do the lexicographic ordering. For example, if 'a' and 'b' has same frequency, then 'a' comes before 'b'. i.e. the char with smaller ASCII value comes first.

[flavio]

Thanks Raiyan!!

I did this and got ACCEPT!!
I've got confused because your case 4 was wrong:

Input:

Code: Select all

123abbccc654987the remaining letters are gone :O

the quick brown fox jumped over the lazy dog


Output:

Code: Select all

tne qbmod iravk haw sbjpec auer tne fgyx cal


I've ignored it. All the other cases were correct after the lexicographic ordering!
Thanks!!

Hugs

[Raiyan Kamal]

Congratulations !

You are welcome.

Are you sure this case is wrong ? This output is generated by my accepted code. I assumed that if a char does not appear then its frequency is zero. So i order and then map the chars with zero frequency too, did not ignore them. But i think, the judge input has all the chars of English alphabet at least once in the first part. So it does not make any difference if you assume this or not.

[flavio]

I think that the judge just input values following this rule:

"The mapping that defines the encoding is one-to-one."

So, both the answers are correct! \o/

Best regards!!
Flavio

[yiuyuho]

how do you know that the KNOWN text has no blank lines?

If KNOWN has blank line, how do you know where to break KNOWN and ENCODE?

Thx.

[flavio]

Because the blank line is used only to separate the encoded and decoded texts.

The decoded text has to be readen until find a blank line...
Imediately after the blank line, the encoded text has to be readen....

That is it!
Thanks

[yiuyuho]

So the KNOWN text contain no blank lines? The FIRST blank line separate the KNOWN and ENCODE text? In the spec. it only said they are separated by a blank line, but does not speciaify which blank line.

[flavio]

Exactly... the unique blank line is used to separate the KNOWN and the ENCODED texts. For example:

Code: Select all

your known text here
another line from known text
and other...

(encoded texto here)


See ya!

[mohsincsedu]

Hi all....................

I faced a problem again!!!!!!


Why i got WA?????


May be my code is ok!!!!!!!!

But what is the problem???


here is my code:

Code: Select all

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

#define M 40000
#define MAX 100

int table[2][30],index[2][30];

void make_table(char s[],int n)
{
   int i = 0;
   while(s[i])
   {
      if(isalpha(s[i]))
      {
         table[n][tolower(s[i])-'a']++;
      }
      i++;
   }

}

void sort_table(int t[],int n)
{
   int i,j,temp;
   for(i = 0;i<26;i++)
      index[n][i] = i;
   for(i = 0;i<25;i++)
   {
      for(j = 25;j>=i+1;j--)
      {
         if(t[j]>t[j-1])
         {
            temp = index[n][j];
            index[n][j] = index[n][j-1];
            index[n][j-1] = temp;

            temp = t[j];
            t[j] = t[j-1];
            t[j-1] = temp;
         }
      }
   }

}

int search_pos(int n)
{

   int i = 0;
   while(1)
   {
      if(n==index[1][i])
         break;
      i++;


   }
   return index[0][i];
}

void main()
{
   char input1[MAX],input2[M][MAX];
   long i,j,num,temp,len;
   memset(table[0],0,sizeof(table[0]));
   while(1)
   {
      gets(input1);
      if(input1[0]=='\0')
         break;
      make_table(input1,0);
   }
   i = 0;
   memset(table[1],0,sizeof(table[1]));
   while(gets(input2[i])!=NULL)
   {

      if(input2[i][0]=='\0')
         break;
      make_table(input2[i],1);
      i++;
   }

   len = i;
   sort_table(table[0],0);


   sort_table(table[1],1);
   for(j = 0;j<=len;j++)
   {
      for(i = 0;input2[j][i];i++)
      {
         if(isalpha(input2[j][i]))
         {
            num = tolower(input2[j][i])-'a';
            temp = search_pos(num);
            if(islower(input2[j][i]))
               printf("%c",temp+'a');
            else
               printf("%c",temp+'A');
         }
         else
            printf("%c",input2[j][i]);
      }
      printf("\n");
   }
}

Why way i get input?? plz tell me!!!

Thanks in advanced!!!!

[mohsincsedu]

Hi all....................

I faced a problem again!!!!!!


Why i got WA?????


May be my code is ok!!!!!!!!

But what is the problem???


here is my code:

Code: Select all

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

#define M 40000
#define MAX 100

int table[2][30],index[2][30];

void make_table(char s[],int n)
{
   int i = 0;
   while(s[i])
   {
      if(isalpha(s[i]))
      {
         table[n][tolower(s[i])-'a']++;
      }
      i++;
   }

}

void sort_table(int t[],int n)
{
   int i,j,temp;
   for(i = 0;i<26;i++)
      index[n][i] = i;
   for(i = 0;i<25;i++)
   {
      for(j = 25;j>=i+1;j--)
      {
         if(t[j]>t[j-1])
         {
            temp = index[n][j];
            index[n][j] = index[n][j-1];
            index[n][j-1] = temp;

            temp = t[j];
            t[j] = t[j-1];
            t[j-1] = temp;
         }
      }
   }

}

int search_pos(int n)
{

   int i = 0;
   while(1)
   {
      if(n==index[1][i])
         break;
      i++;


   }
   return index[0][i];
}

void main()
{
   char input1[MAX],input2[M][MAX];
   long i,j,num,temp,len;
   memset(table[0],0,sizeof(table[0]));
   while(1)
   {
      gets(input1);
      if(input1[0]=='\0')
         break;
      make_table(input1,0);
   }
   i = 0;
   memset(table[1],0,sizeof(table[1]));
   while(gets(input2[i])!=NULL)
   {

      if(input2[i][0]=='\0')
         break;
      make_table(input2[i],1);
      i++;
   }

   len = i;
   sort_table(table[0],0);


   sort_table(table[1],1);
   for(j = 0;j<=len;j++)
   {
      for(i = 0;input2[j][i];i++)
      {
         if(isalpha(input2[j][i]))
         {
            num = tolower(input2[j][i])-'a';
            temp = search_pos(num);
            if(islower(input2[j][i]))
               printf("%c",temp+'a');
            else
               printf("%c",temp+'A');
         }
         else
            printf("%c",input2[j][i]);
      }
      printf("\n");
   }
}

Why way i get input?? plz tell me!!!

Thanks in advanced!!!!

[jjtse]

I know this thread has been closed for a while. I tried solving this problem, and it seems ridiculously easy. I tried all the sample input provided, and they all worked. When I submit, I get TLE. I don't know why it should do that though. I sort an array of size 26 using bubble sort. That shouldn't cause it to TLE. And I have no other big time loops anywhere else. Does anyone see why I get TLE?

Code: Select all


code cut after accepted.  Main speedup: 

change sytem.out.print to system.out.write
change Character.tolower/toupper to  c +- 32
use arrays instead of vectors.
bubble sort ok for this problem

thanks Darko!





[Darko]

I am not sure what Character.toLower() does, but I think (char)(c+32) would be faster.

Oh, and going the other way - Character.toUpper() is (char)(c-32).

And you want to use System.out.write() instead of print().

And Vector is slow, too.

When you fix those, and if it's still TLE I'll take another look.

[EDIT] I don't think any of the above is the reason - I just tried it and it keeps looping for the second string for some reason (like it never reads null). Now I'm puzzled, too