You are not logged in. Please login at www.codechef.com to post your questions!

×

CHANGED ONCE AGAIN!!! HIGHWAYBYPASS@INOI Practice Server

On submission, It works fine for 90%+ testcases under each subtask but the final score is 20, since I got a WA some...PLEASE HELP!!!

include "iostream"

include "algorithm"

using namespace std;

int main()

{

int r, c;
cin >> r >> c;
int d;
cin >> d;
d++;
int x[r][c];
for (int i = 0; i<=r-1; i++)
for (int j = 0; j<=c-1; j++)
cin >> x[i][j];
long long int ans[r][c];
int temp1, temp2, temp3, temp4;
ans[0][0]=1;
for (int p = 0; p<=r-1; p++)
for (int q = 0; q<=c-1; q++)
{
    temp1 = (p>=d)?ans[p-d][q]%20011:0;
    temp2 = (q>=d)?ans[p][q-d]%20011:0;
    temp3 = (p>=1)?ans[p-1][q]%20011:0;
    temp4 = (q>=1)?ans[p][q-1]%20011:0;
    if (temp3+temp4-temp1-temp2>=0)
    ans[p][q]=temp3+temp4-temp1-temp2;
    else
    ans[p][q]=0; 
    if (x[p][q]==0)
    ans[p][q]=0;
    ans[0][0]=1;
}
cout << ans[r-1][c-1];
return 0;
}

I know of the O(n^3) & the O(n^4) solutions. Given the constraints, they should work... But my solutions is, in fact, O(n^2). The method is called GRAPH CUTTING. It is a very correct algorithm. There are probably slight mistakes in memory allocation, implementation of the algorithm etc. So, I need help in debugging the solution...So please try to...THANKS!!!

asked 05 Jan '15, 23:07

arpanb8's gravatar image

3★arpanb8
120210
accept rate: 13%

edited 20 Jan '15, 21:11

Yeah, Somebody Please answer...

(20 Jan '15, 21:12) arpanb83★

Hi,

No! Stop using next_permutation for each problem.

This is again a dynamic programming problem. Try thinking of the number of ways to reach a particular (x, y) with a certain number of consecutive moves (for both directions allowed), and how to formulate that in terms of smaller (x, y).

Cheers.

link

answered 05 Jan '15, 23:21

idraumr's gravatar image

0★idraumr
2463
accept rate: 45%

1

@arpanb8 My answer, unfortunately, still holds. Try to think a bit more! Think in four dimensions -- a particular (x, y), coming from left/right, with 0 to K consecutive moves. If you want the complete answer, say so. :)

(15 Jan '15, 23:28) idraumr0★

@arpanb8 , When you use

ans[p][q]=temp3+temp4-temp1-temp2;

The value stored in ans[p][q] may exceed the integer limits, and that is a possible reason for the 'wrong answer'. So, you must make sure that it is small, and still get the correct answer, and the best way to do that is :

ans[p][q] = (temp3 + temp4 - temp1 - temp2)%20011;

And this will work as, (a%c + b%c)%c = (a+b)%c, and ans[p][q] will always be inside the limits (0 - 20010). Also, ans being an int** should be sufficient now.

link

answered 08 Jan '15, 13:09

codelegend's gravatar image

3★codelegend
213
accept rate: 0%

but even after doingg dat im getin WA in some test cases...

(08 Jan '15, 16:56) arpanb83★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,825
×288
×29

question asked: 05 Jan '15, 23:07

question was seen: 7,701 times

last updated: 20 Jan '15, 21:12