solution for game master on cf

game_master.md

"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:

1. each player can only dominate a prefix of the sorted array
2. 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

proof part 1

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

proof part 2: electric boogaloo

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();
        }
    }
}