XxOoRr Codechef Solution

XxOoRr Codechef Solution

Given an array A1,A2…ANA1,A2…AN, find the minimum number of operations (possibly zero) required to convert all integers in AA to 00.

In one operation, you

  • choose a non-negative integer pp (p≥0p≥0),
  • select at most KK indices in the array AA, and
  • for each selected index ii, replace AiAi with Ai⊕2pAi⊕2p. Here, ⊕⊕ denotes bitwise XOR.

See Also : July Long Challenge 2021 Solutions Codechef

Input

  • The first line contains an integer TT – the number of test cases. Then TT test cases follow.
  • The first line of each test case contains two integers NN, KK – the size of the array and the maximum number of elements you can select in an operation.
  • The second line of each test case contains NN integers A1,A2…ANA1,A2…AN.

Output

For each test case, output the minimum number of operations to make all elements of the array 00.

Constraints

  • 1≤T≤1051≤T≤105
  • 1≤N,K≤1051≤N,K≤105
  • 0≤Ai≤1090≤Ai≤109
  • The sum of NN over all test cases does not exceed 2⋅1052⋅105

Subtasks

  • Subtask #1 (100 points): Original Constraints

Sample Input

1
3 2
3 6 10

Sample Output

5

Explanation

Here is one way to achieve [0,0,0][0,0,0] from [3,6,10][3,6,10] in 55 operations:

  1. Choose p=0p=0 and indices {1}{1}. Now AA becomes [2,6,10][2,6,10].
  2. Choose p=1p=1 and indices {1,2}{1,2}. Now AA becomes [0,4,10][0,4,10].
  3. Choose p=1p=1 and indices {3}{3}. Now AA becomes [0,4,8][0,4,8].
  4. Choose p=2p=2 and indices {2}{2}. Now AA becomes [0,0,8][0,0,8].
  5. Choose p=3p=3 and indices {3}{3}. Now AA becomes [0,0,0][0,0,0].

It can be shown that at least 55 operations are required.

Solution’s will be post with explanation. Join Us on Telegram for update

Explanation

Credit: Coder Guy

Solution

Program C++:

#include <stdio.h>
#include<bits/stdc++.h>
using namespace std;
typedef long long int nt;
void solve (vector<nt> &r,nt n)
{
    string s="";
    nt i,j=31;
    while(n>0)
    {
        s+=to_string(n%2);
        n/=2;
    }
        nt n1=s.size();
        for(i=0;i<n1;i++)
        {
            if(s[i]=='1')
            {
                r[j]+=1;
            }
            
            j--;
        }
        
    
}
int main()
{
    nt t,i,j;
    cin>>t;
    while(t--)
    {
        nt n,k;
        cin>>n>>k;
        vector<int> a(n);
        for(i=0;i<n;i++)
        cin>>a[i];
        
        vector<nt> r(32,0);
        for(i=0;i<n;i++)
        {
            solve(r,a[i]);
        }
        nt ans=0;
        for(i=0;i<32;i++)
        {
            if(r[i]==0)
            continue;
            else if(r[i]%k==0)
            {
                ans+=(r[i]/k);
            }
            else
            {
                ans+=(r[i]/k+1);
            }
        }
        cout<<ans<<"\n";
    }

    return 0;
}

July Long Challenge 2021 Solutions

Weekly Contest 247

Biweekly Contest 55

Codechef Long Challenge Solutions

June Long Challenge 2021 Solutions

March Long Challenge 2021 Solutions

April Long Challenge 2021 Solutions

February Long Challenge 2021

January Long Challenge 2021

November Challenge 2020 SOLUTION CodeChef

October Lunchtime 2020 CodeChef SOLUTIONS

Leave a Comment

Please Click on 1 or 2 Ads to help us run this site.
+