PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: fremder
Tester: wasd2401
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
An integer is called good if its binary representation doesn’t contain \texttt{101} as a subsequence.
You’re given an integer N. In one move, you can add 2^x to it (for a cost of 2^x).
Find the minimum total cost required to convert N into a good integer.
EXPLANATION:
First, look at the cost: since adding 2^x to N costs 2^x itself, the total cost of converting N to (N+Y) is simply Y.
So, what we really want to do is find the smallest good integer that’s \geq N — the answer is then their difference.
This brings us to the main question: is there a simpler classification for good integers?
There is!
It can be observed that an integer is good if and only if it has only a single ‘block’ of ones in its binary representation.
Since the first digit of the representation is always \texttt{1}, that means the binary form of a good integer will look like \texttt{111\ldots 111000\ldots 000}_2.
Proof
If the binary form looks like \texttt{111\ldots 11100\ldots 000}_2, clearly \texttt{101} doesn’t appear as a subsequence.
Conversely, if there are \geq 2 blocks of ones, \texttt{101} will always occur as a subsequence: for example, take the leftmost one and the rightmost one - there will definitely be a 0 between them (if not, every 1 would have to form a single block, which as per our assumption is not true).
With this classification in hand, there are now several different ways to solve the problem.
For instance,
- Since we’re dealing with numbers that have \leq 30 bits, there are only 30\cdot (30+1)/2 = 465 distinct numbers with a single block of ones.
You can precompute them all, then find the smallest one that’s \geq N with binary search, or even just by iterating across the whole list (which is still fast enough). - Alternately, notice that a number has a single block of ones if and only if it equals 2^{x+1} - 2^y for some integers x and y.
So, we can choose x to be the highest set bit in N, and then find the largest y (the more we subtract, the better) such that 2^{x+1} - N \geq 2^y.
With x and y known,the target value is also known: meaning the answer is easily computed.
TIME COMPLEXITY:
\mathcal{O}(\log N) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t; cin >> t;
while(t--) {
int n; cin >> n;
int first = 0, last = 0;
int cnt = 0;
for(int i = 29; i >= 0; i--) {
if(n & (1 << i)) first = max(first, i), last = i;
}
if(first == last) {
cout << 0 << "\n";
continue;
}
int pos = -1, sub = 0;
for(int i = first; i >= last; i--) {
if(n & (1 << i)) {
sub += (1 << i);
continue;
}
pos = i;
break;
}
if(pos == -1) cout << 0 << "\n";
else cout << (1 << pos) - (n - sub) << "\n";
}
}
Tester's code (C++)
/*
* * * *** * *****
* * * * * * * *
* * * *** ***** *
* * * * * * * * *
* * * * * * **
*
* *
*****
* *
***** * *
_* *_
| * * * * | ***
|_* _ *_| * *
* * *
***** * **
* * ***
{===* *===}
* IS * ***
* IT * * *
* RATED?* *
* * * **
* * ***
* *
***** * *
* *
* *
* *
***
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define osl tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
#define ll long long
#define ld long double
#define forl(i, a, b) for(ll i = a; i < b; i++)
#define rofl(i, a, b) for(ll i = a; i > b; i--)
#define fors(i, a, b, c) for(ll i = a; i < b; i += c)
#define fora(x, v) for(auto x : v)
#define vl vector<ll>
#define vb vector<bool>
#define pub push_back
#define pob pop_back
#define fbo find_by_order
#define ook order_of_key
#define yesno(x) cout << ((x) ? "YES" : "NO")
#define all(v) v.begin(), v.end()
const ll N = 2e5 + 4;
const ll mod = 1e9 + 7;
// const ll mod = 998244353;
ll modinverse(ll a) {
ll m = mod, y = 0, x = 1;
while (a > 1) {
ll q = a / m;
ll t = m;
m = a % m;
a = t;
t = y;
y = x - q * y;
x = t;
}
if (x < 0) x += mod;
return x;
}
ll gcd(ll a, ll b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
return (a / gcd(a, b)) * b;
}
bool poweroftwo(ll n) {
return !(n & (n - 1));
}
ll power(ll a, ll b, ll md = mod) {
ll product = 1;
a %= md;
while (b) {
if (b & 1) product = (product * a) % md;
a = (a * a) % md;
b /= 2;
}
return product % md;
}
set<ll> t;
void panipuri() {
ll n, m = 0, k = -1, c = 0, sum = 0, q = 0, ans = 0, p = 1;
string s;
bool ch = true;
cin>>n;
assert(n>=1 && n<(1<<30));
cout<<(*(t.lower_bound(n)))-n;
return;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int laddu = 1;
cin>>laddu;
assert(laddu>=1 && laddu<=1e5);
ll z=30;
vl v(z,1);
forl(i,1,z) v[i]=2*v[i-1];
forl(i,0,z){
ll c=0;
forl(j,i,z){
c+=v[j];
t.insert(c);
}
}
forl(i, 1, laddu + 1) {
// cout << "Case #" << i << ": ";
panipuri();
cout << '\n';
}
}
Editorialist's code (C++)
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
int n; cin >> n;
int pw = 31 - __builtin_clz(n);
int target = (2 << pw) - n;
cout << (2 << pw) - (1 << (31 - __builtin_clz(target))) - n << '\n';
}
}
