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) ) )
Can you please share a problem link?
no ,i dont have that. is there anything which is not clear??
To make sure that it's not an ongoing contest
ok,contest was yesterday,it was a hiring contest(link:https://app.talentforwork.com/flow/netapp-it-intern-test-ii). Now i dont have problem link as it expired...
It's from here.
And here is the editorial. Check page 9.
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.
we have to remove both
okay, here we have to remove both
Deleted