CHEFPDIG - Editorial

PROBLEM LINK:

[Practice][111]

[Contest][222]

Author: [Dmytro Berezin][4444]

Tester: [Jingbo Shang][5555]

Editorialist: [Hanlin Ren][6666]

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

Given a number s(actually a string of digits), pick two digits a,b in s that’s different by position. For which characters between A-Z can \overline{ab}(i.e., 10a+b) be its ASCII code?

EXPLANATION:

How to store that big number?

This is the most frequent comment we receive.

The number N can be as large as 10^{100\ 000}, so we can only store this number as a string. That is, we regard the input as a string of length 100\ 000.

Here are some code snippets to manipulate a string:

language Define a string Read a string
C ``` char s[MAXLEN+10]; ``` ``` scanf("%s", s); ```
C++ ``` #include string s; ``` ``` cin >> s; ```
Python ```
</td><td>

s = raw_input();

</td></tr>
</table>

## How do I handle ASCII codes?

Also we need to convert between a character and its ASCII code. This is easy in C/C++: a `char` is just a signed 8-bit integer, so we don't need to convert anything. For example, we can enumerate the ASCII codes of all capital letters like this:

for (char c = ‘A’; c <= ‘Z’; c++)
do something


Also if we want the first(or last) digit of the ASCII code of a character(say `'A'`), we just treat it as an integer:

asc = ‘A’;
first_dgt = asc / 10;
last_dgt = asc % 10;


Some other language may have functions converting between ASCII codes and characters. For example, Python provides two functions `ord(char)` and `chr(ascii code)`. You can also google to find out how to do this in your language.

## The solution

Let's consider every character $c$ from `'A'` to `'Z'` separately. Suppose $c$ has ASCII code $\overline{ab}$. Let the input be $s$(a string).

When $a\ne b$, we need to pick both $a$ and $b$ from $s$. We can just check if both digit appears in $s$.

When $a=b$, we need to pick two $a$'s from $s$, thus we need to check if $a$ appears in $s$ twice.

We need to find how many time a character occurs in $s$. This can be done by iterating all chars in $s$. In C you can use `s[i]` to recognize the end of string, since C-style string ends with ASCII 0.(a common mistake is that don't confuse `s[i] != 0` with `s[i] != '0'`. `0` is NULL character but `'0'` has ASCII $48$)

count = 0;
for (int i = 0; s[i] != 0; i++)
if (s[i] == c) count++;


In C++, you can use `string::length()` method to get a string's length:

count = 0;
for (int i = 0; i < s.length(); i++)
if (s[i] == c) count++;


In some languages like Python, things become even easier! Just use `s.count(ch)` to count how many times a char $ch$ appears in a string $s$.

The time complexity is $O(\sigma|s|)$, where $|s|$ is the length of input, and $\sigma=26$ is the size of alphabet.

## A common mistake
If you use C/C++, you may write the following code:

for (int i = 0; i < strlen(s); i++)
do something;


This code may make you TLE. Why? Because `strlen()`'s time complexity is $O(len)$, not $O(1)$. The code above executes $O(|s|)$ `strlen()`'s, and each execution takes $O(|s|)$ time, so the time complexity is actually $O(|s|^2)$.

A small modification should correct this mistake:

int l = strlen(s);
for (int i = 0; i < l; i++)
do something;


However, in C++, if `s` is a `string`(rather than a `char` array), the following code is OK:

for (int i = 0; i < s.length(); i++)
do something;


This is because `length()` method is $O(1)$.

### ALTERNATIVE SOLUTION:
We first preprocess $s$, and maintain a table $occur[0\sim 9]$, where $occur[i]$ is the number of times that digit $i$ appears in $s$.

for (int i = 0; s[i]; i++)
occur[s[i] - ‘0’]++;


Let's then do the algorithm above. Suppose the ASCII code we are checking is $\overline{ab}$. 

When $a\ne b$, we check if $occur[a]\ge 1$ and $occur[b]\ge 1$.

When $a=b$, we check if $occur[a]\ge 2$.

The time complexity is $O(|s|)$.

### AUTHOR'S AND TESTER'S SOLUTIONS:
Tester's solution can be found [here][444].  
Editorialist's solution can be found [here][555]. 

[111]: http://www.codechef.com/problems/CHEFPDIG
[222]: http://www.codechef.com/SEPT17/problems/CHEFPDIG

[4444]: http://www.codechef.com/users/berezin
[5555]: http://www.codechef.com/users/jingbo_adm
[6666]: http://www.codechef.com/users/r_64
[444]: http://www.codechef.com/download/Solutions/SEPT17/Tester/CHEFPDIG.cpp 
[555]: http://www.codechef.com/download/Solutions/SEPT17/Editorialist/CHEFPDIG.py
2 Likes
//