DRAGNXOR - Editorial

editorial
, , ,
1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

EASY

EXPLANATION

We need to make A^B maximum by shuffling the 1 bits within A and B. As 1 ^ 0 = 0 ^ 1 = 1, we need to make maximum number of (1,0) or (0,1) pairs, where a pair means the corresponding bits from A and B at a particular bit position. Also, to make the result maximum, we want all the ones towards the most significant side (left). Lets pair each 1 bit of A with a 0 bit of B. There can be at max x = minimum _ of( number of 1s in A, number of 0s in B). Similarly, pair each 1 bit of B with a 0 bit of A. There can be at max y = minimum _ of( number of 1s in B, number of 0s in A). Rest of the pairs are either (1,1) or (0,). So, the number of ones in the result is at max P = x + y. The answer is (1111…) : P times followed by (…000) : N-P times, which is nothing but the integer ( ((1<<P)-1) << (N-P) ).

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

2 Likes
2

Tester’s solution is failing

1

25 76767543267 77272727272
Exception in thread “main” java.util.InputMismatchException: For input string: “76767543267”

I have written code in c++. Its passing basic testcases mentioned on the program page but failing otherwise. I am using ‘long long’ data type as input, converting them to strings and then finding the pairs and ultimately writing output on console. But its failing, can you pls have a look.

Click to see code

3

The number 76767543267 exceeds 30 bits. In the problem, there is a restriction on N = 30

4

Can you please provide the secret test cases? It shows wrong answer when submitting on CodeChef.