Thread: help 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

What ideas have you had so far?

Originally Posted by Ackbeet

What ideas have you had so far?

i didin't understand the problem so i write i want explaination for it

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?

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

how can i calculate the area this is my question

Well, what are the shapes with which you're dealing here? What's the area under a small straight-line segment look like?

it is irregular shape so i can't determine its area

it is irregular shape

I'm not sure I agree there. Visualize a shape with a horizontal base (the x-axis), vertical sides (the beginning point and end point of the interval), and a straight line connecting two points on the vertical lines. What shape is that? (Hint: turn your face 90 degrees and look at it sideways).

Originally Posted by Ackbeet

I'm not sure I agree there. Visualize a shape with a horizontal base (the x-axis), vertical sides (the beginning point and end point of the interval), and a straight line connecting two points on the vertical lines. What shape is that? (Hint: turn your face 90 degrees and look at it sideways).

can i cut it into many shapes and calculate each area

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.

Originally Posted by Ackbeet

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.

i think i don't know this shape i 'm a young boy so may i didn't take it in school
u can tell my a new thing about this figure
all i know
(square , rectangle , triangle , circle , sphere , cube , cuboid , pyramid , tetrahedron )

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?

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:


so it is a ploygon

the answer of your question :i think it is a quadrilateral

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.

Originally Posted by Ackbeet

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.

i don't know quadrilaterals except (square , rectangle , parallelogram , rhombus )