This question was asked in CodeChef Starters 10 Division 2 (Rated), I solved this question using recursion ( which failed because it got TLE).
I tried my best to convert it into DP but wasn’t able to do it.
Question Name: Magical Flips (CRDFLP)
Question Link: https://www.codechef.com/START10B/problems/CRDFLP
My Code:
def solve(idx, prev_and, flips):
global max_and
global min_flips
if idx == n:
if prev_and > max_and:
max_and = prev_and
min_flips = flips
return
solve(idx+1, prev_and&arr[idx], flips)
solve(idx+1, prev_and&brr[idx], flips+1)
for _ in range(int(input())):
n = int(input())
arr = list(map(int, input().split()))
brr = list(map(int, input().split()))
max_and = -1
min_flips = 0
d = dict()
solve(0, 2**31-1, 0)
print(max_and, min_flips)
My Logic: My logic was simple, for each card we have 2 options either we take the front face card number in our final result or we take the back face number, and then we have to calculate the maximum and from all available combinations.
My code is currently O(2^n) but by using DP it can be reduced.
Only suggestions will also be helpful ( or code in any language )
Thanks in advance.