 # COLGLF5 - Editorial

Author: Daanish Mahajan
Tester: Rahul Dugar
Editorialist: Aman Dwivedi

Easy

# PREREQUISITES:

Two Pointers, Implementation

# PROBLEM:

You are given two arrays - F_1, F_2, \ldots, F_n, which denote the times when an important event happens in the football match. And similarly C_1, C_2, \ldots, C_m for cricket.

You sadly have the remote in hand. You start out by watching the El Clasico. But whenever an Important event happens in the sport which isn’t on the TV right now, you will be forced to switch to that sport’s channel, and this continues, i.e., you switch channels if and only if when an important event in the other sport happens.

Find the total number of times you will have to switch the channels.

# EXPLANATION:

We need to find the total number of times we have to switch the channel. A channel is switched whenever an important event happens in the sport which isn’t on the TV right now. We can implement it in many ways, one of the ways is to use the Two Pointer Approach.

Case 1: We are watching Football currently

Suppose we are at i^{th} index of Football event and at j^{th} index of Cricket Event. Since it is already mentioned in the constraints that F_i \neq C_j for any i and j. Hence there are two possibilities left.

• If F_i < C_j. It means that Football has some important event before the Cricket Event. Since currently, we are watching Football hence we need not switch the channel. We will increment i and repeat the above procedure again.

• If C_j < F_i. It means that Cricket has some important event before the Football Event. Since currently, we are watching Football hence we need to switch the channel. We will increment j and now we will be watching Cricket.

Case 2: We are watching Cricket currently

• If F_i < C_j. It means that Football has some important event before the Cricket Event. Since currently, we are watching Cricket hence we need to switch the channel. We will increment i and now we will be watching Football.

• If C_j < F_i. It means that Cricket has some important event before the Football Event. Since currently, we are watching Cricket hence we need not switch the channel. We will increment j and repeat the same procedure again.

What happens when all the important events of one of the sport are completed ?

In this case, we will be watching those sports currently and since the important events are about to come for the other sports hence we are forced to switch the channel. However, once we switched the channel we need to switch the channel again as all the important events of other sport are completed.

By following the above approach we will be find the number of times we need to switch the channel and finally we will output this number.

# TIME COMPLEXITY:

O(N+M) per test case

# SOLUTIONS:

Setter
``````#include <bits/stdc++.h>
#define pb push_back
#define ll long long int
#define pii pair<int, int>

using namespace std;

int main(){
int t; cin >> t;
while(t--){
int n, m; cin >> n >> m;
vector<pii> v; v.clear();
for(int i = 0; i < n; i++){
int x; cin >> x;
v.pb(make_pair(x, 1));
}
for(int i = 0; i < m; i++){
int x; cin >> x;
v.pb(make_pair(x, 2));
}
sort(v.begin(), v.end());
int p = 1, ans = 0;
for(int i = 0; i < n + m; i++){
if(v[i].second != p){
ans++; p = v[i].second;
}
}
cout << ans << endl;
}
}
``````
Tester
``````#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifndef rd
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef double f80;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<ll,ll> pll;
#define double long double
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const int infi=0x3f3f3f3f;
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int mod=998244353;
//const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
uniform_int_distribution<int> uid(0,lim-1);
return uid(rang);
}
int powm(int a, int b) {
int res=1;
while(b>0) {
if(b&1)
res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}

long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);

assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
}
long long readIntLn(long long l,long long r){
}
}
}

int f,c;
int sum_n=0,sum_m=0;
void solve() {
sum_n+=n;
sum_m+=m;
assert(sum_n<=200000&&sum_m<=200000);
fr(i,1,n)
if(i!=n)
else
fr(i,1,m)
if(i!=m)
else
vector<pii> a;
fr(i,1,n)
a.pb({f[i],0});
fr(i,1,m)
a.pb({c[i],1});
sort(all(a));
int last=0,ans=0;
for(auto i:a) {
if(i.se!=last) {
ans++;
last=i.se;
}
}
cout<<ans<<endl;
}

signed main() {
ios_base::sync_with_stdio(0),cin.tie(0);
srand(chrono::high_resolution_clock::now().time_since_epoch().count());
cout<<fixed<<setprecision(1);
//	cin>>t;
fr(i,1,t)
solve();
assert(getchar()==EOF);
#ifdef rd
cerr<<endl<<endl<<endl<<"Time Elapsed: "<<((double)(clock()-clk))/CLOCKS_PER_SEC<<endl;
#endif
}

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

#define int long long

void solve()
{
int n,m;
cin>>n>>m;

int f[n],c[m];

for(int i=0;i<n;i++)
cin>>f[i];

for(int i=0;i<m;i++)
cin>>c[i];

int l1=0,l2=0;

int flag=0;

int ans=0;

while(l1<n && l2<m)
{
if(f[l1]<c[l2])
{
if(flag)
{
ans++;
flag=0;
}

l1++;
}
else
{
if(!flag)
{
ans++;
flag=1;
}

l2++;
}
}

ans++;

cout<<ans<<"\n";
}

int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);

