MarriageAndCirclingChallenge
SRM 803 · 2021-03-30 · by a.poorakhavan
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.
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.
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
Submissions are judged against all 36 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class MarriageAndCirclingChallenge with a public method long long solve(int N, int threshold, int state) · 36 test cases · 2 s / 256 MB per case