[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
.