int t;
cin>>t;

while(t--)
solve();

return 0;
}

``````
5 Likes

i have done this problem using queues and got AC correct answer
is my approach correct int main()

{

``````int t;

cin >> t;

while (t--)

{

int n, m;

cin >> n >> m;

queue<int> f;

queue<int> c;

for (int i = 0; i < n; i++)

{

int ans;

cin >> ans;

f.push(ans);

}

for (int i = 0; i < m; i++)

{

int sd;

cin >> sd;

c.push(sd);

}

int req = 1; //football;

int count = 0;

for (int i = 1; i <= n * m; i++)

{

if (f.front() < c.front())

{

int target = 1;

if (req != target)

{

count++;

req = target;

}

f.pop();

}

else if (c.front() < f.front())

{

int target = 0;

if (req != target)

{

count++;

req = target;

}

c.pop();

}

if (f.empty())

{

if (req == 1)

{

count = count + 1;

}

break;

}

else if (c.empty())

{

if (req == 0)

{

count = count + 1;

}

break;

}

}

cout << count << endl;

}

return 0;
``````

}

My logic in short is that :
combine two arrays F and C given in sorted order using two pointers . and all elements of C have a negative sign
eq F=1 3 5 7
C=2 4 6

combined = 1,-2,3,-4,5,-6,7
now , number of times the sign changes is the answer and if the start itself is -ve , add 1 to the answer
so in this case , answer is 6

This isn’t giving correct answer . I don’t understand which cases are missed or whats wrong in my logic.

4 Likes
```````int main(){
speedUP();
ll t; cin >> t;
while(t--){
ll n, m; cin >> n >> m;
set<ll> arr;
for(ll i = 0; i < n; i++){
ll x; cin >> x;
arr.insert(x);
}
for(ll i = 0; i < m; i++){
ll x; cin >> x;
arr.insert(x);
}
ll s1 = *arr.begin(), s2 = *arr.begin();
//debug(s1,s2);
ll cnt = 0, curr = 1, yo = s1;
if(s2 < s1){
cnt++;
curr = 0;
yo = s2;
}

while(1){
if(arr[curr].upper_bound(yo) == arr[curr].end())break;
ll el = *arr[curr].upper_bound(yo);
//debug(el,yo,curr);
yo = el;
curr = !curr;
cnt++;
}
print(cnt);
}
``````

}`
Keeping the track of time using sets! This implementation looks nice and I learnt from HealthyUg from one of his submissions lol!

1 Like
``````#include<iostream>
#include<cmath>
#include<cstdlib>
#include<cctype>
#include<algorithm>
#include<limits>
#include<vector>
#include<stack>
#include<string>
#include<deque>
#include<set>
#include<list>
#include<bitset>
#include<ctime>
#include<functional>
#include<numeric>
#include<cfloat>
#include<sstream>
#include<complex>
#include<queue>
#include<cstring>
#include<stdexcept>
#include<utility>
#include<map>
#include<fstream>
#include<iomanip>
#include<cassert>
using namespace std;

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>>m;
int f[n], c[m];
for(int i=0;i<n;i++) cin>>f[i];
for(int i=0;i<m;i++) cin>>c[i];
int *present=f;
int *prev=f;
int a=0,b=0,count=0;
for(int i=0;i<m+n;i++)
{
if(f[a]<c[b])
{
if(a<n)
++a;
present=f;
if(prev!=present)
count=count+1;
}
else if(f[a]>c[b])
{
if(b<m)
++b;
present=c;
if(prev!=present)
count=count+1;
}
else if(f[a]==c[b])
{
if(prev=f)
{
present=c;
++a;
count=count+1;
}
else
{
present=f;
++b;
count=count+1;
}
}
else
{
;
}
prev=present;
}
cout<<count<<"\n";
}

return 0;
}
``````

can any one tell why my coe is giving wrong answer or can you give some testcases? 1 Like

#include <stdio.h>

#include <stdlib.h>

int main()

{

``````int t;

scanf("%d", &t);

while (t--)

{

int n, m;

scanf("%d %d", &n, &m);

long long *f = (long long *)malloc(sizeof(long long) * n);

long long *c = (long long *)malloc(sizeof(long long) * m);

for (int i = 0; i < n; i++)

{

scanf("%llu", &f[i]);

}

for (int i = 0; i < m; i++)

{

scanf("%llu", &c[i]);

}

/////////////////////////////////////////

int *finalArr = (int *)malloc(sizeof(int) * (m + n));

int i = 0, j = 0, k = 0;

while (i <= n && j <= m)

{

if (f[i] < c[j])

{

finalArr[k] = f[i];

i++;

}

else

{

finalArr[k] = -c[j];

j++;

}

k++;

}

while (i != n)

{

finalArr[k] = f[i];

i++;

k++;

}

while (j != m)

{

finalArr[k] = -c[j];

j++;

k++;

}

int intial = 1, count = 0;

for (int i = 0; i < m + n; i++)

{

if (finalArr[i] < 0 && intial == 1)

{

count++;

intial = 0;

}

else if (finalArr[i] > 0 && intial == 0)

{

count++;

intial = 1;

}

}

printf("%d\n", count);

}
``````

}

