200 - Rare Order

[cyph1e]

Hi, I'm don't know the reason why I get WA for this one. Every input I try seems to yield the correct output.

Code: Select all

#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>

using namespace std;

int main()
{
   
   #ifndef ONLINE_JUDGE
   freopen("in.txt", "r", stdin);
   freopen("out.txt", "w", stdout);
   #endif
   
   string str;  
   vector<string> vec;
   bool table[26][26] = {0};
   int len;
     
   while(getline(cin, str)) {
      if(str == "#") {    
         if (vec.size()==1) {
            cout << vec[0][0] << endl;
            vec.clear();
            for(int i=0; i<26; i++)
               for(int j=0; j<26; j++)
                  table[i][j] = 0;
            continue;
         }  
         for(int i=0; i<vec.size()-1; i++) {
            len = min( vec[i].length(), vec[i+1].length() );
            for(int j=0; j<len; j++) {
               if(vec[i][j] != vec[i+1][j]) {
                  table[ vec[i][j] - 'A' ][ vec[i+1][j] - 'A' ] = true;
                  break;
               }  
            }
         }
         
         int starting=(vec[0][0]-65);
         int k=starting;
                  
         string res="";
         res+=(char)(starting+65);
         char candidate;
         
         // right part
         while (true) {
               candidate=-1;
               for (int j=0; j<26; j++) {
                   if (table[k][j]) {
                      if (candidate==-1) {
                         candidate=j;                  
                      } else {
                        if (table[j][candidate]) {
                           candidate=j;
                        }      
                      }                 
                   }    
               }
               if (candidate!=-1) {
                  res+=(char)(candidate+65);
                  k=candidate;                  
               } else {
                 break;       
               }      
         }
         
         
         // left part
         k=starting;
         
         while (true) {
               candidate=-1;
               for (int j=0; j<26; j++) {
                   if (table[j][k]) {
                      if (candidate==-1) {
                         candidate=j;                  
                      } else {
                        if (table[candidate][j]) {
                           candidate=j;
                        }      
                      }                 
                   }    
               }
               if (candidate!=-1) {
                  res=(char)(candidate+65)+res;
                  k=candidate;                  
               } else {
                 break;       
               }      
         }
         /*
         if (counter==0) {
            cout << res;
            counter=1;
         } else {           
           cout << endl << res;
         }   
         */
         cout << res << endl;
               
         vec.clear();
         for(int i=0; i<26; i++)
            for(int j=0; j<26; j++)
               table[i][j] = 0;
      } else {
         vec.push_back(str);
      }
   }
      
   return 0;
}

[serur]

to cyph1e:
I didn't scrutinize your code , but this problem should be easily solved using a queue,
think of it, I should fancy shouldn't be too difficult

Sau bol!
(Be healthy- from my native language )

[viniciusweb]

What's the correct output for the case below?

Code: Select all

AZ
B
#

Here we are sure that A comes before B, but we can't say anything about Z. The problem description does not explain this case.

EDIT: just read the problem description again and I it seems that there'll be no case like the one above: "Not all letters are necessarily used, but the list will imply a complete ordering among those letters that are used. ". Is it right?

Thanks.

[porker2008]

Not all the letters that have been used should be printed.

If you can't determine the order of some letters, you need not to print them.

for example:

A
BZ
#

You can just output

AB

However, there will be some strange situation you should pay attention.

Such as:

A
BC
BD
#

You should output

ABCD

But if the input is:

C
DA
DB

You also should output

ABCD

In the two cases above, we know that D after C, B after A.
However, we don't know whether A after D or C after B or other something else.
When we meet this kind of situation, we should output the order according to the alphabet order.
So that's why we should output ABCD in both cases.

[deadangelx]

What's the correct output for the case below?

Code: Select all

AZ
B
#

Here we are sure that A comes before B, but we can't say anything about Z. The problem description does not explain this case.

EDIT: just read the problem description again and I it seems that there'll be no case like the one above: "Not all letters are necessarily used, but the list will imply a complete ordering among those letters that are used. ". Is it right?

Thanks.

my AC code output is

Code: Select all

AZB

/* not ABZ */

but in the problem description, it says "Not all letters are necessarily used, but the list will imply a complete ordering among those letters that are used."
the important word is "complete ordering". So, I guess there is no such test case in the judge.

my algorithm is:
first, set the initial character ordering in the list. Then, fill other characters between these characters, and judge if it conflicts with the clue or not.
When you fill other characters, you first find which string this character is there.
Then, in the range of strings having the same length as this string and having the same initial character as this string, you can see which character is before and which character is behind.
ex.input

Code: Select all

XWY
ZX
ZXY
ZXW
YWWX
#

first set X Z Y
Then, we must fill 'W' between X Z Y or the last position.
1.we find X W Y has 'W', but there is no clue.
2.we find Z X W has 'W', and Z X Y before Z X W and both length are 3 and both initial character are Z.
this means, in index 2(start from 0), Y is before W.
3. we find Y W W X has 'W', but there is no clue.
so we just know Y is before W, and it is enough to set 'W' after 'Y'
then we get X Z Y W.

output

Code: Select all

XZYW

I usually doubt my algorithm is right or not, but it passed the judge test case.

try this input

Code: Select all

XZY
XGY
XWY
ZXY
ZGW
YWWX

