Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change
 
PerlMonks  

Re: Convex Hull Problem

by code-ninja (Scribe)
on Aug 27, 2013 at 03:49 UTC ( [id://1051053]=note: print w/replies, xml ) Need Help??


in reply to Convex Hull Problem

The problem statement is updated. I, unfortunately, cannot find the exact problem that we faced in the ACM ICPC but I'm sure that the problem aggregated to the update.

Replies are listed 'Best First'.
Re^2: Convex Hull Problem
by BrowserUk (Patriarch) on Aug 27, 2013 at 08:15 UTC
    The problem statement is updated.

    Hm. Still woolly. Does that mean you can run (service, maintain) two 'events' that overlap, provided that they do not start at the exact same time?

    Ie. You can 'do' b through e if you skip a?

    8 9 10 11 12 1 2 3 4 5 aaaaaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbbbbbbbbbb ccccccccccccccccccc ddddddddddddddddddd eeeeeeeeeeee

    With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.
      No.

      Events may overlap and in such a case, I'll have to select the one with the highest cost. Keep in mind that "cost" here refers to the income I'll get for each event.

      Consider my example.

      1 4 6 1 2 10 2 4 9 ...

      The first event transcends the start of the third event, right? But I'm selecting the second because it does not clash with any other and gives me maximum cost.

      OTOH, if the input would've been:

      1 5 2 1 2 5 2 4 9 ...

      The first even transcends the other two but I ignore it and select 2 4 9 because the event takes less time and is more profitable.

      I hope its clearer now. If not, let the problem statement rest and comment on the algorithm that I coded. I'll search for the exact problem statement and repost this question.

      My apologies, but this question bugs me periodically and for a while I get really intense about solving it and get carried away. :).

        The first event transcends the start of the third event, right?

        By "transcend" do you mean 'overlaps'? And why is that a question. Are you unsure?

        I hope its clearer now. If not, let the problem statement rest and comment on the algorithm that I coded.

        Sorry, but quite how you've selected a convex hull algorithm applied to a 2D reduction of 3D coordinate system as an appropriate approach to solving what seems to be a very simple scheduling problem, is quite beyond me.

        Reducing start & end times to a time period throws away all the inter-dependancy information between events, renders any results produced devoid of any time-based restrictions. And conflating a time period with money as a 2D coordinate is the proverbial mixing of apples and oranges. (Simpler to divide money by time to get a single number and sort.)

        Quite frankly, I don't see any application for convex hulls to the problem description; so I'll back-the-f-off and leave you to it.


        With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
        Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
        "Science is about questioning the status quo. Questioning authority".
        In the absence of evidence, opinion is indistinguishable from prejudice.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://1051053]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others learning in the Monastery: (3)
As of 2024-03-28 16:48 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found