Results 1 to 3 of 3
  1. #1
    trl
    trl is offline Member
    Join Date
    May 2011
    Posts
    6
    Rep Power
    0

    Default Divide and conquer

    Hello,

    I've been assigned a homework problem to code and I don't know where or how to begin. This is it:

    Anne and Brenda found some cookies scattered on the lattice points in the 2D coordinate system. They agreed to divide them in the following manner.
    First, Anne draws a vertical line (that is, a line with the equation x = c, for any real number c) somewhere in the plane. Then Brenda draws a horizontal line (y = d) somewhere in the plane. Now they have divided the plane in four quadrants. Anne gets all the cookies lying in the upper right and the lower left quadrant, and Brenda gets all the cookies lying in the upper left and the lower right quadrant. Cookies which lie on the vertical or the horizontal line are ignored. Anne’s goal is to maximize the number of cookies she gets, knowing that Brenda plays optimally (in order to maximize her number of cookies).

    There are up to 600 test cases with each case having up to 1000 cookies.

    So far all I've done is create the x and y arrays. I assume the lines will be the arrays divided in half. I'm supposed to do this through recursion but I don't understand how any of this will result in a maximum amount of cookies for Anne.

    Does anyone have a suggestion on what the algorithm would look like?

    Thanks for any help.

  2. #2
    joshdgreen's Avatar
    joshdgreen is offline Senior Member
    Join Date
    Oct 2010
    Location
    Colorado Springs, CO
    Posts
    212
    Rep Power
    5

    Default Re: Divide and conquer

    Does the assignment say anything about how you are supposed to determine how many cookies or where these cookies will be placed?
    Sincerely, Joshua Green
    Please REP if I help :)

  3. #3
    trl
    trl is offline Member
    Join Date
    May 2011
    Posts
    6
    Rep Power
    0

    Default Re: Divide and conquer

    Here's everything in the instructions:

    Anne and Brenda found some cookies scattered on the lattice points in the 2D coordinate system. They agreed to divide them in the following manner.
    First, Anne draws a vertical line (that is, a line with the equation x = c, for any real number c) somewhere in the plane. Then Brenda draws a horizontal line (y = d) somewhere in the plane. Now they have divided the plane in four quadrants.

    Anne gets all the cookies lying in the upper right and the lower left quadrant, and Brenda gets all the cookies lying in the upper left and the lower right quadrant. Cookies which lie on the vertical or the horizontal line are ignored.
    Anne’s goal is to maximize the number of cookies she gets, knowing that Brenda plays optimally (in order to maximize her number of cookies).

    Input
    In the first line of input there is an integer T (1 <= T <= 600), the number of test cases.

    Each test case starts with an integer N (1 <= N <= 1000), the number of cookies. In the next N lines there are coordinates (Xi, Yi) of the cookies, integers in the interval [1, 1000]. There can be multiple cookies at the same point.

    Output
    For each of the T cases, output in a separate line the maximal number of cookies Anne can surely get.

    Example

    Input:
    251 14 14 55 13 31 17 107 117 107 116 65 54 81 51 61 47 1

    Output:
    25

    Anne makes the first move (x = c) and Brenda counters (y = d). The professors explanation was basically a rehash of the above. It's a game. That's all I know.

    Thanks for the interest.

Similar Threads

  1. Divide and Conquer
    By whateverme in forum New To Java
    Replies: 1
    Last Post: 05-20-2011, 02:51 PM
  2. Divide bigdecimal again
    By ellhar in forum New To Java
    Replies: 3
    Last Post: 03-23-2011, 11:19 AM
  3. All possible way to divide a number?
    By bobocheez in forum New To Java
    Replies: 4
    Last Post: 09-24-2010, 03:24 AM
  4. Divide and Conquer@Array...im becoming crazy!
    By wyldstyle in forum New To Java
    Replies: 0
    Last Post: 08-23-2009, 10:20 PM
  5. How to divide code in classes?
    By hendrix79 in forum New To Java
    Replies: 2
    Last Post: 12-10-2008, 06:36 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •