AqaAsadiSaves | Topcoder Archive

Problem Statement

The devil is coming to INOI land. INOI land has N cities and M bidirectional roads between them. Each road connects either one city to itself, or two distinct cities to each other. Each pair of cities can be connected by multiple roads. (I.e., INOI is a graph in which both self-loops and multiple edges may appear.)

The devil wants to destroy one road. The devil will always choose the road whose destruction will cause the most damage. The damage caused by the destruction of a road is the number of (unordered) pairs of cities that will get disconnected when the road is destroyed.

Aqa Asadi, as the hero of INOI, wants to prevent as much damage as possible. The night before the devil attacks, Aqa Asadi can build one additional road. The devil will then consider the new road network (including the road Aqa Asadi built) when choosing which road he should destroy. Calculate and return the smallest possible amount of damage done by the devil.

Use the pseudocode below to generate two arrays A and B with M elements each. For each valid i, one of the roads in INOI land connects cities A[i] and B[i].

A = PA
B = PB
for i = size(PA) to M-1:
    A.append( Seed )
    Seed = (Seed * X + Y) modulo N
for i = size(PB) to M-1:
    B.append( Seed )
    Seed = (Seed * X + Y) modulo N

Definition

Class:: AqaAsadiSaves
Method:: minDamage
Parameters:: int, int, int[], int[], int, int, int
Returns:: long
Method signature:: long minDamage(int N, int M, int[] PA, int[] PB, int Seed, int X, int Y)
(be sure your method is public)

Notes

The road added by Aqa Asadi can connect any two cities, even if they are already connected by one or more other roads. Alternately, he may also choose to build a self-loop at any city.

Constraints

N will be between 1 and 200,000, inclusive.
M will be between 1 and 200,000, inclusive.
PA and PB will have the same number of elements.
PA will have at most M elements.
PA will have at most 500 elements.
Elements of PA and PB will be between 0 and N-1, inclusive.
Seed, X, Y will each be between 0 and N-1, inclusive.

Examples

```
3
```
```
3
```
```
{0, 1, 2}
```
```
{1, 2, 0}
```
```
0
```
```
0
```
```
0
```
```
Returns: 0
```

{0, 1, 2, 2, 4, 4}

{1, 2, 3, 4, 5, 6}

Returns: 6

```
10
```
```
1
```
```
{4}
```
```
{7}
```
```
0
```
```
0
```
```
0
```
```
Returns: 0
```

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.