10259 - Hippity Hopscotch

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

Moderator: Board moderators

Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am

10259 - Hippity Hopscotch

Post by Christian Schuster »

Hi there,

I'm currently trying to succeed on Problem 10259 (Hippity Hopscotch, from the latest contest), but I keep getting WA. I'm using a recursive algorithm with memoization which does the following thing:

maxpennys(x,y) = pennys[x][y] + MAX { maxpennys(x,yn) ; maxpennys(xn,y) }

where (x,yn) respectively (xn,y) refer to reachable fields.

I don't know what's wrong with this, because it seems quite simple.

I just don't know why nobody got AC before...

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel »

Hi,
I think the input they use is incorrect. Because I have tested my program with the test cases of the Waterloo website, and everything was ok. I have written an email to problemset@uva.es.
And in 10262 I got Presentation Error without reason, I think.

blue cat
New poster
Posts: 3
Joined: Tue Apr 09, 2002 6:03 am

It's surely something wrong with the judge.

Post by blue cat »

You algorithm is right.
I got accepted the second time during the real contest time,but my original program can't get accepted now.

ftomi
Learning poster
Posts: 64
Joined: Sun Jan 06, 2002 2:00 am
Location: Hungary
Contact:

Post by ftomi »

I haven't tried to submit it in the 24-h contest, but did you care about multiple input? In the contest, there were no problem with this task.
blue cat wrote:but my original program can't get accepted now.
It's all right. (because the multiple input)

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

10259

Post by htl »

I always get WA in this problem. Is anything I didn't consider yet?
Could someone give some data?
[c]
#include<stdio.h>
#include<stdlib.h>
typedef struct position
{
int x,y;
long n;
}pos;
int comp(const void*,const void*);
void main(void)
{
int n,k,count,x,y,z,a,tempx,tempy;
long board[100][100],table[100][100],max;
pos *data;
scanf("%d",&count);
for(x=0;x<count;x++)
{
if(x)
printf("\n");
scanf("%d %d",&n,&k);
data=(pos *)malloc(sizeof(pos)*n*n);
for(y=0,a=0;y<n;y++)
for(z=0;z<n;z++)
scanf("%ld",&board[y][z]),data[a].x=y,data[a].y=z,data[a].n=table[y][z]=board[y][z],a++;
qsort(data,n*n,sizeof(pos),comp);
for(y=0,max=-1;y<n*n;y++)
{
tempx=data[y].x,tempy=data[y].y;
for(z=1;z<=k;z++)
{
if(tempx-z>=0 && board[tempx][tempy]>board[tempx-z][tempy] && table[tempx][tempy]+board[tempx-z][tempy]>table[tempx-z][tempy])
{
table[tempx-z][tempy]=table[tempx][tempy]+board[tempx-z][tempy];
if(table[tempx-z][tempy]>max)
max=table[tempx-z][tempy];
}
if(tempx+z<n && board[tempx][tempy]>board[tempx+z][tempy] && table[tempx][tempy]+board[tempx+z][tempy]>table[tempx+z][tempy])
{
table[tempx+z][tempy]=table[tempx][tempy]+board[tempx+z][tempy];
if(table[tempx+z][tempy]>max)
max=table[tempx+z][tempy];
}
if(tempy-z>=0 && board[tempx][tempy]>board[tempx][tempy-z] && table[tempx][tempy]+board[tempx][tempy-z]>table[tempx][tempy-z])
{
table[tempx][tempy-z]=table[tempx][tempy]+board[tempx][tempy-z];
if(table[tempx][tempy-z]>max)
max=table[tempx][tempy-z];
}
if(tempy+z<n && board[tempx][tempy]>board[tempx][tempy+z] && table[tempx][tempy]+board[tempx][tempy+z]>table[tempx][tempy+z])
{
table[tempx][tempy+z]=table[tempx][tempy]+board[tempx][tempy+z];
if(table[tempx][tempy+z]>max)
max=table[tempx][tempy+z];
}
}
}
printf("%ld\n",max);
free(data);
}
}
int comp(const void *a,const void *b)
{
return ((pos *)b)->n-((pos *)a)->n;
}
[/c]

