Statistics

Problem Statement for "BearCavalry"

Problem Statement

Would you want to fight against bears who ride horses? Me neither.


Limak is a grizzly bear. He is a general of the dreadful army of Bearland. The most important part of the army is, of course, the cavalry.


The cavalry of Bearland consists of the same number of warriors and horses. Limak knows the strength of each warrior and also the strength of each horse. These are given in int[]s warriors and horses, respectively.


General Limak must assign exactly one horse to each warrior. Obviously, different warriors must be given different horses.


A warrior together with his assigned horse is called a unit. The strength of a unit is equal to the product of the strengths of the warrior and the horse that form the unit.


The warrior that corresponds to element 0 in warriors is called Bravebeart. He is always the first to charge the enemy. Limak decided that Bravebeart deserves some respect. Thus, his unit must be strictly stronger than any other unit. (Ties are not allowed.)


Given this constraint, let X be the number of valid ways in which Limak can create the units. A general must know everything about his army. Help Limak count the valid assignments. Compute and return the value (X modulo 1,000,000,007).

Definition

Class:
BearCavalry
Method:
countAssignments
Parameters:
int[], int[]
Returns:
int
Method signature:
int countAssignments(int[] warriors, int[] horses)
(be sure your method is public)

Constraints

  • warriors will contain between 2 and 50 elements, inclusive.
  • warriors and horses will contain the same number of elements.
  • Each element in warriors and in horses will be between 1 and 1000, inclusive.

