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

×

GSS5 SPOJ EXPLANATION

GSS5 In this sum I can't understand why can't we take the minimum of x1,y1,x2,y2 as the lower limit and maximum of those as the higher limit and then find the bestsum of (lower,higher) Can anyone explain this??

asked 24 Nov '14, 11:59

abeyaar's gravatar image

1★abeyaar
33422140
accept rate: 30%

converted to question 24 Nov '14, 12:00


If you take the minimum and maximum of the given range to perform a query, it is then possible that the maximum sum of a segment you calculate is not in the range. Let's consider an example.

x1 = 1, x2 = 3, y1 = 3, y2 = 5;

According to your technique, the query performed on i = 1 to j = 5 should yield the correct answer. But as we can see that in a query from 1 to 5 the result can be such that the maximum sum is obtained in the range [4, 5]. But since x1 <= i <= y1 and x2 <= j <= y2, we can see that 4 is not in the range [x1, y1] = [1, 3]. Hence you will get an incorrect result.

Here is the hint to the solution. Consider two cases, in which (x1, y1) and (x2, y2) are overlapping and the other where they are disjoint. Can you come up with a way to combine answers on different ranges to give the optimal result?

Hint: Solve GSS1.

link

answered 05 Dec '14, 18:41

vastolorde95's gravatar image

5★vastolorde95 ♦
324
accept rate: 11%

edited 05 Dec '14, 18:45

(05 Dec '14, 21:11) abeyaar1★
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:

×1,136

question asked: 24 Nov '14, 11:59

question was seen: 3,793 times

last updated: 05 Dec '14, 21:11