i want anyone to explain this problem to me

https://www.spoj.pl/problems/INTEGMAX/

and hints in how to solve this by math(Itwasntme)

Printable View

- Aug 23rd 2010, 07:02 AMmido22help in Integral Maximization
i want anyone to explain this problem to me

https://www.spoj.pl/problems/INTEGMAX/

and hints in how to solve this by math(Itwasntme) - Aug 23rd 2010, 07:23 AMAckbeet
What ideas have you had so far?

- Aug 23rd 2010, 07:26 AMmido22
- Aug 23rd 2010, 07:38 AMAckbeet
Well, you should know by now that this forum is not about simply providing answers, since that won't help you. Instead, we'll nudge you towards the answer, in hopes that you can solve it yourself. That way, you'll own the answer, and you'll really understand what's going on (see my signature).

I will happily re-state the problem and see if that gives you any ideas.

Given a set of x-coordinates $\displaystyle \{x_{1},\x_{2},\dots,x_{N}\}$ and a set of y-coordinates $\displaystyle \{y_{1},y_{2},\dots,y_{N}\},$ find a pairing such that the area under the piecewise linear function defined by the pairing is maximized.

Example:

Suppose the x-coordinates are $\displaystyle \{1,2,3\},$ and the y-coordinates are $\displaystyle \{4,5,6\}.$ One pairing would be $\displaystyle \{\{1,4\},\{2,5\},\{3,6\}\}.$ What would be the area under the piecewise linear functions defined by these points?

We're supposed to maximize the area under the piecewise linear functions by changing up the pairing. Another pairing in our example would be $\displaystyle \{\{1,5\},\{2,4\},\{3,6\}\}.$ You could calculate the area under these piecewise linear functions, and it might be different from the previous example.

So what ideas do you have now? - Aug 23rd 2010, 07:44 AMmido22
ok u meant that i must check all pairs together but how can i calculate the area this is my question

note : i knew that this forums help me only and didn't give the answer :D - Aug 23rd 2010, 07:47 AMAckbeetQuote:

how can i calculate the area this is my question

- Aug 23rd 2010, 07:51 AMmido22
it is irregular shape so i can't determine its area

- Aug 23rd 2010, 07:54 AMAckbeetQuote:

it is irregular shape

- Aug 23rd 2010, 07:59 AMmido22
- Aug 23rd 2010, 08:03 AMAckbeet
You could, but I don't think you'd gain anything other than complexity and possibility for errors. The shape I've described is a known shape with a known area. You don't even need to use calculus to find its area, although, of course, you can if you want to.

Put your thinking cap on! You can do this. What shape is it? I want you to figure out what shape it is. That's really the crux of this problem. - Aug 23rd 2010, 08:06 AMmido22
- Aug 23rd 2010, 08:14 AMAckbeet
Ok. Try this: one of the two y-values will be smaller than the other one, in general. Divide up this figure into two pieces: everything below the lower y-value, and everything above that value that is still below the straight line. What two figures do you have now?

- Aug 23rd 2010, 08:18 AMmido22
A polygon is a closed figure made by joining line segments, where each line segment intersects exactly two others.

Examples:

The following are examples of polygons:

http://www.mathleague.com/help/geometry/IMG00049.GIF

so it is a ploygon

the answer of your question :i think it is a quadrilateral - Aug 23rd 2010, 08:20 AMAckbeet
You're correct. However, the answer is not specific enough. You're dealing with a particular kind of quadrilateral. Which one?

Incidentally, my post # 12 is an alternate route to getting the answer. It's a bit more complicated in some ways, but requires less knowledge, if that makes any sense. This approach is better because it's more scalable. - Aug 23rd 2010, 08:22 AMmido22