10336 - Rank the Languages

[Mahbub]

Isnt it dfs?

I got TLE..is there any faster algo?

Thanks

[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

[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

[deddy one]

I also got TLE for this problem,

how to sort the output faster anyway????

[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

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

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

[Sumon]

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?!?

[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?

[Jan]

Does your code really work for an (m x n) matrix? Check your code again.

Hope it helps.

[razor_blue]

Thank you Jan, silly mistake again...

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

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

[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

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