New Virus Spread - Editorial

About the Problem

Setter(s) Neelam Bugalia
Tester(s) Vichitr Gandas, Balajiganpathi S, Divyansh Verma
Difficulty Cakewalk
Topics Bit Manipulation
Practice Link
Contest Link

Solution Idea

As asked in the problem, people can get infected from each other only if absolute difference of number of set bits in the natural powers of the two persons is less than or equal to 1. Hence start with first person, find number of set bits for him, lets say its x then all people with number of set bits x will get infected. Also all the people with set bits x-1 and x+1 get infected. So from x first we will move to x-1 , x-2 ,… and so on. If for some y, there are no people with set bits y then this chain will break and none of the people with set bits < k will get infected. Similarly from x we will also move in other side i.e. x+1, x+2 ,... and so on. If for some y , there are no people with set bits y then this chain will break and none of the people with set bits > k will get infected.
This can be achieved with first finding count of how many people with set bits x for all possible x . And then looping on them as explained above.

Complexity Analysis

Time Complexity: \mathcal{O}(n \log{n}) because of finding number of set bits for n people.
Space Complexity: \mathcal{O}(1) for storing count of people with set bits from 0 to 30.

Codes

Setter's Code
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
typedef long long int ll;
using namespace std;

int main()
{
    int t; cin>>t;
  	assert(t <= 1e5);
  	int tot = 0;
    while(t--){
        int n; cin>>n;
	  	assert(n <= 1e5);
	  	tot += n;
        vector<int> a(n);
        for(int i=0;i<n;++i){
            cin>>a[i];
		  	assert(a[i] >= 0 and a[i] <= 1e9);
		}
        vector<int> f(35, 0);
        for(int i=0;i<n;i++){
            int x = __builtin_popcount(a[i]);
            f[x]++;
        }
        int startBit =  __builtin_popcount(a[0]); 
        
        int ans = f[startBit];
        for(int i=startBit-1; i>=0;i--){
            if(f[i] > 0)
                ans += f[i];
            else
                break;
        }
        for(int i=startBit+1; i<35;i++){
            if(f[i] > 0)
                ans += f[i];
            else
                break;
        }
        cout<<ans<<'\n';
    }
  	assert(tot <= 2e5);
    return 0;
}

If you have used any other approach, share your approach in comments!
If you have any doubts, ask them in comments!

3 Likes

seems like i m in codechef discuss lol

It is standard discourse theme! Discourse platform looks like this only :stuck_out_tongue:

1 Like