TopCoder problem "SquareLanguage" used in SRM 238 (Division I Level Three)



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

0)
    
{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.
1)
    
{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".
2)
    
{1,100}
{10,90}
{20,80}
{30,70}
Returns: 410390615610000
Here there is no danger of duplicates.
3)
    
{0,20}
{0,30}
{0,40}
{0,47}
Returns: 1641220888605

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=3050

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=6537&pm=3050

Writer:

AdminBrett

Testers:

PabloGilberto , lbackstrom , Olexiy

Problem categories:

Math, String Manipulation