Problem : Problem - C - Codeforces
Can somebody explain how to solve it along with the intuition behind it? A brief explanation would help. Thank you.
The approach is try to make every number equal to zero.
Find the jth power of k which is less than equal to every no ai and the subtract pow(k,j) from ai.
Keep doing it until you make ai equal to zero.
However, while doing this keep storing j in a set and if j repeats it is impossible to do it and print “NO”. If j never repeats print “YES”.
Code link which might help you to understand better -
1 Like
You are given an array of size n, initially filled with 0. You have to make this array equal to another array a given as input. For this you can use i-steps( 0 indexed), In each step you can pick any index of array filled with 0 and increase element at that index by k to power i.
In this question, main point to understand is any value of k to power i can be used not more than one time( Because in one step you can only select one array position and increment its value). Now, what you need to do is just store power of k upto 10^18, and a boolean array to mark which power you have used.If you are able to make all elements of array from 0, without using any power twice, answer will be “YES”, otherwise “NO”.
My AC code looks like this:
#include<bits/stdc++.h>
using namespace std;
#pragma GCC push_options
#pragma GCC optimize ("unroll-loops")
#define watch(x) cout << (#x) << " is " << (x) << "\n"
#define watch2(x,y) cout <<(#x)<<" is "<<(x)<<" and "<<(#y)<<" is "<<(y)<<"\n"
#define pow2(x) ((x)*(x))
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define ll long long
#define ld long double
#define eb emplace_back
#define pb push_back
#define pf push_front
#define mod 1000000007
#define clock (clock() * 1000.0 / CLOCKS_PER_SEC)
#define mp make_pair
#define ff first
#define ss second
#define all(c) (c).begin(),(c).end()
#define nl "\n"
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector< vi > vvi;
typedef vector< vl > vvl;
typedef pair< int,int > ii;
typedef pair< ll,ll> pll;
typedef map< ll,ll> mll;
typedef map< int,int> mii;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll t;
cin >> t;
while(t--)
{
ll n,k;
cin >> n >> k;
ll ar[n];
for(int i=0;i<n;i++)
{
cin >> ar[i];
}
vl v;
vector<bool> v1;
ll ashu = 1;
while(ashu<=1e18 && ashu>=1)
{
v.eb(ashu);
v1.eb(false);
ashu *= k;
}
sort(ar,ar+n);
bool flag = true;
for(int i=n-1;i>=0;i--)
{
int j = v.size()-1;
ll sum = ar[i];
while(sum!=0 and j>=0)
{
if(sum<v[j])
{
j--;
}
else
{
ll temp = sum/v[j];
if(temp>1 || v1[j])
{
flag = false;
break;
}
else
{
sum -= v[j];
v1[j] = true;
j--;
}
}
}
if(sum!=0)
flag = false;
if(!flag)
break;
}
if(flag)
cout << "YES\n";
else
cout << "NO\n";
}
return 0;
}
1 Like
Thanks, I’ve applied this logic but I’m going wrong somewhere. 
Will try again and let you know.
EDIT: Meanwhile I’m trying to debug it, if anyone is able to find out where I’m going wrong, please point out. Thanks 
Sure
try to create a container to store bits from 0 to k power bits.
If they try to repeat then the answer is false.
link to AC solution where i implemented this idea.
1 Like
Simply find the representation of every number in base k same way you do for conversion of a number from decimal to base2 that is binary : here only base is changing . Now sum all the values for each number at a particular bit and find for all the bits most probably total bits will be less than 40 : So for each of these just check if its summed value for all numbers in an array is less than or equal to 1 or not if yes then continue else break and return no and if all bits satisfied the condition then simply output yes . COOL
1 Like