I have a modification of the Josephus problem (e.g., we have $$$n$$$ people in a circle, and we kick each $$$k$$$-th out till we have only one, tell which number he has), but I have to output the order in which the last $$$4$$$ people (I guess it generalises to $$$p$$$ people in the end) are kicked out.

The constraints are $$$10^7$$$ for both $$$n$$$ and $$$k$$$, which makes it almost impossible to pass a naive solution ($$$O(n \log{k})$$$) without optimisation magic. All Josephus problem approaches which are known to me seem to be ungeneralisable to get the order of elements which are removed from the circle.

Feel free to comment if you have any ideas! The unfolding from the last state (1 element left) doesn't seem to be a very promising strategy, but I might have missed some important observations.

The problems available on the EDU section, and in the ITMO course in particular, are very helpful in learning the basics. It would be awesome to be able to add them to private mashups for school trainings and other stuff. I couldn't find a way to copy any of the EDU problems to my mashup contests.

If this is impossible without big changes, is there a way to reduce the amount of work required to have those problems in a mashup? The tests can be opened after the problem is solved by the user, which (at least) simplifies the test writing problem. Otherwise it becomes a massive pain to use the basic, almost theoretical problems because the archive problems are more advanced and sometimes don't suit the level of the audience.

What do you think? If there is a way to get those basic problems (especially from Binary search and Segment tree sections) or I miss something important please comment.

Манифест спортивного программиста

1. Приоритетом спортивного программиста является процветание науки и продвижение знаний в массы.
2. Спортивный программист никогда не списывает и не дает списывать, но помогает товарищу в учении, делая все возможное для понимания темы.
3. Спортивный программист не оскорбляет достоинства и приоритеты своих коллег и соперников, уважает оппонентов.
4. Спортивный программист не обязан доказывать свои решения.
5. Спортивный программист, как и любой порядочный человек, следит за своими словами и отвечает за них.
6. Спортивный программист с умом относится к выбору тем для изучения, уделяя основное время решению задач.
7. Спортивный программист следит за своим здоровьем и физической формой, так как понимает важность спорта для работы мозга.
8. Спортивный программист читает художественную литературу, не считает ее бесполезной и непрактичной.
9. Спортивный программист уважает своих учителей.
10. Спортивный программист вносит посильный вклад в доступность знаний для сообщества путем расширения онлайн-энциклопедий и обновления доступных ресурсов.

Комментарии приветствуются!

UPD: после всеобщего возмущения решилось, что доказательство решений не обязательно.

Tupper's formula is a way to encode some 106 by 17 pictures using one number k, for example:

49932790667390235006810925780144730667086920970723202128025820188112422448853248013915761930483464556355134017845070361006803072732535328765570896616771854041487727670861790300002477702654579875870985483450138587826833172648192309028942474529051678976718347977727635901521352785976482413650034570571098999776199186760370814287019004384092624950892514730954399259539885243921322241518159777104263926442504211715099364527901887270118023434451175608564304647278998357332871172697781368938037248

Original image

Share your number pictures!

Learn more and decode/encode the pictures: https://keelyhill.github.io/tuppers-formula