help in Integral Maximization

Show 40 post(s) from this thread on one page
Page 1 of 4 1234 Last
• Aug 23rd 2010, 07:02 AM
mido22
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(Itwasntme)
• Aug 23rd 2010, 07:23 AM
Ackbeet
What ideas have you had so far?
• Aug 23rd 2010, 07:26 AM
mido22
Quote:

Originally Posted by Ackbeet
What ideas have you had so far?

i didin't understand the problem :D so i write i want explaination for it
• Aug 23rd 2010, 07:38 AM
Ackbeet
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 AM
mido22
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 AM
Ackbeet
Quote:

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?
• Aug 23rd 2010, 07:51 AM
mido22
it is irregular shape so i can't determine its area
• Aug 23rd 2010, 07:54 AM
Ackbeet
Quote:

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).
• Aug 23rd 2010, 07:59 AM
mido22
Quote:

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
• Aug 23rd 2010, 08:03 AM
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.
• Aug 23rd 2010, 08:06 AM
mido22
Quote:

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 :D
all i know
(square , rectangle , triangle , circle , sphere , cube , cuboid , pyramid , tetrahedron )
• Aug 23rd 2010, 08:14 AM
Ackbeet
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 AM
mido22
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

• Aug 23rd 2010, 08:20 AM
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.
• Aug 23rd 2010, 08:22 AM
mido22
Quote:

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 )
Show 40 post(s) from this thread on one page
Page 1 of 4 1234 Last