"Convolution" sum of 2 increasing sequences.
source link: http://codeforces.com/blog/entry/97875
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
I was working on a different problem and I would need to solve this as a subproblem in faster than O(n2)O(n2) to solve the actual problem.
Statement
You are given 2 arrays a0,a1,...,an−1a0,a1,...,an−1 and b0,b1,...,bn−1b0,b1,...,bn−1, both increasing i.e. ∀0≤i<n−1∀0≤i<n−1 ai≤ai+1ai≤ai+1 and bi≤bi+1bi≤bi+1 and also ∀iai≥0,bi≥0∀iai≥0,bi≥0. You task is to find array cc such that:
ci=max0≤j<2∗naj+bi−j.ci=max0≤j<2∗naj+bi−j.
For example, for a=[2,3,5,8]a=[2,3,5,8] and b=[1,4,7,8]b=[1,4,7,8], the result would be c=[3,6,9,10,12,15,16]c=[3,6,9,10,12,15,16].
So the simple code to solve this is:
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
c[i + j] = max(c[i + j], a[i] + b[j]);
}
}Tried approach
I had a few ideas of attacking this by drawing out the full matrix of sums of aa x bb and trying to notice that the cici's will form a path within this matrix from the top-left to lower-right corner, but I wasn't able to complete this. Is there a better solution than the proposed brute-force solution?
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK