## 200 - Rare Order

Moderator: Board moderators

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

### Re: 200 - Rare Order

Sorry, you are correct about *p and *q.

My algorithm gets AC in 1 second. I keep track of each ordered pair of letters, for the sample input you can determine that:
X is before Z
Y is before W
Z is before Y

I then call a function on each used letter i. For each letter j found after i it adds one to a count for j and recursively calls j.
XZYW
For W it does nothing (nothing after W).
For X it adds one to Z and then recursively calls Z, which adds one to Y and recursively calls Y, which adds one to W and recursively calls W.
For Y it adds one to W and recursively calls W.
For Z it adds one to Y and recursively calls Y, which adds one to W and recursively calls W.

You end up with the count for W=3, X=0, Y=2, and Z=1. Sort and output.
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

wow great algorithm. thanks. i'll try it

tzupengwang
New poster
Posts: 36
Joined: Fri Dec 02, 2011 1:30 pm
Location: Kaohsiung, Taiwan

### Re: 200 - Rare Order

I find all the edges first, and do topological sort!!
I can't find out any mistake after testing so many sample I/O, BUT I get WA all the time~
Can anyone help?
(I use adjacency list to record the edges)

Code: Select all

``````/*200*/
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;

char A,B,*a,*b;
bool use;
priority_queue<int,vector<int>,greater<int> > q;
int amm;

void INITIAL()
{
for (int i=0;i<26;i++)
{
al[i]=0;
use[i]=0;
}
}
{
use[y-'A']=true;
use[x-'A']=true;
al[x-'A'][++al[x-'A']]=y-'A';
}
void SCAN()
{
scanf("%s",A);
use[A-'A']=true;
a=A;b=B;
while (scanf("%s",b)!=EOF)
{
if (b=='#')break;
int la=strlen(a),lb=strlen(b);
for (int i=0;i<min(la,lb);i++)
{
if (a[i]==b[i])continue;
printf("1\n");
break;
}
swap(a,b);
}
}
void TOPOLOGICAL_SORT()
{
amm=0;
for (int i=0;i<26;i++)
{
if (use[i])
{
amm++;
{
q.push(i);
}
}
}
int ptr=0;
while (!q.empty())
{
int k=q.top();
TS[ptr++]=k;
q.pop();
for (int i=1;i<=al[k];i++)
{
q.push(al[k][i]);
}
}
}
int main()
{
INITIAL();
SCAN();
TOPOLOGICAL_SORT();
for (int i=0;i<amm;i++)
{
printf("%c",TS[i]+'A');
}
puts("");
//system ("pause");
return 0;
}
``````

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

### Re: 200 - Rare Order

There shouldn't be any 1's in the output.
Check input and AC output for thousands of problems on uDebug!

tzupengwang
New poster
Posts: 36
Joined: Fri Dec 02, 2011 1:30 pm
Location: Kaohsiung, Taiwan

### Re: 200 - Rare Order

There shouldn't be any 1's in the output.
Excuse me, I don't really understand.
Could you give further explanation?
TKS~

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

### Re: 200 - Rare Order

In your code, line 44 is:
printf("1\n");

The sample output doesn't have any 1's.
Check input and AC output for thousands of problems on uDebug!

LazyTym
New poster
Posts: 31
Joined: Tue Jun 24, 2014 9:10 pm

### 200 - Rare Order

pls help me!!!!!!!! where is the problem to my code???? it's very annoying to me!!! why my code getting Runtime Error and what is the proper meaning of Runtime Error???

Code: Select all

``````#include<iostream>
#include<string>

using namespace std;

int Min(string x,string y) {
if(x.length()>y.length()) return (y.length());
else return (x.length());
}

int main()
{
int c=0;
string s,f;
char order;
int check;

while(1) {
cin>>f;
if(f=="#") break;
s[c]=f;
c++;
}

for(int i=0;i<27;i++) check[i]=0;

order=s;
check[s-'A']=1;
int flag=0,index=1,j;

for(int i=0;i<c-1;i++) {

for(j=0;j<Min(s[i],s[i+1]);j++) {
if(s[i][j]!=s[i+1][j] && check[s[i+1][j]-'A']==0) {
flag=1;
check[s[i+1][j]-'A']=1;
order[index]=s[i+1][j];
index++;
break;
}
}
if(flag==0) {
for(int k=j;k<s[i+1].length();k++) {
if(check[s[i+1][k]-'A']==0) {
order[index]=s[i+1][k];
check[s[i+1][j]-'A']=1;
index++;
flag=0;
break;
}
}
}
}
for(int i=0;i<index;i++){
cout<<order[i];
}
cout<<endl;
return 0;
}