Examples

  1. {5,8,4,8}

    {19,40,25,20}

    Returns: 2

    There are four warriors and four horses for them. Bravebeart's strength is warriors[0] = 5. There are two valid ways to pair the warriors and horses into units. Below, each unit is presented as an ordered pair (warrior's strength, horse's strength). The warriors are presented in the same order as in warriors. Valid assignment #1: (5,40), (8,19), (4,25), (8,20). Valid assignment #2: (5,40), (8,20), (4,25), (8,19). In assignment #1, the strength of Bravebeart's unit is 5*40 = 200. The other three units have strengths 8*19 = 152, 4*25 = 100, and 8*20 = 160. This is a valid assignment because the number 200 is strictly greater than each of the numbers 152, 100, and 160.

  2. {1,1}

    {1,1}

    Returns: 0

  3. {10,2,10}

    {100,150,200}

    Returns: 3

    There are three valid assignments. (10,200), (2,150), (10,100) (10,200), (2,100), (10,150) (10,150), (2,200), (10,100) (Again, the warriors are printed in the same order as in warriors. Hence, in each assignment Bravebeart's unit is the first one printed.)

  4. {10,20}

    {1,3}

    Returns: 1

  5. {20,20,25,23,24,24,21}

    {20,25,25,20,25,23,20}

    Returns: 0

  6. {970,800,800,800,800,800,800,800,800,800,800,800,800,800,800,800,800,800,800,800,800,800,800,800,800, 800,800,800,800,800,800,800,800,800,800,800,800,800,800,800,800,800,800,800,800,800,800,800,800,800}

    {1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000, 1000,1000,1000,1000,1000,1000,1000,1000,1000,1000}

    Returns: 318608048

    In all 50! assignments Bravebeart's unit is the strongest one. Thus, you should return 50! modulo 1,000,000,007. Note that even if different warriors/horses have the same strength, they are still considered distinct.

  7. {1,1}

    {1,1}

    Returns: 0

  8. {1000,1000}

    {1000,1000}

    Returns: 0

  9. {1000,100}

    {5,6}

    Returns: 2

  10. {100,1000}

    {5,6}

    Returns: 0

  11. {7,1,2,2}

    {13,19,2,1}

    Returns: 12

  12. {36,44,75,44,18,5}

    {97,63,93,49,99,60}

    Returns: 0

  13. {868,353,810,34,728,580,170,505,142,177}

    {434,308,917,315,901,281,425,922,222,961}

    Returns: 1482144

  14. {501,503,503,502,503,503,505,501,504,503,502,505,504,501,500}

    {505,505,501,503,502,503,501,501,504,503,505,502,504,504,505}

    Returns: 0

  15. {321,186,823,128,273,774,279,122,970,231,669,424,402,921,40,606,900,235,683,736}

    {923,585,357,270,107,292,517,909,652,37,285,324,575,107,451,199,881,82,320,850}

    Returns: 382551910

  16. {664,340,625,66,261,664,23,512,250,706,599,172,642,955,793,100,247,661,8,250,50,292,926,976,399,728,174,631,161,493,832,825,832,456,890}

    {444,472,264,308,721,321,906,245,962,213,389,61,811,50,69,60,99,712,337,74,110,65,599,92,225,91,923,401,274,731,290,70,202,906,377}

    Returns: 548755580

  17. {274,226,282,870,540,494,259,600,304,660,20,716,758,84,404,183,545,468,781,637,45,223,911,445,848,641,87,917,194,344,293,820,569,927,689,108,772,299,60,428,958,431,495,715,514,898,249,59,718,381}

    {47,114,955,957,910,803,598,996,71,143,691,716,962,612,642,3,719,765,301,130,192,259,913,686,325,426,584,926,836,653,306,882,766,613,839,675,415,788,23,837,930,713,552,244,324,545,246,395,310,898}

    Returns: 0

  18. {876,853,156,788,891,833,214,474,758,401,478,415,283,243,27,121,917,793,260,291,630,541,4,533,784,679,430,381,73,91,279,949,943,786,88,833,970,653,658,727,54,135,142,336,729,168,808,646,961,67}

    {936,942,607,291,474,743,970,903,123,394,993,753,694,288,891,782,120,860,434,130,939,487,264,432,822,993,599,981,990,911,47,277,852,6,920,678,748,889,932,870,634,277,975,328,564,865,109,35,76,894}

    Returns: 526892922

  19. {164,14,381,780,797,554,124,748,535,465,658,933,741,862,938,660,891,685,900,822,907,534,450,881,861,13,97,321,48,172,214,563,538,946,342,334,852,465,81,738,929,91,670,22,304,960,681,194,644,933}

    {367,550,466,817,782,678,181,878,998,228,50,563,791,939,509,484,272,360,949,705,449,229,147,118,250,450,77,283,995,73,215,713,974,32,881,108,709,62,985,58,289,386,972,431,324,832,915,948,543,215}

    Returns: 0

  20. {4,991,443,150,109,693,951,537,327,297,961,541,9,287,924,890,394,984,951,378,41,591,116,364,374,439,196,288,738,738,502,741,729,296,890,189,988,192,725,314,488,38,206,497,324,129,738,69,112,688}

    {798,504,630,913,868,3,704,63,642,441,800,143,182,528,439,423,68,778,615,793,444,102,182,649,950,857,130,687,277,593,726,74,97,708,987,316,710,690,378,352,130,529,846,663,409,636,86,476,766,700}

    Returns: 0

  21. {620,209,153,801,209,103,9,338,141,285,283,867,359,379,926,697,694,635,738,423,338,219,951,536,882,711,171,967,187,288,666,158,848,818,311,57,272,319,746,413,956,28,631,314,758,556,362,803,542,99}

    {225,232,669,528,767,550,238,289,868,776,577,885,934,424,55,244,832,326,914,930,90,869,957,72,182,67,979,895,869,521,345,94,104,14,621,870,915,210,510,783,986,438,19,271,214,73,514,45,399,779}

    Returns: 178242452

  22. {4,10,8,3,2,1,9,10,6,7,2,2,2,5,5,4,6,2,4,6,6,1,3,4,1,6,7,6,1,7,4,6,6,3,10,9,4,8,1,1,7,2,2,8,7,9,2,2,10,7}

    {9,7,7,2,10,9,7,6,6,9,4,1,7,2,4,6,10,7,6,10,7,2,4,10,9,2,8,2,5,9,8,4,5,6,5,5,4,3,2,1,4,8,2,10,9,7,5,10,3,10}

    Returns: 697704267

  23. {995,993,992,995,990,996,991,990,992,997,994,999,992,996,996,991,997,999,997,995,991,1000,1000,992,1000,1000,999,996,996,999,995,990,1000,995,995,990,999,994,999,991,990,992,1000,991,998,993,990,994,1000,995}

    {998,991,994,997,991,991,995,990,998,990,997,992,990,997,995,993,995,994,997,993,993,995,995,992,994,991,993,995,993,993,1000,990,992,992,998,993,993,990,991,999,990,999,999,999,993,994,991,998,996,996}

    Returns: 962820433

  24. {578,416,548,465,486,475,566,520,454,428,542,459,514,534,586,548,582,550,573,524,540,413,544,573,426,599,575,473,522,524,584,449,540,532,515,425,557,480,495,410,458,588,419,523,521,405,470,452,505,594}

    {577,444,406,520,416,433,469,541,456,591,464,440,591,554,522,505,529,478,535,424,488,594,562,457,516,432,462,536,485,517,529,461,562,536,531,528,569,550,469,575,541,483,414,481,437,536,586,566,564,470}

    Returns: 577422300

  25. {208,202,203,203,202,205,207,209,200,201,210,208,202,207,203,202,209,202,209,203,206,201,206,205,202,203,206,204,207,202,205,203,203,207,206,205,201,202,203,210,203,202,208,205,207,209,208,206,210,206}

    {207,203,207,202,208,209,203,203,202,200,204,205,203,207,201,209,210,203,210,202,200,202,203,208,206,208,205,203,203,204,207,209,207,203,200,202,210,204,204,210,202,208,202,203,202,204,210,201,205,209}

    Returns: 18765063

  26. {1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000}

    {1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000}

    Returns: 0

  27. {1000,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

    {1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000}

    Returns: 318608048

  28. {2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

    {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

    Returns: 318608048

  29. {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

    {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

    Returns: 0

  30. {970, 800, 800, 800, 800, 800, 800, 800, 800, 800, 800, 800, 800, 800, 800, 800, 800, 800, 800, 800, 800, 800, 800, 800, 800, 800, 800, 800, 800, 800, 800, 800, 800, 800, 800, 800, 800, 800, 800, 800, 800, 800, 800, 800, 800, 800, 800, 800, 800, 800 }

    {1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000 }

    Returns: 318608048

  31. {100, 100, 100 }

    {100, 100, 10 }

    Returns: 0

  32. {99, 44, 37, 71, 42, 13, 74, 10, 44, 66, 47, 62, 83, 8, 10, 49, 6, 36, 85, 96, 100, 80, 82, 63, 37, 38, 31, 7, 54, 63, 62, 76, 45, 62, 41, 62, 62, 66, 3, 12, 91, 62, 45, 11, 69, 20, 50, 55, 36, 61 }

    {23, 41, 57, 50, 42, 77, 100, 98, 12, 38, 21, 95, 60, 25, 52, 42, 12, 26, 19, 73, 80, 25, 70, 72, 95, 7, 62, 58, 31, 45, 13, 99, 87, 57, 2, 69, 26, 53, 43, 84, 27, 21, 83, 28, 100, 98, 54, 12, 20, 11 }

    Returns: 722138777

  33. {1, 2 }

    {5, 2 }

    Returns: 1

  34. {244, 906, 586, 214, 912, 926, 485, 761, 876, 233, 903, 957, 357, 920, 620, 613, 511, 575, 445, 935, 313, 446, 222, 900, 340, 82, 505, 729 }

    {29, 606, 498, 207, 928, 419, 309, 761, 119, 813, 373, 676, 724, 929, 302, 883, 124, 340, 205, 700, 972, 198, 143, 180, 928, 511, 447, 26 }

    Returns: 0

  35. {1000, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

    Returns: 318608048

  36. {755, 482, 704, 747, 831, 836, 288, 254, 426, 952, 907, 617, 640, 381, 394, 999, 730, 908, 515, 96, 205, 954, 122, 386, 177, 683, 200, 940, 303, 784, 608, 877, 386, 898, 252, 913, 166, 164, 972, 780, 412, 684, 790, 780, 835, 321, 894, 242, 448, 158 }

    {19, 770, 566, 423, 264, 798, 861, 592, 743, 673, 679, 396, 754, 954, 163, 721, 969, 6, 781, 983, 194, 150, 945, 325, 199, 347, 318, 169, 965, 460, 492, 343, 449, 348, 560, 646, 939, 446, 285, 417, 204, 962, 763, 297, 753, 871, 746, 917, 567, 57 }

    Returns: 493594631

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: