[REDACTED] Well I guess I need to practice writing better.

I think yes, since the competition finished... Anyway, AoPS deleted P2 and P3. I am not sure now... day1 was held yesterday.

Yes, allowed

rightways wrote: Yes, allowed Медеубек Кунгожин сказал что пока нельзя

В jolynefag wrote: rightways wrote: Yes, allowed Медеубек Кунгожин сказал что пока нельзя Второй тур нельзя, первый можно

a brilliant problem

Note: If the first card has a second card clockwise in the next $500$ cards, let's call it the second one beating. $Fact$ $1$: If you choose any two cards, one will beat the other and two cards will never beat each other (it's easy to prove). $Fact$ $2$: A card with a blue mark $a$ ($a\geq 501$) could only lie on cards with a red mark: $0,1,...,1001-a$. $The process of $ $finding:$ We will search first for $1001$, then knowing the location of $1001$, we will find $1000$, and after knowing the location of $1001,1000$ we will find $999$ and so on… The search for $1001$ is very easy, we will consider only cards with $0$ (#2) as a candidate, and in this case it can be understood that if the first card with $0$ beats the second, then this card is larger than the second, then we will find the largest card with the inscription $0$ (all cards beat each other friend, #1), $1001$ will be there. Now, instead of $0$, we will write $1001$ on this card with a blue pen (for convenience). We will find the card $a$ if we know the cards $1001,1000, ..., a+1$. To begin with, consider only cards with $0,1,...,1001-a$ (#2). Let's say we are considering the best candidate from the cards with the red inscription $b$ from these numbers. Note that candidates from such cards need to take into account only those who have exactly $b$ of already defined numbers in the next $500$ of numbers clockwise. If there is less, then for some reason our $a$ card will be smaller than some indefinite card (which is impossible, because we have determined all cards greater than $a$). And it cannot be more obviously, because $b$ could not be written on the card. Let this be called the first filter. After the first filter, let's make the second one, it looks like this: Now let's look again at the cards with the red inscription $b$ that have already passed the first filter. According to #1, each card beats the other, which means that the beating other card has a bigger number, because we know all the numbers that are greater than $a$, which means any indefinite number in the field of $500$ numbers clockwise from the card with $b$ is always less than it, which means that the one that beats is more than the one that receives the blow. This is the $2$ filter. So, according to #1, we will output only one candidate with $b$, and we will do this with each (if there are cards left) $b$$\in[0,1,...,1001-a]$ and nominate all candidates. According to #1, again, each beats the other, which means it’s number is bigger on the same principle as in the $2$ filter. So, we will get only one candidate, there will be our cherished $a$. Let's write $a$ on this card in blue to remember. Thus, we will do with each card from $1001$ to $501$, and after that, we can forget about these cards altogether and rewrite all red cards with $a$ into $1001-a$ and find $0$ first, then knowing $0$, $1$ and so on up to $500$, which was required to be proved.

Very cute! Let $S$ be the set of all cards which have $500$ written in red. There must exist a card that has all other elements of $S$ among the next $500$ from it, and this must be the minimal number among all the cards (Initially this number is $1$). Now turn over this card $c$ with and write $c+1001$ in blue on it. Write $0$ in red on it and the $500$ cards before it, increase $f(C)$ by $1$ for them. Then it is the same problem, so we can find the new minimal number, which is $2$, and repeat until we have every blue number, done. $\blacksquare$

We call the card visible if we know the blue value on it. We will try to find a non-visible maximum card (a card is maximum if a blue value on it is the biggest) one by one. Let's say some cards are visible and they aren't counted (as a bigger number) while writing red numbers on other cards and also assume that only non-visible cards have red values. So our task is to find maximum non-visible card. Consider following algorithm : let $S$ be the set of cards with red number $0$ on it. It is obvious maximum card is in the $S$. If $|S| = 1$ we already found maximum card so we are done. Otherwise let's choose any card $A \in S$. If for all $B \in S$, $dist(A,B) \leq 501$ (We call the distance from the card $A$ to the card $B$, the number of cards we will see moving clockwise from $A$ to $B$, $dist(A, B)$ is just distance from those cards), We can say that $A$ is maximum card, since blue value on it is greater than any card's value in the set. Now consider the card $C$, for which $dist(A,C) > 501$ and $dist(A,C)$ is as small as possible. Notice that $A$ and any other card $B$ with property $dist(A,B) > 501$ are in the $500$ cards following $C$ clockwise. On the other hand any card $D$ with property $dist(A,D) \leq 501$ has less blue value than A, which has less value than $C$. Therefore $C$ is the card with maximum value. On each step we can find maximum non-visible card, and decrease $500$ cards value counter clockwise by 1 (since we know that this card was counted as a bigger card). So at the end we will find every single card.

Replace $1001$ with $2N+1$ and $500$ with $N$. Note that $2N+1$ is the maximal blue number, so it must have red number $0$. But, there may exist multiple $0$s. To resolve this issue, note that given any 2 $0$s, say $0_1, 0_2$, either $0_1$ lies in the $N$ cards lying clockwise from $0_2$ or vice versa. This is proved easily, since else there must exist $\geq N+N+2=2N+2$ cards, contradiction. Given this, we can easily compare between any two $0$s. Now we have found the $0$ having the largest value, we perform the following algorithm: In the $N$ cards preceding it, we decrease their red number by $1$. Now ignore the card with maximal blue number ($2N+1$) we found, maybe cross it out. We compare the $0$s we get from this algorithm (which is again, doable from above claim) and get our second largest blue number. Continuing so, we have found $2N+1,2N, \dots, 2,1$ as needed.

@above Exactly my solution.....just didn't know how to write it..

This problem is equivalent to the subtask "2k > n" of IOI 2020 plants problem. Link: https://oj.uz/problem/view/IOI20_plants