``````

lighted
Guru
Posts: 587
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 200 - Rare Order

One of the most common cause of run-time errors is getting out of range in array. Why do you assume that judge's input contains only 25 strings? To avoid RE increase array's range to s.

It will be good if you remove all your codes after getting accepted. A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

MNT.95
New poster
Posts: 7
Joined: Thu Jan 23, 2014 5:40 pm

### Re: 200 - Rare Order

I don't completely understand the problem :3 but this is my code, please if someone can tell what is wrong

My Approach:
1) make an edge from every character in the string to character before it, I made the map "hs" to exchange the characters with numbers ("id" variable) so that would make the graph nodes just numbers.
2) apply dfs and make topological sort.

Code: Select all

``````AC :D
``````
Last edited by MNT.95 on Thu Feb 05, 2015 11:59 am, edited 1 time in total.

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

### Re: 200 - Rare Order

Try running your code on the sample input.
Check input and AC output for thousands of problems on uDebug!

redwan1795
New poster
Posts: 1
Joined: Sat May 28, 2016 2:19 pm

### Re: 200 - Rare Order

Why am I getting WA in the following code?
=========================================

Code: Select all

``````#include<stdio.h>

#define SIZE 22

int input[SIZE], ruleArray;

char inputCh;
int inputInt;

int colorArray;
int inputArray, outputArray, visited;

int count;

bool didResultComputed;

void bin (int level)
{
if (level==count )
{
for (int i =0; i< count; i++)
{
printf("%c", (90-outputArray[i]));
}
//printf("\n");

didResultComputed = true;
return;
}

for (int i =0; i< count; i++)
{
if (visited[i]==0 && didResultComputed==false)
{
for (int j = 0; j < count; j++)
{
if (ruleArray[i][j] == 1 && visited[j] == 1)
return ;
}
outputArray[level] = inputArray[i];
visited[i]=1;
bin(level+1);
visited[i]=0;
}
}

}

void printInputArray(int count)
{
printf("\nInput Array: \n");
printf("count: %d \n", count);
for (int i =0; i<count; i++)
{
printf("%d ", inputArray[i]);
}

printf("\n");
}

void printRuleArray()
{
for (int i =0 ; i <26; i++)
{
for (int j =0 ; j <26; j++)
{
printf("%d ", ruleArray[i][j]);
}
printf("\n");
}
}

int getAbs(int value)
{
if (value<0)
return value * -1;
else
return value;

}

void createRuleArray (int m, int n)
{
int index1 = 0, index2 = 0;
for (int i = 0; i < m; i++)
{
for(int j = 0; i<n;i++)
{
if (i+1<m && j+1<n && input[i][j] !=0 && input[i+1][j]!=0)
{
if (input[i][j] != input[i+1][j])
{
index1 = getAbs(90-input[i][j]);
index2 = getAbs(90-input[i+1][j]);
ruleArray[index1][index2] = 1;

//printf("index1: %d index2: %d ruleArray[%d][%d]: %d \n", index1, index2, index1, index2, ruleArray[i][j]);

i++;
}
else if (input[i][j] == input[i+1][j])
{
//j++;
}
else
{
continue;
}
}
}
}
}

void printInputArray(int m, int n)
{
//printf ("m: %d n: %d", m,n);

for(int i =0 ; i<m;  i++)
{
for (int j=0; j <n; j++)
{
printf("%d ", input[i][j]);
}
printf("\n");
}
}

int main()
{
int m =0, n =0;

while((inputCh=getchar())!='#')
{

inputInt = inputCh;

if(inputInt == 10)
{
//printf("\n");
m++;
n = 0;
continue;
}
if (inputInt>= 65 && inputInt <= 90)
{

input[m][n]= inputInt;
colorArray[getAbs(90-inputInt)] = 1;
n++;
}
}

count=0;
for(int i =0; i<100; i++)
{
if(colorArray[i]==1)
{

inputArray[count]=i;
count++;

}
}

//debug
//printInputArray(count);
//debug
//printInputArray(m, SIZE);

createRuleArray(m, SIZE);

//debug
//printRuleArray();

didResultComputed = false;
bin (0);
return 0;
}
``````
=====================================