Thanks For giving me the logic…I think if intially we to jump to cricket if(c < f) then we have to count ++ extra…i got ac with your approach…mtlb ki agr suru mei hi apn ko switch krna pada toh ek extra count++ krna hoga kyuki humari array intially hi - ve thi…isliye maine code mei alg variable banaya jismei intial value 1 rkhi…ek baar mera code dekh lena shyad kuch madad mile tumhe…again Thanks for sharing your approach.

thanks brother for your help hey manish ,can you tell any other problem with my code because still i ma getting wrong answer , help me out brother.

your code is giving runtime error

Most Easy Solution —>

``````#include<bits/stdc++.h>
``````

using namespace std;
bool comp(pair<int,int> p1,pair<int,int> p2)
{
return p1.first<p2.first;
}
int main()
{
int t;
cin>>t;
while(t–)
{
int n,m;
cin>>n>>m;
vector<pair<int,int>> Q;
pair<int,int> p;
int temp;
for(int i=0;i<n;i++)
{
cin>>temp;
p=make_pair(temp,0);
Q.push_back§;

``````		}
for(int i=0;i<m;i++)
{
cin>>temp;
p=make_pair(temp,1);
Q.push_back(p);
}
int c=0;
sort(Q.begin(),Q.end(),comp);
int ch=0;
for(int i=0;i<Q.size();i++)
{
if(Q[i].second!=ch)
{

c++;
ch=(!ch);
}
}
cout<<c<<endl;
}
``````

}

#include<bits/stdc++.h>
#define ll long long int
#define endl ‘\n’
#define all(x) x.begin(), x.end()
#define alld(x) x.begin(), x.end(), greater()
#define MOD 1000000007;
using namespace std;
void printVll(vector arr){
for(ll i = 0;i < arr.size();i++)
cout << arr[i] << " ";
cout << endl;
}
vector getVll(ll n){
vector v(n);
for(ll i = 0;i < n;i++)
cin >> v[i];
return v;
}

int main(){
ios_base :: sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll tt = 1;
cin >> tt;
while(tt–){
ll n,m;
cin >> n >> m;
queue c,f;
ll time;
for(ll i = 0;i < n;i++){
cin >> time;
f.push(time);
}
for(ll i = 0;i < m;i++){
cin >> time;
c.push(time);
}
ll ans = 0;
int flag = 1;
while(!c.empty() && !f.empty()){
while(f.front() < c.front() && !f.empty()){
f.pop();
}
if(!c.empty())ans++;
if(c.empty() || f.empty())break;
while(c.front() < f.front() && !c.empty()){
c.pop();
}
if(!f.empty())ans++;
}
cout << ans << endl;
}
return 0;
}

#include <stdio.h>

#include <stdlib.h>

int main()

{

``````int t;

scanf("%d", &t);

while (t--)

{

int n, m;

scanf("%d %d", &n, &m);

long long *f = (long long *)malloc(sizeof(long long) * n);

long long *c = (long long *)malloc(sizeof(long long) * m);

for (int i = 0; i < n; i++)

{

scanf("%llu", &f[i]);

}

for (int i = 0; i < m; i++)

{

scanf("%llu", &c[i]);

}

/////////////////////////////////////////

int turn = 1, count = 0;

int i = 0, j = 0;

while (i != n && j != m)

{

if (f[i] < c[j] && turn == 2)

{

count++;

i++;

turn = 1;

}

else if (f[i] < c[j] && turn == 1)

{

i++;

}

else if (c[j] < f[i] && turn == 1)

{

count++;

j++;

turn = 2;

}

else

{

j++;

}

}

if (i == n && turn == 1)

{

count++;

}

else if (j == m && turn == 2)

{

count++;

}

printf("%d\n", count);

}
``````

}

// bs turn change krna h or intially football ka turn hoga (==1)
// it just like merge alogrithm.

why we have to increase ans by +1?
I also think of that same approach & I have to also increase it but why

What happens when all the important events of one of the sports are completed? Let us suppose all the important events of Cricket had been completed.

• It means that currently on TV we are watching Cricket.
• Since the important events of Football are not finished and hence we need to switch our channel. Once we switch the channel to Football, we need not to switch the channel again as all the Cricket Events are done.
1 Like

I guess bro…Bcoz one of my also get AC using queues  i have done this problem using binary search in python and got AC correct answer.
Simple Solution ``````from bisect import bisect_left
def BinSearch(a, x):
i = bisect_left(a, x)
if i != len(a) and a[i] == x:
return i
else:
return -1
for _ in range(int(input())):
n,m=map(int,input().split())
arr=sorted(list(map(int,input().split())))
brr=sorted(list(map(int,input().split())))
c=sorted(arr+brr)
cnt=0
flag=False
for i in range(len(c)):
x=BinSearch(brr,c[i])
if(x!=-1):
if(flag==False):
cnt+=1
flag=True
else:
if(flag==True):
cnt+=1
flag=False
print(cnt)
``````