Problem 149
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.
See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
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
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.

 Posts: 27
 Joined: Mon Aug 22, 2011 11:20 am
Re: Problem 149
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
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
Re: Problem 149
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...
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...
Re: Problem 149
Can you check my results and tell which are wrong:
max in rows: 13414319
max in columns: 11593776
max in antidiagonals: 10284763
max in diagonals: 10785046
max in rows: 13414319
max in columns: 11593776
max in antidiagonals: 10284763
max in diagonals: 10785046
Re: Problem 149
Those numbers are all too low.
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.find the greatest sum of (any number of) adjacent entries
Re: Problem 149
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:
max in rows: 34
max in columns: 31
max in antidiagonals: 19
max in diagonals: 25
Can you check these?
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 7results:
max in rows: 34
max in columns: 31
max in antidiagonals: 19
max in diagonals: 25
Can you check these?
Re: Problem 149
Based on what I can see, those values look correct. Does your algorithm work for this row?
5 3 1 2 5
5 3 1 2 5
Re: Problem 149
No it wasn't, I had to modify my code to handle such cases correctly.. Thanks a lot.
 Oliver1978
 Posts: 166
 Joined: Sat Nov 22, 2014 9:13 pm
 Location: Erfurt, Germany
Re: Problem 149
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[k24] + s[k55] + 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?
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
Re: Problem 149
What would you say is the range a valid values for s[k]? Are all your values in this range?leghorn wrote:.. What could possibly go wrong with s[k] = ((s[k24] + s[k55] + 1000000) mod 1000000)  500000? ...
 Oliver1978
 Posts: 166
 Joined: Sat Nov 22, 2014 9:13 pm
 Location: Erfurt, Germany
Re: Problem 149
It's like this in Pascal.
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
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[k24] + s[k55] + 1000000) mod 1000000)  500000;
end.
49.157.5694.1125
 nicolas.patrois
 Posts: 118
 Joined: Fri Jul 26, 2013 4:54 pm
 Contact:
Re: Problem 149
Are your values of s[10] and s[100] correct?
 Oliver1978
 Posts: 166
 Joined: Sat Nov 22, 2014 9:13 pm
 Location: Erfurt, Germany
Re: Problem 149
Alas, no.
[edit]
I've also tested things in D:
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.
I just don't see what I might be missing...I am getting s[10] correctly, but for some weird reason s[100] is always 357419.
[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[k24] + s[k55] + 1_000_000) % 1_000_000;
s[k] = j  500_000;
}
return 0;
}
Weird stuff that even s[100]@Pascal and s[100]@D are different although the calculations are basically the same.
49.157.5694.1125
Re: Problem 149
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.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[k24] + s[k55] + 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?
_{Jaap's Puzzle Page}
 Oliver1978
 Posts: 166
 Joined: Sat Nov 22, 2014 9:13 pm
 Location: Erfurt, Germany
Re: Problem 149
Once again you saved my day, jaap!
I'd mistaken the compiler to internally use maximum precision, but I failed.
I'd mistaken the compiler to internally use maximum precision, but I failed.
49.157.5694.1125
 Oliver1978
 Posts: 166
 Joined: Sat Nov 22, 2014 9:13 pm
 Location: Erfurt, Germany
Re: Problem 149
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?
Speaking of rows, I get xxxx2415. Sound reasonable?cska wrote:Can you check my results and tell which are wrong:
max in rows: 13414319
max in columns: 11593776
max in antidiagonals: 10284763
max in diagonals: 10785046
49.157.5694.1125
 Oliver1978
 Posts: 166
 Joined: Sat Nov 22, 2014 9:13 pm
 Location: Erfurt, Germany
Problem 149
What's the point of adding a million, modulo one million?For $56 ≤ k ≤ 4000000$, $s_k = [s_{k−24} + s_{k−55} + 1000000] (modulo 1000000) − 500000.$
Re: Problem 149
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.
Oh and also: don't start a new topic for a problem if one exists already.