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

×

October LunchTime UNofficial Editorials (First two problems) Revised

11
1

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. :)

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

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 :D )
  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. :P

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 code

Enjoy Coding. :D

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

asked 28 Oct '17, 23:54

taran_1407's gravatar image

6★taran_1407
4.0k31103
accept rate: 22%

edited 31 Oct '17, 16:34


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.

link

answered 29 Oct '17, 00:39

vijju123's gravatar image

5★vijju123 ♦♦
15.5k12066
accept rate: 18%

3

Agreed

That ought to be the case, but i thought of real life calculators, which never print 0000. Maybe the author's calculator wasn't that faulty to print 0000. :D

(29 Oct '17, 00:43) taran_14076★
2

Possible XD. Imagine my reaction when I opened comment section after 20min only to realzie that leading zeroes are giving WA. I was like, "...................... (xinfinity)XDXD"

(29 Oct '17, 00:47) vijju123 ♦♦5★

Happens Mate...

(29 Oct '17, 00:58) taran_14076★

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

link

answered 29 Oct '17, 00:47

soham1234's gravatar image

6★soham1234
1.8k614
accept rate: 22%

How Come??

Surely you can ask anything here mate..

(29 Oct '17, 00:55) taran_14076★

I see you haven't participated in lunchtime..

Ask away mate...

(29 Oct '17, 01:00) taran_14076★

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

link

answered 28 Oct '17, 23:57

noxious_av's gravatar image

5★noxious_av
637
accept rate: 0%

2

Mate, Your solution is O(n^2) because Substring function itself take O(N) time because it has to transverse whole string. Further, using Integer.parseInt this many times, you can simply store a number in array, ith element of array being ith digit of number (from left to right or right to left, as you feel comfortable with. :) ).

(29 Oct '17, 00:04) taran_14076★

@taran_1407 the very first solution that passed is O(N^2)! Can you please look at his code and please comment that whether the test cases are weak or he has made some optimization ?

(29 Oct '17, 08:34) pk3012★
(29 Oct '17, 08:39) pk3012★

Probably weak test cases...

(30 Oct '17, 12:55) taran_14076★

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

link

answered 29 Oct '17, 00:15

rockstarsam's gravatar image

4★rockstarsam
233
accept rate: 0%

Mate, i replied on your thread too. I'm still working with your solution only. :)

(29 Oct '17, 00:18) taran_14076★

sorry bro didn't see then. thanks :)

(29 Oct '17, 00:22) rockstarsam4★

No problem mate.

(29 Oct '17, 00:26) taran_14076★
1

By the way, why are you using variable p in your code??

(29 Oct '17, 00:26) taran_14076★
1

@soham1234 https://www.codechef.com/viewsolution/16001805

just remove the line where you have checked the value of p and AC :)

the idea is that when you get the value lesser, in the position nearer to the units place it will lead to better solution than that in the higher digits !

(29 Oct '17, 09:25) pk3012★

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

link

answered 29 Oct '17, 00:22

vishaldugyala's gravatar image

2★vishaldugyala
1
accept rate: 0%

Try Following test case.

1

55 54

Correct answer 9

Your answer 09

(29 Oct '17, 00:26) taran_14076★

@taran_1407 but wouldn't the calculator print exactly 09 only?

(29 Oct '17, 00:28) vishaldugyala2★

Nope, It isn't mentioned in problem but a calculator always print 9, not 09. You may try. :)

(29 Oct '17, 00:30) taran_14076★

Yes, but since the calculator is faulty and skips carry i thought it should print 5555+5555 as 0000. Thanks for replying though.

(29 Oct '17, 00:34) vishaldugyala2★
1

No problem at all.

By the way, the calculator isn't that faulty :D

(29 Oct '17, 00:36) taran_14076★

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

link

answered 29 Oct '17, 00:25

rockstarsam's gravatar image

4★rockstarsam
233
accept rate: 0%

Mate, in his solution, that matters not.

Because he used the condition a>0 || b > 0

If one of them is zero, it will be automatically ignored.

(29 Oct '17, 00:44) taran_14076★

Thanks Taran! Great job helping out others. Kudos!

link

answered 29 Oct '17, 00:27

akashbhalotia's gravatar image

5★akashbhalotia
865214
accept rate: 10%

Thanks mate. :)

(29 Oct '17, 00:27) taran_14076★

Is erase function also linear in Time???

link

answered 29 Oct '17, 00:28

doramon's gravatar image

3★doramon
865
accept rate: 5%

Which language you are talking about mate??

I work with java. Either share code link. :)

(29 Oct '17, 00:29) taran_14076★
(29 Oct '17, 00:38) doramon3★

The logic of your code isn't clear to me. Can you elaborate??

(29 Oct '17, 00:40) taran_14076★

for each i erased character at that place...

And checked the string so formed is divisble by 6 or not

check condition in O(1)

condition:

1.check even or not

2.if yes check (sum-a[i])%3 or not

I think it's just because erase giving Tle

(29 Oct '17, 00:46) doramon3★

@taran_1407 plzz join this group,it gonna helpful for us!!

https://www.facebook.com/groups/1232901383475983/

(29 Oct '17, 00:50) doramon3★

As far as i know about c++, String s = p itself takes Linear time, making your solution time out.

(29 Oct '17, 00:53) taran_14076★
showing 5 of 6 show all

Thanks for the explanation :)
Can you help me debugging my code please? LINK

link

answered 29 Oct '17, 00:43

dishant_18's gravatar image

4★dishant_18
61419
accept rate: 12%

Your code can only delete 3,6 and 9 from given number due to line

if(p%3==0)

Further, no need to check sum%3==0

Simply check (sum-d)%3==0 where d is the deleted digit.

(29 Oct '17, 00:49) taran_14076★

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?

link

answered 29 Oct '17, 01:07

gaurav_iiitian's gravatar image

4★gaurav_iiitian
953
accept rate: 8%

I did use two loops but not two nested loops. There's a difference. Nested loop is loop within a loop, which i haven't used and you have.

That's what that make the difference. :)

(29 Oct '17, 01:13) taran_14076★

thanks mate, but loop will traverse at max six time because it is traversing digits. So how can it be TLE... I just can't understand.

(29 Oct '17, 23:15) gaurav_iiitian4★

How come loop will transverse 6 times only??

Loop will transverse like 10^6 times as i know,

(29 Oct '17, 23:57) taran_14076★

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

link
This answer is marked "community wiki".

answered 29 Oct '17, 03:31

prince367's gravatar image

2★prince367
714
accept rate: 0%

Mate, you are complicating your life a lot by using that vector V. Simply check for digit remainder 3 during a loop, check if sum%3 == d%3. It will give same reaults.

Refer to my implementation and feep free to ask anythibg.. :)

(29 Oct '17, 17:17) taran_14076★

I'm getting WA in the second subtask in BUGCAL... Why?

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

link

answered 29 Oct '17, 09:50

data2000's gravatar image

3★data2000
12
accept rate: 0%

edited 29 Oct '17, 09:51

Your Code gives wrong input for

1

99999999 99999999

output: 88888880

But Unable to figure out the exact reason for WA

@taran_1407 @vijju check out this code why showing wrong

(29 Oct '17, 13:45) doramon3★
1

Thats because of pow10 function, which stores result in double. Due to precision loss of ~${10}^{-8}$, it shows deviation at large values.

(29 Oct '17, 14:05) vijju123 ♦♦5★

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.

link

answered 29 Oct '17, 10:08

gomu's gravatar image

4★gomu
2084
accept rate: 5%

A must know thing for python coders. When dealing with large number, Even basic arithmetic operations like remainder cost time proportional to number of digits, making your solution O(N^2).

Feel free to ask anything....

(29 Oct '17, 17:29) taran_14076★

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

link

answered 29 Oct '17, 10:18

vparas's gravatar image

4★vparas
1
accept rate: 0%

Mate, you cannot take a number greater than or equal to 2^31 or smaller than -2^31 as int in java.

Take input as

String p = obj.next();

Feel free to ask anything... :)

(29 Oct '17, 17:33) taran_14076★

Your scanner gives element not found exception by scanner because it cannot find any integer in input file. All number this large will be treated as string input by scanner

(29 Oct '17, 17:37) taran_14076★

by doing these it again show RE(NZEC) and i doesn't understand
Your scanner gives element not found exception by scanner because it cannot find any integer in input file. All number this large will be treated as string input by scanner

(29 Oct '17, 19:10) vparas4★

@vparas , please read about java errors on input, limit of int and long data types.

(29 Oct '17, 19:42) vijju123 ♦♦5★

maximum value of n is 100000 so it remain in the int range so it is not the reason of getting RE(NZEC) . So why i am getting RE(NZEC).please help! thank you.

(30 Oct '17, 00:21) vparas4★

N is the number of digits in given problem... Means the number can be upto 10^(10^5), way beyond int and long range

(30 Oct '17, 12:58) taran_14076★
showing 5 of 6 show all

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

link

answered 29 Oct '17, 10:45

ayushi09's gravatar image

1★ayushi09
325
accept rate: 0%

Well, i certainly can't find any test cases. First thing, keep your code clean, it will help degugging. Second thing, you haven't added last digit to sum after testing for impossible cases.

(29 Oct '17, 17:43) taran_14076★

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

link

answered 29 Oct '17, 10:54

spidy_j's gravatar image

3★spidy_j
413
accept rate: 0%

you are getting -1 for 66666666666

(29 Oct '17, 13:40) spp____2★

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

link

answered 29 Oct '17, 11:16

new_naveen602's gravatar image

4★new_naveen602
1
accept rate: 0%

Maybe you can ask problem setters for this.. They can provide much better test cases then i can. :)

(29 Oct '17, 17:44) taran_14076★

can u tell me the solution for 102 and 100

(29 Oct '17, 21:58) new_naveen6024★

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

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

link

answered 29 Oct '17, 11:39

shivam2296's gravatar image

3★shivam2296
173
accept rate: 0%

Hey @shivam2296 ur code showing wrong for a.length<b.length

Example: input:

2

11 1145

12 13456

output:

-)

)9

(29 Oct '17, 13:16) doramon3★
(29 Oct '17, 13:21) doramon3★

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

link

answered 29 Oct '17, 12:07

new_naveen602's gravatar image

4★new_naveen602
1
accept rate: 0%

Taran, Can you help me debug my code? It seems like I'm missing some corner cases.

Edit: I'm sorry. The link was wrong. This is link to solution. https://www.codechef.com/viewsolution/16002813

link

answered 29 Oct '17, 12:34

nimmumanoj's gravatar image

3★nimmumanoj
01
accept rate: 0%

edited 30 Oct '17, 19:45

it's showing Acess Denied :(

(29 Oct '17, 13:46) doramon3★

That link was wrong! I changed it:D

(30 Oct '17, 19:46) nimmumanoj3★

Hey

Try the following test case

1

630

Correct answer is 60.

Enjoy coding :D (PS:i won't tell the bug)

(30 Oct '17, 23:44) taran_14076★

Hey taran I am getting wa for the 2nd subtask in the problem BUGCAL. Any testcase where I might fail. Here's the link to my solution - link text

link

answered 29 Oct '17, 13:30

prateek_codec's gravatar image

3★prateek_codec
11
accept rate: 0%

Ur code printing leading Zeroes!!

(29 Oct '17, 17:11) doramon3★

But i tested my code on clion and codechef compiler, it didn't printed any leading zeroes.Could you please specify the test case in which it printed leading zeroes.

(30 Oct '17, 20:41) prateek_codec3★

Hey @taran_1407, did you solve the third problem i.e. Optimal Subset? I have a conventional O(n^2) DP approach and optimizing it seems way too difficult to me and I can't even think of any other way to approach that problem too. Any suggestions on that?

link

answered 29 Oct '17, 22:00

gagan86nagpal's gravatar image

5★gagan86nagpal
11116
accept rate: 11%

I got only 40 points in Optimal Subset using an observation. Just waiting for official editorial to find out whether its correct or not. :D

(29 Oct '17, 22:44) taran_14076★

Loving your explanations dude.

well done C.A :P as your institute suggests

link

answered 30 Oct '17, 02:27

striverlearner's gravatar image

3★striverlearner
46910
accept rate: 0%

Thanks..

PS: I am a first year student, not yet CA. Long way to go!!

(30 Oct '17, 19:15) taran_14076★

code , can you please help me out why it is giving wrong answer.

link

answered 30 Oct '17, 04:23

striverlearner's gravatar image

3★striverlearner
46910
accept rate: 0%

@taran_1407 I am getting run-time error. I tried too much to find where i am getting this but failed.
please help me. this is my code-->
https://www.codechef.com/viewsolution/15994545
thank you

link

answered 30 Oct '17, 09:57

umesh9414's gravatar image

5★umesh9414
182
accept rate: 12%

Mate

Try following tesr case

1

10000200000000000

(30 Oct '17, 13:00) taran_14076★

Can anyone give me a test case where my code fails? It's working well for all the test cases I checked.

PLEASE HELP ME!!!

I'm storing the digits in an array from one's place. Then I am iterating through all the digits and finding the new number by removing that particular digit. Now, I'm checking whether it is divisible by 6 or not and if it is then I check whether it is largest number possible which I initially set to -1. At last I'm printing the new number with k-1 digits where k is the total number of digits in the initial number. Leading zeros will be printed since I used %0*d and passed k-1 and maxnum to it. LINK:-My Solution

link

answered 30 Oct '17, 14:31

ramini's gravatar image

2★ramini
615
accept rate: 8%

Mate, You cannot take a number with 10^5 digits in int data type. You have to input it as a string.

Try following test case.

1

10000200000000000

Second thing, Your solution try to delete one digit, check the resultant number. This way, Your solution has time complexity O(N^2), which won't even pass the time limit for number of digits upto 10^3.

(30 Oct '17, 19:19) taran_14076★

Taran, sorry for posting that link which didn't work. I updated it. Can you help me?

link

answered 30 Oct '17, 19:48

nimmumanoj's gravatar image

3★nimmumanoj
01
accept rate: 0%

In problem maximum number in my code I am not able to figure out mistake. It gives wrong answer on submission.

Can anyone help me debugging it. Link to my code is

Here.

Please help :)

link

answered 30 Oct '17, 21:41

jb1998's gravatar image

3★jb1998
557
accept rate: 16%

edited 30 Oct '17, 22:28

The link that I gave before was not working , Sorry for that.. Now I updated the link

(30 Oct '17, 22:30) jb19983★

Try the test case

1

3602

Correct answer is 360

PS:what if last two digits are both even and last digit on deletion gives the maximum answer.

Enjoy coding :D

(30 Oct '17, 23:32) taran_14076★

i dont know why my code is getting wrong anser. please help me; link is https://www.codechef.com/viewsolution/16015871

link

answered 31 Oct '17, 00:05

ankitssingh26's gravatar image

5★ankitssingh26
161
accept rate: 16%

Try test case

1

660

Correct answer 66, your answer 60

(31 Oct '17, 00:14) taran_14076★

thanks,buddy

(31 Oct '17, 00:19) ankitssingh265★

i dont know why my code is getting wrong answer, please help; link https://www.codechef.com/viewsolution/15998613

link

answered 02 Nov '17, 18:56

koushik_iyer's gravatar image

2★koushik_iyer
1
accept rate: 0%

You cannot take a number with 10^5 digits as int data type. You have to take it as string.

Try following test case

1

11100000000000000000000

Enjoy

(02 Nov '17, 20:30) taran_14076★

thanks much!

(02 Nov '17, 21:49) koushik_iyer2★

simply just check when sum of the digit >= 10 take mod of the ans and store it in an array during calculation in O(n) time then print the same

link

answered 02 Nov '17, 20:47

coder_ishmeet's gravatar image

4★coder_ishmeet
214
accept rate: 0%

Hey can anyone plz tell me what's wrong with this code? https://www.codechef.com/viewsolution/15993064

link

answered 03 Nov '17, 16:58

vaibhavvg's gravatar image

6★vaibhavvg
112
accept rate: 0%

edited 03 Nov '17, 16:59

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:

×15,852
×64

question asked: 28 Oct '17, 23:54

question was seen: 2,192 times

last updated: 03 Nov '17, 16:59