Problem 663

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.
Post Reply
michelebastione
Posts: 3
Joined: Tue Apr 02, 2019 4:51 pm

Problem 663

Post by michelebastione »

Hello everyone!
I'm quite new to the site, and I really need a clarification about this one. It's written:

"After each step i, define Mn(i) to be max{∑j=pqAn[j]:0≤p≤q<n}, the maximal sum of any subsequence of An."

I'm not sure I fully understand what is meant by subsequence, as the example is a bit misleading. Is it simply an ordered subset of An with the order induced by An (like the mathematical definition of subsequence would suggest) or does it also have the property to contain all numbers between p and q (like the sigma notation would indicate) ? I've been trying to figure it out by myself, but I had no luck so far, so if you please could help me here I'd be very grateful!

User avatar
hk
Administrator
Posts: 10871
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

Re: Problem 663

Post by hk »

From Wikipedia:
"In mathematics, a subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements'
See: https://en.wikipedia.org/wiki/Subsequence
Image

michelebastione
Posts: 3
Joined: Tue Apr 02, 2019 4:51 pm

Re: Problem 663

Post by michelebastione »

Thanks a lot! I knew the definition, I just wanted to make sure.

User avatar
Animus
Administrator
Posts: 1903
Joined: Sat Aug 16, 2014 1:23 pm

Re: Problem 663

Post by Animus »

I am sorry, michelebastione, in this problem we we did NOT use the word subsequence according to the wikipedia's definition, but the way it's described in the definition of $M_n(i)$ (as this would also make the problem quite trivial, since you'd only have to add all positive values of the sequence. Unfortuneately the example also doesn't clarfify this by itself).
So according to our definition the maximal subsequence of $1,-2,3,4,-5$ is $3+4=7$ and not $1+3+4=8$

We could make this clearer by adding something like "subsequences of $A_n$, that are made up of consecutive elements."
I'll discuss this with the dev team shortly.

User avatar
Animus
Administrator
Posts: 1903
Joined: Sat Aug 16, 2014 1:23 pm

Re: Problem 663

Post by Animus »

We've edited the problem text (inserted "contiguous"). Thanks, michelebastione, for mentioning this issue.

michelebastione
Posts: 3
Joined: Tue Apr 02, 2019 4:51 pm

Re: Problem 663

Post by michelebastione »

Thank you very much!
I must admit I was very puzzled, I was having quite a hard time trying to figure out what I was missing. Now it's much more cleare to me, and I'm going to get to work asap to see if everything checks out!

vamsikal3
Posts: 113
Joined: Sat Oct 01, 2016 9:25 am

Re: Problem 663

Post by vamsikal3 »

Just wanted to check, say the array $A_n = [8, -1, 2, 3, -5, 6, -100, 2, 4, 6]$, so would the maximum sub-array sum be $8 + (- 1) + 2 + 3 + (- 5) + 6 = 13$. So if negative values can be "absorbed", we should "absorb" them?
my friend key --> 990813_OZPwQtCjkD6KlvxirOoTSZxccMFsuw1L
Image

DJohn
Posts: 63
Joined: Sat Oct 11, 2008 12:24 pm

Re: Problem 663

Post by DJohn »

vamsikal3 wrote:
Fri Apr 05, 2019 12:35 pm
Just wanted to check, say the array $A_n = [8, -1, 2, 3, -5, 6, -100, 2, 4, 6]$, so would the maximum sub-array sum be $8 + (- 1) + 2 + 3 + (- 5) + 6 = 13$. So if negative values can be "absorbed", we should "absorb" them?
That's what the definition of M implies, and you won't get the right value for S(107, 1000) without it. So, yes. A maximal sum can include negatives (as long as the positives on the other side are worth it).

MaksymTatarenko
Posts: 2
Joined: Sat Apr 13, 2019 11:40 am

Re: Problem 663

Post by MaksymTatarenko »

My python code find S(5,100)=2416, S(14,100)=3881 and S(107,1000)=1618572.
But when I started to find S(10000003,10000000) it's say than I need 1 year to calculate results. :-(

1 M= XXX Iteration time: 5.44500
2 M= XXX Iteration time: 5.89250
3 M= XXX Iteration time: 5.29500
So 10000000 iterations will be calculated near 1 years.
So we need some tricks to calculate M but not just stupid "maximal sum of any contiguous subarray"?
Image

vamsikal3
Posts: 113
Joined: Sat Oct 01, 2016 9:25 am

Re: Problem 663

Post by vamsikal3 »

I think so, that is exactly why I have not been able to solve this problem. I was unable to come up with a "dynamic" version of the "maximum sub-array sum" algorithm. : :-|
my friend key --> 990813_OZPwQtCjkD6KlvxirOoTSZxccMFsuw1L
Image

MaksymTatarenko
Posts: 2
Joined: Sat Apr 13, 2019 11:40 am

Re: Problem 663

Post by MaksymTatarenko »

vamsikal3 wrote:
Sat Apr 13, 2019 1:10 pm
I think so, that is exactly why I have not been able to solve this problem. I was unable to come up with a "dynamic" version of the "maximum sub-array sum" algorithm. : :-|
In my case I use "dynamic" version of the "maximum sub-array sum" algorithm but in Python.
For array size = 10000003 it take 5.4 sec to find "maximum sub-array sum" M for every steps .
So I think we need to find some algorithm to skip duplicate results, i.e. when for example M32=M33=M34=M35=M36.
Image

User avatar
hk
Administrator
Posts: 10871
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

Re: Problem 663

Post by hk »

This board is not meant to discuss solutions.
As made clear from the onset it is meant to resolve problems with understanding what is asked.
As far as I can see both of you understand perfectly what is asked.
Attemps to discuss things further will be deleted.
Image

Post Reply