PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: awoholo
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
There are N frogs, numbered from 1 to N and placed in 2N buckets.
Every second, all frogs will move simultaneously:
- If all frogs are in the same bucket, nothing happens.
- Otherwise, each frog will jump one step towards whichever frog is the smallest-numbered one in a different bucket from it.
All such movements happen simultaneously.
Find the maximum number of frogs in a bucket at some point of time.
EXPLANATION:
Consider two different frogs i and j. Note that since they both move every second, the distance between them will change by either +2, 0, or -2 after each second.
In particular, if the initial distance between frogs i and j is odd, these two frogs will never meet each other.
On the other hand, if the distance between frogs i and j is even, they will surely meet at some point in the future.
Proof
Let L and R be the leftmost/rightmost buckets containing frogs, and B be the bucket containing frog 1.
Then,
- If B = L, all buckets $\gt L will jump towards L, while bucket L will jump to the right.
So, L cannot decrease, whereas R will decrease by 1 (as long as R-L \gt 1, that is).- Similarly, if B = R, L will increase by 1 while R won’t increase (again, as long as R-L \gt 1).
- If L \lt B \lt R, then both the buckets L and R will move towards B.
B itself might end up taking the position of L or R, but in any case at least one of them will come closer.So, as long as R-L\gt 1, every second the value of R-L will reduce by (at least) 1.
This means, eventually R-L will be either 0 or 1.
0 means everything is in the same bucket, while 1 means all the frogs are in adjacent buckets (and frogs in adjacent buckets can never meet, due to the parity condition).This already proves what we want: any two frogs with the same initial parity will initially meet, because the distance between them will eventually become \lt 2 (and hence must be 0).
Now, we saw that only the parity of distance between two frogs matters - and it must be even for frogs to meet.
An even distance means the parity of the buckets containing the frogs must be the same.
So,
- All frogs at odd positions will eventually be in the same bucket.
- Let there be X such frogs.
- All frogs at even positions will eventually be in the same bucket.
- Let there be Y such frogs.
Note that X+Y = N.
- Let there be Y such frogs.
- The answer is then simply \max(X, Y).
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()))
odd = sum(x%2 for x in a)
print(max(odd, n - odd))
