# Doubt in College Life 5 - march CC starters(rated for div3)

In this question I am not able to get the correct answer for 1st test case…rest two test cases give the correct results…will someone pls tell me what the problem in my code is?

``````#include <iostream>
#include <vector>
using namespace std;

int main(){
int t;
cin >> t;
while(t--){
int nfo,mcr;
cin >> nfo >> mcr;
vector<int> football(nfo);
vector<int> cricket(mcr);
for(int i : football){
int x;
cin >> x;
football[i] = x;
}
for(int i : cricket){
int x;
cin >> x;
cricket[i] = x;
}
//0 - football and 1 - cricket
int f = 0,c = 0,curr = 0,sw = 0;
while(f != nfo && c != mcr ){
if((football[f] < cricket[c]) && curr == 0){
f++;
}else if((football[f] > cricket[c] )&& curr == 0){
c++;
sw++;
curr = 1;
}else if((football[f] < cricket[c]) && curr == 1){
f++;
sw++;
curr = 0;
}else if((football[f] > cricket[c]) && curr == 1){
c++;
}
}
while(f != nfo){
if(curr == 1){
sw++;
curr = 0;
f++;
}else{
f++;
}
}
while(c != mcr){
if(curr == 0){
sw++;
curr = 1;
c++;
}else{
c++;
}
}
cout << sw << endl;
}
return 0;
}`````````

I know I need to make it Long long…but I was just trying to satisfy the test cases…pls tell me what’s wrong with my logic/code…I have been trying this ques for 2 hrs now…pls help! You don’t need to make it long long, the problem constraints are fine. Just put all of the “important” event times in a single vector with indicators for football/cricket. Sort this and iterate over it to know the number of inversions.

Here is the code.

``````void testcase(){
int n,m;
cin >> n >> m;
vector<int> a(n),b(m);
vector<pair<int,int>> all;
for(int i = 0; i < n; i++){
cin >> a[i];
all.push_back({a[i],0});
}
for(int i = 0; i < m; i++){
cin >> b[i];
all.push_back({b[i],1});
}
sort(all.begin(),all.end());
int ans = 0,now = 0;
for(int i = 0; i < n+m; i++){
ans += all[i].second != now;
now = all[i].second;
}
cout << ans << "\n";
}
``````
1 Like

Also debugging you code is hard without indentation so maybe post a link to your submission or use ``` at the start and end of your code

@akanksha_2000 Please Format Your Code With ``` At Start And At End
Like This

``````#include
#include
// I included iostream and vector
using namespace std;

int main(){
int t;
cin >> t;
while(t–){
int nfo,mcr;
cin >> nfo >> mcr;
vector football(nfo);
vector cricket(mcr);
for(int i : football){
int x;
cin >> x;
football[i] = x;
}
for(int i : cricket){
int x;
cin >> x;
cricket[i] = x;
}
//0 - football and 1 - cricket
int f = 0,c = 0,curr = 0,sw = 0;
while(f != nfo && c != mcr ){
if((football[f] < cricket[c]) && curr == 0){
f++;
}else if((football[f] > cricket[c] )&& curr == 0){
c++;
sw++;
curr = 1;
}else if((football[f] < cricket[c]) && curr == 1){
f++;
sw++;
curr = 0;
}else if((football[f] > cricket[c]) && curr == 1){
c++;
}
}
while(f != nfo){
if(curr == 1){
sw++;
curr = 0;
f++;
}else{
f++;
}
}
while(c != mcr){
if(curr == 0){
sw++;
curr = 1;
c++;
}else{
c++;
}
}
cout << sw << endl;
}
return 0;
}

``````

Ok…I’ll format the code…I didn’t know that can be done

But…why to sort at all?..I mean…the question already says that the i/p array is in ascending order…and I used two pointer…very much like merge sort technique…what’s wrong in my code?  I mean…this approach should be correct ,right?
Also ,it has a tag of 2 pointers too…which I saw now…
Why should we merge both the vectors ,then pair it up with cricket/football?

ans += all[i].second != now;
What is done here?

Thanks for the code btw…
Pls tell me whats wrong with my approach?
I really want to learn…as I am a beginner in CP.

1 Like

Hi,
I have used a similar approach. Hope it helps.

https://www.codechef.com/viewsolution/44966309

1 Like

Here I am adding all the times when a new event occurs. a[i].second != now will be true when I get an event which has a tag different than that of now and then 1 will be added to my answer. It is the same as

``````if(a[i].second != now) ans++;
``````
1 Like

When you merge those two, all the times get lumped up together. So now you have a vector with all the events in ascending order of times. Then I just iterate over it to get the number of channel changes.

Oh wow…I didn’t know that if statement can be written like than in cpp…
great! hmm…Ok…I got you approach…but i wanted to know the fault in mine

Thanks…But i tried it in cpp,using the following code…
But it still doesn’t work for the 1st test case  ``````#include<vector>
using namespace std;

int main(){
int t;
cin >> t;
while(t--){
int nfo,mcr;
cin >> nfo >> mcr;
vector<int> football(nfo);
vector<int> cricket(mcr);
for(int i : football){
int x;
cin >> x;
football[i] = x;
}
for(int i : cricket){
int x;
cin >> x;
cricket[i] = x;
}
//0 - football and 1 - cricket
int f = 0,c = 0,curr = 0,sw = 0;
while(f != nfo && c != mcr ){
if((football[f] < cricket[c]) && curr == 0){
f++;
}else if((football[f] > cricket[c] )&& curr == 0){
c++;
sw++;
curr = 1;
}else if((football[f] < cricket[c]) && curr == 1){
f++;
sw++;
curr = 0;
}else if((football[f] > cricket[c]) && curr == 1){
c++;
}
}
if(f < nfo && curr == 1) sw++;
if(c  < mcr && curr == 0) sw++;
cout << sw << endl;
}
return 0;
}``````

This is the two pointer approach

``````void testcase(){
int n,m;
cin >> n >> m;
vector<int> a(n),b(m);
for(int i = 0; i < n; i++){
cin >> a[i];
}
for(int i = 0; i < m; i++){
cin >> b[i];
}
a.push_back(1e9 + 50);
b.push_back(1e9 + 50);
int i = 0,j = 0,now = 0,ans = 0;
while(i < n || j < m){
if(a[i] < b[j]){
if(now == 1)ans++;
now = 0;
i++;
}
else{
if(now == 0)ans++;
now = 1;
j++;
}
}
cout << ans << "\n";
}
``````

Are you sure that you are taking the input correctly ? Shouldn’t it be like this

``````for(int &i : cricket){
cin >> i;
}
``````

or

``````for(int i = 0; i < n; i++){
cin >> cricket[i];
}
``````

or

``````for(int i = 0; i < n; i++){
int x;
cin >> x;
cricket[i] = x;
}
``````

a.push_back(1e9 + 50);
b.push_back(1e9 + 50);
Why are these two done?

Well…This:
for(int i = 0; i < n; i++){
int x;
cin >> x;
cricket[i] = x;
}

Is similar to this:

for(int i : cricket){
int x;
cin >> x;
cricket[i] = x;
}

right? This is done to combat any out of index issues. I added two events at infinite times (Infinite as in that they are bigger than all input values). So that the statement `a[i] < b[j]` will never be true once I need the end of the array. Using this I won’t have to worry about whether I have left something at the end (which I assume you have done with additional while loops).

1 Like