Isn’t it the case that it takes usual a few hours…
1 Like
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//bool comp(pair<ll,ll> &p1,pair<ll,ll>&p2){
// return p1.first>p2.first;
//}
class comp{
public:
bool operator()(pair<ll,int>&p1,pair<ll,int>&p2){
if(p1.first==p2.first){
return p1.second>p2.second;
}
return p1.first<p2.first;
}
};
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--){
int n,k;
cin>>n>>k;
ll d;
vector<int> v(64,0);
for(int i=0;i<n;i++){
cin>>d;
int p=0;
while(d){
if(d&1){
v[p]++;
}
p++;
d=d>>1;
}
}
ll power=1;
//vector<pair<ll,ll>> P;
priority_queue<pair<ll,int>,vector<pair<ll,int>>,comp> pq;
for(int i=0;i<64;i++){
v[i]*=power;
power*=2;
pq.push({v[i],i});
//cout<<"{"<<v[i]<<" "<<i<<"}"<<endl;
}
ll ans=0;
while(k--){
auto p=pq.top();
pq.pop();
ans+=pow(2,p.second);
}
cout<<ans<<endl;
//sort(P.begin(),P.end(),comp);
}
return 0;
}
My code also failed on the first sub-task. Can anyone point out the reason? Is there a way to get the test case which did not pass?
Can anyone solve this problem with dp? i think it can be solved by dp 
@Im10_piyush
could you please explain your approach.
Thanks in advance🙂.
Same issue without long long I got partial marks. Could not figure out why , Now after seeing your post I tried with long long got AC . Can anyone explain why ? All constraint are accordingly taken
Partial Marking → CodeChef: Practical coding for everyone
AC solution → CodeChef: Practical coding for everyone
I don’t think overflow can occur in my partial code as count array is long long in both cases.
Could anyone help me with why my solution isn’t working for sub-task - 2?
Here’s my solution : https://www.codechef.com/viewsolution/34788321
Subtask 1 is passing. Same approach. used long long int also still unable to pass subtask-2. Can anyone have a look?
#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ll long long
#define MOD 1000000007
using namespace std;
bool comp(pair<ll, ll> a, pair<ll, ll> b) {
if (a.second == b.second)
return a.first < b.first;
return a.second > b.second;
}
int main() {
#ifndef ONLINE_JUDGE
freopen(“input.txt”, “r”, stdin);
freopen(“output.txt”, “w”, stdout);
#endif // ONLINE_JUDGE
FAST
int t;
cin >> t;
while (t--) {
ll n, k, temp;
cin >> n >> k;
ll arr[33];
memset(arr, 0, sizeof(arr));
for (ll i = 0; i < n; i++) {
cin >> temp;
ll j = 0;
while (temp) {
arr[j++] += temp % 2;
temp /= 2;
}
}
vector < pair<ll, ll> > vec;
for (ll i = 0; i < 33; i++) {
vec.push_back(make_pair(i, arr[i] * (ll)pow(2, i)));
}
sort(vec.begin(), vec.end(), comp);
ll res = 0;
// for (ll i = 0; i < 33; i++) {
// cout << vec[i].second << " " << vec[i].first << endl;
// }
for (ll i = 0; i < 33 && k; i++) {
if (vec[i].second) {
res += (ll)pow(2, vec[i].first);
k--;
} else
break;
}
cout << res << endl;
}
}
Why my DP solution is giving WA for the last case ? All others passed though and its not a TLE also.
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t--){
int n,k;
cin>>n>>k;
vector<long long int> v(n);
for(int i=0;i<n;i++) cin>>v[i];
vector<vector<unsigned long long int>> dp(33,vector<unsigned long long int>(k+1));
for(int i=0;i<=32;i++){
for(int j=0;j<=min(k,i);j++){
if(i==0 || j==0) dp[i][j]=0;
else{
unsigned long long int sum = 0;
for(int tt=0;tt<n;tt++){
sum += (v[tt]>>(i-1))&1;
}
sum = pow(2,i-1)*sum;
if(i==j){
dp[i][j] = sum + dp[i-1][j-1];
}
else{
dp[i][j] = max(dp[i-1][j], sum + dp[i-1][j-1]);
}
}
}
}
// for(int i=0;i<32;i++){
// for(int j=0;j<=k;j++){
// cout<<dp[i][j]<<" ";
// }
// cout<<endl;
// }
unsigned long long num = 0;
int j = k;
for(int i=32;i>=1;i--){
if(dp[i][j] != dp[i-1][j]){
num += 1<<(i-1);
j--;
}
}
//cout<<endl;
cout<<num<<endl;
}
return 0;
}
You can visit the video editorial of this problem.
thanks for replying brooo!!! 
can you just tell me what wrong with my code
In setter’s solution. in this line:-
res.push_back(make_pair(count[i]*x,50-i));
why 50-i is getting pushed? why not only i working?
4 Likes
I submitted two codes yesterday and both of them were partially accepted.
Both the codes gave me a WA as verdict ( not TLE).
for _ in range(int(input())):
n,k = map(int,input().split())
a = list(map(int,input().split()))
m = len(bin(max(a))[2:])
s={}
for i in range(m):
x=0
for j in a:
if bin(j)[2:].rjust(m,'0')[-1*(i+1)]=='1':
x+=1
s[i] = x*(2**i)
s1 = sorted(s.items(), key=lambda x: x[1], reverse=True)
y=0
for i,j in s1:
y+=2**(i)
k-=1
if k<1:
break
print(y)
Later, in order to expand the scope of accuracy, I decided to re-sort the dictionary s1 for keys with the same value. ( Although, I guessed it was not needed since I traversed the bits from 0 to m ).
for _ in range(int(input())):
n,k = map(int,input().split())
a = list(map(int,input().split()))
m = len(bin(max(a))[2:])
s={}
for i in range(m):
x=0
for j in a:
if bin(j)[2:].rjust(m,'0')[-1*(i+1)]=='1':
x+=1
s[i] = x*(2**i)
s1 = sorted(s.items(), key=lambda x: x[1], reverse=True)
for i in range(m):
for j in range(i+1,m):
if s1[i][1]==s1[j][1] and s1[i][0]>s1[j][0]:
s1[i],s1[j]=s1[j],s1[i]
y=0
for i,j in s1:
y+=2**(i)
k-=1
if k<1:
break
print(y)
Why are any of these codes wrong?
@dean_student my solution passed sub task 2, but it is failing sub task 1. I am using long long. Please help.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector vi;
typedef vector vll;
typedef pair<int,int> pii;
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define rrep(i,a,b) for(int i=a;i>=b;–i)
#define fastio() ios::sync_with_stdio(0);cin.tie(0);
#define nl “\n”
#define wi(x) cerr << #x << " is " << x << nl
const double eps = 1e-6;
bool cmp(pair<ll,int> a,pair<ll,int> b){
if(a.ff == b.ff) return a.ss > b.ss;
return a.ff < b.ff;
}
void solve(){
int n,k; cin>>n>>k;
vi in(30,0);
rep(i,1,n){
int a; cin>>a;
rep(pos,0,29){
if(a & (1<<pos)) in[pos]++;
}
}
vector<pair<ll,int>> val(30);
rep(pos,0,29){
val[pos].ff = (1<<pos)*in[pos];
val[pos].ss = pos;
}
sort(all(val),cmp);
/rep(pos,0,29){
cout << val[pos].ss << " " << val[pos].ff << nl;
}/
vector<bool> out(30,false);
int pnt = 29;
rep(it,1,k) out[val[pnt--].ss] = true;
//rep(i,0,29) cout << out[i] << nl;
ll ans = 0;
rep(pos,0,29) if(out[pos]) ans += (1<<pos);
cout << ans << nl;
}
int main(){
fastio()
//int T=1;
int T; cin>>T;
while(T--) solve();
return 0;
}
Don’t know but it failed in test case same case where long long was required.
what is wrong in my code
#include <bits/stdc++.h>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define int long long
#define endl '\n'
#define MOD 1000000007
#define INF 10000000000000000
// find_by_order(), order_of_key()
#define oset tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define fastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define FORI(i,j,n) for(int i=j; i<n; i++)
#define FOR(i, n) FORI(i, 0, n)
#define all(a) a.begin(),a.end()
#define mp make_pair
#define vi vector<int>
#define ss second
#define pb push_back
#define ff first
#define pii pair<int,int>
#define vii vector<pii>
#define pq priority_queue<int>
#define pdq priority_queue<int, vi, greater<int> >
#define gethash(l, r) (MOD-(h[r+1]*p_pow[r-l+1])%MOD+h[l])%MOD;
using namespace __gnu_pbds;
using namespace std;
const int N = 5e5+4;
int arr[N];
int freq[32];
bool compare(pii p, pii q){
if(p.ff!=q.ff) return p.ff>q.ff;
else if(p.ff==q.ff && p.ss!=q.ss) return p.ss<q.ss;
}
void solve(int test){
int n, k;
cin>>n>>k;
memset(freq, 0, sizeof(freq));
FOR(i, n){
cin>>arr[i];
int j = 0;
while(j<32){
if(arr[i]&(1<<j)) freq[j]++;
j++;
}
}
int sum[32]={0};
vector<pii> pp(32);
FOR(i, 32) {
sum[i] = freq[i]*pow(2,i);
pp[i] = {sum[i], i};
}
sort(all(pp), compare);
int ans = 0;
FOR(i, k){
pii curr = pp[i];
ans+=pow(2, curr.ss);
}
cout<<ans<<endl;
}
signed main()
{
fastIO
int t;
cin>>t;
for(int i=0; i<t; i++){
solve(i);
}
return 0;
}DP BASED SIMPLE SOLUTION.
O(N) TIME COMPLEXITY.
#include <bits/stdc++.h>
using namespace std;
long long int b[31];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin>>t;
while(t--)
{
int n,k;
cin>>n>>k;
int a[n];
int i,j;
for(i=0;i<n;i++)
cin>>a[i];
memset(b,0,sizeof(b));
for(i=0;i<n;i++)
{
int x=a[i];
j=30;
while(x)
{
b[j]+=x%2;
x/=2;
j--;
}
}
long long int dp[32][k+1];
long long int ans[32][k+1];
for(i=0;i<32;i++)
{
dp[i][0]=0;
ans[i][0]=0;
}
long long int x=0;
for(i=0;i<=k;i++)
{
dp[0][i]=0;
ans[0][i]=x;
x=2*x+1;
}
for(i=1;i<=31;i++)
{
for(j=1;j<=k;j++)
{
dp[i][j]=0;
long long int xx=b[i-1]+2*dp[i-1][j-1];
dp[i][j]=max(2*dp[i-1][j],xx);
if(dp[i][j]==xx && dp[i][j]==2*dp[i-1][j])
ans[i][j]=min(2*ans[i-1][j],2*ans[i-1][j-1]+1);
else if(dp[i][j]==xx)
ans[i][j]=2*ans[i-1][j-1]+1;
else
ans[i][j]=2*ans[i-1][j];
}
}
cout<<ans[31][k]<<endl;
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define inf 1000000
#define ll long long int
const double pi = 3.14159265358979323846;
int main()
{
int t;
cin>>t;
while(t–)
{
ll n,sum1=0,sum2=0,k,maxi=0;
cin>>n>>k;
ll a[n];
for(int i=0;i<n;i++)
cin>>a[i];
priority_queue< pair<ll,pair<ll,ll> > >p;
for(ll i=0;i<=31;i++)
{
ll x=1<<i;
int c=0;
for(int j=0;j<n;j++)
{
if(x&a[j])
c++;
}
p.push(make_pair(c*x,make_pair(-x,x)));
}
ll ans=0;
while(k--)
{
ll y=p.top().second.second;
ans+=y;
p.pop();
}
cout<<ans<<endl;
}
}
what is wrong with that code?(it is partially accepted)
please help!!!
can i get test case of sub task 1??