PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: pols_agyi_pols
Tester: kingmessi
Editorialist: iceknight1093
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
There are N people, the i-th has friendliness A_i.
Is it possible to arrange them in a circle in such a way that for each person, there exists someone adjacent to them with smaller or equal friendliness?
EXPLANATION:
Let M = \min(A) denote the minimum friendliness of anyone among these N people.
For a person with friendliness M, it’s impossible for there to be someone with smaller friendliness next to them in the circle; after all M is the minimum.
So, the only way they can be satisfied at all, is if someone with equal friendliness is next to them.
This, of course, is only possible when there are at least 2 people with friendliness M present at all.
So, if the number of people with friendliness M is equal to 1, the answer is surely No.
On the other hand, if the count is \ge 2, then the answer is always Yes.
A simple construction is to just place people in ascending order of friendliness along the circle, with the lowest and highest friendliness people adjacent to complete it.
It’s easy to see that as long as the lowest friendliness M occurs multiple times, everyone will be satisfied.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
mn = min(a)
if a.count(mn) == 1: print('No')
else: print('Yes')