Counting out game with std::list

Question

I recently tried to solve the Josephus Problem on Sphere Online to help answer this question but am getting TLE for any solution I come up with.

The exact parameters of the problem are:

This is new year in Planet X and there is something special! A classroom in this planet is looking for a new class leader using an unique game!

These are the ways how the game is played.

1. There are n students in the class. Each student is labeled from 1 (first student) to n (last student).
2. A paper is given to m-th student.
3. The next o-th student who gets the paper quits the game.
4. The paper is passed until there is one last student who hasn't quitted the game.
5. The student becomes the class leader.

Now, your task is to find the number of such student.

Input

The first line contains a number T (0 <= T <= 106). Each of the next T lines contains 3 integers which are n (0 < n <= 103), m, o (0 < m, o <= n) and are separated by a single space.

Output

For each test case, print the required answer.

Example

Input:
2
4 1 2
5 2 3

Output:
2
1

Explanation for test case 1

1 2 3 4 -> The paper is being held by student 1. Pass the paper by 2 students. Now, the paper is being held by student 3.

1 2 4 -> Student 3 quits. Pass the paper by 2 students. Now, the paper is being held by student 1.

2 4 -> Student 1 quits. Pass the paper by 2 students. Now, the paper is being held by student 4.

2 -> Student 4 quits. Student 2 becomes the class leader.

I chose to use a linked list for several reasons. First I wanted the fast random deletion times. I considered a vector because calculating the index may be faster than traversal but I also got TLE with that.

In the following code I iterate to the start_index, then iterate each step-remove sequence until there is only one node left, then return its value.

#include <iostream>
#include <iterator>
#include <list>

int josephus(int num_students, int start_index, int steps)
{
    std::list<int> students;

    for (auto i = 1; i <= num_students; ++i)
    {
        students.push_back(i);
    }

    std::list<int>::iterator it = students.begin();
    for (auto i = 1; i < start_index; ++i)
    {
        ++it;
        if (it == students.end())
        {
            it = students.begin();
        }
    }

    int countdown = num_students - 1;
    while (countdown--)
    {
        for (auto i = 0; i < steps; ++i)
        {
            ++it;
            if (it == students.end())
            {
                it = students.begin();
            }
        }

        if (it != students.begin())
        {
            it = students.erase(it);
            --it;
        }
        else
        {
            students.erase(it);
            it = students.end();
            --it;
        }
    }

    return *it;
}

int main() {
    int num_tests;
    std::cin >> num_tests;

    while (num_tests--)
    {
        int num_students; // formerly n
        int start_index; //formerly m
        int steps; //formerly o
        std::cin >> num_students >> start_index >> steps;

        std::cout << josephus(num_students, start_index, steps) << '\n';
    }
}

The biggest issues I can think of are the insertion and the iteration.

With insertion I mean setting the value of each node grows with the size of num_students and is thus \$\mathcal{O}(n)\$. That is just setting the list it doesn't even account for iteration and removal. The only solution to this I can think of is to express the problem mathematically.

When I say iteration may be a problem I mean two things. First I have no idea if I implemented the iterator properly and therefor are there so speed issues there? Is this the proper way to use an iterator efficiently in modern C++? Do you need to implement it differently for Lists? But also I was far more concerned with large values of steps and the lengthy iteration process with that.

Also, am I getting cache misses with the use of Lists? Inserting continuously doesn't guarantee contiguous memory if I understand correctly. Is there any way around that?

Being stumped with linked lists and determined to figure out the solution I tried to find a mathematical solution. After all Time Limit Exceeded usually just means you were trying a naïve and brute-force approach. I was able find this mathematical expression on GeeksForGeeks which ultimately was not fast enough either.

#include <iostream>

int josephus(int num_students, int steps) {
    if (num_students == 1)
    {
        return 1;
    }
    else
    {
        /* The position returned by josephus(n - 1, k) is adjusted because the
        recursive call josephus(n - 1, k) considers the original position
        k % n + 1 as position 1 */
        return (josephus(num_students - 1, steps) + steps - 1) % num_students + 1;
    }
}

int main() {
    int num_tests;
    std::cin >> num_tests;

    while (num_tests--)
    {
        int num_students; // formerly n
        int start_index; //formerly m
        int steps; //formerly o
        std::cin >> num_students >> start_index >> steps;

        int answer = josephus(num_students, steps);

        answer = (answer + start_index) % num_students;

        if (answer != 0) {
            std::cout << answer << '\n';
        }
        else
        {
            std::cout << num_students << '\n';
        }
    }
}

