Page 1 of 2

10336 - Rank the Languages

Posted: Sun Sep 15, 2002 12:59 pm
by Mahbub
Isnt it dfs?

I got TLE..is there any faster algo?

Thanks

Posted: Mon Sep 16, 2002 5:22 am
by uzioriluzan
I also used a kind of DFS (Connected Components Algorithm) and got Accepted in 0.000secs.

Maybe your DFS loops because you does not mark the "vertices" you visit.

Regards

about 10336 - Why it is wrong ?

Posted: Wed Nov 20, 2002 10:24 am
by Faisal Chowdhury
Can anybody help me why I am getting "no" ?

@begin_of_source_code
#include<stdio.h>

unsigned long z,n,t, stack[40000][2], len[26];
long x, y, i, j, k, r, c;
char w[5000][5000], ch;

void search()
{

for( i=0; i<r; i++ )
for( j=0; j<c; j++ )
if( w[j]!='0' )
{
len[w[j]-97]++;
ch= w[j];

x=i;
y=j;
k=0;
stack[k][0]= x, stack[k][0]= y;
k++;

while(k!=0)
{
if( w[x][y+1]==ch && y<c )
{
w[x][y+1]='0';
stack[k][0]= x;
stack[k][1]= y+1;
y++;
k++;
}
else if( w[x][y-1]==ch && y>-1 )
{
w[x][y-1]='0';
stack[k][0]= x;
stack[k][1]= y-1;
y--;
k++;
}
else if( w[x+1][y]==ch && x<r )
{
w[x+1][y]='0';
stack[k][0]= x+1;
stack[k][1]= y;
x++;
k++;
}
else if( w[x-1][y]==ch && x>-1 )
{
w[x-1][y]='0';
stack[k][0]= x-1;
stack[k][1]= y;
x--;
k++;
}
else
{
k--;
x= stack[k][0];
y= stack[k][1];
}

}
}
}

void main()
{
n=1;
FILE *fp;
fp= stdin;

fscanf(fp,"%lu", &t);

while(n<=t)
{
for( i=0; i<26; i++ )
len= 0;

fscanf(fp,"%ld", &r);

fscanf(fp,"%ld", &c);

for( i=0; i<r; i++ )
fscanf(fp,"%s", w);
search();
printf("World #%lu\n", n);

for( i=0; i<26; i++ )
{
k=0;
z=0;
for( j=0; j<26; j++ )
if( z<len[j] )
{
z= len[j];
k=j;
}

if( z!=0 )
{
printf("%c: ", 97+k);
printf("%lu\n", z);
len[k]=0;
}
}

n++;
}

}
@end_of_source_code

Posted: Thu Dec 19, 2002 11:56 am
by deddy one
I also got TLE for this problem,

how to sort the output faster anyway????

Posted: Fri May 02, 2003 1:18 pm
by deddy one
I've given up this problem months ago,
until I tried to solve it again today,
and I get Accepted after experimenting with
a lot of submission

the max row and column never exceed 15,
hope this could help anyone out there that still
got time limit or memory limit in this problem

bye

test cases?

Posted: Tue May 20, 2003 3:51 pm
by stcheung
Can anyone find a test case that can break my code? I think my code works after some testing, but it got me a WA. Any help would be appreciated. Thanks.

[cpp]#include <iostream.h>
#include <stdlib.h>
#include <string>
#include <set>

int row, column;
char map[16][16];

void explore(int x, int y, char c);

