The proofs below are very verbose and long-winded, but the ideas behind the algorithms are not all that complicated. The steps can be summarized as:

1. A trivial solution (trying all possibilities and simulating the tournament for each one) gives an ~\mathcal O(N^2 R)~ algorithm.
2. One can observe that after no more than ~2N~ rounds, the tournament becomes cyclical with all positions repeating every ~N~ rounds. This allows the trivial algorithm to be sped up to ~\mathcal O(N^3)~.
3. One can optimize the simulation of the tournament (once we have chosen an initial position) from ~\mathcal O(N^2)~ to ~\mathcal O(N)~. This is the most complicated part of the solution. The key here is that we are only interested in our own position at the end, not in everyone else's.
4. Once you have a subroutine that tells you where you will end up given where you start, you can use it with a modified binary search, improving the ~\mathcal O(N^2)~ algorithm to ~\mathcal O(N \log N)~; or alternatively, improving the ~\mathcal O(N^3)~ algorithm to ~\mathcal O(N^2 \log N)~.
5. The last two algorithms above also have slower versions (~\mathcal O(N^2 \log N)~ and ~\mathcal O(N \log^2 N)~) if you try to solve the problem by also keeping track of other archers' positions, not just your own.

Optimising to ~\mathcal O(N^3)~

A trivial solution is to try all possible starting positions and simulate the tournament for each round, giving complexity of ~\mathcal O(N^2 R)~. We now show how this can be reduced to ~\mathcal O(N^3)~.

Consider the archers numbered from ~N+2~ to ~2N~. Let's call them the weak archers.

Theorem 1. After enough rounds (no more than ~2N~) the weak archers will occupy the targets numbered ~2~ to ~N~, one such archer on each target, and will stay there until the end of the tournament.

Proof. After ~N-1~ rounds, archer number ~1~ will be on target ~1~ and will stay there until the end. From this point on, if we consider the set of ~N~ archers consisting of archer number ~1~ plus the ~N-1~ weak archers (let us call this the weak+1 set), and if we imagine the targets arranged in a circle (~1~ to ~N~ and then again ~1~), we have the following scenario:

• When an archer from the weak+1 set competes with an archer outside of weak+1, then the weak+1 archer will stay on the target and the other archer will move.
• When two archers belonging to the weak+1 set compete against each other, one of them will stay and the other will move to the target on his left.

Lemma 1. Within ~N~ rounds after archer number ~1~ has arrived on target ~1~, every target will have at least one weak+1 member on it.

Proof. Suppose the above is not true. We know that once a target is occupied by a weak+1 member, then it will always be occupied by at least one (because weak+1 members never move out of their target unless there is another weak+1 archer to replace them there). Thus if Lemma 1 is false, there must exist a target that is never occupied by a weak+1 member (within the ~N~ rounds). Let's call this target ~A~. If ~A~ is never occupied by a weak+1 archer, then the target to the left of ~A~ (let us call it ~B~) would have at most one such archer within one round and would remain this way. Then within two rounds the target to the left of ~B~ would have at most one weak+1 archer, and within three rounds the next target to the left would have at most one such archer. Continuing around the circle, within ~N-1~ rounds the target to the right of ~A~ would have at most one weak+1 archer. Thus within ~N-1~ rounds, all targets except ~A~ would have at most one weak+1 archer. But since there are ~N~ such archers and ~N~ targets, this means that ~A~ must have at least one weak+1 archer. Since this contradicts our supposition that ~A~ remains free of weak+1 archer for ~N~ rounds, this proves Lemma 1.

Now that we know every target has at least one weak+1 archer within ~2N~ rounds from the start of the competition, and since we know that once a target has such an archer it never ceases to have at least one, we have proved Theorem 1.

Now consider all archers that don't belong to weak+1. If we have one weak+1 archer on every target, this also means we also have one non-weak+1 archer on every target. Since under this scenario the weak+1 archers always stay where they are, this means the archers numbered ~2~ to ~N+1~ will cyclically rotate around the ~N~ targets, periodically repeating their positions after every ~N~ rounds.

This means that if we replace ~R~ by ~R' = 2N+(R \bmod N)~ we would get an identical answer, since the outcome of the tournament after ~R~ rounds would be identical to the outcome after ~R'~ rounds (remember that ~R \ge 2N~).

The above means that we can easily improve our ~\mathcal O(N^2 R)~ algorithm to ~\mathcal O(N^3)~.

Optimising to ~\mathcal O(N^2)~

