200 - Rare Order

[brianfry713]

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.

[rambo1980]

wow great algorithm. thanks. i'll try it

[tzupengwang]

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[22],B[22],*a,*b;
int al[30][30], link[30],TS[30];
bool use[30];
priority_queue<int,vector<int>,greater<int> > q;
int amm;

void INITIAL()
{
     for (int i=0;i<26;i++)
     {
         al[i][0]=0;
         link[i]=0;
         use[i]=0;    
     }     
}
void LINK(char x,char y)
{
     use[y-'A']=true;
     use[x-'A']=true;
     link[y-'A']++;
     al[x-'A'][++al[x-'A'][0]]=y-'A';
}
void SCAN()
{
     scanf("%s",A);
     use[A[0]-'A']=true;
     a=A;b=B;
     while (scanf("%s",b)!=EOF)
     {
           if (b[0]=='#')break;
           int la=strlen(a),lb=strlen(b);
           for (int i=0;i<min(la,lb);i++)
           {
               if (a[i]==b[i])continue;
               LINK(a[i],b[i]);
               printf("1\n");
               break;
           }
           swap(a,b);
     }
}
void TOPOLOGICAL_SORT()
{
     amm=0;
     for (int i=0;i<26;i++)
     {
         if (use[i])
         {
            amm++;   
            if (link[i]==0)
            {
               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][0];i++)
           {
               if (--link[al[k][i]]==0)
                  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]

There shouldn't be any 1's in the output.

[tzupengwang]

There shouldn't be any 1's in the output.

Excuse me, I don't really understand.
Could you give further explanation?
TKS~

[brianfry713]

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

The sample output doesn't have any 1's.

[LazyTym]

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[25],f;
    char order[25];
    int check[27];

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

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

    order[0]=s[0][0];
    check[s[0][0]-'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]

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[5000].

It will be good if you remove all your codes after getting accepted.

[MNT.95]

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

[brianfry713]

Try running your code on the sample input.

[redwan1795]

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

Code: Select all

#include<stdio.h>

#define SIZE 22

int input[10000][SIZE], ruleArray[26][26];

char inputCh;
int inputInt;

int colorArray[102];
int inputArray[26], outputArray[26], visited[26];

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;
}

=====================================