10336 - Rank the Languages
Moderator: Board moderators
10336 - Rank the Languages
Isnt it dfs?
I got TLE..is there any faster algo?
Thanks
I got TLE..is there any faster algo?
Thanks
-
- New poster
- Posts: 27
- Joined: Thu Feb 14, 2002 2:00 am
-
- New poster
- Posts: 1
- Joined: Wed Nov 20, 2002 10:17 am
- Location: Khulna, Bangladesh
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
@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
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]
[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]
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
...
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?!?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
![:evil:](./images/smilies/icon_evil.gif)
Change your view,your life will be changed.
-
- New poster
- Posts: 27
- Joined: Mon Nov 27, 2006 4:44 am
- Location: Indonesia
Somebody please help.... why my code is wrong?
I've tried many test cases. I think my output is right, but why WA?
Code: Select all
/* removed after AC */
Last edited by razor_blue on Mon Apr 30, 2007 8:24 am, edited 1 time in total.
Does your code really work for an (m x n) matrix? Check your code again.
Hope it helps.
Hope it helps.
Ami ekhono shopno dekhi...
HomePage
HomePage
-
- New poster
- Posts: 27
- Joined: Mon Nov 27, 2006 4:44 am
- Location: Indonesia
sd
hi,i got WA..this is my code :
please help me..thanks..
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
why this is WA
i can't find
can anyone help me
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;
}
-
- Learning poster
- Posts: 84
- Joined: Fri Jan 09, 2009 4:37 pm
- Location: IRAN
Re: 10336 - Rank the Languages
to bishop
try this:
input
correct output is
try this:
input
Code: Select all
1
4 8
ttuuttdd
ttuuutdd
uuutuudd
uuttuudd
Code: Select all
World #1
t: 3
d: 1
u: 1
Impossible says I`m possible
-
- 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..
The submit say: Wrong Answer.
What is wrong on my code ?
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;
}
}
}
}
}