Statistics

Problem Statement for "ComputationalComplexity"

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

  1. {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.

  2. {5, 50, 45}

    {2, 1, 1}

    {0, 1, 1}

    10

    Returns: 0

    For the small N the first algorithm works faster.

  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}

    300

    Returns: 2

  4. {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

  5. {100}

    {5}

    {5}

    1000

    Returns: 0

  6. {1, 3, 9, 27, 81}

    {5, 4, 3, 2, 1}

    {5, 5, 5, 5, 5}

    3

    Returns: 0

  7. {1, 4, 16, 64}

    {3, 2, 1, 0}

    {4, 4, 4, 4}

    4

    Returns: 0

  8. {1, 2, 4, 8, 16, 32}

    {5, 4, 3, 2, 1, 0}

    {4, 4, 4, 4, 4, 4}

    2

    Returns: 0

  9. {45, 34, 69, 61, 55, 96, 86, 58, 25, 21, 22, 93, 68, 92, 8, 39, 50, 10}

    {5, 0, 3, 0, 2, 4, 4, 4, 5, 1, 2, 5, 1, 3, 3, 0, 2, 3}

    {4, 2, 3, 4, 1, 5, 5, 1, 4, 3, 4, 1, 1, 0, 1, 4, 3, 5}

    958

    Returns: 1

  10. {53, 52, 76, 14, 65, 73, 57, 32, 68, 38, 55, 51, 25, 37, 29, 26, 62, 10, 13, 53, 70, 49}

    {1, 3, 0, 0, 0, 5, 4, 0, 3, 1, 2, 1, 1, 3, 4, 1, 2, 2, 3, 3, 1, 3}

    {3, 1, 4, 5, 2, 0, 3, 4, 0, 0, 5, 1, 4, 0, 2, 1, 1, 2, 4, 2, 5, 3}

    21

    Returns: 4

  11. {73, 76, 17, 39, 81, 29, 69, 5, 28, 34, 16, 21, 6, 20, 53, 43, 27, 91, 69, 13, 63, 94, 73, 9, 38, 84, 90, 49, 93, 58, 69, 9, 6, 59, 16, 2, 84, 33, 60, 83, 43, 78, 77, 85, 2, 15}

    {2, 4, 2, 1, 4, 4, 0, 5, 4, 3, 3, 4, 5, 2, 4, 0, 0, 4, 0, 1, 3, 1, 3, 3, 3, 3, 1, 5, 3, 2, 1, 4, 5, 0, 0, 1, 5, 5, 5, 0, 1, 1, 1, 5, 2, 4}

    {3, 2, 2, 5, 4, 5, 2, 2, 3, 0, 4, 3, 5, 5, 0, 4, 4, 2, 2, 2, 3, 1, 5, 3, 1, 0, 2, 1, 2, 1, 3, 0, 0, 2, 3, 5, 1, 2, 5, 3, 2, 2, 2, 3, 4, 1}

    927

    Returns: 33

  12. {28, 63, 24, 27, 20, 39, 71, 39, 56, 98, 84, 59, 64, 94, 29, 57, 72, 94, 58, 2, 38, 78, 34, 16, 35, 15, 70, 84, 51, 35, 100}

    {3, 3, 3, 0, 4, 3, 0, 2, 0, 2, 5, 2, 1, 5, 5, 5, 3, 0, 5, 4, 4, 4, 0, 4, 1, 4, 0, 1, 3, 4, 1}

    {4, 1, 4, 4, 2, 0, 3, 4, 4, 3, 4, 2, 2, 3, 5, 2, 2, 4, 0, 1, 3, 0, 4, 0, 5, 3, 1, 0, 4, 2, 4}

    410

    Returns: 26

  13. {53, 34, 50, 49, 51, 11, 14, 81, 42, 93, 77, 29, 12, 19, 84}

    {1, 5, 2, 1, 2, 1, 4, 4, 4, 5, 4, 3, 1, 0, 5}

    {4, 3, 5, 4, 1, 2, 2, 1, 1, 2, 2, 0, 3, 2, 2}

    748

    Returns: 13

  14. {42, 49, 9, 27, 29, 80, 43, 61, 46, 91, 47, 77, 9, 25, 96, 1, 85, 48, 56, 54, 56, 93, 96, 39, 97, 72, 34}

    {2, 5, 0, 5, 1, 0, 5, 0, 1, 5, 5, 1, 1, 2, 2, 0, 5, 0, 4, 2, 4, 3, 4, 1, 1, 1, 1}

    {3, 1, 0, 5, 3, 2, 1, 3, 3, 4, 3, 5, 1, 1, 4, 1, 1, 0, 1, 5, 3, 5, 2, 2, 4, 3, 3}

    48

    Returns: 15

  15. {86, 19, 33, 64, 42, 21, 100, 90, 87, 83, 42, 40, 75, 40, 19, 2, 11, 38, 60, 53, 2, 7, 79, 6, 52, 37, 76, 42, 100, 13, 48, 68, 57, 19, 84, 13, 62, 83, 88, 31, 83, 91, 88, 49, 90, 75, 51, 94, 77, 85}

    {2, 5, 4, 1, 5, 5, 5, 0, 3, 2, 3, 4, 1, 3, 5, 5, 0, 0, 0, 5, 5, 3, 0, 5, 3, 1, 5, 4, 4, 4, 3, 3, 3, 5, 3, 5, 1, 1, 4, 4, 5, 2, 4, 3, 0, 0, 3, 3, 4, 4}

    {2, 5, 2, 5, 3, 5, 3, 5, 4, 3, 5, 1, 5, 4, 2, 0, 5, 2, 0, 2, 5, 2, 1, 0, 2, 5, 0, 0, 5, 0, 5, 4, 1, 1, 1, 2, 0, 4, 5, 5, 3, 3, 1, 5, 2, 0, 3, 0, 2, 1}

    692

    Returns: 18

  16. {7, 2, 88, 59, 67, 3, 94, 5, 16, 17, 58, 48, 61, 57, 58, 64, 71, 29, 98, 46, 31, 46, 21, 88, 64, 66, 90, 43, 35, 40, 89}

    {0, 2, 2, 4, 5, 3, 2, 5, 3, 3, 0, 1, 2, 4, 0, 0, 4, 1, 0, 0, 5, 1, 2, 4, 2, 3, 4, 2, 2, 0, 4}

    {2, 1, 0, 5, 2, 4, 1, 4, 2, 2, 2, 4, 1, 3, 1, 1, 2, 2, 5, 4, 5, 4, 2, 4, 3, 4, 1, 5, 2, 5, 3}

    25

    Returns: 0

  17. {40, 19, 68, 36, 21, 91, 23, 44, 63, 34, 12, 8, 88, 59, 88, 42, 72, 9, 21, 8, 41, 23, 77, 82, 91, 40, 24}

    {1, 2, 5, 0, 3, 5, 4, 0, 1, 2, 3, 2, 3, 0, 4, 4, 0, 4, 1, 2, 3, 2, 1, 4, 0, 0, 0}

    {2, 0, 5, 5, 4, 4, 0, 4, 1, 0, 3, 5, 2, 5, 4, 3, 0, 2, 1, 0, 0, 0, 3, 3, 5, 0, 4}

    59

    Returns: 25

  18. {75, 34, 38, 63, 33}

    {2, 2, 4, 0, 4}

    {3, 5, 0, 0, 0}

    368

    Returns: 3

  19. {82, 66, 13, 45, 87, 3, 71, 67, 75, 48, 1, 29, 18, 84, 81, 45, 83, 74, 51, 64, 21, 94, 19, 22, 30, 81, 18, 74, 95}

    {0, 4, 4, 3, 2, 0, 2, 3, 2, 2, 4, 4, 5, 5, 3, 4, 2, 2, 2, 2, 2, 0, 1, 4, 5, 2, 1, 2, 5}

    {5, 5, 2, 0, 5, 1, 3, 4, 0, 4, 5, 3, 3, 2, 2, 4, 2, 5, 3, 0, 5, 0, 0, 3, 1, 1, 5, 3, 1}

    235

    Returns: 5

  20. {45, 74, 59, 44, 41, 82, 1, 100, 22, 85, 47, 15, 55, 33, 16, 10, 6, 70, 26, 12, 91, 28, 6, 19, 78, 56, 45, 13, 100, 76, 16, 6, 93, 70, 17, 70, 55, 7, 72, 73, 1, 34, 37, 55, 18, 92, 66, 89, 84, 17}

    {0, 2, 1, 4, 3, 3, 1, 5, 4, 3, 5, 1, 1, 5, 4, 1, 2, 2, 3, 1, 2, 5, 0, 5, 1, 2, 4, 5, 0, 2, 0, 1, 1, 3, 4, 1, 3, 3, 5, 0, 3, 3, 4, 3, 5, 2, 0, 5, 2, 3}

    {0, 2, 2, 4, 5, 4, 4, 1, 2, 4, 1, 4, 2, 2, 2, 5, 1, 5, 3, 3, 1, 2, 0, 0, 3, 1, 0, 3, 2, 2, 4, 2, 5, 5, 3, 5, 4, 4, 3, 5, 4, 2, 5, 0, 2, 3, 1, 5, 1, 1}

    532

    Returns: 22

  21. {44, 62, 54, 45, 47, 60, 14, 38, 91, 11, 29, 45, 24, 12, 2, 34, 45, 16, 89, 88, 74, 26, 86, 72, 28, 90, 14, 13, 25, 45, 51, 89, 10, 18, 99, 91, 51, 54, 68, 18, 38, 3}

    {5, 4, 3, 3, 1, 4, 3, 1, 5, 1, 3, 4, 5, 2, 1, 4, 3, 2, 4, 0, 4, 5, 3, 4, 4, 1, 3, 2, 5, 5, 5, 3, 3, 3, 5, 1, 2, 1, 0, 0, 3, 1}

    {1, 1, 3, 0, 1, 1, 2, 0, 5, 3, 1, 2, 0, 5, 5, 5, 4, 2, 0, 4, 4, 1, 2, 0, 3, 4, 4, 1, 0, 5, 2, 4, 4, 1, 1, 2, 2, 5, 2, 2, 0, 0}

    287

    Returns: 39

  22. {94, 96, 84, 58, 19, 41, 41, 83, 2, 29, 49, 69, 45, 57, 96, 32, 26, 70, 27, 10, 59, 46, 74, 8, 61, 15, 90, 98, 84, 56, 72, 82, 50, 1, 12, 74, 20, 51, 18, 5, 74}

    {2, 5, 0, 3, 5, 1, 2, 4, 0, 5, 5, 4, 5, 0, 4, 2, 2, 1, 5, 0, 1, 4, 0, 2, 5, 1, 4, 4, 5, 2, 4, 0, 1, 2, 3, 1, 3, 2, 1, 5, 5}

    {5, 3, 0, 0, 2, 5, 5, 0, 0, 1, 0, 5, 0, 1, 5, 2, 4, 2, 4, 1, 3, 3, 0, 4, 0, 5, 3, 2, 5, 5, 5, 4, 3, 1, 1, 1, 5, 5, 3, 4, 4}

    961

    Returns: 8

  23. {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

  24. {86, 22, 69, 77, 51, 2, 9, 6, 30, 15, 58, 74, 80, 82, 51, 18, 100, 32, 98, 73, 46, 15, 59, 52, 96, 28}

    {0, 5, 5, 4, 3, 3, 5, 0, 4, 4, 0, 3, 1, 0, 4, 1, 0, 4, 2, 1, 1, 2, 4, 0, 0, 0}

    {5, 3, 2, 2, 2, 1, 5, 5, 4, 0, 3, 3, 1, 0, 5, 0, 5, 3, 4, 2, 5, 5, 5, 2, 0, 3}

    383

    Returns: 13

  25. {14, 2, 42, 27, 84, 56, 11, 45, 33, 80, 41, 62, 69, 43, 18, 41, 37, 64, 16, 43, 27, 43, 83, 13, 30, 23, 12, 63, 53, 19, 7, 63, 76, 11, 68, 38, 34, 59}

    {0, 3, 5, 4, 5, 0, 0, 2, 5, 3, 1, 0, 0, 1, 0, 3, 0, 4, 1, 1, 5, 2, 5, 1, 0, 0, 3, 3, 4, 0, 0, 0, 2, 2, 1, 4, 5, 2}

    {0, 0, 2, 1, 3, 5, 0, 5, 0, 5, 0, 2, 2, 0, 2, 0, 4, 4, 1, 1, 2, 4, 5, 0, 0, 2, 0, 1, 4, 5, 0, 4, 0, 1, 1, 2, 4, 0}

    815

    Returns: 30

  26. {98, 52, 45, 58, 76, 27, 36, 54, 5, 51, 82, 94, 92, 38, 62, 8, 51, 6, 38, 38, 51, 58, 71, 26}

    {1, 5, 1, 3, 2, 0, 0, 1, 1, 2, 3, 0, 2, 3, 3, 1, 0, 3, 1, 3, 3, 3, 1, 4}

    {5, 3, 0, 4, 3, 3, 4, 2, 3, 0, 2, 2, 0, 1, 1, 0, 3, 4, 2, 1, 0, 3, 2, 3}

    503

    Returns: 11

  27. {86, 11, 42, 11, 66, 60, 64, 80, 78, 30, 52, 20, 43, 55, 21, 5, 77, 97, 31, 75, 91, 55, 95, 35, 94, 91, 24, 94, 9, 33, 79, 31, 64, 79, 2, 59, 56, 69, 42, 44, 41, 34, 79, 44}

    {0, 0, 0, 5, 5, 3, 0, 5, 4, 4, 2, 4, 2, 4, 4, 3, 0, 5, 5, 0, 4, 2, 4, 3, 5, 5, 4, 5, 1, 3, 0, 3, 3, 0, 0, 5, 5, 4, 3, 2, 5, 2, 5, 0}

    {4, 3, 2, 0, 2, 3, 2, 2, 3, 4, 2, 3, 3, 5, 4, 1, 1, 0, 5, 5, 3, 3, 2, 4, 0, 2, 2, 3, 3, 3, 0, 4, 3, 2, 1, 5, 0, 1, 1, 2, 3, 5, 1, 4}

    195

    Returns: 34

  28. {62, 84, 41, 1, 50, 16, 20, 32, 43, 60, 35, 28, 82, 19, 61, 73, 3, 39, 12, 83, 59, 13, 52, 17, 72, 6, 65, 94, 10, 29, 59, 53, 85, 44, 23, 15, 43}

    {3, 1, 4, 4, 0, 5, 4, 5, 4, 3, 2, 0, 0, 1, 3, 1, 4, 5, 5, 1, 5, 4, 5, 5, 1, 3, 5, 2, 1, 0, 5, 0, 4, 1, 3, 3, 1}

    {5, 5, 2, 4, 5, 4, 0, 2, 3, 5, 3, 5, 3, 0, 2, 3, 3, 0, 3, 2, 5, 2, 2, 5, 4, 2, 1, 5, 2, 1, 0, 0, 5, 3, 5, 4, 4}

    368

    Returns: 31

  29. {1, 25, 50, 72, 99, 100}

    {4, 3, 2, 1, 0, 5}

    {3, 3, 3, 3, 3, 5}

    1000

    Returns: 4

  30. {1, 1, 1}

    {1, 1, 1}

    {2, 1, 0}

    3

    Returns: 2

  31. {100}

    {5}

    {1}

    1000

    Returns: 0

  32. {3,96}

    {5,4}

    {4,5}

    163

    Returns: 0

  33. {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

  34. {44, 33, 45 }

    {0, 0, 0 }

    {0, 0, 0 }

    50

    Returns: 1

  35. {50, 50, 50 }

    {2, 2, 2 }

    {0, 0, 0 }

    400

    Returns: 0

  36. {100, 99 }

    {5, 5 }

    {5, 5 }

    1000

    Returns: 1

  37. {100 }

    {5 }

    {2 }

    1000

    Returns: 0

  38. {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, 1 }

    {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, 1 }

    {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, 1 }

    1000

    Returns: 33

  39. {100, 100 }

    {5, 4 }

    {1, 1 }

    1000

    Returns: 1

  40. {100, 100, 100 }

    {5, 4, 5 }

    {1, 1, 1 }

    1000

    Returns: 1

  41. {1, 1 }

    {0, 0 }

    {2, 3 }

    2

    Returns: 1

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: