POPGATES - Editorial

Can you solve this in O(n)?

PROBLEM LINK:

Practice
Div-2 Contest

DIFFICULTY:

Cakewalk

PREREQUISITES:

Ad-hoc

PROBLEM:

There are N coins and you process the last K coins starting from the right. Each time you process a coin, you should remove it and flip all remaining coins if the coin was showing heads. Find the number of coins showing heads in the end.

QUICK EXPLANATION 1

Do what the problem says directly in O(n^2).

QUICK EXPLANATION 2

We only need to check the k-th coin from the right and flip all coins if it shows heads. This works in O(n).

EXPLANATION 1:

After we process the last K coins, only the first N-K coins will remain. Note that it is unnecessary to remove the last K coins. We can keep the K coins and make sure that we only count the first N-K coins in the end.

To start with, we should iterate over the last K coins starting from the right. If we use 0-indexing, we will process coins from coin N-1 to coin N-K. We can write a for-loop for this:

for(int i=n-1; i>=n-k; --i) {
	//process coin i
}

We need an if-statement to check if coin i is heads:

for(int i=n-1; i>=n-k; --i) {
	//process coin i
	if(c[i]=='H') {
		//flip all coins
	}
}

We need an for-loop and a few if-statements to handle the cases when flipping the coins:

for(int i=n-1; i>=n-k; --i) {
	//process coin i
	if(c[i]=='H') {
		//flip all coins
		for(int j=0; j<n; ++j) {
			if(c[j]=='H')
				c[j]='T';
			else
				c[j]='H';
		}
	}
}

Lastly, we count the remaining coins showing heads, so we iterate over the first N-K coins and increment the answer if the coin shows heads:

int ans=0;
for(int i=0; i<n-k; ++i)
	if(c[i]=='H')
		++ans;

Processing a single coin takes O(n) time and we process up to O(n) coins, so the time complexity is O(n^2).

EXPLANATION 2:

We can notice that after processing coins N-1 to N-K, coin N-K must show tails. If, before processing coin N-K, it is heads, then we would flip all coins and coin N-K would end up showing tails. If coin N-K was already showing tails then no flips would happen, so it would end up also showing tails.

So, instead of checking all of the last K coins, we just need to check if coin N-K shows heads, and if so, we will flip all coins. Then, we will finish in the same way by counting the first N-K coins that show heads. This works in O(n).

SOLUTIONS:

Tester's Solution
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val
 
using namespace std;
using namespace __gnu_pbds;
 
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout) 
#define primeDEN 727999983
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
// find_by_order()  // order_of_key
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
 
int a[1234];
int main(){
    std::ios::sync_with_stdio(false); cin.tie(NULL);
    int t;
    cin>>t;
    while(t--){
    	int n,k;
    	cin>>n>>k;
    	int i;
    	string str;
    	rep(i,n){
    		cin>>str;
    		if(str=="H")
    			a[i]=1;
    		else
    			a[i]=0;
    	}
    	int flip=0;
    	rep(i,k){
    		a[n-1-i]^=flip;
    		flip^=a[n-1-i];
    	}
    	int ans=0;
    	f(i,k,n){
    		a[n-1-i]^=flip;
    		ans+=a[n-1-i];
    	}
    	cout<<ans<<endl;
    }
    return 0;   
}
Editorialist's Solution 1
#include <bits/stdc++.h>
using namespace std;

int n, k;
char c[100];

void solve() {
	//input
	cin >> n >> k;
	for(int i=0; i<n; ++i)
		cin >> c[i];

	//from right to left
	//last coin we remove will be n-k
	for(int i=n-1; i>=n-k; --i) {
		//process coin i
		if(c[i]=='H') {
			//flip all coins
			for(int j=0; j<n; ++j) {
				if(c[j]=='H')
					c[j]='T';
				else
					c[j]='H';
			}
		}
	}

	//count heads
	int ans=0;
	for(int i=0; i<n-k; ++i)
		if(c[i]=='H')
			++ans;
	cout << ans << "\n";
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int t;
	cin >> t;
	while(t--)
		solve();
}
Editorialist's Solution 2
#include <bits/stdc++.h>
using namespace std;

int n, k;
char c[100];

void solve() {
	//input
	cin >> n >> k;
	for(int i=0; i<n; ++i)
		cin >> c[i];

	//coin n-k should be T
	if(c[n-k]=='H') {
		for(int i=0; i<n; ++i) {
			if(c[i]=='H')
				c[i]='T';
			else
				c[i]='H';
		}
	}

	//count heads
	int ans=0;
	for(int i=0; i<n-k; ++i)
		if(c[i]=='H')
			++ans;
	cout << ans << "\n";
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int t;
	cin >> t;
	while(t--)
		solve();
}

Please give me suggestions if anything is unclear so that I can improve. Thanks :slight_smile:

9 Likes

@tmwilliamlin, I have doubt.

In the for-loop for flipping the coins, why is taken from j=0 to j<n? it should be j<i right? as we have to flip only the remaining coins and remove the coin at the right?

It doesn’t matter whether we choose j<i or j<n, since the state of the coins after i will not matter.

2 Likes

@tmwilliamlin wont the value of n-kth element determined by no of Heads in n-k to n-1 positions?

