You are not logged in. Please login at www.codechef.com to post your questions!

×

Problem 1 - INOI 2015

Can someone go through an efficient way of solving the first problem in today's INOI? I just calculated the maximum sum when i is less than j and the max. sum when i is greater than j and compared both. But it was more or less a brute force algorithm, going through all the combinations.

asked 31 Jan '15, 17:10

batcrazt's gravatar image

2★batcrazt
2812
accept rate: 20%

edited 31 Jan '15, 17:10


I break up this problem into three cases: i = j, i < j, i > j. Note that I use 1-indexed arrays.

i = j:

The max for this case is just the max of all ai, i = 1 to n. This can be found in O(n);

i < j:

For each j, we find the value of i such that the sum from i to j is maximum.

sum(i, j) = a[i] + b[i + 1] + ... + b[j - 1] + a[j]

= (b[1] + b[2] + ... + b[j - 1] + a[j]) - (b[1] + b[2] + ... b[i] - a[i])

Clearly, the first term depends only on j and the second term depends only on i. Since the second term is being subtracted, to find the maximum sum, we need to find the minimum value of the second term.

Thus the maximum sum ending at j corresponds to the minimum value of the second term for all i < j

The following snippet of code in pseudoc++ finds the maximum of all segments with i < j:

ans = -inf;
minsec = cursec = b[1] - a[1];
curfir = a[1];
for(int j = 2; j <= n; j++)
{
   curfir = curfir - a[j - 1] + b[j - 1] + a[j];
   ans = max(ans, curfir - minsec);
   cursec = cursec + a[j - 1] + b[j] - a[j];
}

j < i

sum(i, j) = (b[1] + b[2] + ... + b[j - 1] + a[j]) + (a[i] + b[i + 1] + ... + b[n - 1] + b[n])

Once again, the first term depends only on j and the second term depends only on i.

let frontbest[k] = the maximum value of the first term for all i <= k

and similarly let reversebest[k] = the maximum value of the second term for j >= k.

We can compute both of the above arrays in O(n) each.

The answer for this case can be found as

for(int i = 1; i < n; i++)
{
   ans = max(ans, frontbest[i] + reversebest[i + 1]);
}

Finally, the answer for the problem is the maximum of the answer for each of the three sub cases.

Edit: Does anybody have an easier solution to this problem? Mine seems quite complex in hindsight.

link

answered 31 Jan '15, 17:44

superty's gravatar image

3★superty
36417
accept rate: 31%

edited 31 Jan '15, 17:55

1

Hi; my i < j solution was basically: you keep tracking of the maximum score you can have if you picked b[k] in down[k]. For a particular k, the maximum sum possible is a[k] + down[k - 1]. That seems fine to me, and ran perfectly well for subtask 3.

The only stupid mistake I did was to not tackle i > j separately, which would've solved all subtasks. Your solution seems the most efficient solution for i > j, to me.

The other thing I tried for i > j and i < j together was two passes of the first algorithm. That seemed fairly neat, but ended up with complications (read: bugs).

(31 Jan '15, 18:44) idraumr0★

down[k] = max(down[k - 1] + b[k], b[k]) right? This seems wrong to me somehow.

Could you elaborate on extending this for i > j?

(31 Jan '15, 19:09) superty3★

That does seem wrong. down[k] = max(down[k - 1], a[k - 1]) + b[k] is what I did. Then, answer = max(answer, a[k] + down[k - 1]).

I basically tried the 'copy same array twice' trick, and then on the second iteration you're only looking for contiguous subarrays with length <= N.

(31 Jan '15, 19:17) idraumr0★

Ah yes, of course. Not sure why I was saying the other thing.

Can you elaborate further? Sorry, I have no clue what you're talking about.

Edit: Just got an idea: you can find the segment with (i < j) having minimum value of -a[i] + b[i] + b[i + 1] + ... + b[j - 1] + b[j] - a[j] and subtract this from the sum of all b[i]. Maybe that's what you meant?

(31 Jan '15, 19:34) superty3★
1

Hi; convinced by the i < j solution? No, although that struck me after the exam.

http://stackoverflow.com/questions/11610443/n-numbers-are-arranged-in-a-circle-we-need-to-find-the-maximum-sum-of-consecuti for quick description of my approach. If still not clear, I'll do a write-up in another answer.

(31 Jan '15, 19:44) idraumr0★
1

Ah, cool idea. Yeah, I get it now.

(31 Jan '15, 20:01) superty3★

Right, should clarify---I forgot the case where [i, i + 1] can form a maximum sequence. Only needed a answer = max(answer, a[k] + a[k - 1]) along with what I said earlier.

(16 Feb '15, 16:25) idraumr0★

A more elegant way is down[k] = max(down[k - 1] + b[k], a[k]);

(17 Feb '15, 17:29) superty3★
showing 5 of 8 show all
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×69

question asked: 31 Jan '15, 17:10

question was seen: 14,722 times

last updated: 17 Feb '15, 17:29