Is there an alternative solution to CSES Josephus Problem II?

Revision en2, by EJam, 2022-04-24 07:02:00

I'm revisiting CSES problem set to help a friend. In "Sorting and Searching", there is this problem: Josephus Problem II. My solution was using an ordered set, and after a quick search, it seems like everyone online did this too. However, we see the more general version of this problem: List Removals in the section "Range Queries".

The category of this problem and a solution which is more general made me wonder if there is an alternative solution, perhaps without ordered set. I did some search online and found O(n) solution to the Josephus Problem (also see cp-algorithm). But this is different from the CSES problem, as it only finds the last element.

So, out of curiosity, is there any solution that is not doing removal on ordered set? Otherwise, this feels like a pretty bad problem.

Tags cses, josephus problem, interesting

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English EJam 2022-04-24 07:02:00 96 (published)
en1 English EJam 2022-04-24 06:53:58 1030 Initial revision (saved to drafts)