JACKPOT - Editorial

editorial
, , ,
1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

Medium

PREREQUISITES

Simple Math

PROBLEM

Alice is given a target number to achieve. She begins with number 1. She can make 1 move each week. In 1 move, she can either increment her number by one or double it.

Bob will help Alice. They will split the target among themselves and decide their own sub-targets. They will try to achieve their sub-targets and then combine them to achieve the initial target.

Each one them is limited to at most one (maybe zero) purchases per week. What is the fewest number of weeks needed for them to reach the initial target?

QUICK EXPLANATION

The first sub-problem to solve is the minimum number of weeks (or purchases) required by a single person to achieve a target T.

  • Let S(t) be the binary representation of t
  • Let Z(t) be the number of 0s in S(t) (after the leftmost 1)
  • Let O(t) be the number of 1s in S(t) (excluding the leftmost 1)

We can show that there is a strategy to achieve the sum T in ( Z(T) + 2 * O(T) ) moves.

  • You start with 1.
  • To introduce a 0 in the binary representation, perform a double-ing move.
  • To introduce a 1 in the binary representation, perform a double-ing move following by an increment move.

Thus, the total number of moves would be ( Z(T) + 2 * O(T) ) to achieve the exact representation that T has.

In fact, ( Z(T) + 2 * O(T) ) is the minimum number of moves it would take.

EXPLANATION

Let M(T) = ( Z(T) + 2 * O(T) )

We wish to split T into two sums A and B, which should be reached independently. A naive algorithm that comes to mind is to try every possible split. Let us look at the pseudo code for such an approach

int answer = infinity
for n = 1 to N-1
  answer = min( answer, max( M(n), M(N-n) ) )

Unfortunately, such an approach would be too slow. N can be as much as 109. To think about a faster solution, we require some crucial insights

  • At least one of the two would need as many double-ing moves as the original number, to introduce enough bits in the final number.
  • Both of them will never introduce a set bit at the same bit position. Such a case can always be replaced with an alternative where only one of them had to introduce a set bit.

Thus, the optimal strategy for them is to divide the set bits among themselves and create final target with those set bits. For this strategy, we can split the bits in the number into two parts. Each one of them generates the number responsible for their part respectively.

answer = infinity
for b = 1 to O(T)+Z(T)
  A = T bitwise-and (2b - 1)
  B = T - A
  answer = min( answer, max( M(A), M(B) ) )

There is 1 special case that is not handled above. The case where you wish to achieve a power of two. To handle this case you require exactly 2Z(T) - 1 operations. This is the only case for which it is beneficial for both Alice and Bob to set the second highest bit (and avoid a double-ing move altogether.

The limits of this problem are small enough to allow for many slower solutions to pass as well. Although, the naive solution described first will not pass.

The tester’s solution uses dynamic programming on the bits to avoid having to lay faith on the above insights.

TESTER’S SOLUTION

Can be found here

4 Likes