MAXNUM3 - Editorial

ad-hoc
easy
ltime53
maxnum3

#1

PROBLEM LINK:

Practice

Contest

Author: Trung Nguyen

Tester: Oleksandr Kulkov

Editorialist: Oleksandr Kulkov

DIFFICULTY:

EASY

PREREQUISITES:

None

PROBLEM:

You’re given bunch of numbers. For each number you should remove exactly one digit to get the largest number that is divisible by 6.

QUICK EXPLANATION:

Brute-force the digit to be removed and check if it’s possible by divisibility rule for 2 and 3. Among all possibilities choose either first with s_{i+1} < s_i or the last one if there is no such position where s_i is removed element.

EXPLANATION:

Number is divisible by 6 if it is divisible by 2 (i.e. the last digit is even) and by 3 (i.e. sum of digits is divisible by 3) simultaneously. Given that we can quickly check if we can remove some particular digit. Now we should choose among all possible digits one which will lead to the largest number.

For convenience let’s assume that in block of repeated digits we always consider only the last one. Thus s_i=s_{i+1} never takes place and after we remove i^{th} digit, first i-1 digits will be same as in the initial numbers and next digit will be equal to s_{i+1} eq s_i. Thus if it is possible to get the number which is lexicographically larger then initial one, we should choose one which is larger in the earliest possible position to get the largest number among all possible. On the other hand if we can only delete last character or one with s_i > s_{i+1}, we’ll get the number which is lexicographically lesser than s with first differ in position i. In this case we should maximize the difference position which leads us to the algorithm described in quick explanation. Here is the main code to solve the problem:

string s;
cin >> s;
int n = s.size();
string ans = "-1";
int sum = (accumulate(begin(s), end(s), 0) - '0' * n) % 3;
int lpos = -1;
for(int i = 0; i < n; i++) {
    if((s* - '0') % 3 == sum && 
       (s[n - 1 - (i == n - 1)] - '0') % 2 == 0) {
        lpos = i;
        if(i + 1 < n && s* < s[i + 1]) {
            break;
        }
    }
}
cout << (lpos == -1 ? "-1" : s.substr(0, lpos) + s.substr(lpos + 1)) << '

';

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.

RELATED PROBLEMS:


#2

A very nice problem for sure.

Joined the Codechef Discuss community today.
Apologize if it’s out of the context, but how and when will I be able to ask questions ?


#3

“Among all possibilities choose either first with si+1<si” Can anyone explain this point? Couldn’t follow the explanation.


#4

What does this mean s[n - 1 - (i == n - 1)]


#5

In this problem, when it is submitted through python 3 it shows EOFError: EOF When reading line.


#6

Please can anyone tell me why my submission gave WA. I checked many test cases they all are going correct

Here’s my solution
https://www.codechef.com/viewsolution/16037688

Also what we need to do if ‘the sum of n over all test cases ≤ 106’ Constraint fails


#7

Bro, n can have a maximum of 10^5 digits. So, you have to store it in a string or character array. Read the question again, it is given that the integer has n>1 digits.


#8

What is wrong with my approach and why am I getting SIGABRT here https://www.codechef.com/viewsolution/17192149


#9

The condition should be s[i+1] > s* and not the other way around; where s* is the element to be removed.


#10

You can ask your questions now. :slight_smile:


#11

Google out “New karma system codechef discuss” and read the blog. It will clear most of your doubts on these stuff.


#12

Let us compare 2 cases where you delete ith digit in one case and jth digit in other case where j>i and original number is “s[1] s[2] … s[i-1] s* s[i+1] … s[j] … s[n]”.

delete ith digit -> “s[1] s[2] … s[i-1] s[i+1] … s[j] … s[n]”

delete kth digit -> “s[1] s[2] … s[i-1] s* s[i+1] … s[j-1] s[j+1] … s[n]”

So if it is the case that s[i+1]>s* then you can clearly see that number generated by deleting ith digit is lexicographically larger for any j>i. And hence we will select first such i such that s*<s[i+1].


#13

If i am correct does (i == n - 1) return boolean value i.e., 0 or 1.


#14

Thank You :slight_smile: