PROBLEM LINK:
Author: Chirag Shetty
Tester: Tushar Kadam
Editorialist: Akshay Padte
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Presum, Mod
PROBLEM:
Given a string, 10 rupees are earned for each power of six within it and 5 for each multiple of six, find the maximum possible money we can earn.
QUICK EXPLANATION:
First take out all sixes and ones and take 10 rupees for each of them. Then in the remaining disconnected strings, find an optimal way to break them down into the maximum number of multiples of six. Multiples of six must be multiples of 3 and 2. For 2, simply look at the last digit. For 3 use a presum and use counters to keep a track of presum mod 3 at each step. When either count_modresult0 is 1 or count_modresult1 or count_modresult2 is 2, the condition for 3 is satisfied. If it also satisfies for the contition for 2, add 5 rupees to the score and proceed.
EXPLANATION:
We can first note that 6 and 1 are both powers of 6 (6^1 and 6^0 respectively) and that all powers of six except 1 end with 6. Thus to maximize our score, we simply take out all sixes and ones and get 10 rupees for each of them.
We are now left with several disconnected strings. We must find a way to further divide them into of multiples of six. Obviously, multiples of six must be multiples of both 2 and 3. For a multiple of 2, the check is easy as only the last digit must be a multiple of 2. Further recall that the check for divisibility for 3 is that the sum of all the digits of that number must be a multiple of three.
We can maintain a presum. As a first step, whenever the presum value is a multiple of 3 and the last digit added was even, we’ve got a multiple of 6 and have earned 5 rupees! But simply doing this is not enough. There may be multiples of six hidden within the the sequence of digits added to the presum.
For example 472. We would miss 72, which is a multiple of six. We must also keep a track of rem0, rem1, rem2, where they are the counters of how many times the remainders were 0, 1 and 2 respectively, when the presum was divided by 3. When we get two occurences of rem1 or two occurences rem2, we can say that the substring in between them (excluding the digit where rem1/2 count updated first and including the digit where the rem1/2 count updated again) must be a multiple of 3, since the mod3 of sum of digits between them totals to 0, and hence we get rem1/2 again. If the digit that caused the count rem1/2 to be updated for a second time is a multiple of 2, we have got our multiple of six! Add 5 rupees to your score, reset presum and the rem counters and proceed forward.
Complexity: O(N)
Cases where you might have got it wrong:
1 61611 422 666 630 424 426 3644824 472
Solutions for these:
10 50 5 30 15 5 15 20 5
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here
Testers’s solution can be found here