Problem 149

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.

This forum is NOT meant to discuss solution methods for a problem.

In particular don't post any code fragments or results.

Don't start begging others to give partial answers to problems

Don't ask for hints how to solve a problem

Don't start a new topic for a problem if there already exists one


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
Fogmeister
Posts: 27
Joined: Mon Aug 22, 2011 11:20 am

Re: Problem 149

Post by 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 :D

Very pleased :D
Image
mdean
Posts: 169
Joined: Tue Aug 02, 2011 2:05 am

Re: Problem 149

Post by 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...
Image
cska
Posts: 5
Joined: Thu Apr 19, 2012 5:40 pm

Re: Problem 149

Post by 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
Posts: 356
Joined: Sun Mar 27, 2011 10:01 am

Re: Problem 149

Post by 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.
Image
cska
Posts: 5
Joined: Thu Apr 19, 2012 5:40 pm

Re: Problem 149

Post by 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
Posts: 169
Joined: Tue Aug 02, 2011 2:05 am

Re: Problem 149

Post by mdean »

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

5 -3 1 -2 5
Image
cska
Posts: 5
Joined: Thu Apr 19, 2012 5:40 pm

Re: Problem 149

Post by cska »

No it wasn't, I had to modify my code to handle such cases correctly.. Thanks a lot.
User avatar
Oliver1978
Posts: 166
Joined: Sat Nov 22, 2014 9:13 pm
Location: Erfurt, Germany

Re: Problem 149

Post by 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?
49.157.5694.1125
User avatar
mpiotte
Administrator
Posts: 1914
Joined: Tue May 08, 2012 5:40 pm
Location: Montréal, Canada

Re: Problem 149

Post by mpiotte »

leghorn wrote:.. 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?
Image
User avatar
Oliver1978
Posts: 166
Joined: Sat Nov 22, 2014 9:13 pm
Location: Erfurt, Germany

Re: Problem 149

Post by 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 :?
49.157.5694.1125
User avatar
nicolas.patrois
Posts: 118
Joined: Fri Jul 26, 2013 4:54 pm
Contact:

Re: Problem 149

Post by nicolas.patrois »

Are your values of s[10] and s[100] correct?
Image
User avatar
Oliver1978
Posts: 166
Joined: Sat Nov 22, 2014 9:13 pm
Location: Erfurt, Germany

Re: Problem 149

Post by 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.
49.157.5694.1125
User avatar
jaap
Posts: 554
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: Problem 149

Post by jaap »

leghorn wrote: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.
User avatar
Oliver1978
Posts: 166
Joined: Sat Nov 22, 2014 9:13 pm
Location: Erfurt, Germany

Re: Problem 149

Post by Oliver1978 »

Once again you saved my day, jaap!

I'd mistaken the compiler to internally use maximum precision, but I failed.
49.157.5694.1125
User avatar
Oliver1978
Posts: 166
Joined: Sat Nov 22, 2014 9:13 pm
Location: Erfurt, Germany

Re: Problem 149

Post by 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?
cska wrote: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?
49.157.5694.1125
User avatar
Oliver1978
Posts: 166
Joined: Sat Nov 22, 2014 9:13 pm
Location: Erfurt, Germany

Re: Problem 149

Post by Oliver1978 »

Never mind. I think I've worked it out...
49.157.5694.1125
User avatar
mscha
Posts: 6
Joined: Sat Jan 21, 2017 9:55 pm

Problem 149

Post by 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?
Image
User avatar
hk
Administrator
Posts: 11040
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

Re: Problem 149

Post by 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.
Image
Post Reply