10285 - Longest Run on a Snowboard

[ttwu]

I don't know why I get Wrong Answer with Q10285..
Can someone tell me where I am wrong, or is there more test cases? Thx!

[cpp]
#include<stdio.h>
int a[101][101],R,C,max,len;

void dig(int i,int j)
{
len++;
if (len>max) max=len;

if (i-1>=0 && a[i-1][j]<a[j]) { dig (i-1,j); len--; } // Up
if (i+1<R && a[i+1][j]<a[j]) { dig (i+1,j); len--; } // Down
if (j-1>=0 && a[j-1]<a[j]) { dig (i,j-1); len--; } // Left
if (j+1<C && a[j+1]<a[j]) { dig (i,j+1); len--; } // Right

}

void main()
{
char name[100];
int i,j,N,k;

scanf("%d",&N);
for (k=1;k<=N;k++)
{
scanf("%s %d %d",&name,&R,&C);
for (i=0;i<R;i++) for (j=0;j<C;j++) scanf("%d",&a[j]);

len=0;
for (i=0;i<R;i++) for (j=0;j<C;j++)
{
dig (i,j);
len--;
}
printf("%s: %d\n",name,max);
}
}
[/cpp]

[Ivan Silva]

Try to use something like:

void dig(int len,int i,int j)
{

....

if (i-1>=0 && a[i-1][j]<a[j]) dig (len+1,i-1,j); // Up

.....
}

Good luck
-Ivan

[ttwu]

I changed my code like this and got accepted..but I really have no idea what the difference is.
Can somebody explain why? Thanks!
[cpp]
#include<stdio.h>
int a[101][101],R,C,max1,max2;

void dig(int i,int j,int len)
{
if (len>max1) max1=len;

if (i-1>=0 && a[i-1][j]<a[j]) dig (i-1,j,len+1); // Up
if (i+1<R && a[i+1][j]<a[j]) dig (i+1,j,len+1); // Down
if (j-1>=0 && a[j-1]<a[j]) dig (i,j-1,len+1); // Left
if (j+1<C && a[j+1]<a[j]) dig (i,j+1,len+1); // Right

}

void main()
{
char name[100];
int i,j,N,k;

scanf("%d",&N);
for (k=1;k<=N;k++)
{
max1=max2=0;
scanf("%s %d %d",&name,&R,&C);
for (i=0;i<R;i++) for (j=0;j<C;j++) scanf("%d",&a[j]);

for (i=0;i<R;i++) for (j=0;j<C;j++)
{
dig (i,j,1);
if (max1>max2) max2=max1;
}
printf("%s: %d\n",name,max2);
}
}
[/cpp]

[Algoritmo]

At least for this program, a pseudocode is very helpfull. I was making a pseudo-code to post here because it's easyer for others to understand. Suddenly I perceived my mistake, by reading what I wrote.

I was solving it by DP in this manner:

All cells start with length 0. Cells out of area have -1 of tallness, weight 0.
LongestRun = 0
For weight W = 0 to 100 do:
--For any cell C (inside the area) with height W do:
----For each adjacent cell C2 do:
------If LengthOf(C2) + 1 > LengthOf(C), then do:
--------LengthOf(C) = LengthOf(C2) + 1
------end if
----end do
----If LengthOf(C) > LongestRun then LongestRun = LengthOf(C)
--end do
end do

I assumed the longest run would always end in an border cell of that area, so one more unit of length would be counted as a dropping to outside the area. But not I realised the longest run can finish inside the area. My new pseudo code is:

All cells start with length 1.
LongestRun = 0
For weight W = 0 to 100 do:
--For any cell C (inside the area) with height W do:
----For each adjacent cell C2 (inside the area) do:
------If LengthOf(C2) + 1 > LengthOf(C), then do:
--------LengthOf(C) = LengthOf(C2) + 1
------end if
----end do
----If LengthOf(C) > LongestRun then LongestRun = LengthOf(C)
--end do
end do

And here are some critical inputs I made:

4
me 0 0
me2 1 1
0
you 3 3
0 0 0
0 0 0
0 0 1
center 3 3
1 1 1
1 0 1
1 1 1

Sample output for it:

me: 0
me2: 1
you: 2
center: 2

But I still did NOT get accepted
Any problems with my critical input answers or with my assumptions?

By the way, ttwu.. I also can't see why your second code worked but your first one didn't. Both seem to backtrack well the Len value, but the 2nd solution is cleaner.

[vahid sanei]

i got accepted with backtrack

How can i memoize that ????

memo[j][?]

thanks in advance

[Shafaet_du]

