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() < 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
600
47
42
Returns: 1995601890
Largest N.
600
1
1
Returns: 53059386
600
99
997
Returns: 57640607
567
0
86
Returns: 0
578
100
76
Returns: 0
593
33
33
Returns: 1624537189
589
89
78
Returns: 594308810
475
53
24
Returns: 782285130
396
16
6363663
Returns: 172837238
600
50
12345678
Returns: 2004873448
600
22
32
Returns: 1228645076
600
50
1234567
Returns: 2005430424
600
47
2671821
Returns: 1995488967
600
50
87
Returns: 2004336788
600
13
345256
Returns: 746362467
600
50
1313
Returns: 2006551470
600
50
50
Returns: 2004640570
600
50
13245327
Returns: 2003735258
600
99
90821348
Returns: 55575169
455
19
125453517
Returns: 354336348
600
49
0
Returns: 2004028267
600
50
238172368
Returns: 2004669311
600
50
123456789
Returns: 2005077351
600
50
4124122
Returns: 2005285376
600
50
123
Returns: 2005143564
600
50
1
Returns: 2005187214
600
50
1234512
Returns: 2004300090
600
50
47
Returns: 2004450760
600
50
2147483647
Returns: 2005367197
600
100
556
Returns: 0
600
0
123
Returns: 0
600
50
12
Returns: 2003978775
600
100
2147483647
Returns: 0