Finding Sum(F(i)) where F(i) = min(⌈ Ai / B1 ⌉ * C1, ⌈ Ai / B2 ⌉ * C2, ⌈ Ai / B3 ⌉ * C3, .... ,⌈ Ai / Bm ⌉ * Cm)

Given three arrays A, B, and C of size n, m, and m respectively (1-based indexed). A function F(i) is defined as -

F(i) = minimum_of(⌈ Ai / B1 ⌉ * C1 , ⌈ Ai / B2 ⌉ * C2 , ⌈ Ai / B3 ⌉ * C3 , .... , ⌈ Ai / Bm ⌉ * Cm)

where ⌈x⌉ is defined as the ceiling function. For example : ⌈2.3⌉ = 3, ⌈3.9⌉ = 4 and ⌈3⌉ = 3.

Find the value of F(1) + F(2) + F(3) + ..... + F(n).

Constraints: 1 <= n, m, Ai, Bi, Ci <= 1000000

How do I solve this question in better than O(N*N) time complexity? The question is from a past onsite final. Problem link

• What's the best algorithm you can come up with? The community might not respond well to posts that consist of solely the statement of a contest-style task and a request for us to tell you how to solve it.
– D.W.
Commented May 3, 2022 at 18:06
• What is the influence of the $A_i \text{ on the } \frac{C_k}{B_k}$? Commented May 3, 2022 at 20:47
• @Nachiket It might appear preposterous to you that you are supposed to show some failed attempts to solve this difficult problem. That expectation is used to weed out people who just copy and past to gain some advantage elsewhere. Commented May 4, 2022 at 7:19
• I have already tried approaching this multiple times. Also, this is not from any ongoing contest, as I mentioned in the link, above. Commented May 5, 2022 at 11:15
Let's take a particular $$a_i$$ and $$b_j$$, what would be it's result if $$a_i$$ is a multiple of $$b_j$$, obviously $$\frac{a_i}{b_j} \cdot c_j$$.
Now, think about what would be the result if $$a_i$$ isn't a multiple of $$b_j$$, it would be the same answer as for the least multiple of $$b_j$$ which is greater than $$a_i$$.
For all $$b_j$$'s, we can calculate the answer for their multiples, now we just have to take minimum of the answer for the least multiples for every $$b_j$$, think about how to do it.