You are not logged in. Please login at to post your questions!


[closed] Topcoder- Bad Neighbour dp based problem

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.

asked 10 Dec '16, 16:51

arpit728's gravatar image

accept rate: 10%

closed 06 May '17, 16:17

vijju123's gravatar image

5★vijju123 ♦

The question has been closed for the following reason "The question is answered, right answer was accepted" by vijju123 06 May '17, 16:17

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.


answered 10 Dec '16, 17:32

samarjeet27's gravatar image

accept rate: 16%

edited 13 Dec '16, 19:54

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.


answered 06 May '17, 14:43

tuhinat221b's gravatar image

accept rate: 0%

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 10 Dec '16, 16:51

question was seen: 1,892 times

last updated: 06 May '17, 16:17