10336 - Rank the Languages

All about problems in Volume 103. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Mahbub
New poster
Posts: 26
Joined: Thu Aug 08, 2002 8:04 am

10336 - Rank the Languages

Post by Mahbub » Sun Sep 15, 2002 12:59 pm

Isnt it dfs?

I got TLE..is there any faster algo?

Thanks

uzioriluzan
New poster
Posts: 27
Joined: Thu Feb 14, 2002 2:00 am

Post by uzioriluzan » Mon Sep 16, 2002 5:22 am

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
New poster
Posts: 1
Joined: Wed Nov 20, 2002 10:17 am
Location: Khulna, Bangladesh

about 10336 - Why it is wrong ?

Post by Faisal Chowdhury » Wed Nov 20, 2002 10:24 am

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
Thinker

deddy one
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm

Post by deddy one » Thu Dec 19, 2002 11:56 am

I also got TLE for this problem,

how to sort the output faster anyway????

deddy one
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm

Post by deddy one » Fri May 02, 2003 1:18 pm

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
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

test cases?

Post by stcheung » Tue May 20, 2003 3:51 pm

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]

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Sat Aug 09, 2003 11:01 pm

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
New poster
Posts: 17
Joined: Fri May 30, 2003 8:14 pm
Location: Bangladesh
Contact:

Post by Sumon » Sat Oct 14, 2006 1:19 am

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:
Change your view,your life will be changed.

razor_blue
New poster
Posts: 27
Joined: Mon Nov 27, 2006 4:44 am
Location: Indonesia

Post by razor_blue » Fri Apr 27, 2007 7:31 am

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?
Last edited by razor_blue on Mon Apr 30, 2007 8:24 am, edited 1 time in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sat Apr 28, 2007 10:57 pm

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

Hope it helps.
Ami ekhono shopno dekhi...
HomePage

razor_blue
New poster
Posts: 27
Joined: Mon Nov 27, 2006 4:44 am
Location: Indonesia

Post by razor_blue » Mon Apr 30, 2007 8:22 am

Thank you Jan, silly mistake again... :D

darkos32
New poster
Posts: 27
Joined: Tue Jul 25, 2006 8:10 am
Location: Indonesia
Contact:

sd

Post by darkos32 » Thu Aug 23, 2007 9:22 am

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
New poster
Posts: 43
Joined: Fri May 04, 2007 12:57 pm

Re: 10336 - Rank the Languages

Post by bishop » Wed Oct 01, 2008 6:44 pm

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


User avatar
vahid sanei
Learning poster
Posts: 84
Joined: Fri Jan 09, 2009 4:37 pm
Location: IRAN

Re: 10336 - Rank the Languages

Post by vahid sanei » Sat Feb 28, 2009 9:52 am

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
Impossible says I`m possible

mastergoos
New poster
Posts: 2
Joined: Tue Nov 01, 2011 9:46 pm

10336 - Rank the Languages

Post by mastergoos » Tue Nov 01, 2011 9:50 pm

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

Post Reply

Return to “Volume 103 (10300-10399)”