CR197 - Editorial

bitmasking
cord2019
easy-medium
editorial

#1

Contest
Practice

Author: Ankit Rao

DIFFICULTY

Easy - Medium

PREREQUISITES

Bit Manipulation

PROBLEM

Given an array of n integers where each index i represents a value a_i - cost of buying 2^i items, and a value L representing the minimum threshold of items to buy.
Print the minimum cost for this.

###EXPLANATION

Here
Let m=1+max\begin{Bmatrix} n+1 ,\left \lfloor 1+Log_2L \right \rfloor \end{Bmatrix}

Here in the given problem, let’s say is cost_i represents the minimum cost to purchase 2^i items, then the following relation holds -

cost_i = \begin{Bmatrix} a_0 & if \,\, i=0 \\ min(2*cost_{i-1},a_i)& otherwise \end{Bmatrix}

prev = +INFINITY ;
for ( int i = 0 ; i < m ; i ++){
   if ( i < n )
     c o s t [ i ] = min ( prev , c o s t [ i ] ) ;
   else
     c o s t [ i ] = prev ;
   prev = 2· c o s t [ i ] ;
}

Note that if 2 *a^ia^{i + 1}, then it doesn’t make sense to buy any it of type i + 1 — it won’t ever be worse to buy two items of type i instead.

Now for all i it’s true that 2 *a^i a^{i + 1}. Note that now it doesn’t make sense to buy more than one item of type i if i-1 \le n .

for ( int i = 0 ; i < m ; i ++){
   if (L & ( 1LL << i ) )
     answer += c o s t [ i ] ;
   else
     answer = min ( answer , c o s t [ i ] ) ;
}

If i^{th} bit is set in L, then no cost[j] or any form of their sum for 1 \le j \le i-1 can satisfy the requirement because 2^0 + 2^1 + ....... 2^{i-1} = 2^i - 1 .
But as you go further, if the cost[i] corresponding to higher bits is lower, it can certainly lead to minimum cost solution.
With this approach you may end up getting more than L items, but it will lead you to the minimum cost.

Also, in the given problem run the loop only till m instead of 64 as it can easily lead to overflow.


#2

How did you get this relation? I mean can u give any proof or something (links, blog etc) ?