Alireza's blog

By Alireza, 10 years ago, In English

Hey guys,

Recently I faced an interesting problem which took me about couple of days of thinking but I couldn't find out the polynomial time solution. So I decided to share it with you:

Let

0 ≤ si ≤ 3

0 ≤ ti ≤ 1

Now we want to Change the elements of S in a way that the following conditions are fulfilled:

2 ≤ i ≤ n

The only operations allowed are to increase or decrease si by 1 or let it to be unchanged. The goal is to find the minimum number of increasing or decreasing operations which satisfy the above equations for S and T. This task can be simply done using the Dynamic Programming in O(n) for any given S and T.

The main Problem is "what is the expected value of minimum operations for every given n?". The first Idea is to generate every Sequence of S and T for a given n, after computing the minimum operations for each pair, calculate the expected or average value. but this runs in O(n8n). Is there a polynomial time algorithm like DP for solving this task?

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

»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

It appears your problems stem from not thinking carefully about the original problem. Sure, it can be solved in O(n) using DP, but you need a simpler solution than that.

Try to prove that the following greedy algorithm works: whenever you are forced to change an element si and 1 ≤ si ≤ 2, change it so that si + 1 does not need to be changed.

From here, it should be easy to use DP to solve the full problem. I'm leaving the details as an exercise for the reader.