my output is

Code: Select all

XZGYW

Hope it helps.

[phpUnsorter]

I don't suppose this is where I put my questions about UVa 200? Obviously, I'm getting WA. Here's my methodology:

1) Create a reverse-linked graph of known pairings. For example, from the test data given above:

Code: Select all

XZY
XGY
XWY
ZXY
ZGW
YWWX
#

'Z' would have a link to 'X', 'Y' would have a link to 'Z', from the first column.
'W' would have a link to 'Y', from the 3rd column of the 'Z' set.

2) Add all nodes to a TreeSet. The compareTo method for a node is as follows:

Code: Select all

If (other.numLinks==my.numLinks) return my.data-other.data
return my.numLinks-other.numLinks;

3) While this set is not empty, grab the next node. This node is guaranteed to have two properties: a) it is the next node topologically, and b) it is the next node lexicographically. Stop me if one of these two properties is false, which it very well might be.

4) Add this node to the result. For all other nodes, remove any links to this node and reset the ordering.

5) Repeat 3.

6) The end result should be a slight variation of a topological sort. Here's the test data it works with:

Code: Select all

XZY
XGY
XWY
ZXY
ZGW
YWWX
#
CA
CAE
CAF
AFFE
AFFB
AFFBC
EF
EB
#
XWY
ZX
ZXY
ZXW
YWWZ
#

The first case is obviously not going to be in the judge data as it has two possible orderings (XZGYW and XZYGW), but I thought I'd try it anyways. Also, it only takes in one test case. I just put all of them together here for convenience's sake. Here's the output, just in case:

Code: Select all

XZGYW
CAEFB
XZYW

[sazzadcsedu]

i have found a lots of discussion about this problem in board which makes the problem harder than it is.its a simple problem.just follow the algorithm given below

1.take the input in a 2d array str[][].
2.then

Code: Select all

from str[1][0]... str[n][0] insert the letter in a queue if not previously inserted.
then from str[1][1]... str[n][1] insert the letter in a queue if not previously inserted.  then from str[1][2]... str[n][2] insert the letter in a queue if not previously inserted.
and so on.
3.just print the queue.

[mf]

1.take the input in a 2d array str[][].
2.then

Code: Select all

from str[1][0]... str[n][0] insert the letter in a queue if not previously inserted.
then from str[1][1]... str[n][1] insert the letter in a queue if not previously inserted.  then from str[1][2]... str[n][2] insert the letter in a queue if not previously inserted.
and so on.
3.just print the queue.

Looks wrong to me - it won't work on

Code: Select all

XW
YX
YZ
YY
YW

If that got accepted, it's because judge has just a single and very weak test case.

Speaking of algorithms - this problem basically asks to do a topological sorting. Every pair of adjacent strings (except when one string is a prefix of the other) tells you an edge, e.g "XW, YX" tells that X < Y, and "YX, YZ" tells X < Z, and so on. Once you got all the edges, just topologically sort the vertices.

[Rashad]

I am getting WA in 200. Can anyone give me some I/O. Thanks in advance.

[alexiago]

I'm getting Runtime error with my code below. I'm not sure if I should increase any array but I believe their sizes are enough for this problem.
Any ideas? Thanks in advance.

My algorithm:
1) For all rows for the same column I'm looking for undiscovered characters and store them in the ans array - this would pick up the ascending order
Using the input below it would store XZY in the first iteration
XWY
ZX
ZXY
ZXW
YWWX
#
2) Removing all rows that don't have the same character, for comparison purposes the current position has to be the same for the next iteration so it unties the order, it "removes" rows by setting their size to zero ( sz[last[j]] = 0 )
Again, using the example above, it would "remove" the first and the last rows - so the comparison would be among the rows below at the second column (go back to step 1)
ZX
ZXY
ZXW

Code: Select all

Accepted Code :) - missed an index limit and my code got AC

[rambo1980]

Anyone help me please, why am i getting WA for this problem? It gives me right answers for all testcases i found on the board.

GOT AC

[brianfry713]

In your process function you loop until *p&&*q. What happens if a and b aren't the same length?

[rambo1980]

In your process function you loop until *p&&*q. What happens if a and b aren't the same length?

I suppose in that case a decision cannot be made
like-

Code: Select all

AGQ
AGQBE

What decision can i make out of this? In the problem it was mentioned that

Not all letters are necessarily used, but the list will imply a complete ordering among those letters that are used.

So i guess this case should never arise where i have to make a decision out of this type of relations.

[brianfry713]

Look at the sample input:
ZX
ZXY

Yes, this doesn't give you any information about the order, but this case can appear in the input. By looping until *p&&*q you're relying on the strings to be the same length. The data in the string beyond the terminating null character is uninitialized, and could be non-zero, causing your code to fail. Instead you should loop until (!*p)||(!*q).

[rambo1980]

Sorry i don't get it. I'm looping while *p and *q both is non-zero. If at some point both are non-zero(not null character) and have different value then a ordering information is added and the return statement is executed. If the strings are not of the same lengths, then the null character of the smaller length-ed string can be reached only if all the previous characters of the strings are the same.

I've tried what u've told me to do. But

Code: Select all

!( (!*p) || (!*q) ) ==  !(!*p) && !(!*q) == *p && *q

anyway got WA again. Could u please give me two strings for which my code will fail?