Since we flip all coins in one operation, each coin is either always the same as coin n-k or always different from coin n-k. So, the answer depends on the final state of coin n-k. From the editorial, coin n-k will always end up tails no matter what the last k-1 coins are.
Guys can you please tell me what is wrong with this code???
my testcases(the testcases mentioned in the question) all passed but the task from codechef failed.
def count_H_T(arr):
return arr.count('T'), arr.count('H')
if __name__ == '__main__':
testcases = int(input())
for i in range(testcases):
n, k = map(int, input().split())
arr = input().split()
T_count_1st_half, H_count_1st_half = count_H_T(arr[:(n-k)])
T_count_2nd_half, H_count_2nd_half = count_H_T(arr[(n-k):])
if H_count_2nd_half%2==0 or H_count_2nd_half==0:
print(H_count_1st_half)
else:
print(T_count_1st_half)
from sys import stdin
for _ in range(int(stdin.readline())):
n,k = map(int,stdin.readline().split())
c = list(map(str,stdin.readline().split()))
tmp = 'H'
for i in range(n-1,n-k-1,-1):
if c[i]=='H' and tmp=='H':
tmp = 'T'
elif c[i]=='T' and tmp=='T':
tmp = 'H'
print(c[:n-k].count(tmp))
I doubt that I have improper English and grammar (at least, not to the point that makes my explanations incomprehensible). I did make a typo, though. In the second line of explanation 2, I have changed “it heads” into “it is heads”. If you think that any other parts are incorrect then please point them out instead of just saying that I have improper English and grammar.
By the way, you have some obvious grammar mistakes:
The “g” in “grammar” should not be capitalized as “grammar” is a common noun and not a proper noun.
There is no “the” before “Explanation”.
There should be a space between “Explanation” and “2” as “Explanation2” does not make sense as a single own word.
I think what he was trying to say is that it doesn’t depend on the parity of switches until the n-kth coin. Because if the number of switches are even, it would stay as is. so when its a head we output n(tails) since parity becomes odd, and n(heads) if its tails, since parity remains even. If the number of switches are odd, then it would be the opposite of what it is. So if it was initially a tail, it becomes a head and flips again, making the parity even, and if it was initially a head, then now its a tail, and the parity remains odd. It is obvious that the answer is only affected by parity which is only dependent on the n-kth coin, since the parity is odd when the n-kth coin is a head, and even when the n-kth coin is a tail.
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)?
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:
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
[/quote]
#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)