Currently, when we choose a starting position and we simulate what happens after ~R'~ rounds, we do ~\mathcal O(N^2)~ calculations per starting position. We can reduce the complexity of this part to ~\mathcal O(N)~ in the following way.

Observe that there are three types of archers: ones that are better than us, which we'll call the black archers; ones that are worse than us, which we'll call the white archers; and ourself (a single archer) which we'll denote as the gray archer. In order to solve our problem, we need not make any distinctions between archers of the same colour, as it is irrelevant to the final outcome. If two archers of the same colour compete against each other, it does not matter to us which one prevails (i.e., it is not going to impact the gray archer's final position). And we know that whenever two archers of different colours compete against each other, the archer of the darker colour wins.

Now there are three different cases which we'll handle separately.

Case 1 There are no black archers. This means we are the best archer and in this case it is trivial to show that the optimal target to start on is target ~N~.

Case 2 There is at least one black archer, but no more than ~N~. This means that our rank is between ~2~ and ~N+1~, which means we are part of the group of archers that eventually ends up circling the targets periodically. In this case, it is notable that we do not need to simulate the full tournament, but only what happens on target ~1~. If we know who competes on target ~1~ every round, then just observing when between rounds ~2N~ and ~3N~ the gray archer gets to compete against archer number ~1~ will tell us where the gray archer will finish the tournament (which is all that we are interested in). We will track what happens on target number ~1~ using the following algorithm:

We assign each archer ~i~ a number ~P_i~, which informally speaking indicates the earliest possible round where ~i~ might potentially compete on target ~1~. Initially each archer's ~P~ number equals his original target number. Then we simulate each round of the tournament with the following procedure:

1. We determine who is competing on target ~1~. The first archer there is clearly the winner on target ~1~ from the previous round (or initially the leftmost archer). We determine his opponent in the following way. We take all archers with ~P~ number less than or equal to the number of the current round. The best archer among them will now be competing on target ~1~ (the proof of why this is correct is further below).
2. We compare these two archers and assign the loser a ~P~ value equal to the number of the current (just passed) round plus ~N~. This is the earliest round when we might potentially see this archer back on target ~1~.

