Statistics

Problem Statement for "SortishDiv2"

Problem Statement

Everyone likes some sequences more than others. Every person has their own function which tells them how good a sequence is. For example, for some people this function could simply be the count of negative numbers in the sequence.


Jezalb's most favorite sequences are ones that are sorted in increasing order. When he sees a sequence S, he immediately calculates the number of pairs of indexes i < j such that S[i] < S[j]. He calls this number the "sortedness" of S.


This morning Jezalb entered a classroom and saw a permutation of 1 through N on the blackboard. He quickly calculated its sortedness. He then left the classroom and forgot the permutation. He only remembered the sortedness he computed. You are given this value in a int sortedness.


Later that day Jezalb reentered the classroom and saw a sequence on the blackboard. The sequence was a permutation of 1 through N, but with some elements erased. You are given this sequence as a int[] seq with N elements. Some of the elements in seq may be 0, which indicates an erased number.


Jezalb thinks that the sequence seq may have been obtained by erasing some elements of the sequence he saw during his first visit to the classroom. He would like to restore the erased elements.


You are given the int sortedness and the int[] seq. Return the number of ways in which he can fill in the missing elements into seq in such a way that the sortedness of the obtained permutation will be exactly sortedness.

Definition

Class:
SortishDiv2
Method:
ways
Parameters:
int, int[]
Returns:
int
Method signature:
int ways(int sortedness, int[] seq)
(be sure your method is public)

Constraints

  • sortedness will be between 0 and 1,000,000,000, inclusive.
  • seq will contain between 1 and 100 elements, inclusive.
  • Elements in seq will be between 0 and number of elements in seq, inclusive.
  • Positive elements in seq will be distinct.
  • Number of elements equal to 0 in seq will be between 0 and 5, inclusive.

