SquareLanguage | Topcoder Archive

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 S² 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 = {aⁱ b^j c^k d^m | la <= i <= ua, lb <= j <= ub, lc <= k <= uc, ld <= m <= ud }

Here aⁱ denotes the letter 'a' repeated i times. For example,

	a³ b² c⁰ d¹ = 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 S².

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,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.
```
{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".

{1,100}

{10,90}

{20,80}

{30,70}

Returns: 410390615610000

Here there is no danger of duplicates.

{0,20}

{0,30}

{0,40}

{0,47}

Returns: 1641220888605

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.