POPGATES - Editorial

editorial
, , , ,
50

#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> t;
while(t–)
{
int n,k,c=0,c1=0;
cin >> n;
cin >> k;
char a[n];
for(int i=0;i<n;i++)
cin >> a[i];
for(int i=n-k;i<n;i++)
{
if(a[i]==‘H’)
c++;
}
if(c%2==1)
{
for(int i=0;i<n-k;i++)
{
if(a[i]==‘T’)
c1++;
}
cout << c1 <<“\n”;
}
else
{
for(int i=0;i<n-k;i++)
{
if(a[i]==‘H’)
c1++;
}
cout << c1 <<“\n”;
}
}
}

why isnt this code working?[quote=“tmwilliamlin, post:1, topic:54846, full:true”]
To update before posting: difficulty, setter’s solution
Can you solve this in O(n)?

PROBLEM LINK:

Practice
Div-2 Contest

DIFFICULTY:

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:

Setter's Solution
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:
[/quote]

It is showing correct in the input test cases.

51

#Soloution in O(n) time complexity and O(1) space complexity

t=int(input())    
for i in range(t):
    n,k=map(int,input().split())
    arr=[i for i in input().split()]
    count=0
    index=n-1
    head,tails=0,0
    count=0
    k1=k
    while k1>0:
        if (arr[index]=='H' and count%2==0) or (count%2!=0 and arr[index]=='T'):
            count+=1
        k1-=1
        index-=1    

    for i in range(n-k):
            if arr[i]=='H':
                head+=1
            else:
                tails+=1

    if count%2==0:
        print(head)
    else:
        print(tails)
52

checkout this solution CodeChef: Practical coding for everyone which takes only O(n) by storing number of Heads occurred.

53

can you tell me how you get to the thought of checking a[n-k]==T or not.

54

Your logic is wrong: your code is counting ‘H’ or ‘T’ based on the number of coins removed, not the nature of those coins.

Eg:
1
6 3
H H H T T T

produces ‘0’. Whereas it should produce ‘3’.