@tmwilliamlin , Is there any tricky part in this question, which can create mistakes.
My code seems to work correctly for the sample case but goes wrong in the submission.
Kindly let me know where I’m going wrong. Here is my code.

After processing coins n-1 to n-k+1, the value of coin n-k will depend on those coins, but after processing coin n-k, its value must be tails, as described in the editorial above.

1 Like

The last for-loop of your code must be from j=0 to j<=i.

:stuck_out_tongue:

1 Like

I kept two vectors of char, one with original input while another just opposite of it.
kept check which vector is of my interest, currently its original
I looped from end till k time, checked if it is H, then changed my current array to the opposite one.
since current array is changed so if I find H again, I change my current array to original one.

int the end I looped from 0 to k, counted the H in the array which was last current array of interest.
its O(n), right?

edit:
can also do without the need of another array, just keep check if you’re on the original array or fliiped one, check for H if one original array , and for T if one flipped one while performing the moves from end,(loops k times from end)

similarly if you were on the original array counter then count the number of H from 0 to arr[n-k-1] else count T if counter is on flipped array

I HAVE CHECKED NO OF HEADS FROM N-K TO N;
C=NO OF HEADS FROM N-K TO N;
AND CHECKED NO OF HEADS FROM START TO N-K;
C1=NO OF HEADS FROM START TO N-K;
C2=NO OF TAILS FROM START TO N-K;
IF (C IS EVEN )
PRINT C1
ELSE
PRINT C2

IS IT CORRECT?

I couldn’t run your code correctly https://ideone.com/hyC68q
It seems you are doing what Dastan is supposed to do physically with the coins. A lot of popping & counting. If all is good then this should be expensive code giving TLE at the end.

No, but if you change C = number of heads from coin n-k to n-k (which is either 0 or 1) then it will be correct.

Popping & counting should be fine, the constraints are set so that O(n^2) can pass.

/* AUTHOR : SHIVANK JAIN */

#include<bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false)
#define itt cin.tie(0)
#define now cout.tie(0)

using namespace std;

#define ll long long
#define li long int

#define pb push_back
#define io int i=0;i<n;i++
#define endl “\n”

#define fr first
#define se second
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define mp make_pair

#define BIG 1000000007

int main(){
fast;itt;now;

 int t; cin>>t;
 
 while(t--){
 	int n , k ; cin>>n>>k;
 	
 	vector<char> v(n);
 	
 	for(io){
 	  cin>>v[i];	
	}
	int k1 = k;
 	  int h1 = 0;
 	  int i = n - 1; 
 	while(k1){
 		if(v[i] == 'H')
 		 ++h1;
 		 --k1;
 		 --i;
	 }
	   int j = 0 , kk = n - k;
	   int h2  = 0 , t2 = 0; 
	   
	 while(kk){
 		if(v[j] == 'H')
 		 ++h2;
 		else
		 ++t2;
		--kk;
		++j;  
	 } 
	    
	 	 if(h1 % 2 == 0)
	 	  cout<<h2<<endl;
	 	 else
		  cout<<t2<<endl; 
 }

return 0;
}
WHAT IS WRONG IN THIS???

No it will fail when all coins are head

#include<bits/stdc++.h>
#include
using namespace std;
int main(void)
{

int t;
cin>>t;
while(t--)
{
	int i,j,n,c=0,k,c1=0,c2=0;
	char f;
	cin>>n>>k;
	for(i=0;i<n;i++)
	{
		cin>>f;
		//x.push_back(f);
		if(i<(n-k))
		{
			if(f=='H')
			c1++;
			else
			c2++;
		}	
		//cout<<"c1 "<<c1<<"c2 "<<c2<<endl;
		if(i>=(n-k))
		{
			if(f=='H')
			c++;
		}	
		
	}	
	if(c%2==0)
		cout<<c1<<endl;
	else
		cout<<c2<<endl;
}

}
THIS IS MY CODE BUDDY?
WHAT SHOULD I CHANGE?

I dont think this works!

In explanation 2, how it is possible that last k-1 coins are not effecting the final answer?
May you make it more clear…

why is the code given above wrong output when all head are there input. Please explain.
This is my code

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

int main() {
int t,i,n,k,j,head=0;
vector str;
char c;

cin>>t;

if(1<=t && t<=200)
{
for(i=0;i<t;i++)
{   
   str.clear();
   cin>>n>>k;
   if(n<=100 && k<=100 && 1<=n && 1<=k)
   //take the input of ith string
   {
   for(j=0;j<n;j++) 
   {  
      cin>>c;
      str.push_back(c);
   }
   
   
   
   while(k--)
   {
      
      if(str[--n]=='H') //used for flipping coins 
      {
         for(j=0;j<str.size();j++)
         {
            if(str[j]=='H')
              str[j]=='T';
            else
              str[j]=='H';
         }
      }
      
      
      str.pop_back();  //removes the last coin
      
   }
   
   n=str.size();
   
   for(j=0,head=0;j<n;j++) //for couting the heads
   {
      if(str[j]=='H')
      head++;
   }
   
   cout<<head<<endl;
   }
}
}
return 0;

}

@tmwilliamlin please help

can anybody tell me what’s wrong with my code