854 - Worse Code

All about problems in Volume 8. 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
..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

854 - Worse Code

Post by .. »

To the problem data setter(I guess littlejoey will answer me :))

1. A setence is terminated with a blank line or EOF.
"blank line" means a line with no char, right?

2. Any char except letters and space are IGNORED. What does this mean?
For example,

Code: Select all

 ! .
How should I handle this setence?
1. it has 2 non-consecutive space
2. After ignoring the '!' and '.', the sentence is just 2 space chars only, and all the space are ignored.(as they are at the end of setence)
3. After ignoring the '!' and '.', the sentence is just 2 space chars only, the 2 spaces are converted to a single char.

3. For this example,

Code: Select all

AAAaaaAAA
Is the answer 0 or 9?

4. What is the max. length of a line in input?
Last edited by .. on Tue Oct 18, 2005 4:59 pm, edited 1 time in total.
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

1. right; this means the input should be a blank line, not the result of ignoring characters, spaces and newlines.

2. The '!' and '.' are ignored, resulting in a sequence of spaces that are replaced by one space. If it's at the end of a sentence, that space would be ignored. But be careful with the distinction between sentence and line:

Code: Select all

 ! .
some       text
 ! .
more letters
 ! .

 some text more letters
contains two sentences, one with 5 lines and one with 1 line. The first occurrence of " ! ." will be concatenated with the succeeding newline to form one space at the start of the sentence. The second occurrence will be concatenated with the preceeding and the succeeding newline to form one space. The third occurrence will be ignored (together with two newlines) because it's at the end of the sentence. So both sentences will be interpreted the same.

3. 9, obviously.

4. Indetermined (but 256 should be more than enough for a line; a sentence can be (much) longer).

I might have made an error in the input file. The last sentence in the input is followed by a blank line and an end of file ("....bla bla bla<NEWLINE><NEWLINE><EOF>"), which might lead some programs to print "0" as the last answer. There shouldn't be one though, so I'll ask the judges to change it to "...bla bla bla<EOF>".

Since the testset is new, and Ruben an I are the only ones accepted, it can't be ruled out that there is a mistake. If you want you can PM me your code and I can verify it with the judge's input.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. »

Thanks for the reply, I get AC by specially handle the last case as you say. :)
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

Great, I changed the input file and sent it to the judges.
BTW, can you edit the line in your first posting that mentions the name of the algorithm? It is somewhat of a spoiler.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. »

OK~~ :wink:
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Post by minskcity »

I think that the answer for

Code: Select all

aaaaaaaaaa
should not be 10.
As long as we only have 1 type of character, we are only interested in the total count. Set

Code: Select all

xx = 0
xy = 1
yx = 2
yy = terminator
x, y - two types of signals we can send
then the total number of characters can be send as a nubmer in base 3 with a terminator at the end...The AC rate for the problem would be even lower if that was the case :lol:

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

A sequence of dots and dashes forms a symbol.
Since we want to transmit 10 symbols, we need at least 10 atomic symbols (dots or dashes).
In your encoding the transmission of a single character would take 4 atomic symbols, which is clearly not optimal.

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Post by minskcity »

You took a quote from the description of the Morse code, while we are working with the Worse code... :-? I realize that the problem askes to encode each symbol individually, but there are can be many interpretations of how
optimal Worse code, tailored for the input sentence
is allowed to be formed.

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

Post by Jan »

I cant understand what the problem really wants.

Should we assign a code for space?
a) After formatting, the first sample becomes...
THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG
b) If we find the frequencies..

Code: Select all

A 1
B 1
C 1
D 1
E 3
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
S 1
T 2
U 2
V 1
W 1
X 1
Y 1
Z 1
space 8
c) after sorting the frequencies we get..

Code: Select all

8
4
3
2
2
2
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
d) after assigning we get

Code: Select all

