DUCS Winter Warm Up Discussion

1

How to solve the above problem without using the Boost library?

Also, what was the approach to solving the following problem?

2

The second question is most probably a priority queue implementation. I’ll run my answer once they reopen submissions.

3

1st problem involves LCM trick, 2nd involves lovely segment trees :wink:

1 Like
4

Cant the easier version be done using pq ?

5

Can you explain the lcm trick,
I tried various approaches but all failed.
And than gave one final shot using boost library.

6

lcm(a,b) = a*b/gcd(a,b)

7

The first one can be done easily by simply checking overflow , if overflow does not happen then only update the answer.
The second one is a simple priority queue(Min Heap) implementation or we can say a multiset too

8

you simply have to calculate minimum lcm

9

I was doing same but won’t it overflow in worst case and it wont be possible to store in Long long?
when both a and b are near 10^18?

10

Ok, one doubt if one is using pq, i assume its of int pair type but then how would you choose the smaller element with the smaller index, as mentioned in the question, you’ll have to create a custom checker for it or could it be done some other way as well ?

1 Like
11

that must be why my code failed the third subtask!:grin:

12

For example consider 10^9+7 and other 10^18 the multiplication simply overflows the max permissible value , so better check if it overflows then don’t do any assignment to a variable and hence no need to update the answer.

13

But using this,

it would cause overflow in long long?
lcm(a,b) = a*b/gcd(a,b)

14

Originally priority queue will sort the elements in ascending order(Min heap) by first type and if same then sort by second type of pair value as far as i know.

15

using log trick calculate no of digits rather than caculating actual result and determine the -1 case

16

yeah I believe that is true for pair sorting, if it works in pq as well then its even easier implementation.

1 Like
17

Yeah i tried following,

ll gcdm = __gcd(x, k);
ll first = x/gcdm;
		ll second = k;
		int dig1 = GetNumberOfDigits(first);
		int dig2 = GetNumberOfDigits(second);
		if( dig1 + dig2 <= 20 ){
			ll ans = first * second;
			if( ans <= (ll)1e18 ){
				mn = min( ans, mn);
				poss = 1;
			}
		}

Any changes to it?

18

Can nybody tell me why this doesnt work?

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

[Tanya and Rookies Cats (easy v)]

19

K at max can be 10^18 and the other value also atmax 10^18.
So, gcd of them would be at max 10^18.
So, nothing to worry about gcd.

Then comes lcm, which is (a*b)/gcd(a,b)

Wait, here what’s the else condition?

20

Access denied…

1 Like