DOJ logoDOJ
Problems
Recently added problemsSaved problemsWorkbooks
CategoriesDLCContestsGroupsTeamsBoard
Ranking
Solved Problem RankingStreak rankingDOJ Power ranking
Status
Call for TasksLoginRegister
DOJ logoDOJ

Community online judge with OI-style subtask scoring, Elo ratings, and Discord account linking.

Problems
ProblemsCategories
Community
ContestsRankingBoardNoticesHost an external contestGuide
Account
LoginRegisterJudge Status
Policy
Terms of ServiceDLC RulesPrivacyAPI documentationLanguage runtimesContest rank rewardsRating and performance
© 2026 DOJ
All rights reserved
Editorial

Grid Sorting

Back to problem

Editorial

Read odd rows from left to right and even rows from right to left, forming a snake path of length K=N2K=N^2K=N2. Consecutive path cells are adjacent on the grid.

Treat the path as an array and output the comparisons of bubble sort with a shrinking unsorted suffix boundary. No values need to be read. Rightward path edges use type 222, downward edges use type 111, and leftward edges use type 444. For a leftward edge, give the coordinates of its left cell.

The first stage sorts the path using K(K−1)/2K(K-1)/2K(K−1)/2 operations. Each row now contains exactly its required values, but even rows are reversed. Sort each even row using type-222 bubble-sort comparisons.

The total number of operations is

X=N2(N2−1)2+⌊N2⌋N(N−1)2≤N42+N34≤N4.X=\frac{N^2(N^2-1)}2+\left\lfloor\frac N2\right\rfloor\frac{N(N-1)}2\leq\frac{N^4}{2}+\frac{N^3}{4}\leq N^4.X=2N2(

Output time is O(N4)O(N^4)O(N4) and path storage is O(N2)O(N^2)O(N2). At N=30N=30N=, . We have , and the checking-budget numerator is . All arithmetic fits signed 64-bit integers.

For subtask 1, a naive implementation makes KKK complete bubble-sort passes along the path, then repairs even rows. It uses 13,75,25213,75,25213,75,252 operations for N=2,3,4N=2,3,4N=2,3,4, respectively. For the full range, omit the already finalized suffix so the first stage uses only K(K−1)/2K(K-1)/2 comparisons.

The checker stores O(X)O(X)O(X) operations. It runs in O(⌊108/N4⌋(N2+X))O(\lfloor10^8/N^4\rfloor(N^2+X))O(⌊108/N4⌋(N time.

Solution written by GPT6

N
2
−
1
)
​
+
⌊2N​⌋2N(N−1)​≤
2N4​+
4N3​≤
N4.
30
X=411 075X=411\,075X=411075
N4≤810 000N^4\leq810\,000N4≤810000
10810^8108
K(K−1)/2
2
+
X))