PROBLEM LINK:
Setter: Hasan Jaddouh
Tester: Teja Vardhan Reddy
Editorialist: Teja Vardhan Reddy
DIFFICULTY:
PREREQUISITES:
Simulation.
PROBLEM:
In a multiple choice exam of n questions, you are given correct answers to the questions and answers marked by chef are given strings s and t of length n each respectively. Each of the answer can be either A,B,C or D. If chef does not answer a question we represent it with N. Now we start evaluating Chef’s questions from 1 st one. whenever Chef’s answer is correct, we give him one point. If its wrong, we give him zero points and as a penalty will not evaluate his next question irrespective of whether its correct or wrong.
EXPLANATION
We do exactly what the statement suggests.
We will iterate on the answers of chef from 1 st question to last question.
- whenever answer by Chef is N,we do not change the score and if we currently evaluated i th question we will move to (i+1) th question.
- whenever answer is correct, we add 1 to his score and if we currently evaluated i th question we will move to (i+1) th question.
- whenever its wrong, we do not change the score and if we currently evaluated i th question we will move to (i+2) th question.
TIME COMPLEXITY
O(n). Since we iterate over all the questions once,and checking each of the three cases takes O(1) time.
SOLUTIONS:
Setter's Solution
#include <iostream>
#include <algorithm>
#include <string>
#include <assert.h>
using namespace std;
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
assert(cnt>0);
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
int T;
string s,t;
int n;
int main(){
//freopen("00.txt","r",stdin);
//freopen("00o.txt","w",stdout);
T=readIntLn(1,100);
while(T--){
n=readIntLn(1,100);
s=readStringLn(n,n);
t=readStringLn(n,n);
for(int i=0;i<n;i++){
assert(s[i]=='A' || s[i]=='B' || s[i]=='C' || s[i]=='D');
assert(t[i]=='A' || t[i]=='B' || t[i]=='C' || t[i]=='D' || t[i]=='N');
}
int score=0;
for(int i=0;i<n;i++){
if(t[i]=='N')continue;
if(t[i] != s[i]){
i++;
continue;
}
score++;
}
cout<<score<<endl;
}
assert(getchar()==-1);
}
Tester's Solution
//teja349
#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 main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int t;
cin>>t;
while(t--){
int i;
int n;
cin>>n;
string exp,out;
cin>>exp;
cin>>out;
int cnt=0;
rep(i,n){
if(out[i]=='N'){
continue;
}
if(exp[i]==out[i]){
cnt++;
}
else{
i++;
}
}
cout<<cnt<<endl;
}
return 0;
}
Feel free to Share your approach, If it differs. Suggestions are always welcomed. 