I share this because it still doesn't solve the problem on Sphere Online. I'm not sure what else to try. I didn't use recursion with my List implementation because I didn't think it would help. After all the first post I was answering use exposed nodes that were traversed recursively and when I cleaned that up it was still giving TLE. The mathematic solution above uses lots of calls to mod which I understand can be a very time-consuming operator. If the reason I can't solve this is because the math is just too far over my head then I'll accept that and move on but I have a feeling I'm just being silly and would prefer a hint or a nudge at the solution as apposed to the outright answer.

I am also always trying to improve my programming ability and would love feedback on any and all aspects of my code.

Answer 1

josephus implementation with std::list

• The list initialization can be simplified to

  std::list<int> students(num_students); // No braces here! (Would use the constructor taking a std::initializer_list)
  std::iota(std::begin(students), std::end(students), 1);
  

• Similarly, finding the starting iterator can be simplified to:

  const auto start_offset = (start_index - 1) % num_students;
  auto it = std::next(std::begin(students), start_offset);
  

• while(countdown--) is conceptually the same as while(students.size() > 1), which I personally would prefer because it highlights the intention behind the loop ("run until one element is left").

  There is no real performance loss: Since C++11, std::list::size is required to run in constant time.

• The loop body of the while loop first finds the element to be removed, removes it and then backtracks to the element before it.

  This could be simplified to

  1. Find the element before the one to be removed.
  2. Remove the next element.

So a cleaned up version could look like this:

int josephus(int num_students, int start_index, int steps) {
    std::list<int> students(num_students);
    std::iota(std::begin(students), std::end(students), 1);

    const auto start_offset = (start_index - 1) % num_students;
    auto it = std::next(std::begin(students), start_offset);

    while (students.size() > 1u)
    {
        for(auto i = 1; i < steps; ++i)
        {
            ++it;
            if (it == std::end(students)) it = std::begin(students);
        }

        const auto it_next = std::next(it) == std::end(students) ? std::begin(students) : std::next(it);
        students.erase(it_next);
    }

    return *it;
}

recursive josephus implementation

Seems fine. Just a general note:

• Beware of callstack overflows! It's unlikely to happen for the given input constraints, but it might for larger values, as there doesn't seem to be a way for the compiler to use Tail Call Optimization.

Questions

Note: In the following segments, \$n\$ refers to the number of students and \$k\$ to the stride between selected students.

I chose to use a linked list for several reasons. First I wanted the fast random deletion times. I considered a vector because calculating the index may be faster than traversal but I also got TLE with that.

A good (non-naive) implementation using std::vector should have the same runtime complexity as the std::list one, which is \$\mathcal{O}(k * n)\$. Yes, removal of a single random value is \$\mathcal{O}(n)\$ - but you might be able to remove up to \$\lfloor n / k\rfloor\$ values in one operation at no extra cost.

The biggest issues I can think of are the insertion and the iteration.

Insertion is just \$\mathcal{O}(n)\$, whereas all iteration steps in the while loop have runtime complexity \$\mathcal{O}(k * n)\$ - so iteration is more of a culprit here.

Also, am I getting cache misses with the use of Lists?

Yes, you are, and likely for every iteration step.

Inserting continuously doesn't guarantee contiguous memory if I understand correctly. Is there any way around that?

Using a custom allocator can provide contiguous memory for the nodes. However, iteration is still data dependent (the processor basically has to read the next address before it can continue), so there will be some cost for that. Some prediction or speculative execution might speed this up at the beginning, but after a while those won't work at the same level since the list gets more and more fragmented due to all the deletions.

I tried to find a mathematical solution

This seems to be the way to go. But: The presented recursive version still has runtime complexity \$\mathcal{O}(n)\$. But it's a good start!

The next step to get better runtime complexity is to remove multiple values in one operation: When removing the value at position \$i\$, we can remove values \$i + \text{step}\$, \$i + 2 * \text{step}\$, etc. in the same operation.

However, this only works if \$k < n\$ (obviously). This means we have to cover 3 cases:

1. \$n = 1\$: Just return the end of recursion value.
2. \$n \leq k\$: Similar to the current implementation
3. \$n > k\$: Some special handling to remove up to \$\lfloor n / k\rfloor\$ values at once.

This is basically what the \$\mathcal{O}(k \log n)\$ solution on wikipedia does.