Archive / 2021 / December 2021
Deceiving the Maestro
So you may have helped Dulaj out with his problem setter pairing dilemma but now, a human runtime exception, Ashan, who is a master competitive programmer with years of knowledge and experience under his belt, throws the whole pairing process astray. So Dulaj decides to single him out and let him decide whom he wants to work with.
There are N number of problem setters who have skill levels from 1 to N where each skill level is unique. Dulaj gives Ashan a constraint that he can select a maximum of M problem setters to be on his team.
Giving the impression of trying to lend a hand, Dulaj being Dulaj decides to take a small kick out of this and gives an altered dataset to Ashan to mislead him. Unfortunately, he underestimated the maestro and it didn’t take long for Ashan to figure out the formula. He figures out that to get the best team, he needs to choose the problem setters such that the XOR sum of their skill levels is highest as possible.
Ashan believes that you are the next grandmaster of competitive programming and hands over this task of finding him the best team, to you. Given the number of candidates N, you have to calculate the largest possible XOR sum of the skill levels that you can get, but the catch is that the number of candidates you select must be less than or equal to M.
Input Format
- A single line containing two space separated integers N and M.
Output Format
- A single integer denoting the maximum skill level a team can have.
Constraints
- 1 \(\leq\) M \(\leq\) N \(\leq\) 1018
Sample Input 0
7 6
Sample Output 0
7
Sample Input 1
6 6
Sample Output 1
7
Open on HackerRank ↗ · Markdown source · Back to the archive