Блог пользователя Borjianamin

Balance Array
Автор Borjianamin, история, 5 лет назад, По-английски

Hello.
I have a problem and I don't know how to solve it. if it is possible to give me hint for start or type of algorithm, etc, I will solve it. Thanks.
We have array $$$A$$$ with $$$n$$$ elements: $$$A[1], A[2], A[3], ..., A[n]$$$ ($$$1 \le A[i] \le 10$$$) ($$$1 \le n \le 1000$$$)
A $$$k$$$ is given beside elements of array. ($$$0 \le k \le 10n$$$)
We define $$$risk = 0$$$.
for each $$$i$$$, if $$$A[i - 1] > A[i]$$$, then $$$risk += A[i - 1] - A[i]$$$
for each $$$i$$$, if $$$A[i + 1] > A[i]$$$, then $$$risk += A[i + 1] - A[i]$$$
we want to $$$risk <= k$$$.
we can reduce one or increase one $$$A[i]$$$ at one step. so $$$risk$$$ will be calculated again. What is minimum steps need to achieve $$$risk <= k$$$?
Example:
in:
2 1
1 10
out:
8
in:
3 2
10 1 10
out:
8

Is it possible to help me? Thanks so much.

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Please, share a link to this problem, it seems interesting for me.

→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    it is a problem in our university and it's site is local. I can't share it with you. I'm sorry. I only try to explain it here. It would be grateful if you can help me.

    → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Not bad, thank you anyway for sharing the problem. I'm thinking in this problem, and waiting with you for a solution :)

      → Ответить
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I think you can solve this with dp. There are three parts to the state [last #][index][risk so far] and we store how many steps were taken. That should be 10^8 states with 10 choices at each state so possibly 10^9 total work. This is fairly tight, so you probably need to do bottom-up and have a generous time limit.

→ Ответить
»
5 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

First of all find the current risk of the array.

For each element of the array A find the next greatest element to left and right of it and store (right-left, (left, right)) in an array of pair(say P).(Take care of boundary conditions)

Then sort the array P based on the first element of the pair. initialize cost = 0 and risk = current_risk


while(risk > k):
    Take out the first element of P, let this be m.
    new_height = min(A[m.second.first], A[m.second.second])
    cost += (m.first-1)*new_height
    for(i=m.second.first+1; i<m.second.second; i++):
        risk -= (new_height-A[i])
        A[i] = new_height
→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    A variation of this works up to a point as a greedy solution, but breaks down later on.

    First, you need to consider both increasing and decreasing items, so you need to store also the next smallest items as well.

    Secondly, you need to worry about increasing items you'll only need to decrease later. Consider the array:

    1 1 1 10 10 1 10 10 1 1 1

    The greedy idea would increase the middle 1 first before decreasing it back down to 1 if 0 risk was required, which is non-optimal

    → Ответить