COW3B-EDITORIAL

editorial
, , , ,
1

PROBLEM LINK :

Practice
Contest

Author: Himanshu Manwani
Tester: Himanshu Manwani
Editorialist: Debrup Mandal

DIFFICULTY:

Easy

PREREQUISITES:

Basic idea, Array Traversal, Maps

PROBLEM:

Find the number of bilateral segments in A with respect to B.
Bilateral segment of a sequence A is a list of consecutive numbers such that each of these is present in the other given sequence B.
The segments must be maximal in nature.

EXPLANATION:

The idea behind the solution is simple. We keep a track of each instance when we either start traversing a new segment or finish traversing it.

This way, each time you enter a bilateral segment, you would have had an EVEN number of such instances before. Say you’ve 0 instances before the first one, 2 before the
second one(since you’ve entered and left a bilateral segment exactly once before)
, 4 times before the third one and so on. Similarly, each time you leave a segment,
you would have had an ODD number of prior instances, say you’ve one entry before the first exit, 2 entries and 1 exit,i.e 2+1=3 instances before the second exit and so on.
And we’re basically done.

We initialize a variable count=0 We maintain a visited array for every element in the second array B.Now we traverse the array A, and every time we encounter a visited element, we increment the count if it was even currently EVEN. Similarly, for each leaving instance, i.e when we encounter a non-visited element after a segment of visited ones, we check the count. If the count is ODD then we increment it.

And now we know that we’ve incremented the count for both entry and exit,i.e twice for every required segment we encountered. To account for both even and odd numbers, we add 1 to the current value and divide it by 2, and there you go! The answer is given by (count+1)/2 .

simple solutions are possible .

SOLUTIONS:

Setter's Solution 
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
using ll = long long;
 
 
bitset<10000007> bt;  
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int t; cin>>t;
    while(t--)
    {
        int n,m;   cin>>n;
        vector<int> arr(n);  // main array , component array.
        for(int i =0;i<n;i++)
        {
            cin>>arr[i];
        }
        cin>>m;
        vector<int> co(m);
        bt.reset();
        for(int i = 0;i<m;i++)
        {
            cin>>co[i];
            bt[co[i]] = 1;
        }
        int ans = 0;
        for(int i =0;i<n;i++)
        {
            if(bt[arr[i]] == 1 && ans % 2==0)
            {
                ans++;
            } 
            if(bt[arr[i]]==0 && ans%2 == 1)
            {
                ans++;
            }
        }
        cout << (ans+1)/2 << "\n";
    }
}
1 Like