October LunchTime UNofficial Editorials (First two problems) Revised

Problem: Buggy Calculator

Problem Statement

Add two number A and B without carrying forward any value.

Solution

The above sum can also be written as

let A consist of M digits and B consist of N digits

let S[i] denote ith digit of required sum of A and B, A[i] be ith digit of A and B[i] be ith digit of B. (starting from unit, ten’s…).

For every digit i < Max(A,B)

S[i] = (A[i]+B[i])%10

Simply calculate this and output. :slight_smile:

Addition (on vijju’s recommendation)

Avoid printing leading zeroes

Suppose you have a string (or char array) C storing digits if your answer, unit place at leftmost position.

Int f = 0;

String output = “”;

for(i = C.length-1; i >= 0;i–){

If(C[i] != ‘0’)f = 1; // for digit int array, replace ‘0’ with 0.

If f==1 out.append(C[i]);

}

if(f==0)print(0);

else print out;

If you feel you have a better idea for above, feel free to share in comments.

My Solution [Here][1]

Problem: Maximum Number

Problem Statement

Given a number N, output Maximum number possible which satisfy constraint that number is multiple of 6. If no such number possible print -1.

Solution

First thing to know:

  1. Every multiple of 2 has 0,2,4,6 and 8 at unit’s place. (I know You know this :smiley: )
  2. Sum of digits of Every multiple of 3 is also divisible by 3.

For checking divisibility by 6, it is sufficient to check divisibility by both 2 and 3.

Then, Following cases arise:

I. Digit at unit’s place is odd

In this case, if digit at ten’s place is also odd, then number cannot be made a multiple of 6. Thus print -1.

If ten’s place digit is even. delete unit’s place digit from given number. Now, if the resultant number is divisible by 3, print that number. Else print -1.

II. Digit at unit’s place is Even

In this case, multiple choices are there.

Let sum be sum of digits of given number. We can delete any digit d (except unit place digit if ten’s place digit is odd, so that the number remains a multiple of 2) for which sum%3 == d%3. This works because after deleting that digit, sum is a multiple of 3.

Now, to maximize this number, we need to find the digit at largest place satisfying above condition. This works because:

Take example number 4510222

sum of digits = 4+5+1+2+2+2 = 16

sum%3 = 1

Now, we can delete digits 1 and 4 (because 1%3=3, 4%3 = 1)

If we delete 1, we get number 450222

If we delete 4, we get number 510222

We delete the largest digit (leftmost) for which the next digit is greater than deleted digit. This is necessary to avoid following case

Number 7510222

Digits 7 and 1 can be deleted according to above solution, giving numbers 510222 and 750222 respectively. Here, deleting largest (leftmost) index give smaller result because 7 > 5. This worked in above case because 4<5.

Correct Solution

Find leftmost digit satisfying constraints

  1. sum%3==digit%3
  2. digit < Immediately next digit

In case no digit is found such that digit < Immediately Smaller digit, find Rightmost digit for which digit > Immediately right digit. This works because of following saying. :stuck_out_tongue:

There’s a well known saying (since now only :D) If you can’t maximize the addition of something, try to minimize it’s reduction. It’s the Same thing.

Just delete that digit and print the answer.

In case no digit satisfy sum%3==digit%3, print -1. (Example number 222)

Here’s my


[2]

Enjoy Coding. :D

Feel free to ask anything... as always :)

  [1]: https://www.codechef.com/viewsolution/15981433
  [2]: https://www.codechef.com/viewsolution/15988110
12 Likes

For the second question my solution is O(n) but still giving TLE, please look into this:- https://www.codechef.com/viewsolution/15998898

hey taran my code is giving wa in 1st subtask. any testcase where it might fail? https://ideone.com/yKzrA3

For the first question why is my solution giving WA in Subtask 2?

@vishaldugyala I guess u haven’t taken care of the fact that no.of digits may be different

Thanks Taran! Great job helping out others. Kudos!

Is erase function also linear in Time???

I think you can add something on how to avoid those leading zeroes. I was simple printing the array and wasted A HUGE CHUNK of my time because it was printing leading 0.

And BTW, I feel the problem statement SHOULD specify that leading zeroes arent allowed. I mean, yeah, to many people “5555+5555=0000” would make sense.

3 Likes

Thanks for the explanation :slight_smile:
Can you help me debugging my code for 2nd problem please? LINK

hey taran can u share your fb profile link or can you send me req.? Needed to talk to you personally. :slight_smile:

1 Like
t = int(input())
while t>0 :
    n = input()
    i = len(n)
    flag = 0
    li = []
    while i>0:
        copy = int(n[:i-1] + n[i:])
        if copy%6 == 0:
            li.append(copy)
            flag = 1
        i -= 1
    if flag == 1:
        print(str(max(li)).rjust(len(n)-1, "0"))
    else:
        print("-1")
    t = t-1

I don’t know why it was giving TLE although you have also used nested loops and hence O(n^2)… please help me?

https://www.codechef.com/viewsolution/16001364
Can you help me debugging my code please?

I’m getting WA in the second subtask in BUGCAL… Why?

https://www.codechef.com/viewsolution/15984308

My solution is in O(number of digits). I don’t know why it is giving TLE. This is my solution.
It is in Python. My logic is I calculate the number if I remove one digit, and check if it is divisible by 6 and greater than previously held value and replace it. Then append zeroes according to input if the first digit is removed.

e.g:- 3268398 is input,
num will hold the values (268398, 368398, 328398, 326398, 326898, 326838, 326839) in each iteration respectively.
Will check if it is divisible by 6 and greater than previously divisible value.

Thanks in advance.

I don’t know why i am getting RE(NZEC)?
this is my solution https://www.codechef.com/viewsolution/15995869

My code gives wrong ans.Any test case where it may fail?
link:https://www.codechef.com/viewsolution/16002121

for the second question ,every test case i checked is satisfied still i am getting a wrong answer please help me out pointing out just 1 test case that this code cannot run ??

https://www.codechef.com/viewsolution/15992968

@taran_1407 can you give some testcases for 2nd question.

https://www.codechef.com/viewsolution/15988759

What is wrong in this code for BUGCAL? PLease help. Everything handled!

@shivam2296 When you are swapping a&b then you should also swap the length also.