olasiliksizci's blog

By olasiliksizci, history, 8 months ago, In English

Hi eveyone!

This is the first blog and the first problem that I wrote. I will share the problem and some different approaches to solve it. If you want to try it first, here is the statement:

There are $$$N$$$ children in a circle. During the game, every other child is removed from the circle until there are no children left (classic Josephus Problem). The order of removals creates a permutation of $$$N$$$ and lets call that $$$p$$$. I want you to find for all $$$i$$$ such that $$$1 \leq i \leq N$$$ and $$$p_i = i$$$. Print them in increasing order. If there is no such a number print $$$-1$$$. For example for $$$N = 7$$$ the permutation is $$$p = {2, 4, 6, 1, 5, 3, 7}$$$. 5th number is 5 and 7th number is 7 so you should print 5 7. There is also $$$T$$$ test cases.

$$$1 \leq T \leq 2 * 10^5$$$
$$$1 \leq N \leq 10^9$$$

I couldn't figure it out but then I've find a solution by looking the answer patterns. I still have no clue why it is like that but here is my code and explanation. I'm sure both solutions are correct, I've checked them with a slower time complexity bruteforce way.

Idea: olasiliksizci

Solution
Explanation

There is another solution with different approach.
Idea: Leadd

Solution
Explanation

There is a hard version of that problem which is I'm completely unsure if it has a solution or not. Only difference is instead of skipping 1 child, skip k child. For example $$$N = 7$$$, $$$K = 2$$$. $$$P = {3, 6, 2, 7, 5, 1, 4}$$$ the answer is 5.

Thanks for reading my very first blog, don't forget to comment and share your ideas.

Good Problem
Bad Problem

  • Vote: I like it
  • +34
  • Vote: I do not like it

»
8 months ago, hide # |
Rev. 2  
Vote: I like it 0 Vote: I do not like it

You can find the solution to k >= 2 here ... Just read few days ago

  • »
    »
    8 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Yes... But not I am asking for. The constraint on $$$N$$$ is up to $$$10^9$$$ so I can't find order for each element I guess. Also I don't want to create the permutation at all.

  • »
    »
    8 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    I think this article talks about the last remaining number and not how to get the order of removals.