Borjianamin's blog

Balance Array
By Borjianamin, history, 5 years ago, In English

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.

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    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.

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

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

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

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.

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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
→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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

    → Reply