I have a question about CF#745(div.2)F Subsequence

Revision en2, by pengyule, 2021-11-15 12:07:16

Hi. The tutorial said that the total time complexity of the solution is $$$O(n^2)$$$, but there seems to be 2 layers of "for"s in each turn of "dfs", which seems to be $$$O(n^3)$$$. Though it must be less than $$$O(n^3)$$$, could anyone please analyse detailedly of the problem? THX!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English pengyule 2021-11-15 12:07:16 1 Tiny change: 'there seem to be 2 l' -> 'there seems to be 2 l'
en1 English pengyule 2021-10-04 06:23:26 320 Initial revision (published)