XxOoRr Codechef Solution

by

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

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

Leave a Comment

nineteen − 5 =