 # PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Setter: Hasan Jaddouh

Tester: Teja Vardhan Reddy

Editorialist: Teja Vardhan Reddy

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.

1. 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.
2. 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.
3. 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. 1 Like

Problem is not available for practice yet

8 Likes

I actually applied the same logic till 0 to n-2 position .
but for n-1 th position I checked separately if `a[n-1]==b[n-1]` as the last answer is never discarded.
(silly mistake ) ^___^ I did the same thing, it was little confusing.

I have also done the same thing, which wasted my 1hr in this question and still can’t get AC

I also did the same thing. Can you please tell me what’s wrong with that ?

when both last elements are matched then point is incremented . if they’re not matching simply skip. show me your code if you need help

#include
using namespace std;
int main()
{
int t,n,count,i,j;
cin>>t;
for(int k=0;k<t;k++)
{
count=0;
cin>>n;
char s,u;
for(int m=0;m<n;m++)
{
cin>>s[m];
}
s[n]=’\0’;
for(int m=0;m<n;m++)
{
cin>>u[m];
}
u[n]=’\0’;
for(i=0;i<n-1;i++)
{
if(u[i]!=‘N’)
{
if(u[i]==s[i])
{
count++;
}
else
{
i++;
}
}
}
if(u[n-1]==s[n-1])
count++;
cout<<count;
}
}

there is a case where n-2 is wrong answer and the n-1 index needed to skip but your loop runs until n-1 . so after loop ends the if condition is checked without checking if its index i is at last element or not . so the modification in your code be this and make a new line before running another case.

``````if (u[i] == s[i] && i==n-1){
count++;}
cout << count << "\n";
``````

full code -

``````#include <iostream>

using namespace std;
int main() {
int t, n, count, i, j;
cin >> t;
for (int k = 0; k < t; k++) {
count = 0;
cin >> n;
char s, u;
for (int m = 0; m < n; m++) {
cin >> s[m];
}
s[n] = '\0';
for (int m = 0; m < n; m++) {
cin >> u[m];
}
u[n] = '\0';
for (i = 0; i < n-1; i++) {
if (u[i] != 'N') {

if (u[i] == s[i]) {
count++;
} else {
i++;
}
}
}
if (u[i] == s[i] && i==n-1){
count++;}
cout << count << "\n";
}
}``````

Let’s consider two strings A and B
You first need to check if B[i] is N if yes then just continue.
Now check if A[i] is equal to B[i] if yes then increment counter and continue
else increment by two or just do i++ and continue ( if in for loop you have i++)

Now the confusion was that
When you reach last character , if it is wrong there is no point of discarding next answer as
There is NO next answers.
and I foolishly thought you can never discard last answer  when it will be available in practise section?

plz will you also see my code
i dont know what iam misssing

#include<stdio.h>
int main(void)
{
int j,k,l,i,c=0,n,t;
char a,b;
printf(“enter test cases\n”);
scanf("%d",&t);
i=1;
while(i<=t)
{
printf(“enter the length of string\n”);
scanf("%d",&n);
printf(“enter the string B\n”);
scanf("%s",b);

``````printf("enter the string A\n");
scanf("%s",a);
c=0;
``````

for(j=0;j<n;j++)

``````{
if(j==n-1)
{
c++;
}
else if(a[j]==b[j])
{
c++;
}
else if (a[j]!=b[j])
{
if(j==n-2)
{

}
else if(a[j]=='N')
{

}
else
{
j=j+2;
}
}

}
printf("%d\n",c);
i++;
}
``````

}

it runs fine according to given input and output

what is wrong with my code? can anyone help?

#include
#include
using namespace std;
int main()
{
int t, i, score, n;
string corr, res;
//cout<<"enter t ";
cin>>t;
while(t>0)
{
score = 0;
cin>>n;
cin>>corr;
cin>>res;
for(i=0; i<=n-2; i++)
{
if(res[i] == ‘N’)
continue;
else if(corr[i] == res[i])
score++;
else
i++;
}
if(corr[n-1] == res[n-1])
score++;
cout<<score<<endl;

``````	t--;
}
``````

}