×

MAXNUM3 - Editorial

Author: Trung Nguyen
Tester: Oleksandr Kulkov
Editorialist: Oleksandr Kulkov

EASY

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.

RELATED PROBLEMS:

4★melfice
811937
accept rate: 0%

15.5k12066

 1 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 ? answered 31 Oct '17, 21:44 63●7 accept rate: 10% You can ask your questions now. :) (31 Oct '17, 22:08) Google out "New karma system codechef discuss" and read the blog. It will clear most of your doubts on these stuff. (31 Oct '17, 23:27)
 0 "Among all possibilities choose either first with si+1i and original number is "s[1] s[2] ... s[i-1] s[i] 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[i] s[i+1] ... s[j-1] s[j+1] ... s[n]" So if it is the case that s[i+1]>s[i] 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[i]
 0 What does this mean s[n - 1 - (i == n - 1)] answered 01 Nov '17, 12:50 37●5 accept rate: 0% If i am correct does (i == n - 1) return boolean value i.e., 0 or 1. (01 Nov '17, 15:05)
 0 In this problem, when it is submitted through python 3 it shows EOFError: EOF When reading line. answered 02 Nov '17, 22:25 2★lave7 1 accept rate: 0%
 0 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 answered 03 Nov '17, 00:21 1 accept rate: 0%
 0 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. answered 03 Nov '17, 12:13 2★ramini 61●5 accept rate: 8%
 0 What is wrong with my approach and why am I getting SIGABRT here https://www.codechef.com/viewsolution/17192149 link This answer is marked "community wiki". answered 29 Jan '18, 16:43 1 accept rate: 0%
 0 The condition should be s[i+1] > s[i] and not the other way around; where s[i] is the element to be removed. answered 01 Nov '18, 22:53 4★ryan312 1●1 accept rate: 0%
 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:

×3,820
×968
×64
×12

question asked: 25 Oct '17, 04:21

question was seen: 1,734 times

last updated: 01 Nov '18, 22:54