Problem - A - Codeforces about:reader?url=https%3A%2F%[Link]%2Fcontest%2F...

[Link]

Problem - A - Codeforces
6-8 phút

An intelligent computing cluster innovatively adopts OXC (optical

circuit switch) as the core layer to enable ultra-large-scale
interconnection for tens of thousands of computing cards.

While OXC demonstrates advantages in latency, power efficiency,

and bandwidth compared to electrical switches, its switching
capability degrades from all-to-all to one-to-one. This makes it
challenging to fully utilize OXC bandwidth.

Please develop a strategy to determine the optimal OXC

configuration and routing schemes in response to AI tasks in real-
time.

All links appearing in this problem can be considered as

bidirectional edges.

What is OXC?

1 trong 8 9:38 SA 28/12/2025

Problem - A - Codeforces about:reader?url=https%3A%2F%[Link]%2Fcontest%2F...

OXC can freely establish an optical connection between ports by

rotating micro-mirrors to reflect light. An OXC optical connection
refers to a connection between one internal port and another
internal port of the OXC, forming a bidirectional pathway.

In the illustrated OXC, one optical connection is established

between ports 0 and 2, while another connects ports 1 and 4. This
allows the device connected to port 0 to have a communication
link with the device connected to port 2, and similarly for ports
1 and 4. Note that optical connections are one-to-one!

In the network scenario shown in the figure above, OXC #0

2 trong 8 9:38 SA 28/12/2025

Problem - A - Codeforces about:reader?url=https%3A%2F%[Link]%2Fcontest%2F...

establishes an optical connection between port 0 and port 2,

creating a communication link between Spine #0 and Spine #1. By
establishing an optical connection between port 1 and port 5, it
creates a communication link between Spine #0 and Spine #2.

Overview of Two-Tier Electrical and One-Tier Optical Network

A Group contains two tiers of electrical switches (referred to as

Leaf and Spine, as shown in the figure) and several NPUs (Neural
Processing Units). Communication between NPUs within a Group
can be completed solely through the electrical switches.

The OXC is only used to route traffic between different Groups.

Such traffic is transmitted via the following path: NPU – Leaf –
Spine – OXC – Spine – Leaf – NPU.

For each Spine, let �� be the number of links to OXCs and ����
be the number of links to Leaves. We define the convergence ratio
as ��: ����. It is guaranteed that this ratio is 1: 1, 1: 3, or 1: 7.

Introduction to Multi-Plane Network

3 trong 8 9:38 SA 28/12/2025

Problem - A - Codeforces about:reader?url=https%3A%2F%[Link]%2Fcontest%2F...

• Spines and OXCs are divided into several independent plane sets
(in the industry, this is done to scale the network size).

• In each plane, between each Spine and each OXC belonging to

this plane, there are exactly � links.

• There are no links between Spines and OXCs in different planes.

• Within each Group, there is exactly one physical link between

each Leaf and each Spine.

Specific Network Description

• There are � Groups numbered from 0 to � − 1.

• There are � OXCs numbered from 0 to � − 1. OXC number �

�
belongs to the plane numbered � �.
�/�

• Each Group has � Spines numbered from 0 to � − 1. Spine

4 trong 8 9:38 SA 28/12/2025

Problem - A - Codeforces about:reader?url=https%3A%2F%[Link]%2Fcontest%2F...

�
number � belongs to the plane numbered � �.
�/�

• Each Group has � Leaves, numbered from 0 to � − 1.

• Within the same plane, each OXC and each Spine have exactly �
links, numbered from 0 to � − 1.

• There are � planes numbered from 0 to � − 1. The number of

OXCs � and the number of Spines � are both divisible by �.

• From this, it follows that the number of ports per OXC is � = � ⋅ (�

/ �) ⋅ �. The ports of each OXC are numbered from 0 to � − 1.
The port corresponding to OXC number �, Group number �, Spine
number �, and link number � has the number � ⋅ (� / �) ⋅ � + (�
mod (� / �)) ⋅ � + �.

