MarriageAndCirclingChallenge | Topcoder Archive

Problem Statement

One of the challenges before marriage (yes, this problem is a bit different from the others in that regard!) is circling. By circling, we mean love circles. The ideal situation in love is when A loves B and B loves A back, as then A and B can get married and be happy together. However, in real life you can get much more complicated situations such as "A loves B, B loves C, C loves D, ..., and X loves A". We will take a closer look at those situations.

Imagine a society in which no ideal love circles exist, for a very simple reason: for any two people A, B in the society either A loves B, or B loves A, but never both.

We are examining one such society. We are currently interested in situations that are in some sense closest to the ideal one: love circles that involve exactly four people. That is, we are interested in four-tuples (A, B, C, D) of distinct people such that A loves B, B loves C, C loves D, and finally D loves A. The cyclic order does not matter, so (B, C, D, A) is the same four-tuple as (A, B, C, D).

You are given N, threshold and state. The society we are examining consists of N people, numbered from 0 to N-1. Use the following simple pseudocode to generate the relationships between them.


def rnd():
    state = (state * 1103515245 + 12345) modulo 2^31
    return state modulo 100

for i = 0 to N-1:
    for j = i+1 to N-1:
        if rnd() &lt; threshold:
            i loves j
        else:
            j loves i

Calculate and return the number of distinct love circles that involve exactly four people.

Definition

Class:: MarriageAndCirclingChallenge
Method:: solve
Parameters:: int, int, int
Returns:: long
Method signature:: long solve(int N, int threshold, int state)
(be sure your method is public)

Constraints

N will be between 4 and 600, inclusive.
threshold will be between 0 and 100, inclusive.
state will be between 0 and 2^31 - 1, inclusive.

Examples

```
10
```
```
0
```
```
12345
```
```
Returns: 0
```
In this society the test rnd() < threshold never returns true and therefore the person with the higher number always loves the person with the smaller number. In such a society there clearly are no love circles at all, regardless of their length.
```
5
```
```
50
```
```
47
```
```
Returns: 4
```
The values returned by rnd() when generating this society are: 8 (0 loves 1), 5 (0 loves 2), 98 (3 loves 0), 91 (4 loves 0), 48 (1 loves 2), 33 (1 loves 3), 50 (4 loves 1), 27 (2 loves 3), 76 (4 loves 2), 37 (3 loves 4). The four love circles of length four in this society are (0, 1, 2, 3), (0, 1, 3, 4), (1, 2, 3, 4), and (3, 4, 0, 2).
```
9
```
```
20
```
```
1234567
```
```
Returns: 29
```

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.