June lunch time discussion

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 :slight_smile:

1 Like

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.

8 Likes

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.

1 Like

I have not solved…

Similar to a question on the hackerearth june circuits.

1 Like

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.

1 Like

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

1 Like

totally agree.

Well, I went till 64 bits, and passed the time limit very comfortably so ig your solution must have some bugs.

1 Like

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.

1 Like

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()