8 1 <- dot
4 1 <- dash
3 2 <- dot dot
2 2 <- dot dash
2 2 <- dash dot
2 2 <- dash dash
2 3 ...
1 3
1 3
1 3
1 3
1 3
1 3
1 3
1 4
1 4
1 4
1 4
1 4
1 4
1 4
1 4
1 4
1 4
1 4
1 4
1 4
So, the result becomes 109?

I read the problem many times, but didnt understand it fully. Can anyone help? Thanks in advance.

ovidiu
New poster
Posts: 10
Joined: Fri Dec 07, 2007 10:42 am

Re: 854 - Worse Code

Post by ovidiu »

Hello,

I got WA.
Please provide me a test file for which my code output is wrong.
I used a well known algorithm for finding the number of atomic symbols.
[I will not name it because I suppose this is a spoiler.]
I think my bug is in reading the input and preparing the string which will be coded.

Here is my code:

Code: Select all

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

#ifndef ONLINE_JUDGE
#include <fstream>
#define cin fi
#define cout fo
fstream fi("854_Worse_Code.in", ios::in);
fstream fo("854_Worse_Code.out", ios::out);
#endif

string s;
int f[100]; // frecventele literelor

void frecvente () {
  int i, ls;

  ls = s.size();
  memset (f, 0, sizeof(f));
  for (i = 0; i < ls; i++)
    f[s[i]]++;
//  for (char l = 'A'; l <= 'Z'; l++)
//    if (f[l])
//      fo << l << " - " << f[l] << '\n';
}

void h () {
  priority_queue<int> q;
  char l;
  int suma, t = 0;

  for (l = 'A'; l <= 'Z'; l++)
    if (f[l])
      q.push(-f[l]); // Ca sa asiguram prioritate pentru cel mai mic element.
  q.push(-f[' ']); // Daca avem o singura litera, frecventa ei impreuna cu frecventa spatiului vor produce doua elemente in coada.
  while (q.size() >= 2) {
    suma = -q.top();
    q.pop();
    suma += -q.top();
    q.pop();
    q.push(-suma);
    t += suma; // Actualizam lungimea textului.
  }
  cout << t << '\n';
}

int main () {
  char c, cp = '-';
  bool gata, litera, dnl; // double newline
  string aux;

  while (cin.peek() != EOF) {
    s = "";
    gata = false;
    while (not gata and cin.peek() != EOF) {
      cin.get(c);
      if ('a' <= c and c <= 'z')
        c -= 32; // litera mare corespunzatoare
      if ('A' <= c and c <= 'Z')
        s += c;
      else { // c este diferit de litera
        aux = "";
        do {
          if (c == '\n' or c == ' ') // Altfel ignoram caracterul.
            aux += c;
          cp = c;
          cin.get(c);
          litera = (('a' <= c and c <= 'z') or ('A' <= c and c <= 'Z'));
          dnl = (c == '\n' and cp == '\n');
        } while (not litera and not dnl and cin.peek() != EOF);
        if (dnl) // In aux pot fi spatii finale, care sunt ignorate.
          gata = true;
        else
          if (litera) { // S-a citit o litera.
            if ('a' <= c and c <= 'z')
              c -= 32; // litera mare corespunzatoare
            if (not aux.empty())
              s = s + " ";
            s += c;
          }
          else // S-a terminat fisierul.
            gata = true;  // Se neglijeaza spatiile finale din aux.
      }
    }
    //cout << s << '|';
    frecvente ();
    h ();
  }
  return 0;
}
Here are my input and output files:

Code: Select all

AAAaaaAAA

Don't make codes for letters not appearing
in the text!

Don  '  t make codes for letters not appearing
in the text!

! .
some       text
! .
more letters
! .

some text more letters




test simplu

THE QUICK BROWN FOX JUMPS
OVER THE LAZY DOG.  !

some text more letters

Code: Select all

9
204
206
70
67
0
38
192
67

Post Reply

Return to “Volume 8 (800-899)”