Blog #3



Amazing solution behind an awesome logical problem


You can find the official problem statement by this link. Here is the brief statement:

There are K cards numbered from 1 to K. Every card has each number from 1 to N written on it. Some numbers exist on the front side of the card and some on the back side. No number exists on both the sides of a card at the same time. These cards are placed on the table in a row such that only one side is visible. You are allowed to flip them any number of times. You task is to flip some of them to maximize the number of different numbers on visible sides.

Solution

Let’s call a X is beautiful if it’s visible in one of the K cards. You can notice that some X will not be beautiful number in only one case - when every card from 1 to K is flipped to the side where X is not visible, which can be represented by a bit mask of length K. Now we can calculate for each a bit mask how many numbers it would affect (making them not beautiful) if we choose it. The answer would be the best mask - where number of not affected numbers is maximum. Also, if 2^K > N, then there exists a bit mask which would not affect any number. Thus, in this case it always possible to find a bit mask where each number from 1 to N is on the visible side.

You can find more detailed solution in the editorial.

For practice, you can try to solve this similar problem.