10259 - Hippity Hopscotch

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

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]

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]

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.

but my original program can't get accepted now.

It's all right. (because the multiple input)

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

if input like

2 100
10 0
0 0

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

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

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.

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

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

[sumankar]

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]

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]

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

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]

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

[Raiyan Kamal]

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