aman1776's blog

Help needed in a problem
By aman1776, history, 3 years ago, In English

Given an array of even size containing only 1,2,3. We can recursively take two adjacent position and remove them until size of array is 0. However we have one additional constraint, that we can not remove two adjacent if they are 1,2 or 2,1. In how many ways array can be formed(containing only 1,2,3) so that we can recursively remove adjacent position till size of array is 0.

constraints: n(size of array)<=1e5 and even

test case : for n=2 answer =7 ({1,2,3} x {1,2,3} — ((1,2) ,(2,1) ) )

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

Comments Comments (9)
| Write comment?
»
3 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Can you please share a problem link?

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can we remove both of the position or one of them at a time.

if 2nd is the case then we know 3^n is total case and we can remove those array which have only 1 and 2 that is 2^n-3 so answer is (3^n-(2^n-3)).

We remove 3 i.e 1 for empty array, 1 for array with only 1 and 1 for array with only 2.

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Deleted

→ Reply