Alireza's blog

By Alireza, 8 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:


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?

Full text and comments »

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