dcordb's blog

Help with this apparently dp problem (from POI)
By dcordb, 9 years ago, In English

Could you help me with this problem from the 13th POI:
http://main.edu.pl/en/user.phtml?op=showtask&task=ork&con=OI13

It seems some kind of DP, but I'm not able to get it. So far I have an idea: to keep the state of the columns and try to filling them adding a valid rectangle, but this is too slow. Could you help me? Thanks beforehand.

Tags dp, poi
  • Vote: I like it
  • +3
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it -24 Vote: I do not like it

Dynamically you can get the sum of elements in any strip needed (store cumulative column and row sums).

At each step, you have 4 possible strips that you can remove. Remove that strip whose sum is the maximum among those which have sum <= k. If more than one have the same highest sum, remove the longer strip. (This can be done in constant time.)

Number of steps cannot exceed m+n. So, this algo is O(m+n).

However, I am not completely sure this is correct. I haven't checked the equality case fully.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why do you say that in every step there are 4 strips that can be removed? In fact for completing a column you actually have lots of configurations.

    For example you can have something like this:

    1 2 3 4
5
7 8
9 1 2 3

    you can complete the figure like this (assuming that every new strip is valid):

    1 2 3 4
5 x x x
7 8 y y
9 1 2 3

    or

    1 2 3 4
5 x y z
7 8 y z
9 1 2 3

    and some more. There are obviously more than 4 ways to complete it.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 4   Vote: I like it -13 Vote: I do not like it

      I meant in each step.
      One step = removing one edge. (One of the 4 edges : top, bottom, right, left)
      In problem statement :
      "He can begin with ploughing a slice from any of the field's edges"
      "Once the nag starts to plough a slice, it won't stop until the slice is completely ploughed."
      "After the ploughing of every successive slice, the yet-unploughed field has a rectangular shape."
      This means that one step is one whole edge; is it not?

      I did not understand your counter example case. Is it not a rectangular region? What do you mean by x,y?

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        well, think about x, y and z as rectangular regions that you add each step. However, I still believe that this greedy won't work.

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Ok, If x, y and z were rectangular regions that you add in your step, my point is that wont be my first step. My first step is always an outer edge of the initial rectangle.

          → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    You don't need equality to break this greedy. Did you even try?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I don't understand you. What do you mean by equality? Could you please elaborate more? And could you answer me why ramprakash_k says that there are 4 strips to be removed?

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 3   Vote: I like it -11 Vote: I do not like it

      Equality case arises with my greedy approach and needs to be handled.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        Man, your greedy is clearly wrong, don't be so stubborn about your solution if you don't know if that's correct.

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          any idea for a solution??

          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            Now I'm preparing for my tomorrow's algebra exam and I don't know solution and remember that this was not an easy problem, so for now — no :P.

            → Reply