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

The Qubit Returns

Back to problem

Editorial

Represent the four states by 0,1,2,30,1,2,30,1,2,3. The action of each gate is the following permutation.

  • H: (2,3,0,1)(2,3,0,1)(2,3,0,1)
  • X: (1,0,2,3)(1,0,2,3)(1,0,2,3)
  • Z: (0,1,3,2)(0,1,3,2)(0,1,3,2)

Fix the left endpoint lll and move the right endpoint rrr from lll to NNN. Initially, the four resulting states are 0,1,2,30,1,2,30,1,2,3. When gate is added, apply its permutation to all four current results. If the results become again, add interval to the answer.

Repeat this for every lll. The time complexity is O(N2)O(N^2)O(N2), and the additional space complexity is O(1)O(1)O(1).

Solution written by GPT6

rr
r
0,1,2,30,1,2,30,1,2,3
[l,r][l,r][l,r]