int main()
{
int numcases;
string str;
cin >> numcases;
for(int i=1; i<=numcases; i++)
{
cin >> row >> column;
cout << "World #" << i << "\n";
for(int x=0; x<16; x++)
{
for(int y=0; y<16; y++)
map[x][y] = '0';
}
int counts[26];
for(int z=0; z<26; z++)
{
counts[z] = 0;
}
for(int j=0; j<row; j++)
{
cin >> str;
for(int k=0; k<column; k++)
{
map[j][k] = str[k];
}
}

char c;
for(int j=0; j<row; j++)
{
for(int k=0; k<column; k++)
{
c = map[j][k];
if(c != '0')
{
counts[c - 'a']++;
explore(j, k, c);
}
}
}

set<int> order;
for(int m=0; m<26; m++)
{
order.insert(counts[m]);
}

order.insert(-1);
order.erase(0);
set<int>::iterator itor = order.end();
while(itor != order.begin())
{
for(int m=0; m<26; m++)
{
if(counts[m] == *itor)
cout << (char)(m + 'a') << ": " << counts[m] << "\n";
}
itor--;
}
}
return 0;
}

void explore(int x, int y, char c)
{
bool up = x>0;
bool down = x<(row-1);
bool left = y>0;
bool right = y<(column-1);
if(up && map[x-1][y] == c)
{
map[x-1][y] = '0';
explore(x-1, y, c);
}
if(down && map[x+1][y] == c)
{
map[x+1][y] = '0';
explore(x+1, y, c);
}
if(left && map[x][y-1] == c)
{
map[x][y-1] = '0';
explore(x, y-1, c);
}
if(right && map[x][y+1] == c)
{
map[x][y+1] = '0';
explore(x, y+1, c);
}
}[/cpp]

Posted: Sat Aug 09, 2003 11:01 pm
by UFP2161
I just created some random input and came across something that the above code (by stcheung) produces the wrong output for:

Code: Select all

1
14 5
wiswy
rksht
wdzoo
ufoxa
awbhe
ubuuq
wrhux
xnpii
zschi
mfkft
twnkc
fsatd
rpxdg
kfvgi

Code: Select all

World #1
j: 0
l: 0
w: 6
f: 5
h: 4
...

Posted: Sat Oct 14, 2006 1:19 am
by Sumon
deddy one wrote:I've given up this problem months ago,
until I tried to solve it again today,
and I get Accepted after experimenting with
a lot of submission

the max row and column never exceed 15,
hope this could help anyone out there that still
got time limit or memory limit in this problem

bye
Thanks for sharing all your experiments with us. By the way, I don't understand why problemsetters play such type of "Hide and Seek" game with us. Can anyone tell me any logical reason for this type of problem setting strategy?!? :evil:

Posted: Fri Apr 27, 2007 7:31 am
by razor_blue
Somebody please help.... why my code is wrong?

Code: Select all

/* removed after AC */
I've tried many test cases. I think my output is right, but why WA?

Posted: Sat Apr 28, 2007 10:57 pm
by Jan
Does your code really work for an (m x n) matrix? Check your code again.

Hope it helps.

Posted: Mon Apr 30, 2007 8:22 am
by razor_blue
Thank you Jan, silly mistake again... :D

sd

Posted: Thu Aug 23, 2007 9:22 am
by darkos32
hi,i got WA..this is my code :

Code: Select all

#include <stdio.h>

int xs[16][16],max;
char s[16][16];
int x,y;

struct data
{
	char a[2];
	int b;
};

data kdat[300];

void cek(int awal,int po1,int po2,int p1,int p2){
	if(xs[p1][p2]==0 && s[po1][po2]==s[p1][p2]){
		if(awal==0) {
			int ada = 0;
			for(int i=0;i<max && ada==0;i++){
				if(kdat[i].a[0]==s[po1][po2]) {
					kdat[i].b++;
					ada = 1;
				}
			}
			if(ada==0){
				kdat[max].a[0]=s[po1][po2];
				kdat[max].b = 1;
				max++;
			}
		}
		xs[p1][p2] = 1;
		if(p1+1<x) cek(1,po1,po2,p1+1,p2);
		if(p2+1<y)  cek(1,po1,po2,p1,p2+1);
		if(p1-1>=0) cek(1,po1,po2,p1-1,p2);
		if(p1-2>=0) cek(1,po1,po2,p1,p2-1);
	}
}

