"Domination". Look it up.
— Scout, TF2
after the dec contest, i have come to the conclusion that i suck a** at dp
so i was grinding cf and i came upon
this
problem that had the tag dp
but my solution was anything but that, so lemme just share my sol
it gives us a bunch of players who have 2 strengths- one for each of two maps
we can match two players on any of the two maps, and the player who's stronger
on that map wins without fail
it then asks us to calculate for each of the players if they can dominate all
the others, whether that be directly or indirectly
so first let's just sort all the players by map 1 strength
this way, if p2 comes after p1, we know that p2 can dominate p2 hard-on
NOTICE! that the rearranged answer array will always look like this:
00000000...0000000 111111...111111111
|------------------| |------------------|
nonnegative # of 0's nonnegative # of 1's
why? i think we just have to prove two sub-things to get to the actual claim:
- each player can only dominate a prefix of the sorted array
- the length of this subarray can only increase or stay the same as you go through the array from left to right
so let's get proofing ig
i mean this part is kinda obvious
if hypothetically, for the sake of the argument, we had a can-dominate array like this:
000111100001111000
that would be insane, because the middle & leftmost segment of 0's can clearly be
dominated through the right sequence of 1's
so yeah
ok say p2 came right after p1
now the domination array can only stay the same or increase, because p2 can dominate
everyone p1 has through p1, and maybe even dominate a bit more!
q.e.d. ez clap
now that the proof is done, we can just use binary search to find the breakpoint
to check if a player can dominate everyone we keep track of the maximum map2 strength
that we can utilize and then while that strength can keep on expanding throughout the
rest of the playerbase we keep on updating that strength
if we get to the final player we win, & we lose if we don't, simple as that
imp here:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
/**
* https://codeforces.com/contest/1608/problem/C
* (input omitted due to length)
*/
public final class GameMaster {
public static void main(String[] args) throws IOException {
BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
int testNum = Integer.parseInt(read.readLine());
for (int t = 0; t < testNum; t++) {
int playerNum = Integer.parseInt(read.readLine());
StringTokenizer map1 = new StringTokenizer(read.readLine());
StringTokenizer map2 = new StringTokenizer(read.readLine());
int[][] players = new int[playerNum][];
for (int p = 0; p < playerNum; p++) {
players[p] = new int[]{
Integer.parseInt(map1.nextToken()),
Integer.parseInt(map2.nextToken()),
p // keep track of the original index
};
}
// elements are guaranteed to be unique
Arrays.sort(players, Comparator.comparingInt(p -> p[0]));
/*
* this[x] = if our current map strength is x,
* what's the maximum index we can dominate up to (inclusive)?
*/
TreeMap<Integer, Integer> maxKills = new TreeMap<>();
for (int p = 0; p < players.length; p++) {
maxKills.put(players[p][1], p);
}
int prev = Integer.MIN_VALUE;
for (int i : maxKills.keySet()) {
if (prev != Integer.MIN_VALUE) {
maxKills.put(i, Math.max(maxKills.get(i), maxKills.get(prev)));
}
prev = i;
}
// this[p] = best map 2 strength up to player p
int[] bestMap2 = new int[playerNum];
bestMap2[0] = players[0][1];
for (int p = 1; p < playerNum; p++) {
bestMap2[p] = Math.max(bestMap2[p - 1], players[p][1]);
}
int lo = 0;
int hi = playerNum - 1;
int valid = -1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
int at = mid;
while (maxKills.get(bestMap2[at]) != at) {
at = maxKills.get(bestMap2[at]);
}
if (at == playerNum - 1) {
valid = mid;
hi = mid - 1;
} else {
lo = mid + 1;
}
}
int[] possible = new int[playerNum];
for (int p = valid; p < playerNum; p++) {
possible[players[p][2]] = 1;
}
for (int p = 0; p < playerNum; p++) {
System.out.print(possible[p]);
}
System.out.println();
}
}
}