CHEFSTLT - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

Author: Roman Furko
Testers: Pushkar Mishra and Sergey Kulik
Editorialist: Pawel Kacprzak
Russian Translator: Sergey Kulik
Mandarian Translator: Gedi Zheng

DIFFICULTY:

Cakewalk

PREREQUISITES:

Implementation

PROBLEM:

You are given two strings S1, S2 with equal lengths. Both strings, on any position, can contain a lowercase latin letter or a question mark ‘?’.

A question mark can be equal to any of lowercase latin letters. We define the difference between the strings as the number of positions i, such that the strings are different on this position. Your task is to compute the minimal and the maximal difference between the strings.

QUICK EXPLANATION:

Let’s consider any position i in the strings. Since a question mark can be any letter, if at least one of the strings have a question mark on the i-th position, we can always change it to match the letter in the other string or we can always change it to a letter which produces a mismatch. Therefore, the minimal difference is the number of positions for which none of the strings contain a question mark and there is a mismatch between them on this position. On the other hand, the maximal difference is the length of the strings reduced by the number of positions for which none of the strings contain a question mark and there is a match between them on this position.

EXPLANATION:

We define a strong match as the position i, such that none of the strings contain a question mark at the i-th position, and the letters in the strings at the i-th position match.

We define a strong mismatch as the position i, such that none of the strings contain a question mark at the i-th position, and the letters in the strings at the i-th position do not match.

Let’s consider any position i in both strings. If at least one string contain a question mark on the i-th position, we can create a match or a mismatch between the strings at this position.

There are basically two cases to consider:

  1. If only one string contains a
    question mark on the i-th position.

    Without loss of the generality,
    let’s assume that S1[i] = ‘?’ and
    S2[i] = ‘a’. Since the latin
    alphabet has 26 letters, we can
    produce a mismatch by setting up
    S1[i] to any letter different by ‘a’
    and we can produce a match by
    setting up S1[i] to ‘a’.

  2. Both strings contain a question mark
    on the i-th position

    Since the latin alphabet has 26
    letters, we can produce a match by
    setting up S1[i] = S2[i] = ‘a’ and
    we can produce a mismatch by setting
    up S1[i] = ‘a’ and S2[i] = ‘b’.

Based on these two facts, we for any position which is not a strong match or a strong mismatch, we can make it a match or a mismatch.

Therefore, the minimal difference is the number of strong mismatches. On the other hand, the maximal difference is the length of the strings reduced by the number of strong matches.

Time complexity:

Linear in terms of the length of input strings.

AUTHOR’S AND TESTER’S SOLUTIONS:

Tester

1 Like
2

#include <stdio.h>
#include <string.h>
#include <math.h>
int main()
{
int t,i,x,y;
char s1[102],s2[102];
scanf("%d",&t);
while(t–)
{
i=0;
x=0;
y=0;
scanf("%s",&s1);
scanf("%s",&s2);
while(s1[i])
{
if(s1[i]==’?’ || s2[i]==’?’)
x++;
else if(s1[i] != s2[i])
y++;
i++;
}
printf("%d %d\n",y,x+y);
}
return 0;
}

3

#include<stdio.h>
int main()
{
int t,minimal,maximal,count,i;
char s1[105],s2[105];
scanf("d",&t); while(t--) { scanf("*c%s%s",s1,s2);
i=0;
count=minimal=maximal=0;
while(s1[i]!=’\0’)
{
if(s1[i]==’?’||s2[i]==’?’)
count++;
else
{
if(s1[i]!=s2[i])
minimal++;
}
i++;
}
maximal=minimal+count;
printf("%d %d\n",minimal,maximal);
}
return 0;
}