1/7/26, 3:29 PM Problem - A - Codeforces
shashank212121 | Logout
HOME TOP CATALOG CONTESTS GYM PROBLEMSET GROUPS RATING EDU API CALENDAR HELP
PROBLEMS SUBMIT CODE MY SUBMISSIONS STATUS STANDINGS CUSTOM INVOCATION
ICPC 2025 Online Winter
The problem statement has recently been changed. View the changes. × Challenge powered by Huawei
Contest is running
A. OXC Ports Arrangement Problem 4 days
time limit per test: 5 seconds Contestant
memory limit per test: 1024 megabytes
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.
→ Submit?
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 Language: GNU GCC C11 5.1.0
challenging to fully utilize OXC bandwidth.
Choose
Please develop a strategy to determine the optimal OXC configuration and routing schemes in Choose File No file chosen
file:
response to AI tasks in real-time.
Submit
All links appearing in this problem can be considered as bidirectional edges.
What is OXC? → Contest materials
[Link]
→ Your points
Points
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 establishes an optical connection
between port 0 and port 2, creating a communication link between Spine #0 and Spine #1. By
[Link] 1/5
1/7/26, 3:29 PM Problem - A - Codeforces
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 Up be the number of links to OXCs and Down be the number of links to
Leaves. We define the convergence ratio as Up : Down . It is guaranteed that this ratio is
1 : 1 , 1 : 3 , or 1 : 7 .
Introduction to Multi-Plane Network
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
K 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
[Link] 2/5
1/7/26, 3:29 PM Problem - A - Codeforces
There are N Groups numbered from 0 to N − 1 .
There are M OXCs numbered from 0 to M − 1 . OXC number i belongs to the plane
numbered ⌊
i
⌋ .
M /P
Each Group has S Spines numbered from 0 to S − 1 . Spine number i belongs to the plane
numbered ⌊
i
⌋ .
S/P
Each Group has L Leaves, numbered from 0 to L − 1 .
Within the same plane, each OXC and each Spine have exactly K links, numbered from 0 to
K − 1 .
There are P planes numbered from 0 to P − 1 . The number of OXCs M and the number of
Spines S are both divisible by P .
From this, it follows that the number of ports per OXC is R = N ⋅ (S /P ) ⋅ K . The ports of
each OXC are numbered from 0 to R − 1.
The port corresponding to OXC number m, Group number i , Spine number j , and link
number k has the number i ⋅ (S /P ) ⋅ K + (j mod (S /P )) ⋅ K + k.
For OXC number m, port number i corresponds to Group number ⌊ i
⌋ , Spine number
(S/P )⋅K
i mod ((S/P )⋅K)
⌊ ⌋ + ⌊
m
⌋ ⋅ (S /P ) , and link number (i mod K ) .
K M /P
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 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 N , S , and L, representing the number of Groups,
the number of Spines per Group, and the number of Leaves per Group, respectively (
5 5 6 14
2 ≤ N ≤ 2 , N is even; 1 ≤ S ≤ 2 ;1 ≤ L ≤ 2 ; additionally, 2 ≤ N ⋅ S ⋅ L ≤ 2 ).
The second line contains three positive integers M , K , and P , representing the number of
OXCs, the number of links between each OXC and each Spine within the same plane, and the
8 4
number of planes (1 ≤ M ≤ 2 ;1 ;
≤ K ≤ 2 1 ≤ P ≤ 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 Q, indicating the number of
1
bidirectional flow demands (1 ≤ Q ≤
2
(N ⋅ S ⋅ L) ).
Each of the next Q lines describes a bidirectional flow demand between LeafA and LeafB.
The i -th line, representing the i -th bidirectional flow demand, contains four integers, in order:
[Link] 3/5
1/7/26, 3:29 PM Problem - A - Codeforces
1. gA , number of Group of LeafA
2. LeafA number
3. gB , number of Group of LeafB
4. LeafB number
The group numbers satisfy 0 ≤ gA < gB ≤ N − 1 , and the leaf numbers are from 0 to
L − 1.
It is guaranteed that S and M are divisible by P , and that N − 1 ≤ S ⋅ (M /P ) ⋅ K .
(M /P )⋅K
It is guaranteed that the convergence ratio L
is either 1 : 1 or 1 : 3 or 1 : 7 .
It is guaranteed that each leaf appears no more than S times in each query.
Output
For each query, the output format is as follows:
First, output M lines. The i -th line (0 ≤ i ≤ M − 1 ) should contain R = N ⋅ (S /P ) ⋅ K
integers, representing the port connection relationships of OXC number i . The j -th integer vj
(0 ≤ j ≤ R − 1) indicates that the j -th port of this OXC is connected to the vj -th port. If vj
is −1, the port is idle.
Then output Q lines. For the i -th line (0 ≤ i ≤ Q − 1), output the planned routing path for
the i -th flow demand, containing five integers, in order:
1. Spine number x (0 ≤ x < S ) connected to LeafA
2. Link number kx (0 ≤ kx < K ) of x connected to the OXC
3. OXC number m (0 ≤ m < M )
4. Spine number y (0 ≤ y < S ) connected to LeafB
5. Link number ky (0 ≤ ky < K ) of y connected to the OXC
Scoring
Maximize the score as much as possible.
α OXC adjustment cost
SCORE = ∑ ∑ + β ⋅ (1 − )
maximum flow conflict ⋅ convergence ratio M ⋅ R
all tests all queries
Where α = 1000 and β = 300 .
Example
input Copy
2 1 2
2 1 1
2
0 1 1 0
0 0 1 1
2
0 0 1 0
0 1 1 1
2
0 1 1 0
0 0 1 1
2
0 0 1 0
0 1 1 1
2
0 0 1 0
0 1 1 1
output Copy
1 0
1 0
0 0 1 0 0
0 0 0 0 0
1 0
1 0
0 0 1 0 0
0 0 0 0 0
1 0
1 0
0 0 1 0 0
0 0 0 0 0
1 0
1 0
0 0 1 0 0
0 0 0 0 0
1 0
1 0
0 0 1 0 0
0 0 0 0 0
[Link] 4/5
1/7/26, 3:29 PM Problem - A - Codeforces
Codeforces (c) Copyright 2010-2026 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Jan/07/2026 15:28:19UTC+5.5 (g1).
Desktop version, switch to mobile version.
Privacy Policy | Terms and Conditions
Supported by
[Link] 5/5