i want anyone to explain this problem to me
https://www.spoj.pl/problems/INTEGMAX/
and hints in how to solve this by math![]()
i want anyone to explain this problem to me
https://www.spoj.pl/problems/INTEGMAX/
and hints in how to solve this by math![]()
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?
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).it is irregular shape
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.
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?
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.