×

CHEFPDIG - Editorial

Practice

Contest

Author: Dmytro Berezin

Tester: Jingbo Shang

Editorialist: Hanlin Ren

Simple

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:

Cchar s[MAXLEN+10];scanf("%s", s);
C++#include <string> string s;cin >> s;
Pythons = raw_input();

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.
Editorialist's solution can be found here.

This question is marked "community wiki".

7★r_64
261924
accept rate: 16%

19.8k350498541

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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,191
×286
×7

question asked: 16 Aug '17, 21:21

question was seen: 1,060 times

last updated: 11 Sep '17, 17:48