Anyone plz discuss third question of div2
Am i doing something wrong in sorting vector of pairs,please help
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define inf 10e7
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
#define print(a,n) for(ll i=0;i<n;i++){cout<<a[i]<<" ";}cout<<"\n";
#define printpair(a,n) for(ll i=0;i<n;i++){cout<<a[i].first<<" "<<a[i].second<<"\n";}cout<<"\n";
#define init0(a,n) for(ll i=0;i<n;i++){a[i]=0;}
string binary(ll n){
string ans="";
if(n==0){
ans="0";
return ans;
}
while (n!=0)
{
if(n%2==0){
ans='0'+ans;
}
else
{
ans='1'+ans;
}
n=n/2;
}
ll dif=30-ans.size();
for(ll i=0;i<dif;i++){
ans='0'+ans;
}
return ans;
}
void bubbleSort(ll arr[],ll arr2[], int n)
{
int i, j;
for (i = 0; i < n-1; i++)
// Last i elements are already in place
for (j = 0; j < n-i-1; j++)
if (arr[j] > arr[j+1])
swap(&arr[j], &arr[j+1]);
}
void solve(){
ll n,k;
cin>>n>>k;
ll a[n];
for(ll i=0;i<n;i++){
cin>>a[i];
}
string s[n];
for(ll i=0;i<n;i++){
s[i]=binary(a[i]);
}
//print(s,n);
ll cnt[30];
init0(cnt,30);
for(ll i=0;i<n;i++){
for(ll j=0;j<30;j++){
if(s[i][j]=='1'){
cnt[j]+=1;
}
}
}
//print(cnt,30);
vector<pair<ll,ll>> vect;
for(ll i=0;i<30;i++){
pair<ll,ll> p;
p.second=n-i-1;
ll z=n-i-1;
p.first=cnt[i]*pow(2,z);
//cout<<p.first<<"##"<<p.second<<"\n";
vect.push_back(p);
}
sort(vect.begin,vect.end);
//printpair(vect,30);
ll answer=0;
for(ll i=0;i<k;i++){
answer=answer+vect[i].first;
}
cout<<answer<<"\n";
}
int main()
{
//fastio
ll t;
t=1;
//cout<<binary(10);
cin>>t;
while(t--)
{
solve();
}
}
Can say that you could have solved it
I dont know why the quality of problems is so poor here at codechef , Nothing other than optimisation is there in this lunchtime, all the first 3 div1 problems just based on tricky optimisations and nothing else one problem was even copied this round must be unrated and I think problem setting has to be improved here. Why time limit on Problem 3 that is squared submatrices was so tight that even some heavy input will let us get TLE in lasts substask last case.
SUck codechef and suck everytime , never ever try learning from your mistake and allow plagiarism, nowadys setters are also doing plagiarism that is ridiculous.
Got AC is subtask 1 using bruteforce. Used algo for finding the next number with the same number of bits till pow(2,30). Giving TLE in the second subtask though.
I have not solved…
Similar to a question on the hackerearth june circuits.
I got subtask 2 correct for Maximum AND and failed subtask 1. Why is that?
I solved the second subtask and still don’t understand why my logic fails the first case.
Any one please discuss the squared subsequence problem?
what did i do wrong in this code??
def binary(array,k):
bits = [0 for i in range(32)]
for i in range(len(array)):
j = 31
while array[i]!=0:
a = array[i]%2
array[i] = array[i]//2
bits[j] += a
j -=1
j =0
for i in range(len(bits)-1,-1,-1):
bits[i] = bits[i]*pow(2,j)
j +=1
ans = 0
while k !=0:
max1 = 0
index =0
for i in range(len(bits)):
if bits[i]>max1:
max1 = bits[i]
index = i
if max1==0:
break
ans += pow(2,len(bits)-1-index)
bits[index] = -1
k -=1
return ans
t= int(input())
for _ in range(t):
n,k = input().split()
n = int(n)
k = int(k)
array = [int(temp) for temp in input().split()]
print(binary(array,k))
will the brute force approach for square subsequence solve first sub task ?
Idk what was the time complexity of my answer, couldn’t get it correct tho.
Plz discuss ur logic whatever u have solved
If you’re looking for the approach then just find contribution of each bit, and set those bits in ans which contribute more greedily
totally agree.
Well, I went till 64 bits, and passed the time limit very comfortably so ig your solution must have some bugs.
For each bit store its frequency, i.e, number of times the bit is set in the input. Then calculate prod[i] = (freq of bit i) * (pow(2,i)). The top k indices having the highest prod will be set in the result.
Here, we’re looking at setting which bit will have maximum contribution in sum S.
Did the exact same thing. Got subtask 2 correct but failed subtask 1. Any idea why is that happening?
can someone help me debug code for second problem. I just can’t figure out what I am missing in here.
t = int(input())
for i in range(t):
n = int(input())
flag = 0
A = [int(j) for j in input().split()]
mapp = dict.fromkeys(A,0)
v1,v2,R = [],[],[]
for i in range(n):
mapp[A[i]] = mapp[A[i]] + 1
if (mapp[A[i]] == 1) :
v1.append(A[i])
elif(mapp[A[i]] == 2):
v2.append(A[i])
else :
flag = 1;
print("NO");
break;
if(flag == 0):
v1.sort();v2.sort(reverse = True);
R = v1 + v2
if(len(v2) != 0):
if(v1[-1] == v2[0]):
print("NO")
break;
print("YES")
for i in R:
print(i,end = " ")
print()