Problem: Buggy CalculatorProblem StatementAdd two number A and B without carrying forward any value. SolutionThe 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 zeroesSuppose 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.length1; 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 NumberProblem StatementGiven a number N, output Maximum number possible which satisfy constraint that number is multiple of 6. If no such number possible print 1. SolutionFirst thing to know:
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
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

For the second question my solution is O(n) but still giving TLE, please look into this: https://www.codechef.com/viewsolution/15998898 answered 28 Oct '17, 23:57
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_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)
link to the code : https://www.codechef.com/viewsolution/15981694
(29 Oct '17, 08:39)
Probably weak test cases...
(30 Oct '17, 12:55)

hey taran my code is giving wa in 1st subtask. any testcase where it might fail? https://ideone.com/yKzrA3 answered 29 Oct '17, 00:15
Mate, i replied on your thread too. I'm still working with your solution only. :)
(29 Oct '17, 00:18)
sorry bro didn't see then. thanks :)
(29 Oct '17, 00:22)
No problem mate.
(29 Oct '17, 00:26)
1
By the way, why are you using variable p in your code??
(29 Oct '17, 00:26)
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)

For the first question why is my solution giving WA in Subtask 2? answered 29 Oct '17, 00:22
Try Following test case. 1 55 54 Correct answer 9 Your answer 09
(29 Oct '17, 00:26)
@taran_1407 but wouldn't the calculator print exactly 09 only?
(29 Oct '17, 00:28)
Nope, It isn't mentioned in problem but a calculator always print 9, not 09. You may try. :)
(29 Oct '17, 00:30)
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)
1
No problem at all. By the way, the calculator isn't that faulty :D
(29 Oct '17, 00:36)

@vishaldugyala I guess u haven't taken care of the fact that no.of digits may be different answered 29 Oct '17, 00:25
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)

Thanks Taran! Great job helping out others. Kudos! answered 29 Oct '17, 00:27

Is erase function also linear in Time??? answered 29 Oct '17, 00:28
Which language you are talking about mate?? I work with java. Either share code link. :)
(29 Oct '17, 00:29)
Here is my sol:https://www.codechef.com/viewsolution/15995643
(29 Oct '17, 00:38)
The logic of your code isn't clear to me. Can you elaborate??
(29 Oct '17, 00:40)
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 (suma[i])%3 or not I think it's just because erase giving Tle
(29 Oct '17, 00:46)
@taran_1407 plzz join this group,it gonna helpful for us!!
(29 Oct '17, 00:50)
As far as i know about c++, String s = p itself takes Linear time, making your solution time out.
(29 Oct '17, 00:53)
showing 5 of 6
show all

Thanks for the explanation :) answered 29 Oct '17, 00:43
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 (sumd)%3==0 where d is the deleted digit.
(29 Oct '17, 00:49)

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

I'm getting WA in the second subtask in BUGCAL... Why? answered 29 Oct '17, 09:50
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)
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)

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. answered 29 Oct '17, 10:08
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)

I don't know why i am getting RE(NZEC)? this is my solution https://www.codechef.com/viewsolution/15995869 answered 29 Oct '17, 10:18
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)
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)
by doing these it again show RE(NZEC)
and i doesn't understand
(29 Oct '17, 19:10)
@vparas , please read about java errors on input, limit of int and long data types.
(29 Oct '17, 19:42)
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)
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)
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 answered 29 Oct '17, 10:45
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)

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 ?? answered 29 Oct '17, 10:54

@taran_1407 can you give some testcases for 2nd question. answered 29 Oct '17, 11:16
Maybe you can ask problem setters for this.. They can provide much better test cases then i can. :)
(29 Oct '17, 17:44)
can u tell me the solution for 102 and 100
(29 Oct '17, 21:58)

https://www.codechef.com/viewsolution/15988759 What is wrong in this code for BUGCAL? PLease help. Everything handled! answered 29 Oct '17, 11:39
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)
plzz join fb group:https://www.facebook.com/groups/1232901383475983/
(29 Oct '17, 13:21)

@shivam2296 When you are swapping a&b then you should also swap the length also. answered 29 Oct '17, 12:07

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 answered 29 Oct '17, 12:34
it's showing Acess Denied :(
(29 Oct '17, 13:46)
That link was wrong! I changed it:D
(30 Oct '17, 19:46)
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)

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 answered 29 Oct '17, 13:30
Ur code printing leading Zeroes!!
(29 Oct '17, 17:11)
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)

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? answered 29 Oct '17, 22:00
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)

Loving your explanations dude. well done C.A :P as your institute suggests answered 30 Oct '17, 02:27

@taran_1407
I am getting runtime error. I tried too much to find where i am getting this but failed. answered 30 Oct '17, 09:57

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 k1 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 k1 and maxnum to it. LINK:My Solution answered 30 Oct '17, 14:31
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, sorry for posting that link which didn't work. I updated it. Can you help me? answered 30 Oct '17, 19:48

i dont know why my code is getting wrong anser. please help me; link is https://www.codechef.com/viewsolution/16015871 answered 31 Oct '17, 00:05
Try test case 1 660 Correct answer 66, your answer 60
(31 Oct '17, 00:14)
thanks,buddy
(31 Oct '17, 00:19)

i dont know why my code is getting wrong answer, please help; link https://www.codechef.com/viewsolution/15998613 answered 02 Nov '17, 18:56
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)
thanks much!
(02 Nov '17, 21:49)

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 answered 02 Nov '17, 20:47

Hey can anyone plz tell me what's wrong with this code? https://www.codechef.com/viewsolution/15993064 answered 03 Nov '17, 16:58
