PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Satyam
Tester: Nishank Suresh, Abhinav sharma
Editorialist: Devendra Singh
DIFFICULTY:
2010
PREREQUISITES:
None
PROBLEM:
Let f(X) denote the number of set bits in X.
Given integers N and K, construct an array A of length N such that:
- 0 \leq A_i \leq K for all (1 \le i \le N);
- \sum_{i=1}^{N} A_i = K
Over all such possible arrays, find the maximum value of \sum_{i=1}^{N} f(A_i).
EXPLANATION:
Claim : Each bit that is present in the numbers (except the most significant bit) of all the numbers is either present in all N numbers or N-1 numbers.
Proof
Let us suppose there exists a bit at position i which is set to 1 in N-2 or less numbers and a bit i+1 is set to 1 in at least one number in A, then we can unset the bit i+1 from a number and set i^{th} bit in two numbers in which it was unset earlier. This increases the total number of set bits without changing the sum of the numbers.
Start iterating from i=0 to i=30 or until K>0. There are three cases now:
- If K\leq N set K bits at the i^{th} position and end the loop.
- If K>N and the parity of N and K is same then some higher bit will be set in the next steps to achieve the sum K. This means i^{th} bit has to be set in either N numbers or N-1 numbers. Since the parity is same we have to set it to N numbers.
- If K>N and the parity of N and K is not same then some higher bit will be set in the next steps to achieve the sum K. This means i^{th} bit has to be set in either N numbers or N-1 numbers. Since the parity is not same we have to set it to N-1 numbers.
Remove the contribution of each bit after each step from the sum by subtracting the number of bits taken and dividing K by 2.
TIME COMPLEXITY:
O(log(K)) for each test case.
SOLUTION:
Setter's Solution
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
const ll INF_MUL=1e13;
const ll INF_ADD=1e18;
#define pb push_back
#define mp make_pair
#define nline "\n"
#define f first
#define s second
#define pll pair<ll,ll>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vvvl vector<vector<vector<ll>>>
#define all(v) v.begin(),v.end()
#ifndef ONLINE_JUDGE
#define debug(x) cerr<<#x<<" "; _print(x); cerr<<nline;
#else
#define debug(x);
#endif
void _print(ll x){cerr<<x;}
void _print(string x){cerr<<x;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T,class V> void _print(pair<T,V> p) {cerr<<"{"; _print(p.first);cerr<<","; _print(p.second);cerr<<"}";}
template<class T>void _print(vector<T> v) {cerr<<" [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T>void _print(set<T> v) {cerr<<" [ "; for (T i:v){_print(i); cerr<<" ";}cerr<<"]";}
template<class T>void _print(multiset<T> v) {cerr<< " [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T,class V>void _print(map<T, V> v) {cerr<<" [ "; for(auto i:v) {_print(i);cerr<<" ";} cerr<<"]";}
template<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> using muloset=tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
//--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
const ll MOD=1e9+7;
const ll MAX=500500;
void solve(){
ll n,x; cin>>n>>x;
ll ans=0;
while(x){
ll cur=min(x,n);
if((cur&1)!=(x&1)){
cur--;
}
ans+=cur;
x=(x-cur)/2;
}
cout<<ans<<nline;
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("error.txt", "w", stderr);
#endif
ll test_cases=1;
cin>>test_cases;
while(test_cases--){
solve();
}
cout<<fixed<<setprecision(15);
cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n";
}
Editorialist's Solution
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(), _obj.end()
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
ll INF = 1e18;
const int N = 1e5 + 11, mod = 1e9 + 7;
ll max(ll a, ll b) { return ((a > b) ? a : b); }
ll min(ll a, ll b) { return ((a > b) ? b : a); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void sol(void)
{
int n, k;
cin >> n >> k;
ll ans = 0;
for (int i = 0; i < 30; i++)
{
if (n % 2 == k % 2)
{
ans += min(n, k);
k -= min(n, k);
}
else
{
ans += min((n - 1), k);
k -= min(n - 1, k);
}
k /= 2;
}
cout << ans << '\n';
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int test = 1;
cin >> test;
while (test--)
sol();
}
) I had some difficulty in passing the first testcase, may someone please help me with it. Thanks in advance 
