Can you solve this in O(n)?
PROBLEM LINK:
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 
