DUCS Winter Warm Up Discussion


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

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

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

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

1 Like

Cant the easier version be done using pq ?

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

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

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

you simply have to calculate minimum lcm

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?

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

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

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.

But using this,

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

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.

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

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

1 Like

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?

Can nybody tell me why this doesnt work?

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

[Tanya and Rookies Cats (easy v)]

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?

Access denied…

1 Like