PROBLEM LINK:
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}\neq 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[i] - '0') % 3 == sum &&
(s[n - 1 - (i == n - 1)] - '0') % 2 == 0) {
lpos = i;
if(i + 1 < n && s[i] < s[i + 1]) {
break;
}
}
}
cout << (lpos == -1 ? "-1" : s.substr(0, lpos) + s.substr(lpos + 1)) << '\n';
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
