- Practice
- Algorithms
- Bit Manipulation
- A or B
- Discussions

# A or B

# A or B

+ 2 comments Nice one. To all participants, be aware of large numbers.

+ 1 comment kinda intuitive. should be easy to understand from below. basically made binary representation for A, B and C and iterated through them to find the optimal solution.

t = int(input()) for _ in range(t): k = int(input()) a = bin(int(input(), 16))[2:] b = bin(int(input(), 16))[2:] c = bin(int(input(), 16))[2:] pad = max(map(len, [a,b,c])) a = list('0'*(pad - len(a)) + a) b = list('0'*(pad - len(b)) + b) c = list('0'*(pad - len(c)) + c) count = 0 for i in range(pad): if c[i] == '0': count += int(a[i]) + int(b[i]) a[i] = '0' b[i] = '0' else: if a[i] == '0' and b[i] == '0': count += 1 b[i] = '1' if count > k: print(-1) else: i = 0 k -= count while i < pad and k > 0: if c[i] == '1': if a[i] == '1' and b[i] == '1': k -= 1 a[i] = '0' elif a[i] == '1' and b[i] == '0' and k >= 2: k -= 2 a[i] = '0' b[i] = '1' i += 1 print(hex(int("".join(a), 2))[2:].upper()) print(hex(int("".join(b), 2))[2:].upper())

+ 0 comments My solution-> https://ideone.com/AwjvFd

+ 3 comments This may sound like an odd complaint, but I feel the hardest test cases for this problem are not hard enough. Let me explain...

A very naive solution would generate all possible sets of A' and B', filter for A' | B' = C, then sort through to pick the ones which make no more than K changes and have minimal A' and B'. This may complete test case 0 in time but will time out for all the others.

A less naive solution to this would build a tree of all possible changes which satisfy A' | B' = C, then navigate the tree to find all solutions which make no more than K,the permitted number of changes, and from those pick the ones with minimal values of A' and B' This will solve test case 0 in the permitted time but time out for almost all the others.

There are several ways to optimise the tree building, some of which make for very complicated code. However, there are three simple optimisations which dramatically improve performance. And (in Haskell, at least), these are sufficient to pass all the tests.

But tree-building is not the most performant solution. With enough insight into the possible changes to A and B, there is a highly performant solution which is also very simple. I had just realised this (and begun to add the first bits of it to my code) when I made the final optimation to my tree building solution - which passed

*all*the tests. This let me see the editorial, where that simple solution is in fact the one used by the creator of the challenge.So now I almost feel as if I have cheated. Or been cheated (my only incentive now for writing the best solution is perfectionism).

I know that if certain bit combinations were predominant in (A,B,C) and K were high, tree building/traversal would be very expensive even with modestly sized input values. I think this challenge could be improved by adding those test cases, offering a 40 score for passing the current tests and 50 for passing all (or 50/60, say).

+ 0 comments Here are my JavaScript solutions passing all test cases:

1) using BigInt to covert strings from hex to bin and back:

function aOrB(k, a, b, c) { [a, b, c] = [a, b, c].map(hex => Array.from(BigInt('0x' + hex).toString(2))); const maxLen = Math.max(a.length, b.length, c.length); [a, b, c] = [a, b, c].map(bin => bin.length === maxLen ? bin : Array(maxLen - bin.length).fill('0').concat(bin)); const bit = ch => ch === '1'; for(let i = 0; i < maxLen; i++) { if(bit(c[i])) { if(!bit(a[i]) && !bit(b[i])) b[i] = '1', k--; } else { if(bit(a[i])) a[i] = '0', k--; if(bit(b[i])) b[i] = '0', k--; } if(k < 0) return console.log('-1'); } for(let i = 0; i < maxLen && k > 0; i++) { if(bit(a[i]) && bit(b[i])) a[i] = '0', k--; else if(bit(a[i]) && !bit(b[i]) && k > 1) { a[i] = '0', b[i] = '1', k -= 2; } } [a, b].forEach(bin => console.log(BigInt('0b' + bin.join('')).toString(16).toUpperCase())); }

2) converting hex to bin and bin to hex manually:

function aOrB(k, a, b, c) { const map = new Map(); for(let i = 0, hex = '0123456789ABCDEF'; i < 16; i++) { const bin_i = [8, 4, 2, 1].reduce((res, j) => res.concat(i & j ? '1' : '0'), ''); map.set(hex[i], bin_i).set(bin_i, hex[i]); } const maxLen = 4 * Math.max(a.length, b.length, c.length); [a, b, c] = [a, b, c].map(hex => { const bin = Array(maxLen - 4 * hex.length).fill('0'); for(let i = 0; i < hex.length; i++) { bin.push(...map.get(hex[i])); } return bin; }); const bit = ch => ch === '1'; for(let i = 0; i < maxLen; i++) { if(bit(c[i])) { if(!bit(a[i]) && !bit(b[i])) b[i] = '1', k--; } else { if(bit(a[i])) a[i] = '0', k--; if(bit(b[i])) b[i] = '0', k--; } if(k < 0) return console.log('-1'); } for(let i = 0; i < maxLen && k > 0; i++) { if(bit(a[i]) && bit(b[i])) a[i] = '0', k--; else if(bit(a[i]) && !bit(b[i]) && k > 1) { a[i] = '0', b[i] = '1', k -= 2; } } [a, b].forEach(bin => { for(var i = 4, hex = ''; i <= maxLen; i += 4) { hex += map.get(bin.slice(i - 4, i).join('')); } console.log(hex.replace(/(?<=^)0+/, '') || '0'); }); }

Sort 28 Discussions, By:

Please Login in order to post a comment