Now let us prove that the above is correct. We will denote with ~A_j~ the archer who is competing on target ~1~ on round ~j~, but who was competing on target ~2~ on round ~j-1~. Every archer ~i~ has a value ~P_i~ that if he were to win every single contest since getting that ~P_i~ value, he would end up being ~A_{P_i}~. Now let's look at the archer selected by our algorithm to be ~A_j~ (for some round ~j~). We will denote him by ~W~. Let ~S = j-P_W~. If ~S~ is zero, this means that ~W~ didn't have the opportunity to become ~A_{j-1}~ even if he were to win all his contests. Hence, in this cycle ~W~ never met ~A_{j-1}~ (or any of the earlier ~A~'s). Since ~W~ never met these archers and since he is better than everybody else who is in the running for ~A_j~, this means that he never lost in this cycle (until he got to target ~1~ at least), which means he truly is ~A_j~ (i.e., our algorithm is correct in this case).

If ~S~ is greater than zero, this means that ~W~ had the opportunity to become ~A_{j-1}~, but lost it. This means he competed directly with ~A_{j-1}~ because the latter was the only candidate for ~A_{j-1}~ that was better than ~W~². Now if ~W~ competed with ~A_{j-1}~ and if he is better than every other ~A_j~ candidate, this means that after their meeting ~W~ was always "on the heels" of ~A_{j-1}~: either on the same target, or on the one immediately to the right. This means that when ~A_{j-1}~ reached target ~1~ (which is in round ~j-1~), ~W~ was on target ~2~. Since by definition he was better than the other archer on target ~2~, this means he was indeed the one to reach target ~1~ on round ~j~.

² This is true because by our algorithm every candidate for ~A_{j-1}~ automatically becomes a candidate for ~A_j~, except for the actual ~A_{j-1}~ — so if ~W~ was an ~A_{j-1}~ candidate, but did not succeed and is now the best among the ~A_j~ candidates, he must have been second to ~A_{j-1}~ among the ~A_{j-1}~ candidates.

Now that our algorithm for keeping track of target ~1~ is proved correct, we can analyze its time complexity. Since we make no distinction between same-coloured archers, we can represent any set of archers by just three numbers: the number of white, gray and black archers in that set. This allows us to execute every step of the algorithm (i.e., every round of simulation) in constant time, because all we have to do is determine the colour of the best archer in a set of candidates and then add to that set only one or two new archers (those whose ~P~ value equals the number of the next round). Since we only need to simulate up to round ~3N~, and we are not interested in ~P~ values above ~3N~, we can implement our simulation algorithm in ~\mathcal O(N)~ time and space.

Case 3 There are more than ~N~ black archers. This means our number is more than ~N+1~, which means that we are one of the archers that eventually end up standing on the same target indefinitely. We only need to determine which target that is.

We already showed that once archer ~1~ arrives on target ~1~, all that the weak+1 archers do is push each other around the targets until they settle on a different target each. Since our number is greater than ~N+1~, this means that all white and gray archers belong to the weak set. Thus all we need to do is simulate how the white and gray archers push each other around. We start at target ~1~ where we know no white/gray archer would be allowed to stay. Then we attempt to count how many white/gray archers end up getting "pushed" around the circle after every target. Initially the white/gray archers pushed from ~1~ to ~N~ would be those that were initially at target ~1~ (note that our count is still a lower bound; later on we may find out there were even more white/gray archers pushed from target ~1~). Then we move to target ~N~. We add any white/gray archers that start there to the ones we transferred from target ~1~ and we leave one of the combined set there (we always leave a white one, if we have one; if not, we leave the gray; if the set is empty, then we obviously do not leave anyone and let the black archers have this spot). We keep going around the circle from ~N~ to ~N-1~, to ~N-2~, etc. On every target, we "pick up" any white/gray archers and we leave one of those we have picked up either earlier or now. Eventually we get to target ~1~ and if we happen to have any white/gray archers pushed to target ~1~, we just transfer them to target ~N~ and keep going with the same procedure. The second time we return to target ~1~ we certainly will not have any more white/gray archers to push around, because by Theorem 1 we know that in ~2N~ rounds every white or gray archer would have settled on a target. This algorithm clearly runs in linear time and space for the same reasons as the algorithm in Case 2 above. It is also correct because we only move around white/gray archers when necessary (i.e., when they would end up on the same target with another white/gray archer or on target ~1~) and we make sure that in the end every white/gray archer would have settled somewhere where he can remain undisturbed until the end of the tournament.

The optimization of the tournament simulation from ~\mathcal O(N^2)~ to ~\mathcal O(N)~ described above improves our solution to the whole problem from ~\mathcal O(N^3)~ to ~\mathcal O(N^2)~.

Optimising to ~\mathcal O(N \log N)~

The last optimization that we use to bring the complexity of our algorithm down to ~\mathcal O(N \log N)~ is based on the well-known technique of binary search. The efficient tournament simulation algorithms described above can easily be modified to also tell us how many times the gray archer moves from target ~1~ to target ~N~ (denoted by ~T~). Combining this information with the final position of the gray archer (denoted ~X~) allows us to view the final position on a linear (as opposed to circular) scale. If we describe the outcome of a simulation as being the number ~X - N \times T~ we can think of every transfer of the gray archer from one target to another as decrementing the outcome by one. Then if we look at the simulation algorithms described above, we can observe that if the starting position is higher, then the final outcome can never be lower. For example, if you choose to start with a larger ~P~ value this can never get you further ahead (on the linear scale, not the circular) than if you had chosen a smaller initial ~P~ value.

Given this monotonic relationship between the starting position and the final outcome of a tournament, can find the optimal starting position as follows:

1. Measure the outcome of starting on target ~1~.
2. Measure the outcome of starting on target ~N~.
3. For each multiple of ~N~ in this range, use standard binary search to find the smallest possible ending position strictly greater than this multiple (and hence the closest to target ~1~ for a particular number of wrap-arounds).
4. Of the starting positions found above, pick the best.

Since there are only ~\mathcal O(N)~ rounds being considered, the range to search is ~\mathcal O(N)~ and hence only ~\mathcal O(1)~ binary searches are required. Each such binary search requires ~\mathcal O(\log N)~ starting positions to be tested, giving a time complexity of ~\mathcal O(N \log N)~.

Additional notes

Finally, we should note that the efficient simulation algorithms described above (which ignore distinctions between same-coloured archers and work in ~\mathcal O(N)~ time per simulation) can be implemented in a way that does distinguish between the different black or white archers, using binary heaps or other similar data structures. This would give a final algorithm of complexity ~\mathcal O(N^2 \log N)~ or ~\mathcal O(N \log^2 N)~, depending on whether one also uses the binary search. One can also achieve a time complexity of ~\mathcal O(N^2 \log N)~ or ~\mathcal O(RN \log N)~ by applying the binary search technique without optimizing the simulation.

It is also possible to solve the problem in linear time, but this is very difficult and left as an exercise to the reader. An ~\mathcal O(N \log N)~ solution is sufficient to receive a full score.