TopCoder problem "ComputationalComplexity" used in SRM 243 (Division II Level One)



Problem Statement

    You are testing several algorithms and you want to find the fastest one for your task. Computational complexities of these algorithms will be given to you in three int[]s - constant, power and logPower. The ith algorithm needs on average constant[i]*Npower[i]*lnlogPower[i](N) operations to solve your task.

Given an int N, the size of your task, return the 0-based index of the fastest algorithm. In case of a tie, return the smallest index.
 

Definition

    
Class:ComputationalComplexity
Method:fastestAlgo
Parameters:int[], int[], int[], int
Returns:int
Method signature:int fastestAlgo(int[] constant, int[] power, int[] logPower, int N)
(be sure your method is public)
    
 

Notes

-ln(x) in the formula means natural logarithm of x. It can be computed as:

- Math.log(x) in java

- log(x) in C++

- Math.Log(x) in C# and VB.
 

Constraints

-constant, power and logPower will have the same number of elements.
-constant, power and logPower will each have between 1 and 50 elements, inclusive.
-N will be between 1 and 1000, inclusive.
-All elements of power and logPower will be between 0 and 5, inclusive.
-All elements of constant will be between 1 and 100, inclusive.
 

Examples

0)
    
{5, 50, 45}
{2, 1, 1}
{0, 1, 1}
400
Returns: 2
The first algorithm needs 5*400*400 = 800000 operations. The second one needs about 50*400*ln(400) (approximately 170000) and the third is even a bit faster.
1)
    
{5, 50, 45}
{2, 1, 1}
{0, 1, 1}
10
Returns: 0
For the small N the first algorithm works faster.
2)
    
{100}
{5}
{5}
1000
Returns: 0
3)
    
{32, 33, 58, 93, 8, 27, 43, 69, 95, 77,
 57, 73, 87, 87, 50, 92, 67, 20, 2, 46,
 73, 48, 25, 90, 48, 18, 28, 26, 20, 33,
 59, 48, 69, 4, 19, 13, 10, 78, 55, 90}
{5, 0, 1, 4, 0, 3, 5, 4, 3, 3,
 0, 5, 0, 5, 5, 3, 0, 4, 1, 1,
 4, 0, 2, 4, 0, 0, 3, 2, 0, 0,
 4, 3, 5, 0, 2, 4, 3, 4, 3, 0}
{2, 2, 2, 0, 4, 5, 2, 3, 4, 5,
 0, 0, 1, 4, 2, 5, 2, 4, 5, 0,
 5, 4, 3, 0, 4, 1, 1, 3, 3, 0,
 1, 5, 2, 1, 1, 4, 0, 0, 2, 3}
1000
Returns: 33

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=4510

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=7218&pm=4510

Writer:

Olexiy

Testers:

PabloGilberto , lbackstrom , brett1479

Problem categories:

Simple Math, Simple Search, Iteration