You are not logged in. Please login at www.codechef.com 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

2★arpit728
6831456
accept rate: 10%

closed 06 May '17, 16:17

vijju123's gravatar image

5★vijju123 ♦
14.9k11856

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.

link

answered 10 Dec '16, 17:32

samarjeet27's gravatar image

4★samarjeet27
763
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.

link

answered 06 May '17, 14:43

tuhinat221b's gravatar image

2★tuhinat221b
311
accept rate: 0%

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×3,607
×1,952

question asked: 10 Dec '16, 16:51

question was seen: 2,051 times

last updated: 06 May '17, 16:17