EXAM1 - EDITORIAL

PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

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.

  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. :slight_smile:

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 ) ^___^
:slight_smile:

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[105],u[105];
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[105], u[105];
    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 :joy::sweat_smile:

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[101],b[101];
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--;
}

}