DUCS Winter Warm Up Discussion

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
21

20 digits is already out of bound

1 Like
22

For the first one let x=gcd(k,ar[i]).

LCM = (k*ar[i])/x.

Make ar[i] = ar[i] /x and then check for each i if log10(k)+log10(x) <= 18. If so then you can take the LCM into consideration. Take min of all possible(less than 1e18) LCM’s.

For the second problem, you can use a set of pair of ints, which hold the value and its position and then it is simulation of the problem.

Link to solution of first problem
Link to solution of second problem

2 Likes
23

Thank you :slight_smile:

24

Actually you can use any height balanced tree or heaps for solving DWW19F. Data structures like Priority Queue or Multiset would be a big help. So no explicit need of a Segment tree.

25

And for DWW19B, there is a simple way to check for overflow in LCM. Though the logarithm approach shared by @sdssudhu is beautiful in itself, but there is another simple integer arithmetic technique also.

Let’s say INF = 10^{18} + 1, now we need to check if lcm(K, A_{i}) \ge INF. Yes lcm(K, A_{i}) can be very large (out of bounds for a 64 bit integer as well, for the last sub task).

So, you can check it like this:

We know that lcm(K, A_{i}) = \frac{K \times A_{i}}{gcd(K, A_{i})}

Just check if \frac{A_{i}}{gcd(K, A_{i})} \ge \Big\lceil\frac{INF}{K}\Big\rceil, that’s it.

And you don’t even need to calculate the ceil value using real arithmetic, there’s a cool integer arithmetic trick:

\big\lceil\frac{a}{b}\big\rceil = \frac{a + b - 1}{b}

Hope it helps!
Also, all solutions have been made public now so you can check them!
Happy Coding!

2 Likes
26

The following is the idea I used to solve the first problem Krishna and Coffee Shop in C++14:

  1. Let ans = LLONG\_MAX and B_{max} = \large\lfloor\frac{10^{18}}{{K}}\rfloor.

  2. For each 1 \leq i \leq N: Let B_{i} = \large \frac{A_i}{gcd(A_i,K)}. If B_i \leq B_{max}, then update ans to min(ans,K*B_{i})

  3. If ans == LLONG\_MAX, then update ans to -1.

The threshold value B_{max} ensures that the answer considers only the values of A_{i} where lcm(A_{i},K) does not exceed 10^{18} without computing the product A_{i} K explicitly, which can be larger than LLONG\_MAX. If no value of B_{i} is less than or equal to B_{max}, then the answer to the test case is -1.

Alternatively, the C++14 library function std::__detail::__lcm can be used directly to compute the answer without computing B_{max} as follows.

https://ideone.com/lvUdqY

1 Like