Even
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan

Post by Even »

if input like

2 100
10 0
0 0

your output is -1 ... but it should be 10 ... got it :wink:

Yu Fan
New poster
Posts: 26
Joined: Thu Nov 13, 2003 3:52 am

10259 how to attain speed

Post by Yu Fan »

i use straightfoward BFS and got AC in 5.xx seconds
but the top of this problem's static solve it within 0.00.137
how to make this?

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego »

I got a lot of WA on this problem before I realized that the contestant must always start at (0,0), not anywhere else. :-) It's good to read the problem statement before coding.
If only I had as much free time as I did in college...

Andrey Grigorov
New poster
Posts: 8
Joined: Thu Jul 15, 2004 3:52 pm
Location: Russia, Cherepovets

Why Compile Error?

Post by Andrey Grigorov »

Please, help me! Why my program get Compile Error

Code: Select all

/*Problem 10259 */
#include <stdio.h>

const osn = 10;
const maxn = 100;
typedef int tlong[maxn];

void sum(tlong a, tlong b, tlong& c){
  int i,n;
  for (i = 0; i <= maxn; i++)
    c[i] = 0;
  n = (a[0] > b[0]) ? a[0] : b[0];
  for (i = 1; i <= n; i++){
    c[i+1] = (a[i]+b[i]+c[i])/osn;
    c[i] = (a[i]+b[i]+c[i])%osn;
  }
  c[0] = (c[n+1] > 0) ? n+1 : n;
}

void printlong(tlong a){
  int i;
  for (i = a[0]; i >= 1; i--)
    printf("%d",a[i]);
  printf("\n");
}

void main(){
  tlong b,a[251];
  int i,j,n;
  for (i = 0; i <= 1; i++)
    for (j = 0; j <= maxn; j++)
      a[i][j] = 0;
  a[0][0] = 1;
  a[0][1] = 1;
  a[1][0] = 1;
  a[1][1] = 1;
  for (i = 2; i <= 250; i++){
    sum(a[i-1],a[i-2],b);
    sum(a[i-2],b,a[i]);
  }
  while (scanf("%d",&n) == 1){
    printlong(a[n]);  
  }
}

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba »

This is C++, not C, so int is no longer the default type. main should return int.

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

Post by sumankar »

Krzysztof Duleba wrote:This is C++, not C, so int is no longer the default type. main should return int.
Even in C, main must return an int value. However, the default to int rule is
not applicable here, as the OP uses void main(), which is not supposed to be
a standard return type for int. Some implementations might support it, but that's it. Try gcc -Wall with the following:

Code: Select all

void main() {}

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 »

To make Krzysztof's explanation clearer, here is the list of compile errors obtained when compiling your code using g++ 2.95:

p10259.cpp:4: ANSI C++ forbids declaration `osn' with no type
p10259.cpp:5: ANSI C++ forbids declaration `maxn' with no type

Why are you doing this:

typedef int tlong[maxn];

when could you could have simply printed integers using %d conversion specifier. And even if you intended to use an int array, you could use int arr[10], for an array of 10 elements.

This is the compile error in your code.

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba »

sumankar wrote:
Krzysztof Duleba wrote:This is C++, not C, so int is no longer the default type. main should return int.
Even in C, main must return an int value.
Did you notice the '.'?
sumankar wrote: However, the default to int rule is
not applicable here, as the OP uses void main(), which is not supposed to be
a standard return type for int.
This statement makes little sense. As I said before, C++ doesn't use int as the default type at all. This has nothing to do with main returning void instead of int.

TISARKER
Learning poster
Posts: 88
Joined: Tue Oct 12, 2004 6:45 pm
Location: Bangladesh
Contact:

10259(Hippity Hopscotch)

Post by TISARKER »

I used recursive + memorigetion.
But getting wrong answer.Can any one come to me for helping.
I need some sample input and output.
Mr. Arithmetic logic Unit

Raiyan Kamal
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
Location: Bangladesh
Contact:

Post by Raiyan Kamal »

Can explain a bit how you modeled the game instances for momoization ?

Post Reply

Return to “Volume 102 (10200-10299)”