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

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

Re: 200 - Rare Order

Post by brianfry713 » Fri Apr 27, 2012 5:06 am

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

Post by rambo1980 » Fri Apr 27, 2012 9:08 am

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

Post by tzupengwang » Tue Jul 24, 2012 5:11 pm

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

Re: 200 - Rare Order

Post by brianfry713 » Wed Jul 25, 2012 2:18 am

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

Post by tzupengwang » Wed Jul 25, 2012 9:38 am

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

Post by brianfry713 » Wed Jul 25, 2012 11:37 pm

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

Post by LazyTym » Sat Oct 25, 2014 8:19 pm

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
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 200 - Rare Order

Post by lighted » Sun Oct 26, 2014 11:40 am

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. 8)
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

Post by MNT.95 » Wed Feb 04, 2015 5:05 pm

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

Post by brianfry713 » Thu Feb 05, 2015 1:59 am

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

Post by redwan1795 » Sat May 28, 2016 2:30 pm

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

Post Reply

Return to “Volume 2 (200-299)”