0
$\begingroup$

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

$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W.
    May 3, 2022 at 18:06
  • $\begingroup$ What is the influence of the $A_i \text{ on the } \frac{C_k}{B_k}$? $\endgroup$
    – greybeard
    May 3, 2022 at 20:47
  • $\begingroup$ @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. $\endgroup$
    – John L.
    May 4, 2022 at 7:19
  • $\begingroup$ I have already tried approaching this multiple times. Also, this is not from any ongoing contest, as I mentioned in the link, above. $\endgroup$ May 5, 2022 at 11:15
  • $\begingroup$ The link does not lead to the problem. Please fix that. $\endgroup$
    – user16034
    Aug 25, 2023 at 8:01

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.