You are not logged in. Please login at www.codechef.com to post your questions!

×

CHEFSTLT - Editorial

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

This question is marked "community wiki".

asked 26 Jun '15, 00:13

pkacprzak's gravatar image

5★pkacprzak ♦♦
75485097
accept rate: 12%

edited 27 Jul '15, 17:04

admin's gravatar image

0★admin ♦♦
19.8k350498541


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; }

link

answered 19 Jan '18, 08:46

lokesh31333's gravatar image

1★lokesh31333
1
accept rate: 0%

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; }

link

answered 20 Jan '18, 12:16

monish_26's gravatar image

0★monish_26
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,852
×1,688
×643
×67

question asked: 26 Jun '15, 00:13

question was seen: 4,284 times

last updated: 20 Jan '18, 12:16