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

×

Editorial/Submissions request for ARMYFGT

It seemed an easy problem. I even took care of edge cases I think. I don't know why I'm getting WA. Will the submissions be made public?

asked 31 Dec '18, 00:18

sddeltech's gravatar image

4★sddeltech
654
accept rate: 0%


You are not considering the probability of overflow in lcm. I also got a wrong answer verdict for the same condition.

My accepted solution link is Solution Link

link

answered 31 Dec '18, 12:55

sorcerer48's gravatar image

5★sorcerer48
1355
accept rate: 30%

edited 31 Dec '18, 12:55

it was not what you said but it had to do with the lcm! I use ceil function in the code and when lcm got very very large, ceil(1/lcm), which i expected to give 1, gave 0. thanks!

(31 Dec '18, 23:55) sddeltech4★

got AC! thanks.

(01 Jan, 00:05) sddeltech4★

Your solution is giving WA on corner case. Here it is :https://ideone.com/mwfrVA The correct answer is +1.

link

answered 31 Dec '18, 19:24

ankush_953's gravatar image

4★ankush_953
657
accept rate: 8%

sorry, your link is private(it says "forbidden"). could you please make a public link or tell me the testcase here?

(31 Dec '18, 23:23) sddeltech4★

It is working now. Sorry for inconvenience. :-)

(01 Jan, 01:24) ankush_9534★

Thanks. By the way, could you please tell how did you find this case? Did you have access to the cases, did you generate cases specifically for this problem or is there some tool I am unaware of?

(01 Jan, 15:16) sddeltech4★

I just tried to generate the worst case. I just needed to find when n and m both are zero. In such cases, your code would have been failed. And I don't have access to test cases. I generated this specifically for this question after seeing your post. :)

(01 Jan, 20:52) ankush_9534★

Do you have the link to the problem and your attempted solution?

link

answered 31 Dec '18, 00:21

masood786's gravatar image

4★masood786
1063
accept rate: 13%

Here is the problem. Here is my solution.

(31 Dec '18, 09:59) sddeltech4★

What is the LCM overflow condition? Can you explain a bit?

link

answered 31 Dec '18, 17:13

rajankit402's gravatar image

3★rajankit402
1
accept rate: 0%

let we have found lcm upto index i - 1. Then for our current index i , lcm would be lcm = (lcm*arr[i]) / (gcd(arr[i] , lcm))

Here you are multiplying two possibly large numbers which could extend upto number more than 10^9. These would lead to overflow since long long is also not capable of holding such large numbers. So I have kept a condition which would not let number to exceed my upper bound.

The condition for the same is if (R < (lcm*arr[i]) . gcd(lcm , arr[i])) then break my loop. The further simplification can be seen in the code which I have linked in my answer.

Hope this helps. :)

(31 Dec '18, 19:55) sorcerer485★

If anyone's interested in C++ solution - Link

link

answered 01 Jan, 10:58

horcrux2301's gravatar image

4★horcrux2301
17117
accept rate: 5%

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
×3
×1

question asked: 31 Dec '18, 00:18

question was seen: 343 times

last updated: 02 Jan, 18:56