I used DP to solve it. here are some I/O from my code:

Code: Select all

4
Bangladesh 1 1
0
Dhaka 2 2
1 1
1 1
CTG 3 3
1 2 3
0 0 3
4 5 1
SYL 5 5
3 56 67 34 67
45 234 56 78 34
0 78 45 0 3
23 56 7 3 12
4 56 34 67 8

output:

Code: Select all

Bangladesh: 1
Dhaka: 2
CTG: 4
SYL: 6

[plamplam]

backtracking...DP....lol? seriously guys....r and c are not bigger than 100 and there are not more than 15 test cases. Just run dfs with a counter from each height. Got accepted in 40 ms

[laituanksa245]

Help me please.
I have tried all the test cases posted in this forum, but i still got WA

Code: Select all

Removed after AC  :D 

[brianfry713]

Input:

Code: Select all

15
M1 3 4
97 3 66 42
29 41 80 10
66 4 67 99
M2 10 10
93 80 11 59 95 54 92 20 2 50
3 55 44 26 71 23 10 33 27 76
76 22 83 21 33 48 92 66 12 36
55 4 15 66 29 76 86 87 63 55
36 32 76 47 58 47 70 68 80 63
44 21 52 26 8 85 41 100 16 19
2 71 91 17 2 86 60 88 73 22
8 75 54 85 21 78 98 58 11 77
87 21 65 38 14 39 89 55 5 4
40 7 75 30 91 77 16 50 31 55
M3 3 1
96
58
90
M4 1 5
87 41 13 30 27
M5 3 2
66 48
100 54
69 4
M6 3 4
11 100 5 2
43 88 18 74
8 23 79 4
M7 10 7
88 83 55 28 96 85 21
29 45 87 44 11 7 12
15 32 21 27 31 94 96
74 47 80 13 56 2 93
60 50 27 47 32 82 75
94 33 62 89 44 49 32
55 22 45 37 54 32 30
51 25 25 92 39 71 4
95 74 97 54 23 23 67
21 72 41 14 71 69 2
M8 4 10
35 2 5 46 39 25 78 69 43 70
60 34 8 97 38 2 70 1 22 59
91 89 46 62 96 26 99 64 29 46
48 30 14 19 42 53 45 19 88 54
M9 8 1
88
63
9
25
31
46
26
19
M10 4 8
7 17 45 69 43 10 33 38
22 47 34 36 66 76 55 77
96 42 30 16 21 17 80 97
9 77 42 1 97 13 18 3
M11 10 9
39 39 6 72 78 28 85 11 64
16 54 18 94 15 26 90 31 13
74 10 9 49 54 52 50 50 31
69 19 27 65 58 66 71 96 43
99 80 21 28 97 75 46 56 90
38 11 20 51 85 98 26 33 51
78 84 0 75 18 86 1 49 44
68 19 39 77 17 19 98 45 82
72 57 37 27 61 48 14 11 100
11 37 32 62 82 82 28 56 66
M12 4 10
14 57 92 100 63 68 16 82 32 27
63 70 50 66 98 10 13 11 88 12
89 92 11 50 39 59 44 61 25 23
85 5 47 76 5 9 10 88 57 42
M13 10 4
78 31 51 75
8 30 52 62
9 40 53 20
56 92 79 100
53 70 90 37
42 36 80 47
45 56 34 68
98 82 19 75
80 70 16 88
66 68 49 75
M14 5 4
61 30 60 6
97 12 76 86
16 17 21 62
30 32 17 31
66 14 12 85
M15 3 8
20 37 45 86 72 61 27 46
29 88 76 55 94 72 34 36
23 50 19 44 11 50 42 95

AC output:

Code: Select all

M1: 4
M2: 8
M3: 2
M4: 3
M5: 3
M6: 5
M7: 6
M8: 6
M9: 4
M10: 7
M11: 8
M12: 6
M13: 8
M14: 5
M15: 6

[laituanksa245]

Thank you very much.

[hpjhc]

I used DP to solve it. here are some I/O from my code:

Code: Select all

4
Bangladesh 1 1
0
Dhaka 2 2
1 1
1 1
CTG 3 3
1 2 3
0 0 3
4 5 1
SYL 5 5
3 56 67 34 67
45 234 56 78 34
0 78 45 0 3
23 56 7 3 12
4 56 34 67 8

output:

Code: Select all

Bangladesh: 1
Dhaka: 2
CTG: 4
SYL: 6

Your output is wrong, the answer is
Bangladesh: 1
Dhaka: 1
CTG: 4
SYL: 6
in uva toolkit