15295 Fall 2024 #10 Interactive Problems -- Problem Discussion

Nov. 6, 2024

The problems for this contest can be found here.

A.

B.

First query: ask about the cell (1, 1), and its result is A. This will let us know the maximum between max(x - 1, y - 1), i.e. the maximum of the row and column distances.

The king will be in either row A + 1 or column A + 1 (or maybe both).

Second query, ask about the cell (1, A + 1) (if possible to do, i.e. A + 1 <= m), and its result is B. This will let us know the specific row of the king.

Third query, ask about the cell (A + 1, 1) (if possible to do, i.e. A + 1 <= n), and its result is C. This will let us know the specific column of the king.

So, now there are some conditions:

• We are not able to ask about (1, A + 1). I.e. the number of columns is less than A + 1, here basically the answer is (A + 1, C + 1). Why? There is no column A + 1, so, the previous calculations for A was representing x.
• We are not able to ask about (A + 1, 1). I.e. the number of rows is less than A + 1, here basically the answer is (B + 1, A + 1). Why? There is no row A + 1, so, the previous calculations for A was representing y.
• We are able to ask about both. The answer is (B + 1, C + 1).

- Omar Ahmed

C.

We will always subtract a power of 2. So, let’s assume we are subtracting 2^x. There are two cases:

• Bit x is turned on:

e.g., the number is 1101010111. Then, when subtracting it, this bit will be turned off, and the number of bits will decrease. So, we will add 2^x to the answer.

• Bit x is turned off:

e.g., the number is 0100001010. Then, when subtracting it, the new binary number is 0101110010.

What happened? All turned-off bits from the current bit to the next turned-on bit will be turned on, and the turned-on bit will be turned off.

So, the number of bits will increase. Here, we will add 2^x  to the answer as we decreased it before and add it again to the answer because we already know that this bit is currently turned on. We will not apply the operation to the number because this would use a much larger number of operations than required. However, we will count them. Let’s call the counter CNT.

So, when to stop?

When the number of known bits, CNT, is greater than or equal to the current bits.

At the end, print the answer.

• Omar Ahmed
  

D. Observe that if the maximum element in the array is m, then the answer must be one of m, 2m, …, floor(n / k) * m. We can check each possible answer in k queries. To determine if the maximum is i, we test f(1, n i) = n for each i = 1, 2, …, n. In total, this takes n + floor(n / k) * k < 2 * n  queries.

E.

F.

The first question is: is it possible for the second player to win?

Yes, the second player can win if and only if the sum of the elements (SUM) is even and there is at least one subsequence with a sum equal to (SUM/2).

Why?

When we have a subsequence with a sum equal to (SUM/2), we can divide the array into two parts, each with a sum equal to (SUM/2). So, when the first player uses a number from one part, we can use any number from the other part, and so on. This way, we always have numbers to use, meaning the second player will be the last one to play.

So, we basically check if the sum is even and if we find a subsequence with a sum equal to (SUM/2). If so, the second player can win; otherwise, the first player will always win.

The strategy for the first player is simply to print any number that is still active (i.e., it’s not equal to 0), then input the second player’s number. Decrease both numbers by the minimum of the two and remove any inactive ones. And so on.

The strategy for the second player is as mentioned: if the first player chooses a number from the first part, choose a number from the second part, and vice versa. Then, decrease both numbers by the minimum value and remove the inactive ones from the parts.

• Omar Ahmed

Thanks Omar.  I would just add two things.  One is that in order to determine if you can form two equal piles of numbers, you have to solve the subset sum problem. Namely, given a list of positive numbers a1, a2, …, an, find a subset of them that sum to a specific value (namely half the total).  This problem is NP-complete, but in this case where the numbers are bounded by B it can be solved using DP in O(n2B) time.

The other thing you didn’t explain is that if there’s no way of partitioning the numbers into two equal piles, then after an arbitrary move pair is made, it’s still impossible to partition it.  And this is true, because if the two numbers are a and b and a≥b what you’re doing is replacing the two numbers a and b in the set by one number a-b.  If the latter was partitionable into two equal piles, you take the pile containing a-b and replace a-b by a, and put b into the other pile.  Which gives an equal partitioning of the original set of numbers.

–Danny