Statistics

Problem Statement for "SquareLanguage"

Problem Statement

The problem statement contains superscripts that are viewable in the applet.
Let S be a set of distinct strings. We form the new set S2 by collecting all distinct strings of the form xy, where the prefix x is in S, and the suffix y is in S as well. Suppose S is defined as follows: 
   S = {ai bj ck dm | la <= i <= ua, lb <= j <= ub, lc <= k <= uc, ld <= m <= ud }
Here ai denotes the letter 'a' repeated i times. For example, 
	a3 b2 c0 d1 = aaabbd
You will be given l_ and u_ as the first and second elements of _bounds respectively (here _ denotes a, b, c, or d). Return the number of strings in S2.

Definition

Class:
SquareLanguage
Method:
howMany
Parameters:
int[], int[], int[], int[]
Returns:
long
Method signature:
long howMany(int[] abounds, int[] bbounds, int[] cbounds, int[] dbounds)
(be sure your method is public)

Notes

  • The set notation T = { x | prop } means that T contains all elements x such that prop is true.

Constraints

  • abounds, bbounds, cbounds and dbounds will each contain exactly 2 elements.
  • In abounds, bbounds, cbounds and dbounds element 0 will not be greater than element 1.
  • In abounds, bbounds, cbounds and dbounds element 0 will be between 0 and 100 inclusive.
  • In abounds, bbounds, cbounds and dbounds element 1 will be between 0 and 100 inclusive.

Examples

  1. {0,100}

    {0,100}

    {0,100}

    {0,100}

    Returns: 10828525844240801

  2. {0,10}

    {0,10}

    {0,10}

    {0,10}

    Returns: 213826481

  3. {1,10}

    {1,10}

    {1,10}

    {1,10}

    Returns: 100000000

  4. {0,2}

    {0,2}

    {0,2}

    {0,2}

    Returns: 6129

  5. {0,1}

    {0,1}

    {0,1}

    {0,1}

    Returns: 224

  6. {0,0}

    {0,0}

    {0,0}

    {0,0}

    Returns: 1

  7. {0,1}

    {0,0}

    {0,0}

    {0,0}

    Returns: 3

  8. {0,1}

    {0,1}

    {0,0}

    {0,0}

    Returns: 12

  9. {0,100}

    {0,0}

    {0,0}

    {0,0}

    Returns: 201

    Here there are 201 possible strings. Each one is distinguished by the number of a's it contains.

  10. {0,1}

    {0,1}

    {0,0}

    {0,0}

    Returns: 12

    The 12 strings in S2 are "", "a", "b", "aa", "ab", "ba", "bb", "bab", "aab", "abb", "aba", and "abab".

  11. {1,100}

    {10,90}

    {20,80}

    {30,70}

    Returns: 410390615610000

    Here there is no danger of duplicates.

  12. {0,100}

    {0,100}

    {0,100}

    {1,100}

    Returns: 10615191408029899

  13. {0,20}

    {0,30}

    {0,40}

    {0,47}

    Returns: 1641220888605

  14. {0,20}

    {0,30}

    {13,40}

    {0,29}

    Returns: 299019748230

  15. {3,20}

    {0,23}

    {0,25}

    {12,29}

    Returns: 40875134976

  16. {9,20}

    {5,20}

    {0,20}

    {3,20}

    Returns: 5267275776

  17. {20,20}

    {0,20}

    {0,20}

    {20,20}

    Returns: 194481

  18. {1,1}

    {19,19}

    {91,91}

    {13,13}

    Returns: 1

  19. {0,2}

    {0,2}

    {0,0}

    {0,0}

    Returns: 57

    The 12 strings in S2 are "", "a", "b", "aa", "ab", "ba", "bb", "bab", "aab", "abb", "aba", and "abab".

  20. {0,0}

    {0,0}

    {0,1}

    {1,1}

    Returns: 4

  21. {0,0}

    {0,0}

    {2,3}

    {0,1}

    Returns: 14

  22. {0,0}

    {0,0}

    {0,1}

    {0,0}

    Returns: 3

  23. {0,0}

    {0,94}

    {0,0}

    {1,59}

    Returns: 31096445

  24. {0,0}

    {0,37}

    {0,59}

    {1,1}

    Returns: 5198400

  25. {0,0}

    {1,1}

    {1,24}

    {1,1}

    Returns: 576

  26. {0,0}

    {12,31}

    {87,97}

    {1,25}

    Returns: 30250000

  27. {0,1}

    {0,0}

    {0,0}

    {0,24}

    Returns: 1323

  28. {0,1}

    {0,0}

    {0,75}

    {1,56}

    Returns: 71994344

  29. {0,1}

    {0,1}

    {0,1}

    {0,92}

    Returns: 484708

  30. {0,1}

    {0,1}

    {55,91}

    {0,54}

    Returns: 65974480

  31. {0,1}

    {0,80}

    {1,1}

    {0,1}

    Returns: 104976

  32. {0,1}

    {1,1}

    {0,0}

    {0,0}

    Returns: 4

  33. {0,1}

    {5,54}

    {31,93}

    {0,0}

    Returns: 39690000

  34. {0,40}

    {0,1}

    {0,0}

    {1,1}

    Returns: 6724

  35. {0,6}

    {0,1}

    {0,78}

    {1,1}

    Returns: 1223236

  36. {0,19}

    {1,1}

    {0,15}

    {1,1}

    Returns: 102400

  37. {0,13}

    {1,14}

    {0,0}

    {20,37}

    Returns: 12446784

  38. {0,33}

    {1,80}

    {0,82}

    {24,57}

    Returns: 58918519705600

  39. {1,1}

    {0,1}

    {16,27}

    {0,0}

    Returns: 576

  40. {1,1}

    {0,67}

    {1,24}

    {1,44}

    Returns: 5156388864

  41. {1,1}

    {1,1}

    {1,74}

    {0,1}

    Returns: 21904

  42. {1,1}

    {1,19}

    {78,79}

    {0,1}

    Returns: 5776

  43. {1,1}

    {25,58}

    {0,16}

    {1,1}

    Returns: 334084

  44. {1,66}

    {0,1}

    {0,1}

    {0,64}

    Returns: 293367100

  45. {1,65}

    {1,66}

    {1,1}

    {0,1}

    Returns: 73616400

  46. {1,86}

    {1,71}

    {1,55}

    {1,1}

    Returns: 112781788900

  47. {37,73}

    {0,0}

    {0,0}

    {0,1}

    Returns: 2884

  48. {10,57}

    {1,62}

    {72,76}

    {0,47}

    Returns: 510138777600

  49. {4,36}

    {62,65}

    {1,35}

    {0,11}

    Returns: 3073593600

  50. {0, 100 }

    {0, 0 }

    {0, 0 }

    {0, 0 }

    Returns: 201

  51. {0, 20 }

    {0, 30 }

    {0, 40 }

    {0, 47 }

    Returns: 1641220888605

  52. {1, 100 }

    {10, 90 }

    {20, 80 }

    {30, 70 }

    Returns: 410390615610000

  53. {0, 20 }

    {0, 30 }

    {2, 40 }

    {0, 47 }

    Returns: 1485116321472

  54. {0, 100 }

    {0, 99 }

    {1, 98 }

    {0, 97 }

    Returns: 9409068287131800

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: