HackerEarth Lights problem solution

In this HackerEarth Lights problem solution there are N lights, numbered from 1 to N. Initially all of them are switched off. We will consider M days. We represent the state of each day as a string of length N, whose ith character is 1 if the ith light on that day was switched on, and 0 otherwise. Each day one of the following things will happen:

L R: All the lights numbered from L to R are flipped, i.e, lights are turned off if they were switched on and vice versa.

A B L R: For each light from L to R, count on how many days from Ath day to Bth day, this light was on (Let it be x). Print how many lights (from L to R) are there which were switched on a total odd number of days (i.e, x mod 2 = 1). Also, print the minimum id of light (from L to R), which was switched on a total odd number of days (considering from Ath day to Bth day). The state of lights does not change in this type of query.

Considering states of all the days till now, which day had the lexicographically largest state (if multiple, print the earliest day). The state of lights does not change in this type of query.

HackerEarth Lights problem solution.

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define endl "n"
#define fr(i,n) for(i=1;i<=n;++i)

const ll N = 100000;
const ll M = 10001;

bitset<N> pre[M], cur, tp, mx;

int main()
{
    ll i,n,m,l,r,a,b,tp2,t,id;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        cur = 0, pre[0] = 0, mx = 0, id = 0;
        fr(i,m)
        {
            cin>>l;
            if(l==1)
            {
                cin>>l>>r;
                l--, r--;
                tp=0, tp.flip();
                tp >>= (N-(r-l+1));
                tp <<= l;
                cur ^= tp;
                
                tp = cur^mx;
                tp2 = tp._Find_first();
                if(tp2>=0 && tp2<N && mx[tp2]==0)
                    mx = cur, id = i;
 
                pre[i] = pre[i-1]^cur;
            }
            else if(l==2)
            {
                cin>>a>>b>>l>>r;
                l--, r--;
                pre[i] = pre[i-1]^cur;
                tp = pre[b]^pre[a-1];
                tp <<= (N-r-1);
                tp >>= (N-(r-l+1));
                tp2 = tp.count();
                if(tp2>0)
                    cout<<tp2<<" "<<tp._Find_first()+l+1<<endl;
                else
                    cout<<tp2<<" "<<0<<endl;
            }
            else
            {
                pre[i] = pre[i-1]^cur;
                cout<<id<<endl;
            }
        }
    } 
    return 0;
}

Second solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 1e3 + 14;
bool state[maxn][maxn], ps[maxn][maxn];
int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n, m;
        cin >> n >> m;
        int best = 0;
        for(int day = 1; day <= m; day++){
            int t;
            cin >> t;
            memcpy(state[day], state[day - 1], n);
            if(t == 1){
                int l, r;
                cin >> l >> r;
                l--;
                for(int i = l; i < r; i++)
                    state[day][i] = !state[day][i];
                if(memcmp(state[best], state[day], n) < 0)
                    best = day;
            }
            for(int i = 0; i < n; i++)
                ps[day][i] = ps[day - 1][i] ^ state[day][i];
            if(t == 2){
                int a, b, l, r;
                cin >> a >> b >> l >> r;
                l--;
                a--;
                int cnt = 0, left_most = -1;
                for(int i = l; i < r; i++)
                    if(ps[b][i] != ps[a][i]){
                        cnt++;
                        if(left_most == -1)
                            left_most = i;
                    }
                cout << cnt << ' ' << left_most + 1 << 'n';
            }
            else if(t == 3)
                cout << best << 'n';
        }
    }
}

HackerEarth Lights problem solution

HackerEarth Lights problem solution.

Second solution

Leave a Reply

Pages

Practice