| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3657 |
| 3 | jiangly | 3638 |
| 4 | turmax | 3442 |
| 5 | tourist | 3380 |
| 6 | Um_nik | 3353 |
| 7 | strapple | 3350 |
| 8 | squareOf105 | 3346 |
| 9 | heuristica | 3322 |
| 10 | maroonrk | 3310 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | AmShZ | 144 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | adamant | 137 |
| 8 | BledDest | 135 |
| 9 | maroonrk | 133 |
| 10 | qwexd | 130 |
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.
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.
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:
you can complete the figure like this (assuming that every new strip is valid):
or
and some more. There are obviously more than 4 ways to complete 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?
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.
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.
You don't need equality to break this greedy. Did you even try?
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?
Equality case arises with my greedy approach and needs to be handled.
Man, your greedy is clearly wrong, don't be so stubborn about your solution if you don't know if that's correct.
any idea for a solution??
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.