You are not logged in. Please login at www.codechef.com to post your questions!

×

MAXNUM3 - Editorial

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}\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:

asked 25 Oct '17, 04:21

melfice's gravatar image

4★melfice
811737
accept rate: 0%

edited 31 Oct '17, 18:35

vijju123's gravatar image

5★vijju123 ♦♦
15.1k11857


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 ?

link

answered 31 Oct '17, 21:44

swarnabja19's gravatar image

1★swarnabja19
637
accept rate: 10%

You can ask your questions now. :)

(31 Oct '17, 22:08) therisingsun4★

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) vijju123 ♦♦5★

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

link

answered 01 Nov '17, 07:10

addy_1996's gravatar image

2★addy_1996
1
accept rate: 0%

1

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[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]<s[i+1].

(01 Nov '17, 13:10) aayushkapadia6★

Thank You :)

(02 Nov '17, 02:07) addy_19962★

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

link

answered 01 Nov '17, 12:50

gautamcse27's gravatar image

2★gautamcse27
375
accept rate: 0%

edited 01 Nov '17, 14:03

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

(01 Nov '17, 15:05) gautamcse272★

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

link

answered 02 Nov '17, 22:25

lave7's gravatar image

2★lave7
1
accept rate: 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

link

answered 03 Nov '17, 00:21

kartik552777's gravatar image

1★kartik552777
1
accept rate: 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.

link

answered 03 Nov '17, 12:13

ramini's gravatar image

2★ramini
615
accept rate: 8%

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, 16:43

gagand33p's gravatar image

3★gagand33p
1
accept rate: 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.

link

answered 01 Nov, 22:53

ryan312's gravatar image

4★ryan312
11
accept rate: 0%

edited 01 Nov, 22:54

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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,677
×921
×64
×12

question asked: 25 Oct '17, 04:21

question was seen: 1,637 times

last updated: 01 Nov, 22:54