roll_no_1's blog

Unable to understand Hackerearth's HourStorm #1's problem complex gcd's editorial
By roll_no_1, history, 6 years ago, In English

I recently participated in HourStorm #1 on hackerearth and during competition time, just managed to solve the last problem partially. Now, I decided to upsolve the problems starting with the first one, but I could not understand the editorial and the author's solution. To clarify my point that I am not trying to ask this without trying myself to understand the editorial, these are the few points that I did not understand:

  • The editorialist says to fix gcd(Ai, Aj), but I do not know how to do that, how can we fix the gcd, if we don't know all pairwise gcd s that exist without iterating over all pairs.

  • The line: An element Ai is inserted in the set as many times as the number of divisors of Bi. ( Even in his solution, the author iterates over all divisors of Bi, and pushes them at the back of the list p[Ai], I do not understand why he did this).

  • The author's solution: Frankly, I understood almost no part of the author's given solution. I mentioned one point in the previous point, and then I saw that he looped i over from mx_value downto 1, and considered every multiple of i. I did not understand why he did that, and what he did in those loops.

P.S. : Sorry, if the above points sound too nooby, but I don't know, whether only I am having troubles understanding it, or did the author omit some details which might be obvious to more experienced coders.

  • Vote: I like it
  • +19
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +16 Vote: I do not like it

A: The possible gcd's can be from 1 to maxVal = 10^5. If we find a gcd that doesn't appear in the array, it doesn't matter, because it means that gcd(a(i), a(j)) will be smaller, so gcd(a(i), a(j)) + gcd(b(i), b(j)) will be smaller, it won't change the answer. Example: for values 10 and 20, you will find them with gcd 2, 5, and, 10, but only 10 will change answer in the end.

B: we insert all divisors of b(i) in list L[i] of a(i). Because after we fix the "possible" gcd, we are interested by max value of GCD(B(i), B(j)), such that A(i) and A(j) are divisible by that gcd.

C: Iterate from mx_val to 1, which means the current gcd of A(i) and A(j). We're now interested in finding the maximum gcd(B(i), B(j)), which is the maximum value that appears at least twice in lists of numbers divisible by mx_val.

→ Reply