CHEF7UP - Editorial

Author: Ashish Kumar
Tester: Danny Mittal
Editorialist: Nishank Suresh

Easy - medium

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:

1. Sort the set of officers.
2. Among the officers to the right of Chef, choose the longest prefix such that their parity is different from C.
3. 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 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()
}

2 Likes

if we have this situation at the end of grid: …CPPP|<-- end of grid
last 4 cells occupied by Chef and 3 police officers.
all three officers (P) cannot move, so why only one is eliminated (why not all three)?

Also the problem has a phrase “maximum number of officers that can be eliminated by Chef”.
it gives the impression that Chef eliminates them, (i.e Chef decides who will be eliminated in such situations) - then it makes sense for him to eliminate P which stands next to the end of grid, this way he can eliminate more officers…

I think all such situations should be more clearly defined in the problem statement.

2 Likes

From the statement:

During their turn, officers will have to move to an adjacent unoccupied cell one by one, in any order they want. Every officer will have to move.

and

Note that the officer team will try to move to eliminate as few officers as possible.

In the situation you mentioned, the leftmost officer is first eliminated, and that frees up a space for the second officer, whose movement then frees up a space for the third officer.
After this, neither remaining officer can be eliminated.
This is optimal from the perspective of the officers, because at least one of them must be eliminated and this guarantees that exactly one will be eliminated.

If you are ever doubtful about some part of any statement during a contest, please ask for a clarification in the comments - the setters and contest admins are online and will attempt to resolve the issue.

4 Likes

So this means, 2 officers can be eliminated at max. One from the either side, if they are present and if their parities are different ??

No, there’s no such bound.
For example, in a case like
.....CP_P_P_P|
all 4 officers will be eliminated eventually, no matter what they do.

3 Likes

OK, Got it. Thanks !!