## 10336 - Rank the Languages

Moderator: Board moderators

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

### 10336 - Rank the Languages

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

### about 10336 - Why it is wrong ?

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

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
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
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
Contact:
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?!?

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

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
Contact:
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
Thank you Jan, silly mistake again...

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

### sd

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) {
if(kdat[i].a[0]==s[po1][po2]) {
kdat[i].b++;
}
}
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);
}
}
}``````

bishop
New poster
Posts: 43
Joined: Fri May 04, 2007 12:57 pm

### Re: 10336 - Rank the Languages

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
Learning poster
Posts: 84
Joined: Fri Jan 09, 2009 4:37 pm
Location: IRAN

### Re: 10336 - Rank the Languages

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

I've tried so much tests, in every tests the result is correct..
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;
}
}
}
}
}
``````