Problem 149

[Fogmeister]

Woop!

I was doing something stupid in my algorithm!

Fixed it now after much debugging with the 4x4 grid and it ran and gave me the correct answer in 1.7 seconds

Very pleased

[mdean]

Well, this problem's going to be a pain to troubleshoot. I may have to comment out most of my program, look at just a corner (maybe 20x20), and add a ton of test code to handle just this corner (which hopefully doesn't introduce different errors...).

Update: All right, finally got back to it. So far, it seems my horizontal and vertical sums are working correctly. I'm testing on the upper left 10x10 square (seems if I print in landscape, 10 numbers is about all that will fit per row...). So either I fouled up on the diagonals or mucked up a limit somewhere...

[cska]

Can you check my results and tell which are wrong:
max in rows: 13414319
max in columns: 11593776
max in anti-diagonals: 10284763
max in diagonals: 10785046

[thundre]

Those numbers are all too low.

find the greatest sum of (any number of) adjacent entries

Are you limiting yourself to whole rows/columns/diagonals? Because many numbers in the table are negative, the maximum sum of adjacent numbers in a row is often greater than the sum of the entire row.

[cska]

I'm not. I also tested my algorithm with few smaller cases and manually checked results and they seemed to be correct, e.g., table:

11  16  -8  -9  10   7
  3   8   0  -9  -8  -6
 -4  -3  -2  -8 -10 -20
  8   6  10 -20   7   3
  1   2   7   8   6  10
 -4   2  -3   2  -8   7

results:
max in rows: 34
max in columns: 31
max in anti-diagonals: 19
max in diagonals: 25
Can you check these?

[mdean]

Based on what I can see, those values look correct. Does your algorithm work for this row?

5 -3 1 -2 5

[cska]

No it wasn't, I had to modify my code to handle such cases correctly.. Thanks a lot.

[Oliver1978]

I've been trying to squeeze the correct values out of that LFG. I am getting s[10] correctly, but for some weird reason s[100] is always -357419. I don't think there's an overflow. What could possibly go wrong with s[k] = ((s[k-24] + s[k-55] + 1000000) mod 1000000) - 500000?

Could someone be so kind and confirm or decline
s[17] = 134343,
s[55] = -1343089,
s[1000] = 355076,
s[123456] = -1414215?

[mpiotte]

.. What could possibly go wrong with s[k] = ((s[k-24] + s[k-55] + 1000000) mod 1000000) - 500000? ...

What would you say is the range a valid values for s[k]? Are all your values in this range?

[Oliver1978]

It's like this in Pascal.

Code: Select all

const MAX_LENGTH = 4000000;

var s: array of longint;
    k: longint;

begin
    setlength(s, MAX_LENGTH+1);
    { LFG: fill array }
    for k := 1 to 55 do
        s[k] := ((100003 - 200003*k + 300007*k*k*k) mod 1000000) - 500000;
    for k := 56 to MAX_LENGTH do
        s[k] := ((s[k-24] + s[k-55] + 1000000) mod 1000000) - 500000;
end.

I don't think I'm giving anything else away but the things which are already in the description. Though I can't seem to locate the error

[nicolas.patrois]

Are your values of s[10] and s[100] correct?

[Oliver1978]

Alas, no.

I am getting s[10] correctly, but for some weird reason s[100] is always -357419.

I just don't see what I might be missing...

[edit]

I've also tested things in D:

Code: Select all

import std.stdio, std.algorithm, std.container;

immutable uint MAX_LENGTH = 4_000_000;

int main()
{
    uint k;
    long j;

    /* fill array */
    long[] s = new long[MAX_LENGTH+1]; s[0] = 0;

    for (k = 1; k < 56; k++)
    {
        j = (100_003 - 200_003*k + 300_007*k*k*k) % 1_000_000;
        s[k] = j - 500_000;
    }

    for (k = 56; k <= MAX_LENGTH; k++)
    {
        j = (s[k-24] + s[k-55] + 1_000_000) % 1_000_000;
        s[k] = j - 500_000;
    }

    return 0;
}

That also gives s[10] correctly = -393027, but s[100] is incorrect with -422827.

Weird stuff that even s[100]@Pascal and s[100]@D are different although the calculations are basically the same.

[jaap]

I've been trying to squeeze the correct values out of that LFG. I am getting s[10] correctly, but for some weird reason s[100] is always -357419. I don't think there's an overflow. What could possibly go wrong with s[k] = ((s[k-24] + s[k-55] + 1000000) mod 1000000) - 500000?

Could someone be so kind and confirm or decline
s[17] = 134343,
s[55] = -1343089,
s[1000] = 355076,
s[123456] = -1414215?

There is an overflow. These are the numbers you get if you use signed 32bit integers everywhere, but for example 300007*k*k*k already overflows for k>24.

[Oliver1978]

Once again you saved my day, jaap!

I'd mistaken the compiler to internally use maximum precision, but I failed.

[Oliver1978]

Since I've read that in several publications... Do you, too, consider the maximum subsequence sum = 0 if all items in that sequence are < 0?

Can you check my results and tell which are wrong:
max in rows: 13414319
max in columns: 11593776
max in anti-diagonals: 10284763
max in diagonals: 10785046

Speaking of rows, I get xxxx2415. Sound reasonable?

[Oliver1978]

Never mind. I think I've worked it out...

[mscha]

For $56 ≤ k ≤ 4000000$, $s_k = [s_{k−24} + s_{k−55} + 1000000] (modulo 1000000) − 500000.$

What's the point of adding a million, modulo one million?

[hk]

The point is to avoid possible confusion when taking the modulus of a negative number.

Oh and also: don't start a new topic for a problem if one exists already.