Examples

  1. 5

    {4, 0, 0, 2, 0}

    Returns: 2

    There are six ways to fill in the missing elements. Out of those six permutations, only two have sortedness 5: {4, 1, 5, 2, 3} and {4, 3, 1, 2, 5}.

  2. 4

    {0, 0, 0, 0}

    Returns: 5

    All 5 possible ways are: {1, 3, 4, 2}, {1, 4, 2, 3}, {2, 1, 4, 3}, {2, 3, 1, 4}, {3, 1, 2, 4}.

  3. 2

    {1, 3, 2}

    Returns: 1

    There are no gaps and sortedness is indeed equal to 2.

  4. 2

    {1, 2, 0, 5, 0, 0}

    Returns: 0

    Regardless of how he fills in the gaps, the sortedness of the resulting permutation will always be greater than 2.

  5. 2405

    {4,62,10,33,86,58,9,49,68,84,30,88,90,67,59,0,19,25,12,72,44,85,51,5,13,98,94,91,24,47,27,95,100,77,15,92,0,70,55,31,28,81,75,39,34,74,2,89,45,63,36,64,43,93,29,50,7,54,0,82,71,66,97,53,23,38,69,52,48,21,26,17,20,57,37,61,11,73,60,78,18,79,0,80,16,83,56,35,0,32,6,96,1,99,46,76,22,87,3,41}

    Returns: 1

    100 5

  6. 7

    {0,0,0,0,0}

    Returns: 15

    5 5

  7. 0

    {0}

    Returns: 1

  8. 1

    {0}

    Returns: 0

  9. 987000123

    {0}

    Returns: 0

  10. 0

    {1}

    Returns: 1

  11. 1

    {1}

    Returns: 0

  12. 0

    {0,0}

    Returns: 1

  13. 1

    {0,0}

    Returns: 1

  14. 2

    {0,0}

    Returns: 0

  15. 0

    {1,0}

    Returns: 0

  16. 1

    {1,0}

    Returns: 1

  17. 2

    {1,0}

    Returns: 0

  18. 0

    {1,2}

    Returns: 0

  19. 1

    {1,2}

    Returns: 1

  20. 2

    {1,2}

    Returns: 0

  21. 0

    {0,2}

    Returns: 0

  22. 1

    {0,2}

    Returns: 1

  23. 2

    {0,2}

    Returns: 0

  24. 0

    {0,1}

    Returns: 1

  25. 1

    {0,1}

    Returns: 0

  26. 2

    {0,1}

    Returns: 0

  27. 0

    {2,0}

    Returns: 1

  28. 1

    {2,0}

    Returns: 0

  29. 2

    {2,0}

    Returns: 0

  30. 6

    {3,0,0,0,0,4}

    Returns: 3

  31. 1

    {0,0,0}

    Returns: 2

  32. 7

    {0,0,0,0,3}

    Returns: 3

  33. 5

    {3,5,0,2,4}

    Returns: 1

  34. 3

    {1,4,0,0}

    Returns: 1

  35. 9

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

    Returns: 1

  36. 3

    {1,4,3,0}

    Returns: 1

  37. 2

    {0,0,0,0}

    Returns: 5

  38. 9

    {4,1,0,6,0,0,3}

    Returns: 1

  39. 8

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

    Returns: 1

  40. 11

    {5,4,6,0,0,0,0}

    Returns: 1

  41. 1

    {3,0,2}

    Returns: 1

  42. 3

    {0,2,1,0}

    Returns: 1

  43. 9

    {0,0,3,0,0}

    Returns: 2

  44. 7

    {0,3,0,6,2,0}

    Returns: 1

  45. 92

    {1,18,0,15,0,12,8,10,5,3,14,0,13,16,0,19,17,2,11}

    Returns: 3

  46. 14

    {7,1,0,0,8,0,0,6}

    Returns: 3

  47. 23

    {9,4,0,0,0,10,6,8,1,7}

    Returns: 2

  48. 31

    {3,6,0,4,0,0,1,5,10,9}

    Returns: 1

  49. 11

    {7,4,9,6,8,0,0,0,0}

    Returns: 5

  50. 26

    {3,7,1,9,2,6,10,0,4,0}

    Returns: 1

  51. 130

    {0,5,13,4,16,6,14,0,10,0,8,3,12,2,19,22,20,15,17,18,11,7}

    Returns: 1

  52. 33

    {5,10,3,0,11,4,2,1,7,12,8,6}

    Returns: 1

  53. 56

    {16,11,17,0,3,6,8,7,13,10,0,2,0,5,14,1,0,4}

    Returns: 3

  54. 109

    {6,17,11,2,0,4,1,7,18,0,10,5,9,19,0,14,0,16,12}

    Returns: 3

  55. 29

    {7,2,12,6,8,0,0,5,0,0,1,3}

    Returns: 4

  56. 928

    {61,44,47,31,33,23,30,54,34,17,58,18,26,43,50,35,6,52,48,22,55,19,53,9,12,57,56,8,29,32,36,60,37,7,62,59,16,24,27,13,25,21,49,42,45,46,0,10,20,2,11,38,4,51,65,28,39,5,3,40,0,63,41,15,64}

    Returns: 1

  57. 2011

    {13,0,76,74,0,68,35,61,32,19,41,22,64,0,33,40,0,67,47,51,54,38,31,56,5,27,70,2,63,73,44,69,26,11,80,37,14,23,77,3,9,12,42,86,43,60,85,84,71,6,45,25,17,88,24,16,18,34,36,57,82,89,20,52,50,66,10,29,48,79,46,58,65,83,90,21,4,49,75,30,1,39,7,72,59,62,15,28,55,78}

    Returns: 2

  58. 957

    {26,62,66,64,12,51,23,68,11,8,61,58,60,43,20,29,14,52,21,45,49,31,54,24,65,6,46,44,35,41,38,39,17,10,63,67,34,22,25,50,18,2,9,0,5,30,27,7,4,42,57,15,53,55,16,56,59,28,37,47,32,40,3,33,48,13,1,36}

    Returns: 1

  59. 1912

    {9,75,19,58,74,18,86,52,47,54,69,60,31,35,73,39,91,23,78,76,20,56,48,55,41,5,84,64,80,83,89,92,93,59,1,21,32,17,66,81,62,72,45,6,33,14,15,53,36,29,67,79,42,63,49,3,68,40,57,22,94,13,0,71,46,87,7,25,34,85,50,8,11,82,16,90,51,28,43,12,26,88,37,77,70,65,38,30,2,27,44,10,4,24}

    Returns: 1

  60. 1056

    {18,22,0,36,23,62,0,52,56,19,57,1,58,0,7,44,60,39,8,24,59,64,46,13,31,55,35,47,2,38,29,53,32,45,33,0,37,20,11,6,50,21,48,49,17,28,25,4,40,16,43,42,41,54,30,51,65,26,63,34,61,12,27,3,14,5}

    Returns: 2

  61. 1115

    {3,35,9,58,20,47,5,34,36,19,23,59,7,21,46,27,8,55,62,6,56,44,1,16,12,26,57,63,61,40,39,41,24,13,11,49,15,10,2,0,45,42,29,53,0,52,50,14,64,0,18,43,28,0,32,4,48,60,51,17,54,37,33,38}

    Returns: 3

  62. 228

    {32,17,13,12,15,29,26,18,19,27,31,23,2,1,3,14,6,22,0,5,10,9,30,8,11,28,4,7,16,25,24,21}

    Returns: 1

  63. 1712

    {27,57,40,80,20,12,11,21,54,70,0,5,74,8,6,4,46,19,53,45,22,48,32,31,66,51,65,47,15,58,73,50,67,62,72,76,9,2,49,25,24,18,61,35,38,30,37,29,68,23,28,81,44,13,79,60,10,26,55,16,1,64,78,42,43,41,36,17,7,59,71,3,77,33,63,14,75,69,39,34,56}

    Returns: 1

  64. 1063

    {50,53,62,36,13,7,28,57,38,33,27,30,5,29,0,45,34,63,17,61,8,55,9,56,2,54,68,69,66,31,26,64,39,67,51,0,3,19,35,44,43,15,65,25,23,0,37,32,52,6,1,16,58,49,48,47,4,22,11,42,59,20,18,14,10,0,21,41,40}

    Returns: 2

  65. 967

    {47,7,3,46,14,38,17,4,27,30,43,21,40,0,52,44,35,13,6,58,31,48,39,5,25,42,59,0,29,10,0,50,45,2,0,23,57,34,1,32,55,18,15,12,60,20,53,8,41,19,22,49,51,36,54,9,0,33,26,56}

    Returns: 3

  66. 2475

    {47,36,12,91,23,89,35,81,38,18,11,72,86,99,22,15,54,55,28,31,14,83,62,41,90,5,96,97,4,19,10,69,98,6,71,20,66,58,65,24,42,37,21,17,46,61,84,78,33,50,77,32,30,74,59,60,9,95,39,44,68,27,92,73,67,25,53,16,76,75,79,43,87,80,7,29,34,26,82,93,2,88,48,56,94,8,63,85,51,45,1,13,64,57,70,49,52,40,3}

    Returns: 1

  67. 2476

    {38,43,36,18,88,86,90,37,58,83,99,48,15,44,64,22,25,45,66,67,68,81,30,82,59,23,91,0,5,56,69,96,21,31,89,0,40,34,16,7,41,60,10,71,35,33,57,42,3,4,50,61,77,9,74,6,85,70,29,62,14,2,24,17,95,39,49,63,93,72,54,12,51,76,94,92,52,98,80,55,75,20,27,100,87,79,46,32,97,28,8,47,84,1,26,65,53,11,19,73}

    Returns: 1

  68. 406

    {40,7,37,11,8,4,12,0,0,18,6,28,26,33,14,0,27,35,19,24,36,2,30,34,3,5,10,23,13,41,21,22,39,15,1,16,17,31,9,29,20}

    Returns: 1

  69. 803

    {0,28,44,10,53,50,26,0,9,4,37,6,30,22,40,19,12,31,34,0,54,57,14,36,2,42,56,51,24,18,20,32,15,1,41,47,17,7,21,23,25,33,3,0,48,35,38,27,45,29,55,43,8,5,16,46,39}

    Returns: 1

  70. 340

    {27,29,22,31,38,13,34,25,10,2,32,17,5,15,6,12,0,1,0,0,36,33,26,37,4,16,24,0,20,39,18,23,7,35,0,8,30,19,3}

    Returns: 3

  71. 2207

    {45,86,2,38,35,65,3,74,89,70,83,61,8,21,41,51,33,58,31,9,7,69,79,17,15,91,76,77,4,36,18,22,60,72,1,12,54,47,11,25,44,57,28,52,71,34,32,81,30,92,64,10,53,5,85,68,37,90,24,93,46,40,16,62,84,29,27,59,88,75,78,82,13,63,48,67,73,49,80,6,50,87,55,14,43,56,42,39,66,23,26,20,19}

    Returns: 1

  72. 344

    {6,37,29,31,40,32,3,0,50,39,45,57,42,0,21,18,54,55,52,47,19,5,51,35,23,8,26,4,38,16,43,13,53,28,11,34,17,0,22,10,30,9,15,46,2,27,36,0,20,12,25,41,7,48,14,56,44}

    Returns: 0

  73. 1473

    {8,0,39,40,56,7,24,5,35,18,30,2,6,15,37,45,26,57,22,38,4,0,17,16,59,13,31,34,33,23,42,14,43,55,47,1,44,49,0,11,12,28,36,29,3,25,32,46,19,21,48,27,51,52,53,60,54,0,50,9}

    Returns: 0

  74. 1089

    {58,82,26,30,66,41,45,59,88,52,25,91,80,77,73,5,6,12,39,72,0,29,21,9,15,20,38,0,42,18,17,0,22,33,85,53,7,32,84,46,4,60,2,43,90,14,36,24,31,57,50,23,65,89,81,93,51,69,86,44,8,62,55,76,92,0,28,83,49,1,27,13,64,11,48,63,67,16,3,0,10,37,71,47,35,79,34,68,54,78,75,19,56}

    Returns: 0

  75. 1230

    {63,41,74,22,19,42,23,70,7,11,0,52,34,76,12,48,26,16,28,33,49,54,36,2,29,3,44,13,18,14,20,35,32,60,4,71,0,10,27,56,1,72,6,53,0,5,55,75,40,31,8,9,62,51,65,46,59,58,68,73,66,38,47,30,21,67,69,39,61,25,50,24,43,57,45,0}

    Returns: 0

  76. 833

    {22,27,3,25,43,37,5,40,16,35,39,34,2,9,33,7,11,30,4,21,15,46,31,45,6,13,20,44,14,10,47,17,36,8,26,24,38,32,23,1,19,29,41,28,42,12,18}

    Returns: 0

  77. 707

    {48,57,44,19,27,0,22,20,0,32,41,11,51,34,16,45,40,29,43,58,47,21,46,0,50,49,4,60,35,59,25,61,24,15,12,30,13,62,56,54,17,37,2,18,9,3,6,38,55,28,14,39,0,5,8,33,1,10,31,52,23,26}

    Returns: 0

  78. 3687

    {73,7,61,26,4,0,57,77,44,38,22,54,87,43,37,70,10,46,14,84,25,42,50,59,72,9,1,76,31,71,36,29,86,62,39,80,15,5,67,30,8,85,79,40,0,3,34,47,60,53,81,75,82,13,6,45,11,23,65,12,18,41,69,21,63,17,78,56,33,49,0,27,58,66,52,32,0,51,24,16,48,74,20,83,35,28,68}

    Returns: 0

  79. 1063

    {12,14,1,17,29,28,45,25,27,46,4,26,22,0,0,5,20,35,9,36,30,23,31,47,38,0,24,6,19,0,42,33,40,44,15,8,13,18,41,48,10,37,0,34,21,11,2,43}

    Returns: 0

  80. 102

    {15,34,0,5,16,10,19,21,3,12,4,7,14,23,1,2,24,30,18,8,27,13,20,0,22,9,28,25,32,26,6,33,31,29}

    Returns: 0

  81. 1441

    {51,24,42,49,43,31,55,8,26,9,50,54,30,2,45,4,1,32,40,36,46,0,61,67,12,44,66,19,3,65,23,17,63,58,27,53,41,5,29,70,18,35,48,11,21,6,33,14,34,10,16,56,0,69,62,25,59,64,13,7,38,20,57,15,60,22,52,47,39,37}

    Returns: 0

  82. 432

    {0,7,3,2,15,13,26,31,10,24,0,12,23,27,6,25,0,19,0,4,32,0,22,28,30,16,9,1,33,8,20,21,14,5,29}

    Returns: 0

  83. 1404

    {58,26,50,2,8,54,23,18,49,28,55,9,35,14,29,59,30,3,27,32,0,16,1,10,60,34,52,31,21,25,36,12,37,5,38,20,51,53,40,33,56,47,43,4,22,15,24,19,45,17,11,48,46,39,41,7,42,44,6,0}

    Returns: 0

  84. 295

    {31,16,28,5,22,2,27,37,23,30,11,10,19,14,35,13,17,24,18,1,32,4,21,26,25,12,3,38,15,0,6,20,33,9,34,29,0,7}

    Returns: 0

  85. 464

    {29,34,2,17,16,11,43,47,13,1,30,12,27,32,28,42,9,51,36,45,49,14,18,33,39,31,37,15,8,44,5,41,4,23,0,22,35,10,26,21,38,46,50,3,7,19,0,48,24,6,25}

    Returns: 0

  86. 858

    {52,67,26,8,1,60,51,50,56,46,22,0,73,45,70,72,6,36,66,2,63,32,0,43,48,16,40,3,31,9,29,69,47,39,7,0,11,30,34,27,41,54,68,0,35,21,25,28,59,37,5,10,19,49,15,23,33,61,65,53,71,18,0,38,13,64,42,62,44,58,12,20,55}

    Returns: 0

  87. 324642071

    {15,21,11,0,22,14,33,20,0,27,36,10,13,24,38,3,1,23,39,31,35,32,29,30,6,4,8,26,18,19,12,17,5,16,7,9,28,34,37}

    Returns: 0

  88. 811148265

    {18,44,34,80,74,53,68,12,26,23,31,60,45,28,32,70,11,7,75,17,72,77,40,15,78,35,27,48,8,57,69,16,38,9,76,10,86,20,89,43,49,59,84,85,39,0,63,54,47,81,24,0,1,52,79,14,4,50,65,30,5,62,2,46,6,73,66,0,42,36,58,37,21,29,33,83,51,3,41,25,67,87,88,13,22,19,71,61,64}

    Returns: 0

  89. 489717553

    {91,85,7,22,44,87,34,13,47,9,100,31,50,10,74,25,14,80,93,48,3,30,78,6,82,28,20,40,67,23,49,36,37,24,0,83,52,29,17,98,19,46,0,33,16,35,60,42,71,75,8,2,5,66,79,39,56,21,72,95,1,54,15,99,69,38,4,59,26,70,65,55,43,41,76,89,63,58,61,27,18,90,53,94,0,64,68,45,57,32,11,81,96,51,62,88,73,92,97,84}

    Returns: 0

  90. 64961987

    {27,8,35,2,12,16,15,4,13,0,34,3,31,24,19,23,0,30,20,1,29,7,11,28,33,21,32,5,17,14,25,10,26,6,9}

    Returns: 0

  91. 708433041

    {52,49,60,17,36,6,54,44,13,46,43,4,29,0,32,8,34,35,55,64,0,57,37,61,0,68,27,3,20,10,15,50,66,12,18,7,11,42,9,39,0,5,51,31,25,63,59,14,40,2,0,19,21,69,22,30,65,41,48,62,26,28,1,24,33,56,53,23,38}

    Returns: 0

  92. 2

    {1, 3, 2 }

    Returns: 1

  93. 4

    {0, 0, 0, 0 }

    Returns: 5

  94. 0

    {1, 2 }

    Returns: 0

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: