YetAnotherGraphColoring | Topcoder Archive

Problem Statement

There are n vertices labeled 1, 2, ..., n. Form a graph by adding an edge between each pair of vertices x, y such that x < y and a[x] > a[y].

Find and return the minimum number of colours needed to colour the graph. (Usual restriction applies: there can be no edge with its endpoints having the same colour.)

You are given the int n: the number of vertices. You are also given the ints a1, a2, x, y, z and m. Please use the following pseudocode to generate the array a[] used above.


a[1] = a1
a[2] = a2
for i = 3 to n:
    a[i] = (x * a[i - 1] + y * a[i - 2] + z) modulo m

Definition

Class:: YetAnotherGraphColoring
Method:: minColors
Parameters:: int, int, int, int, int, int, int
Returns:: int
Method signature:: int minColors(int n, int a1, int a2, int x, int y, int z, int m)
(be sure your method is public)

Constraints

2 <= n <= 200,000
0 <= a1, a2, x, y, z <= 10^9
1 <= m <= 10^9

Examples

```
5
```
```
987654321
```
```
123456789
```
```
12345
```
```
678
```
```
9
```
```
1000000000
```
```
Returns: 3
```
The generated array a = {987654321, 123456789, 703689852, 754925891, 661844060}. Thus, the graph contains the edges 0-1, 0-2, 0-3, 0-4, 2-4, and 3-4. We need at least three colours for this graph. One valid way of using three colours is to use red for vertex 0, green for vertices 1 and 4, and blue for vertices 2 and 3.
```
100
```
```
10
```
```
20
```
```
1
```
```
0
```
```
10
```
```
123456789
```
```
Returns: 1
```
This graph consists of 100 isolated vertices and therefore we can use the same colour for all of them.

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.