RRECIPE - Editorial

editorial
, , , ,
1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

SIMPLE

PREREQUISITES

Simple Math

PROBLEM

You are given a string of length N. Each character of the string is either a lowercase letter (‘a’ - ‘z’) or a question mark (’?’). Count the number of ways to replace each question mark with a lowercase letter in such a way that the resulting string is a palindrome.

QUICK EXPLANATION

Consider the pairs of characters in the string that must be equal for the string to be a palindrome. First, the answer is 1. For each such pair, check the corresponding characters. If both characters are question marks, multiply the answer by 26. If exactly one of them is a question mark, or if both characters are equal lowercase letters, do nothing. If both characters are lowercase letters but they are not equal, set the answer to 0. For odd N, if the middle character is a question mark, also multiply the answer by 26.

EXPLANATION

In a palindrome of length N, the i-th character must be equal to the (N-i-1)th character (all indices are 0-based). For even N, there must be exactly N/2 pairs of equal characters: characters at positions 0 and N-1, positions 1 and N-2, …, positions N/2 - 1 and N/2. For odd N, there must be exactly (N-1)/2 pairs of equals characters: characters at positions 0 and N-1, positions 1 and N-2, …, positions (N-3)/2 and (N+1)/2.

For example, consider N=6. There must be exactly 3 pairs of equal characters: characters at positions 0 and 5, positions 1 and 4, positions 2 and 3. This ASCII art may illustrate better:

+---+---+---+---+---+---+
| 0 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+
  |   |   |   |   |   |
  |   |   +---+   |   |
  |   +-----------+   |
  +-------------------+

Another example, consider N=9. There must be exactly 4 pairs of equal characters: characters at positions 0 and 8, positions 1 and 7, positions 2 and 6, positions 3 and 5. Note that the middle character at position 4 is not included in any pairs.

+---+---+---+---+---+---+---+---+---+
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
+---+---+---+---+---+---+---+---+---+
  |   |   |   |       |   |   |   |
  |   |   |   +-------+   |   |   |
  |   |   +---------------+   |   |
  |   +-----------------------+   |
  +-------------------------------+

Now, we want to count the number ways to replace the question marks in such a way that the resulting string is a palindrome. We can rephrase the problem into: count the number of ways to replace the question marks in such a way that each pair of characters as described above has equal letters. Note that each pair is independent. Therefore, for each pair, we can count the number of ways to make the pair have equal letters, and multiply them all to get the total number of ways.

Consider each pair. There are 4 cases:

  • Both characters are question marks. We can replace one of them with any of the 26 lowercase letters. Since both letter must be equal, the other one must be also replaced with the same letter. The number of ways is 26.
  • Exactly one of the characters is a question mark. We do not have other options besides replacing the question mark with the same letter as the other character. The number of ways is 1.
  • Both characters are lowercase letters, and they are equal. This pair has already satisfied the requirement. The number of ways is 1 (i.e., do nothing).
  • Both characters are lowercase letters, but they are not equal. Obviously, we cannot replace anything to make this pair have equal letters. The number of ways is 0.

There is a special case when N is odd. The middle character (i.e., the character at position (N+1)/2) is not included in any pairs. If the middle character is a question mark, we can replace it with any characters. Therefore, multiply the answer also by 26 if the middle character is a question mark.

The time complexity of this solution is O(N).

Do not forget to perform all calculations modulo 10,000,009.

SETTER’S SOLUTION

Can be found here

TESTER’S SOLUTION

Can be found here

6 Likes
2

Great Problems , Great Editorials. Kudos to both Nikhil and Ashar.

Just wanted to clarify what is the difference between doing

(result*26)%MOD

and

(result%MOD)*26 ?

Won’t doing (result*26)%MOD will result in an overflow if i am using INT or even LL? Considering value of result is already huge.

Where as i can protect it from overflowing by first doing MOD operation and then multiplying as in the second case?

Thanks.

1 Like
3

Note that MOD is about 1e7 here. Clearly at each step 0 <= result < MOD. Hence (results * 26) is about 2.6e8 < 2^31. So we don’t have any overflow here. But if you do (result%MOD) * 26 at each step then in the end result can be >= MOD. So you need additionally take %MOD before printing. In general computation modulo MOD means that you should do (a+b)%MOD and (a * b)%MOD and in most cases you should cast a as long long during multiplication.

1 Like
4

#include<stdio.h>
#include<string.h>
char a[1000005];
main()
{
int t;
long long ctr;
long int len,i;
scanf("%d",&t);
while(t–)
{
ctr=1;
gets(a);
len=strlen(a);
if(len%2!=0)
{
if(a[(len-1)/2]==’?’)
{
ctr=(ctr26)%10000009;
}
}
for(i=0;i<len/2;i++)
{
if(a[i]==a[len-i-1])
{
if(a[i]==’?’)
{
ctr=(ctr26)%10000009;
}
}
else
{
if(a[i]!=’?’&&a[len-i-1]!=’?’)
{
ctr=0;
break;
}
}
}
printf("%lld\n",ctr);
}
return 0;
}

i have checked and rechecked and rechecked my code bt i am not able to figure out the mistake.i am getting a WA.
please help.

5

i have included all the cases as told above but i m getting WA. plz help.
http://www.codechef.com/viewsolution/5203710

6

Getting WA…
Please help…
http://www.codechef.com/viewsolution/5239021

7

Can anyone explain me why are we multiplying by 26 for pairs which are question marks?

8

2
a?c
aba

your output:
1
0

but expected output should be:
0
1