DUCS Winter Warm Up Discussion

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