Editorial for Monster Battle

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Loctildore

This is a maximum matching problem. We want to calculate the maximum number of pairs $(x, y)$ ~(x, y)~ we can form such that- $x$ ~x~ is your monster and $y$ ~y~ is your opponent's monster

$x$ ~x~ beats $y$ ~y~
no monster is used in more than one pair

This can be expressed as a bipartite graph with $O(N)$ ~O(N)~ nodes and $O(N^2)$ ~O(N^2)~ edges, so we can run Hopcroft–Karp to solve it in $O(N^{2.5})$ ~O(N^{2.5})~. A well written implementation passes the time-limit, but we can do better.

Let the set of your monsters be $A$ ~A~ and the set of opponent's monsters be $B$ ~B~.

We want a flow network with the following properties

There is an edge from the source to all $x \in A$ ~x \in A~ with capacity $1$ ~1~.
For all pairs $(x, y) \in A \times B$ ~(x, y) \in A \times B~ there is a path from $x$ ~x~ to $y$ ~y~ iff $x$ ~x~ beats $y$ ~y~. All of the edges on these paths should have infinite capacity.
There is an edge from all $y \in B$ ~y \in B~ to the sink with capacity $1$ ~1~.

If we calculate the maximum flow of this network, it will be precisely the answer to our question. Every unit of flow corresponds to a path which goes from the sink to some $x \in A$ ~x \in A~, then reaches some $y \in B$ ~y \in B~ where $x$ ~x~ beats $y$ ~y~, then goes directly to the sink. As the edges connecting the nodes with the source and sink have a capcity of $1$ ~1~, all $x \in A$ ~x \in A~ and $y \in B$ ~y \in B~ can be used at most once.

To construct this network, we can order the opponent's fire types by skill and add an edge from each to the one with the next highest skill. If we add an edge from each of our monster's to the most skilled fire type they can beat, they will have a path to an opponent fire type iff they can beat it. We do the same for the opponent's water and grass types and our required network is complete.

As there are $O(N)$ ~O(N)~ edges and the size of our maximal flow is at most $N$ ~N~, Ford-Fulkerson runs in $O(N^2)$ ~O(N^2)~.

Python solution:

from bisect import bisect_left
from collections import deque, defaultdict 
import math

def supereffective(a, b):
    return (a == 'W' and b == 'F') or (a == 'F' and b == 'G') or (a == 'G' and b == 'W');

class Monster:
    __slots__ = ["type", "strength", "index"]
    def __init__(self, type, strength, index):
        self.type = type
        self.strength = strength
        self.index = index

    def __lt__(self, other):
        if supereffective(self.type, other.type):
            return self.strength*2 < other.strength
        if supereffective(other.type, self.type):
            return self.strength < other.strength*2
        return self.strength < other.strength

    def __repr__(self):
        return f"{self.type} {self.strength}"


n = int(input())

inp = input().split()
myMonsters = [Monster(inp[2*i], int(inp[2*i+1]), i+1) for i in range(n)]

inp = input().split()
oppMonsters = []
fireMonsters, grassMonsters, waterMonsters = [], [], []
for i in range(n):
    m = Monster(inp[2*i], int(inp[2*i+1]), n+1+i)
    oppMonsters.append(m)
    if m.type == 'F':
        fireMonsters.append(m)
    elif m.type == 'W':
        waterMonsters.append(m)
    elif m.type == 'G':
        grassMonsters.append(m)

capacity = [[0 for _ in range(2*n+2)] for _ in range(2*n+2)]
adj = [[] for _ in range(2*n+2)]

def addEdge(f,t,cap):
    adj[f].append(t)
    adj[t].append(f)
    capacity[f][t] += cap

# Connect all ours to source and all theirs to sink
for i in range(n):
    addEdge(0,i+1,1)
    addEdge(n+1+i,2*n+1,1)

for t in (fireMonsters, grassMonsters, waterMonsters):
    t.sort()
    for i in range(1,len(t))[::-1]:
        addEdge(t[i].index, t[i-1].index, math.inf)

    for m in myMonsters:
        i = bisect_left(t,m)
        if i != 0:
            addEdge(m.index, t[i-1].index, 1)

def bfs(s,t,parent):
    for i in range(len(parent)):
        parent[i] = -1
    parent[s] = -2
    q = deque()
    q.append((s,math.inf))

    while q:
        cur, flow = q.popleft()
        for next in adj[cur]:
            if parent[next] == -1 and capacity[cur][next] > 0:
                parent[next] = cur
                newFlow = min(flow, capacity[cur][next])
                if next == t:
                    return newFlow
                q.append((next,newFlow))
    return 0

def maxFlow(s,t):
    flow = 0
    parent = [0 for _ in range(2*n+2)]

    while (newFlow := bfs(s,t,parent)) > 0:
        flow += newFlow
        cur = t
        while cur != s:
            prev = parent[cur]
            capacity[prev][cur] -= newFlow
            capacity[cur][prev] += newFlow
            cur = prev
    return flow

print(maxFlow(0,2*n+1))

Comments

There are no comments at the moment.