void sort(){
	for(int i=0;i<max;i++){
		for(int j=i+1;j<max;j++){
			if((kdat[i].b<kdat[j].b) || (kdat[i].b==kdat[j].b && kdat[i].a[0]>kdat[j].a[0])){
				char temp[2];
				temp[0] = kdat[i].a[0];
				kdat[i].a[0] = kdat[j].a[0];
				kdat[j].a[0] = temp[0];
				int tempn = kdat[i].b;
				kdat[i].b = kdat[j].b;
				kdat[j].b = tempn;
			}
		}
	}
}

void main(){
	int nd;
	scanf("%d",&nd);
	for(int g=0;g<nd;g++){
		scanf("%d %d\n",&x,&y);
		for(int i=0;i<x;i++){
			gets(s[i]);
			for(int j=0;j<y;j++){
				xs[i][j] = 0;			
			}
		}
		max = 0;
		for(int k=0;k<x;k++){
			for(int l=0;l<y;l++){
				if(xs[k][l]==0) cek(0,k,l,k,l);
			}
		}
		sort();
		printf("World #%d\n",g+1);
		for(int t=0;t<max;t++){
			printf("%c: %d\n",kdat[t].a[0],kdat[t].b);
		}
	}
}

please help me..thanks..

Re: 10336 - Rank the Languages

Posted: Wed Oct 01, 2008 6:44 pm
by bishop
why this is WA
i can't find
can anyone help me

Code: Select all

#include<iostream>
#include<cmath>
#include<queue>
using namespace std;

#define MAX 111
bool g[MAX][MAX];
enum{No=0,white, Black,Gray};
int color[MAX][MAX];
int r,c;
char str[MAX][MAX];	
bool graf[MAX][MAX];
int dfs(int x, int y, char ch)
{
	int i,j,m,n;
	color[x][y]=Gray;
	
	if((x+1<r&&y<c)&&color[x+1][y]==white&&str[x+1][y]==ch)
		dfs(x+1,y,str[x+1][y]);	     
	else if((x-1<r&&y<c)&&color[x-1][y]==white&&str[x-1][y]==ch)
		dfs(x-1,y,str[x-1][y]);	     
	else if((x<r&&y+1<c)&&color[x][y+1]==white&&str[x][y+1]==ch)
		dfs(x,y+1,str[x][y+1]);	     
	else if((x<r&&y-1<c)&&color[x][y-1]==white&&str[x][y-1]==ch)
		dfs(x,y-1,str[x][y-1]);	     
	color[x][y]=Black;
	
	return 0;
}

int main()
{
	queue<char> Q;
	int i,j,k,l;
	int count;
	bool counter[500];
	
	int n,T=1;
	cin >> n;
	char ct[30];
	while(n--)
	{
		cin >> r >> c;
		for(i=0; i<30; i++) 
		{
			ct[i]=0;
			counter[i+97]=false;
		}
		for(i=0; i<r; i++)
		for(j=0; j<c; j++)
		{
			cin >> str[i][j];
			color[i][j]=white;
		}
		for(i=0; i<r; i++)
		for(j=0; j<c; j++)
	 	{
			if(color[i][j]==white)
			{
				ct[str[i][j]-97]++;
				dfs(i,j,str[i][j]);	   	   	   	   
			}
			
		}  	
		char car[MAX];
		int ca[MAX];
		j=0;
		for(i=0; i<26; i++)	   
		if(ct[i]!=0)
		{
			ca[j]=ct[i];
			car[j]=i+97;
			j++;
		}
		
		int m;
		
		for(i=0; i<j-1; i++)
		for(m=0; m<j-1-i; m++)
		{
			if(ca[m]<ca[m+1])
			{
				int t=ca[m];
				char te=car[m];
				ca[m]=ca[m+1];
				car[m]=car[m+1];
				ca[m+1]=t;
				car[m+1]=te;
			}
			else if(ca[m]==ca[m+1])
			{
				if(car[m]>car[m+1])
				{
					int tp=ca[m];
					char tem=car[m];
					ca[m]=ca[m+1];
					car[m]=car[m+1];
					ca[m+1]=tp;
					car[m+1]=tem;
				}
			}
		}
		
		cout << "World #"<<T++<<endl;
		
		for(i=0; i<j; i++)
		{
			cout << car[i] <<": "<<ca[i]<<endl;
		}
	}
	return 0;	 
}


