CHEFPDIG - Editorial

PROBLEM LINK:

Practice

Contest

Author: Dmytro Berezin

Tester: Jingbo Shang

Editorialist: Hanlin Ren

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 s = 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 e 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* to recognize the end of string, since C-style string ends with ASCII 0.(a common mistake is that don’t confuse s* != 0 with s* != '0'. 0 is NULL character but '0' has ASCII 48)

count = 0;
for (int i = 0; s* != 0; i++)
    if (s* == 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* == 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* is the number of times that digit i appears in s.

for (int i = 0; s*; i++)
    occur[s* - '0']++;

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

When a e b, we check if occur[a]\ge 1 and occur**\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.

2 Likes
    #include <bits/stdc++.h>
    #define ll long long int
    #define N 100000
    #define M 1000000007
    #define f(i,a,b) for(ll i=(ll)a;i<=(ll)b;i++)
    #define rf(i,a,b) for(ll i=(ll)a;i>=(ll)b;i--)
    #define po pop_back
    #define pb push_back
    #define lb lower_bound
    #define ub upper_bound
    #define ibs ios_base::sync_with_stdio(false)
    #define cti cin.tie(0)
    #define cot cout.tie(0)//solved by abhijay mitra
    using namespace std;bool a[26];int num[10];
    #define watch(x) cout << (#x) << " is " << (x) << endl
    int main(){
        // ibs;cti; 
        int T;
        cin>>T;
        while(T--){
                cout<<"\n";
                for (int i = 0; i < 10; ++i)
                    num[i]=0;
                for (int i = 0; i < 26; ++i)
                {
                    a[i]=0;
                }
                int n,k;ll m;string s;
                cin>>s;bool check=0;
                char c;
                for(ll i=0;i<s.length();i++){
                    c=s[i];
                    if (num[c-'0']<2)
                        num[c-'0']++;
                }
                if (num[6]!=0 and num[5]!=0)
                {
                    a[0]=1;
                }
                 if (num[6]==2)
                {
                    a[1]=1;
                }
                 if (num[6]!=0 and num[7]!=0)
                {
                    a[2]=1;
                }
                 if (num[6]!=0 and num[8]!=0)
                {
                    a[3]=1;
                }
                 if (num[6]!=0 and num[9]!=0)
                {
                    a[4]=1;
                }
                 if (num[7]==2)
                {
                    a[12]=1;
                }
                 if (num[8]==2)
                {
                    a[23]=1;
                }
                 if (num[9]!=0 and num[0]!=0)
                {
                    a[25]=1;
                }
                for (int i = 7; i < 9; ++i)//70to89 except 77 and 88
                {
                    for (int j = 0; (j<10) ; ++j)
                    {
                        if (!(j-i))
                        {
                            continue;
                        }
                        if(num[i]==0||num[j]==0) continue;
                        int x=i*10+j;
                        a[x-65]=1;
                    }
                }
                for (int i = 0; i < 26; ++i)
                    if(a[i])printf("%c",'A'+i);
            }
        return 0;
    }

my solution to this problem in c++