PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Author: Ashish Kumar
Tester: Danny Mittal
Editorialist: Nishank Suresh
DIFFICULTY:
Easy - medium
PREREQUISITES:
Sorting
PROBLEM:
Chef and N police officers are standing at distinct positions on a one-dimensional grid. They move in turns - first, each officer moves one step either left or right to an unoccupied square, then chef moves either left or right to an unoccupied square. An officer who cannot move is eliminated, and if Chef cannot move he is captured. Find the maximum number of officers that can be eliminated.
QUICK EXPLANATION
If the sorted set of positions is P_1 < P_2 < \dots < P_i < C < P_{i+1} < \dots < P_N, Chef can eliminate the longest prefix of officers starting at i+1 and the longest suffix ending at i such that such that C\pmod 2 \neq P_j\pmod 2.
EXPLANATION:
Suppose Chef starts at position C. Let us concentrate only on officers whose initial positions are greater than C for now - the other case turns out to be symmetric.
Suppose we have C < P_1 < P_2 < \dots P_N.
An initial observation is that the relative parity of C and P_i always stays the same, i.e, if they are initially of the same parity, after any set of moves they will still be of the same parity; and if they are initially different and set of moves will keep them distinct.
Now, let’s look at P_1 first. There are two cases
-
C and P_1 have the same parity
In this case, P_1 can never be eliminated - in fact, none of the officers can be eliminated.
Proof
Given that they have the same parity, and must start on distinct squares at the start of each police turn, we must have P_1 \geq C+2.
This means that P_1 can always simply take one step towards Chef irrespective of the movements of other officers, and in particular will never be eliminated.
Further, because P_1 can always move left towards Chef, that movement will leave at least one empty space for P_2 to move left, which then allows P_3 to move left, and so on.
Thus, every officer always has at least one legal move, meaning none of them can be eliminated.
-
C and P_1 have different parity
In this case, P_1 can always be eliminated.
Proof
Suppose P_1 > C+1. Then, P_1 \geq C+3, so no matter what move P_1 makes, Chef can always move one step right.
Thus, the distance between Chef and P_1 either stays the same, or decreases by 2 - in particular, it does not increase.
What happens if P_1 = C+1?
P_1 then has no choice but to move right, and this allows Chef to also move right on his turn.
However, our grid is finite, and so P_1 cannot move right forever.
Thus, there will come a time when P_1 = C+1, but P_1+1, P_1+2, \dots, 10^{10} are all occupied by officers.
This will force P_1 to be eliminated, as required.
Now that P_1 has been eliminated, let’s look at P_2.
If P_2 and C have different parities, a similar argument as above tells that P_2 can also be eliminated - either after eliminating P_1 by following the same strategy, or P_2 was already eliminated before P_1 was.
On the other hand, if P_2 and C have the same parity, our first argument tells us that P_2 can never be eliminated - and hence P_i for i\geq 2 can never be eliminated.
This brings us to the following result:
Lemma: Let k be the smallest index such that parity(C) = parity(P_i). Then, when the police move optimally, only P_1, P_2, \dots, P_{i-1} can be eliminated, and none beyond that.
The proof follows easily from the processes described above.
Of course, the exact same result follows for officers to Chef’s left, i.e, some suffix of them with different parity from C can be eliminated, and none beyond that.
Thus, we have our final algorithm:
- Sort the set of officers.
- Among the officers to the right of Chef, choose the longest prefix such that their parity is different from C.
- Among the officers to the left of Chef, choose the longest suffix such that their parity is different from C.
The answer is the sum of the above two quantities.
Finally, Chef escapes if and only if all officers are eliminated, so print 1 if all N officers can be eliminated and -1 otherwise.
TIME COMPLEXITY:
\mathcal{O}(N\log N) per test.
CODE:
Setter (C++)
#include <bits/stdc++.h>
using namespace std;
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
int main()
{
int t;cin>>t;
assert(t>=1 and t<=10);
while(t--){
int n;cin>>n;
assert(n>=1 and n<=100000);
int chef;cin>>chef;
assert(chef>=1 and chef<=1000*1000*1000);
int police[n];
for(int i=0;i<n;i++){cin>>police[i];
assert(police[i]>=1 and police[i]<=1000*1000*1000);
assert(police[i]!=chef);
}
sort(police,police+n);
int p1=lower_bound(police,police+n,chef)-police;
int p2=upper_bound(police,police+n,chef)-police;
int ans=0;
p1--;
while(p1>=0 and police[p1]%2!=chef%2){p1--;ans++;}
while(p2<n and police[p2]%2!=chef%2){p2++;ans++;}
cout<<ans<<' ';
if(ans==n)cout<<1<<endl;
else cout<<-1<<endl;
}
}
Tester (Kotlin)
import java.io.BufferedInputStream
const val BILLION = 1000000000
fun main(omkar: Array<String>) {
val jin = FastScanner()
repeat(jin.nextInt(10)) {
val n = jin.nextInt(100000)
val chef = jin.nextInt(BILLION)
val police = IntArray(n) { jin.nextInt(BILLION, it == n - 1) }
val left = police.filter { it < chef }.sortedDescending()
val right = police.filter { it > chef}.sorted()
val answer = (left.indexOfFirst { it % 2 == chef % 2 }.takeUnless { it == -1 } ?: left.size) + (right.indexOfFirst { it % 2 == chef % 2 }.takeUnless { it == -1 } ?: right.size)
println("$answer ${if (answer == n) 1 else -1}")
}
}
class FastScanner {
private val BS = 1 shl 16
private val NC = 0.toChar()
private val buf = ByteArray(BS)
private var bId = 0
private var size = 0
private var c = NC
private var `in`: BufferedInputStream? = null
constructor() {
`in` = BufferedInputStream(System.`in`, BS)
}
private val char: Char
private get() {
while (bId == size) {
size = try {
`in`!!.read(buf)
} catch (e: Exception) {
return NC
}
if (size == -1) return NC
bId = 0
}
return buf[bId++].toChar()
}
fun nextInt(): Int {
var neg = false
if (c == NC) c = char
while (c < '0' || c > '9') {
if (c == '-') neg = true
c = char
}
var res = 0
while (c >= '0' && c <= '9') {
res = (res shl 3) + (res shl 1) + (c - '0')
c = char
}
return if (neg) -res else res
}
fun nextInt(unused1: Int, unused2: Boolean = true) = nextInt()
fun nextInt(unused1: Int, unused2: Int, unused3: Boolean = true) = nextInt()
}