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

×

Google Apactest Round B problem C

Hi, I participated in google apactest Round B. I was unable to solve this problem for large input. Can anyone explain how to solve it: https://code.google.com/codejam/contest/4214486/dashboard#s=p2

asked 16 Sep '14, 13:11

sanjeev1779's gravatar image

1★sanjeev1779
3563814
accept rate: 42%


Let us say we are trying to remove three numbers of the array at positions 'x', 'y', 'z'. Now this is only possible if a[x] = a[y] - k and a[y] = a[z] - k (a[] is the given array) and also all the numbers a[x+1], a[x+2], a[x+3].....a[y-2], a[y-1] and a[y+1], a[y+2]....a[z-2], a[z-1] are removed before because the three numbers x, y, z should be adjacent while removing.

Now let us form a DP array pos[i][j] which is a boolean array which stores the boolean value if we can remove the contiguous elements in the array a[] from index 'i' to index 'j' completely ? The pos[][] array can be computed recursively using the conditions mentioned above. And now how to calculate the final answer using pos[][] array?

We have to make another DP array dp[] where dp[i] stores what is the minimum number of elements that can be achieved if we are only considering the elements a[i], a[i+1], a[i+2]....a[n-1, a[n]. This can also be constructed recursively with conditions : for all 'j' for which we can remove the all numbers between indexes 'i' and 'j', i.e, pos[i][j] is true, dp[i] = min(dp[i], dp[j]). The initial value dp[i] can be dp[i+1] + 1 which is the value if we are not removing a[i] at all.

Our final answer will be in dp[1].

link

answered 16 Sep '14, 16:17

adurysk's gravatar image

5★adurysk ♦
92852428
accept rate: 11%

toggle preview
Preview

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:

×1,970

question asked: 16 Sep '14, 13:11

question was seen: 859 times

last updated: 16 Sep '14, 16:17