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

Improve this question
$\endgroup$
4
  • 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 at 18:06
  • $\begingroup$ What is the influence of the $A_i \text{ on the } \frac{C_k}{B_k}$? $\endgroup$
    – greybeard
    May 3 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 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$
    – Nachiket
    May 5 at 11:15

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.