10407 - Simple division

All about problems in Volume 104. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 10407 - Simple division

Post by lighted » Wed Nov 12, 2014 6:32 pm

I see that you already got accepted. :)
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

richatibrewal
New poster
Posts: 49
Joined: Mon Jun 16, 2014 7:40 pm

Re: 10407 - Simple division

Post by richatibrewal » Wed Nov 12, 2014 7:50 pm

Yes, by the method of gcd. But i couldn't understand the test case. Will someone plz throw some light on the 3rd test case??

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 10407 - Simple division

Post by lighted » Thu Nov 13, 2014 11:40 am

14%3 = 2
whereas -22%3 = 1
There is mistake in mod calculation. (-22) % 3 = (-21) % 3 + (-1) % 3 = 0 + (-1 + 3) % 3 = 2.

Or (-22) % 3 = (-22 + 3 + 3 + 3 + 3 + 3 + 3 + 3 + 3) % 3 = 2.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

richatibrewal
New poster
Posts: 49
Joined: Mon Jun 16, 2014 7:40 pm

Re: 10407 - Simple division

Post by richatibrewal » Thu Nov 13, 2014 1:15 pm

Thanx :)

zodiacLeo
New poster
Posts: 2
Joined: Sun Feb 07, 2016 8:01 pm

Re: 10407 Simple Division - Can anybody explain!?

Post by zodiacLeo » Sun Mar 13, 2016 7:47 pm

theylosehope wrote:Hello guys,

I've got "10407 - Simple Division" AC using the description in Algorithmist. However, I don't fully understand it.

My algorithm:
- Add numbers to set "S".
- If size of S is two: print the difference between the two numbers.
- If size of S is > 2: Erase the first element, and find GCD among all the differences between the remaining numbers.

This works correctly. But can anybody explain it in simple words? How can I figure out that the largest dividend with same remainder among a set of numbers is the GCD among the differences except the first difference?

Thanks in advance.
Let there be 3 (replace "3" with "n" after I complete the explanation) numbers, n1, n2, n3.
The problem claims that there exists a number, "x" which given same remainder, "r" when you divide each of the three numbers with x.
I know for a fact that, if one removes the remainder from a dividend, then the number so obtained becomes completely divisible by divisor( "x" in this case) (which I still have to find). Taking this further, if I subtract "r" from each number like - "n1-r", "n2-r", and "n3-r", then these numbers would be divisible by x.

So we have a number "x" which divides 3 numbers (GCD is screaming!!!). Yes!! x = GCD( n1-r, n2-r, n3-r) is your answer. So if you generate "r" iteratively (like r = 0, 1, 2, ...) and subtract it from each number and then find the GCD then, BAM!! You have your answer!
(The above solution is likely to TLE, but it is important to understand the "improved" solution)

Let's try to improve this further -
My goal is to reduce each number in the list to a values that give me remainder 0. More precisely, I want to convert ->
n1 -> n1-r
n2 -> n2-r and
n3 -> n3-r. But in just one step!. How? How?

If I make the first number (n1) as 0, and subtract n1 from each of the other number then I have something like this -
n1 = 0
n2 = n2 - n1
n3 = n3 - n1

If I choose any number as a divisor and n1 as the dividend, then the remainder is always going to be zero. So in order to find a number that divides n2, and n3 completely, I need to find the GCD(n2, n3).

Post Reply

Return to “Volume 104 (10400-10499)”