For OXC number �, port number � corresponds to Group number

� � ��� ((� / �)⋅�) �
� �, Spine number � � +� � ⋅ (� / �), and link
(� / �)⋅� � �/�
number (� mod �).

Leaf-Level Communication Flow Demand

Each AI task has different communication requirements between

NPU cards. For simplicity, details such as NPU – Leaf connections
are abstracted away in this problem.

Specifically, each query can be considered as several bidirectional

flows. Each flow goes between some two leaves, LeafA and
LeafB.

A flow is transmitted via a bidirectional path: LeafA – SpineA –

OXC – SpineB – LeafB. It is guaranteed that, for all given flows,
the Group numbers of LeafA and LeafB are different.

Now it is required to assign routes to all flows. We define the

maximum flow conflict as the maximum number of flows passing

5 trong 8 9:38 SA 28/12/2025

Problem - A - Codeforces about:reader?url=https%3A%2F%[Link]%2Fcontest%2F...

through any link in the network.

Minimize the maximum flow conflict as much as possible.

OXC Physical Topology Adjustment

The OXC can freely adjust its physical topology, but adjustments
incur overhead.

We define the OXC adjustment cost as a kind of edit distance

between the target physical topology and the current physical
topology. Specifically, we adjust an OXC by performing the
following actions, each of which has a cost of 1:

• Establish a new connection between a pair of ports.

• Remove an existing connection between a pair of ports.

Minimize the OXC adjustment cost as much as possible.

Initially, before any queries, no ports of any OXC have established

connections. Before each query after the first one, the physical
topology is exactly as it was after the previous query.

Here is an example of edit distance calculation:

• Original topology: Port 1 is connected to port 2, port 0 is idle and

unconnected.

• New topology: Port 1 is connected to port 0, port 2 is idle and

unconnected.

• Removing the connection between port 1 and port 2, and

establishing the connection between port 1 and port 0, results in
an OXC adjustment cost of 2.

Input

The first line contains three positive integers �, �, and �,

6 trong 8 9:38 SA 28/12/2025

Problem - A - Codeforces about:reader?url=https%3A%2F%[Link]%2Fcontest%2F...

representing the number of Groups, the number of Spines per

Group, and the number of Leaves per Group, respectively (2 ≤ �
≤ 2 �; 1 ≤ � ≤ 2 �; 1 ≤ � ≤ 2 �; additionally, 2 ≤ � ⋅ � ⋅ � ≤ 2 ��).

The second line contains three positive integers �, �, and �,

representing the number of OXCs, the number of links between
each OXC and each Spine within the same plane, and the number
of planes (1 ≤ � ≤ 2 �; 1 ≤ � ≤ 2; 1 ≤ � ≤ 2 �).

Then five queries are given. For each query, the input format is as
follows:

• The first line of a description contains a positive integer �,

�
indicating the number of bidirectional flow demands (1 ≤ � ≤ (� ⋅
�
� ⋅ �)).

• Each of the next � lines describes a bidirectional flow demand

between LeafA and LeafB. The �-th line, representing the �-th
bidirectional flow demand, contains four integers, in order:
1. �� , number of Group of LeafA

2. LeafA number

3. �� , number of Group of LeafB

4. LeafB number

The group numbers satisfy 0 ≤ �� < �� ≤ � − 1, and the leaf

numbers are from 0 to � − 1.

It is guaranteed that � and � are divisible by �, and that � − 1 ≤ �

⋅ (� / �) ⋅ �.
(� / �)⋅�
It is guaranteed that the convergence ratio is either 1: 1 or
�
1: 3 or 1: 7.

It is guaranteed that each leaf appears no more than � times in

7 trong 8 9:38 SA 28/12/2025

Problem - A - Codeforces about:reader?url=https%3A%2F%[Link]%2Fcontest%2F...

each query.

8 trong 8 9:38 SA 28/12/2025