ComputationalComplexity
SRM 243 · 2005-05-17 · by Olexiy
SRM 243 · 2005-05-17 · by Olexiy · Simple Math, Simple Search, Iteration
Problem Statement
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 anint N, the size of your task, return the 0-based index of the fastest algorithm. In case of a tie, return the smallest index.
Given an
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)
{9, 8, 7, 6, 5, 4, 3, 2, 1}
{3, 3, 3, 3, 3, 3, 3, 3, 3}
{2, 2, 2, 3, 3, 3, 4, 4, 4}
300
Returns: 2
3)
{9, 8, 7, 6, 5, 4, 3, 2, 1}
{3, 3, 3, 3, 3, 3, 3, 3, 3}
{2, 2, 2, 3, 3, 3, 4, 4, 4}
10
Returns: 8
4)
{100}
{5}
{5}
1000
Returns: 0
Submissions are judged against all 41 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class ComputationalComplexity with a public method int fastestAlgo(vector<int> constant, vector<int> power, vector<int> logPower, int N) · 41 test cases · 2 s / 256 MB per case