200 - Rare Order

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

Moderator: Board moderators

cyph1e
New poster
Posts: 2
Joined: Sun Jan 08, 2006 12:30 pm

200 - Rare Order

Post by cyph1e » Thu Jan 19, 2006 4:44 pm

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
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur » Fri Mar 24, 2006 11:05 pm

to cyph1e:
I didn't scrutinize your code :D , 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
New poster
Posts: 24
Joined: Sun Nov 12, 2006 3:38 pm

Re: 200 - Rare Order - WA

Post by viniciusweb » Thu Oct 02, 2008 5:21 am

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
New poster
Posts: 21
Joined: Wed Oct 08, 2008 7:04 am

Re: 200 - Rare Order - WA

Post by porker2008 » Wed Oct 08, 2008 8:43 pm

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
New poster
Posts: 32
Joined: Tue Feb 13, 2007 1:31 pm

Re: 200 - Rare Order - WA

Post by deadangelx » Wed Apr 22, 2009 11:51 am

viniciusweb wrote: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
New poster
Posts: 1
Joined: Wed Jul 01, 2009 2:47 am

Re: 200 - Rare Order - WA

Post by phpUnsorter » Wed Jul 01, 2009 2:58 am

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
Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Location: narayangong,bangladesh.
Contact:

important: 200 - Rare Order

Post by sazzadcsedu » Sat Jul 25, 2009 9:45 pm

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.

Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359
For Hints: http://salimsazzad.wordpress.com

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: important: 200 - Rare Order

Post by mf » Sat Jul 25, 2009 10:17 pm

sazzadcsedu wrote: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
New poster
Posts: 17
Joined: Tue Dec 22, 2009 4:20 pm

Re: 200 - Rare Order

Post by Rashad » Thu Sep 23, 2010 3:43 am

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

alexiago
New poster
Posts: 14
Joined: Thu Jan 24, 2008 6:34 pm

Re: 200 - Rare Order

Post by alexiago » Fri Jul 15, 2011 1:30 am

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
New poster
Posts: 15
Joined: Sun Mar 18, 2012 2:45 pm

Re: 200 - Rare Order

Post by rambo1980 » Tue Apr 24, 2012 7:21 am

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
Last edited by rambo1980 on Fri Apr 27, 2012 9:45 am, edited 2 times in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 200 - Rare Order

Post by brianfry713 » Wed Apr 25, 2012 1:11 am

In your process function you loop until *p&&*q. What happens if a and b aren't the same length?
Check input and AC output for thousands of problems on uDebug!

rambo1980
New poster
Posts: 15
Joined: Sun Mar 18, 2012 2:45 pm

Re: 200 - Rare Order

Post by rambo1980 » Wed Apr 25, 2012 1:40 am

brianfry713 wrote: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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 200 - Rare Order

Post by brianfry713 » Thu Apr 26, 2012 2:02 am

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).
Check input and AC output for thousands of problems on uDebug!

rambo1980
New poster
Posts: 15
Joined: Sun Mar 18, 2012 2:45 pm

Re: 200 - Rare Order

Post by rambo1980 » Thu Apr 26, 2012 10:40 am

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?

Post Reply

Return to “Volume 2 (200-299)”