PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: aryan_sinha15
Tester: yash_daga
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Bitmasks
PROBLEM:
Given N, find the minimum number of distinct powers of 2 or 3 that sum to N.
EXPLANATION:
First off, notice that there’s almost no intersection between the powers of 2 and 3: the only common power they share is 1.
However, it’s never going to be optimal to take both 2^0 and 3^0 so we can ignore this intersection entirely. Do you see why?
In particular, this means the distinct condition is taken care of nicely for us, so we only need to decide on the set of powers of 2 and 3 that we take.
If we didn’t have the powers of three to deal with, this would be a pretty simple problem: the minimum number of powers of 2 required to represent a number equals the number of ones in its binary representation.
Notice that N is pretty small.
In particular, since N \leq 10^8, we have 3^{17} \gt 10^8 \geq N for any input N.
This means the only powers of three we care about are \{3^0, 3^1, 3^2, \ldots, 3^{16}\}.
So, let’s fix which subset of these powers we’re taking into the sum.
There are 2^{17} such subsets.
Let S be the sum of the chosen subset.
We now need to write N - S as the sum of powers of two, which we already know how to do: we just need to count the number of ones in the binary representation of (N-S) which is easy.
This solution can be further optimized a bit by not checking all 2^{17} subsets for every testcase, and instead only checking the subsets of \{3^0, 3^1, \ldots, 3^{\lfloor\log_3 N\rfloor}\}.
This is faster because the sum of N is bounded by 10^8.
TIME COMPLEXITY
\mathcal{O}(2^B\cdot B) per testcase, where B = \lfloor\log_3 N\rfloor.
CODE:
Setter's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define all(vec) vec.begin(), vec.end()
#define endl "\n"
#define pb push_back
#define yes cout << "YES" << endl;
#define no cout << "NO" << endl;
#define ff first
#define ss second
#define flush cout << flush;
// #define N 1e5 + 1
#define PI 3.141592653589793238462643383279
#define IOS \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
ll mod_mul(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a * b) % m) + m) % m;}
ll mod_add(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a + b) % m) + m) % m;}
long long power(ll x, ll y)
{
ll temp;
if (y == 0)
return 1;
temp = power(x, y / 2);
if (y % 2 == 0)
return temp * temp;
else
return x * temp * temp;
}
vector<ll>pre(18);
void _segfault_()
{
ll n;
cin >> n;
vector<ll>vec(18);
for (ll i = 0; i <= 17; i++) {
vec[i] = i;
}
ll m = n;
ll o = 0;
while (m > 0) {
if (m % 2 == 1)
o++;
m /= 2;
}
ll mn = LLONG_MAX;
mn = min(mn, o);
for (ll i = 1; i < (1ll << 17); i++) {
ll sum = 0;
ll cnt = 0;
vector<ll>a;
ll j = i;
ll one = 0;
while (j > 0) {
if (j % 2 == 1)one++;
a.pb(j % 2);
j /= 2;
}
for (ll j = 0; j < a.size(); j++) {
if (a[j] == 1)
sum += pre[vec[j]];
}
if (sum > n)break;
else {
ll b = n - sum;
ll c = b;
while (b > 0) {
if (b % 2)
cnt++;
b /= 2;
}
cnt += one;
mn = min(mn, cnt);
}
}
if (mn == LLONG_MAX)
cout << -1 << endl;
else
cout << mn << endl;
}
int32_t main(int argc, char const * argv[])
{
// int32_t for returning val 32 bit integer always
IOS
clock_t z = clock();
cout.setf(ios::fixed, ios::floatfield);
cout.setf(ios::showpoint);
cout << setprecision(20);
int t=1;
cin >> t;
ll i = 0;
while (i < pre.size()) {
pre[i] = power(3, i);
i++;
}
while (t--)
{
// cout << "Case #" << a << ": ";
_segfault_();
// a++;
}
cerr << "Run Time : " << ((double)(clock() - z) / CLOCKS_PER_SEC);
return 0;
}
Tester's code (C++)
//clear adj and visited vector declared globally after each test case
//check for long long overflow
//Mod wale question mein last mein if dalo ie. Ans<0 then ans+=mod;
//Incase of close mle change language to c++17 or c++14
//Check ans for n=1
// #pragma GCC target ("avx2")
// #pragma GCC optimize ("O3")
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define int long long
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);cout.precision(dbl::max_digits10);
#define pb push_back
#define mod 1000000007ll //998244353ll
#define lld long double
#define mii map<int, int>
#define pii pair<int, int>
#define ll long long
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define rep(i,x,y) for(int i=x; i<y; i++)
#define fill(a,b) memset(a, b, sizeof(a))
#define vi vector<int>
#define setbits(x) __builtin_popcountll(x)
#define print2d(dp,n,m) for(int i=0;i<=n;i++){for(int j=0;j<=m;j++)cout<<dp[i][j]<<" ";cout<<"\n";}
typedef std::numeric_limits< double > dbl;
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
//member functions :
//1. order_of_key(k) : number of elements strictly lesser than k
//2. find_by_order(k) : k-th element in the set
const long long N=200005, INF=2000000000000000000;
const int inf=2e9 + 5;
lld pi=3.1415926535897932;
int lcm(int a, int b)
{
int g=__gcd(a, b);
return a/g*b;
}
int power(int a, int b, int p)
{
if(a==0)
return 0;
int res=1;
a%=p;
while(b>0)
{
if(b&1)
res=(1ll*res*a)%p;
b>>=1;
a=(1ll*a*a)%p;
}
return res;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int getRand(int l, int r)
{
uniform_int_distribution<int> uid(l, r);
return uid(rng);
}
int32_t main()
{
int t;
cin>>t;
int p3[20];
p3[0]=1;
rep(i,1,20)
p3[i]=p3[i-1]*3;
while(t--)
{
int n;
cin>>n;
int ans=setbits(n);
rep(i,0,(1 << 17))
{
int cur=0;
rep(j,0,17)
{
if(i&(1 << j))
cur+=p3[j];
}
if(cur>n)
continue;
ans=min(ans, (int)setbits(i)+setbits(n-cur));
}
cout<<ans<<"\n";
}
}
Editorialist's code (Python)
def getlim(n):
len, val = 0, 1
while val < n:
len += 1
val *= 3
return len
for _ in range(int(input())):
n = int(input())
L = getlim(n) + 1
ans = 40
for mask in range(1 << L):
cur = 0
for i in range(L):
if mask & (1 << i): cur += 3 ** i
if cur <= n: ans = min(ans, bin(mask)[2:].count('1') + bin(n - cur)[2:].count('1'))
print(ans)