Re: 10336 - Rank the Languages

Posted: Sat Feb 28, 2009 9:52 am
by vahid sanei
to bishop
try this:
input

Code: Select all

1
4 8
ttuuttdd
ttuuutdd
uuutuudd
uuttuudd
correct output is

Code: Select all

World #1
t: 3
d: 1
u: 1

10336 - Rank the Languages

Posted: Tue Nov 01, 2011 9:50 pm
by mastergoos
I've tried so much tests, in every tests the result is correct..
The submit say: Wrong Answer.
What is wrong on my code ?

Code: Select all

import java.util.Scanner;

public class Main {

	private static char[][] grid;
	private static int[] dx = { 0, -1, 0, 1 };
	private static int[] dy = { -1, 0, 1, 0 };

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = "";
		int N = Integer.parseInt(sc.nextLine());
		int map = 0;
		while (N-- > 0) {
			s = sc.nextLine();
			String[] size = s.split("\\s");
			int n = Integer.parseInt(size[0]);
			int m = Integer.parseInt(size[1]);
			grid = new char[n][m];
			for (int i = 0; i < n; ++i) {
				grid[i] = sc.nextLine().toCharArray();
			}
			char[] alph = letters();
			int[] amm = new int[alph.length];
			for (int i = 0; i < amm.length; i++) {
				for (int j = 0; j < n; j++) {
					for (int k = 0; k < m; k++) {
						if (grid[j][k] == alph[i]) {
							dfs(j, k, alph[i], Character.toUpperCase(alph[i]));
							amm[i]++;
						}
					}
				}
			}
			sort(alph, amm);
			System.out.print("World #" + (++map) + "\n");
			for (int i = 0; i < amm.length; i++) {
				System.out.print(alph[i] + ": " + amm[i] + "\n");
			}
		}
		System.exit(0);
	}

	public static char[] letters() {
		boolean[] aux = new boolean[26];
		for (int i = 0; i < grid.length; i++) {
			for (int j = 0; j < grid[0].length; j++) {
				aux[grid[i][j] - 'a'] = true;
			}
		}
		int amm = 0;
		for (boolean i : aux) {
			if (i)
				++amm;
		}
		char[] ret = new char[amm];
		amm = 0;
		for (int i = 0; i < 26; ++i) {
			if (aux[i]) {
				ret[amm++] = (char) (i + 'a');
			}
		}
		return ret;
	}

	public static void dfs(int x, int y, char cur, char rep) {
		if (grid[x][y] != cur)
			return;
		grid[x][y] = rep;
		for (int i = 0; i < 4; i++) {
			if (x + dx[i] >= 0 && y + dy[i] >= 0 && x + dx[i] < grid.length && y + dy[i] < grid[0].length && grid[x + dx[i]][y + dy[i]] == cur) {
				dfs(x + dx[i], y + dy[i], cur, rep);
			}
		}
	}

	public static void sort(char[] alph, int[] amm) {
		int n = alph.length;
		for (int i = 0; i < n - 1; i++) {
			for (int j = 0; j < n - i - 1; j++) {
				if (amm[j] < amm[j + 1]) {
					char temp0 = alph[j + 1];
					alph[j + 1] = alph[j];
					alph[j] = temp0;
					int temp1 = amm[j + 1];
					amm[j + 1] = amm[j];
					amm[j] = temp1;
				}
			}
		}
	}
}