[problem:476175A]
Author: Error_Yuan
Over all the triples, which is the most important one?
Note that, after sorting, if the triple $$$(1,2,n)$$$ is valid (i.e. $$$a_1+a_2>a_n$$$), then the whole array is valid. Thus, we are going to maximize the value of $$$a_1+a_2-a_n$$$ and check if it is greater than $$$0$$$. To do this, the optimal solution is to choose $$$a=[m-n+1,m-n+2,\ldots,m]$$$, and if $$$(m-n+1)+(m-n+2)\le m$$$, answer is NO
.
[problem:476175B]
Author: wyrqwq
What condition should $$$s$$$ satisfy to make sure that there is at least one valid index?
Think about the count of $$$\texttt{0}$$$-s and the count of $$$\texttt{1}$$$-s.
Each time we do an operation, if $$$s$$$ consists only of $$$\texttt{0}$$$ or $$$\texttt{1}$$$, we surely cannot find any valid indices. Otherwise, we can always perform the operation successfully. In the $$$i$$$-th operation, if $$$t_i=\texttt{0}$$$, we actually decrease the number of $$$\texttt{1}$$$-s by $$$1$$$, and vice versa. Thus, we only need to maintain the number of $$$\texttt{0}$$$-s and $$$\texttt{1}$$$-s in $$$s$$$. If any of them falls to $$$0$$$ before the last operation, the answer is NO
, otherwise answer is YES
.
[problem:476175C]
Author: Error_Yuan
The strategy for each one is simple.
Claim. Everyone will keep his potato in his hands (if he has) until the last round.
Proof. For everyone, the person previous and next to him both belong to the opposite team.