Topcoder- Bad Neighbour dp based problem

general
,
1

I was solving THIS PROBLEM on top coder, it seemed very easy initially but when I solved it I realized it is not. Help me solving this problem.

1 Like
2

We first solve the problem in a linear way and later extend it to take care of the circle case.

Define the state T(i) = maximum earnings from 0 to i

Let S to be the set containing the optimal solution. Consider an element a[i] , a[i] is in the set S iff a[i - 1] is not there and a[i + 1] is not there. So, the we define the recurrence as follows -

T(i) = max { a[i] + T(i - 2), a[i - 1] + T(i - 3) }

The Base Cases go as -

T(0) = a[0]

T(1) = max { a[1], a[0] }

T(2) = max { T(0) + a[2], T(1) }

Now we need to take care of the fact that the neighbourhood is circular. So, the 1st and the last people are neighbours. The simplest way to handle the circle case is to solve the problem twice. Once without including the last element (may or may not include first) and once without including the first element (may or may not include last element).

The answer will be the maximum of the two as the optimal solution may contain either of the two or neither of the two.

NOTE: Base cases will change depending on whether you are not including the first element or last element.

Please upvote this if you find this helpful because I need it to ask questions.

15 Likes
3

Just tweaking @samarjeet27’s answer a bit

You dont need the T(2) state…
change
T(i) = max { a[i] + T(i - 2), a[i - 1] + T(i - 3) }
to
T(i) = max { a[i] + T(i - 2), T(i-1) }

I came here from the same Bad Neighbour problem on Topcoder
And if you do by @samarjeet27’s process. then You would need to put extra conditions as they said minimum no of inputs is 2.

6 Likes