Problem:


Score : 400 points

Problem Statement

On a two-dimensional plane, there are N red points and N blue points.
The coordinates of the i-th red point are (a_i, b_i), and the coordinates of the i-th blue point are (c_i, d_i).

A red point and a blue point can form a friendly pair when, the x-coordinate of the red point is smaller than that of the blue point, and the y-coordinate of the red point is also smaller than that of the blue point.

At most how many friendly pairs can you form? Note that a point cannot belong to multiple pairs.

Constraints

All input values are integers.

1 \leq N \leq 100

0 \leq a_i, b_i, c_i, d_i < 2N

a_1, a_2, ..., a_N, c_1, c_2, ..., c_N are all different.

b_1, b_2, ..., b_N, d_1, d_2, ..., d_N are all different.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
a_2 b_2
:
a_N b_N
c_1 d_1
c_2 d_2
:
c_N d_N

Output

Print the maximum number of friendly pairs.

Sample Input 1

3
2 0
3 1
1 3
4 2
0 4
5 5

Sample Output 1

2

For example, you can pair (2, 0) and (4, 2), then (3, 1) and (5, 5).

Sample Input 2

3
0 0
1 1
5 2
2 3
3 4
4 5

Sample Output 2

2

For example, you can pair (0, 0) and (2, 3), then (1, 1) and (3, 4).

Sample Input 3

2
2 2
3 3
0 0
1 1

Sample Output 3

0

It is possible that no pair can be formed.

Sample Input 4

5
0 0
7 3
2 2
4 8
1 6
8 5
6 9
5 4
9 1
3 7

Sample Output 4

5

Sample Input 5

5
0 0
1 1
5 5
6 6
7 7
2 2
3 3
4 4
8 8
9 9

Sample Output 5

4



Sample input:
3
2 0
3 1
1 3
4 2
0 4
5 5


Sample output:
2

Submission status: Runtime Error

Solution code:
def abc091_c():
    from operator import itemgetter
    _reds = []
    _blues = []
    _count = 0

    _n = int(input())

    for i in range(_n):
        _instr = str(input()).split()
        _reds.append(list(map(int, _instr)))

    for i in range(_n):
        _instr = str(input()).split()
        _blues.append(list(map(int, _instr)))

    _reds.sort()
    _blues.sort(key=itemgetter(1))

    for i in range(len(_reds)):
        _num = 0
        _blue2=[]
        while _reds[i][1] < _blues[_num][1]:
            _blue2.append(_blues[_num])
            _num += 1
        _blue2.sort()
        if _reds[i][0] < _blue2[0][0]:
            _count += 1
            _blues.remove(_blue2[0])
        """for j in range(len(_blues)):
            if _reds[i][0] >= _blues[j][0]:
                continue
            elif _reds[i][1] < _blues[j][1]:
                _count += 1
                del _blues[j]
                break
            else:
                continue"""
    print(_count)


abc091_c()

Submission status: Runtime Error

Solution code:
import itertools
n=int(input())
red=[]
blue=[]
for i in range(n):
    red.append(list(map(int,input().split())))
for j in range(n):
    blue.append(list(map(int,input().split())))
perm=list(itertools.permutations(blue))
pair=0
ans=0
for k in perm:
    for m in range(n):
        if n-m+pair+1<=ans:
            next(m)
        if int(red[m][0])<int(k[m][0]) and int(red[m][1])<int(k[m][1]):
            pair+=1
        
    if pair>ans:
        ans=pair
    pair=0
print(ans)

Submission status: Runtime Error

Solution code:
if __name__ == "__main__":
    N = int(input())
    A = []
    B = []
    C = []
    D = []
    for i in range(N):
        buf1, buf2 = list(map(int, (input().split(' '))))
        A.append(buf1)
        B.append(buf2)
    for i in range(N):
        buf1, buf2 = list(map(int, (input().split(' '))))
        C.append(buf1)
        D.append(buf2)

    def calc_dist(a, b, c, d):
        return pow((pow((c - a), 2) + pow((d - b), 2)), 0.5)

    A_dist = {}
    B_dist = {}
    for i in range(N):
        a_key = str(A[i]) + '_' + str(B[i])
        b_key = str(C[i]) + '_' + str(D[i])
        A_dist[a_key] = calc_dist(0, 0, A[i], B[i])
        B_dist[b_key] = calc_dist(0, 0, C[i], D[i])
    A_dist = sorted(A_dist.items(), key=lambda x: x[1], reverse=True)
    B_dist = sorted(B_dist.items(), key=lambda x: x[1], reverse=True)
#    print(A_dist)
#    print(B_dist)
    A = []
    B = []
    C = []
    D = []
    for key,ele in A_dist:
        A.append(key.split('_')[0])
        B.append(key.split('_')[1])
    for key,ele in B_dist:
        C.append(key.split('_')[0])
        D.append(key.split('_')[1])
    ans1 = 0
    for i in range(N):
        for j in range(N):
            if len(A) <= i or len(C) <= j:
                break
            if (A[i] <= C[j]) and (B[i] <= D[j]):
#                print(A[i], B[i], C[j], D[j])
                ans1 += 1
                del C[j], D[j]
                break

    A_dist = sorted(A_dist.items(), key=lambda x: x[1])
    B_dist = sorted(B_dist.items(), key=lambda x: x[1])
#    print(A_dist)
#    print(B_dist)
    A = []
    B = []
    C = []
    D = []
    for key,ele in A_dist:
        A.append(key.split('_')[0])
        B.append(key.split('_')[1])
    for key,ele in B_dist:
        C.append(key.split('_')[0])
        D.append(key.split('_')[1])
    ans2 = 0
    for i in range(N):
        for j in range(N):
            if len(A) <= i or len(C) <= j:
                break
            if (A[i] <= C[j]) and (B[i] <= D[j]):
#                print(A[i], B[i], C[j], D[j])
                ans2 += 1
                del C[j], D[j]
                break
    if ans1 > ans2:
        print(ans1)
    else:
        print(ans2)

Submission status: Runtime Error

Solution code:
def main():
    N = int(input())
    red = []
    for i in range(N):
        x,y = [int(i) for i in input().split()]
        red.append([x,y])
    blue = []
    for i in range(N):
        x,y = [int(i) for i in input().split()]
        blue.append([x,y])
    red.sort(reverse=True)
    blue.sort(reverse=True)
    #print(red)
    #print(blue)
    pair = 0
    for a in range(N):
        flag = False
        for i in range(N):
            for j in range(N):
                if(red[i][0] <= blue[j][0] and red[i][1] <= blue[j][1]):
                    pair = pair + 1
                    flag = True
                    print(f'{red[i]} {blue[j]}')
                    blue[j][0] = -10000000000
                    blue[j][1] = -10000000000
                    break
                
        if flag:
            break
    print(pair)
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    N = int(input())
    red = []
    for i in range(N):
        x,y = [int(i) for i in input().split()]
        red.append([x,y])
    blue = []
    for i in range(N):
        x,y = [int(i) for i in input().split()]
        blue.append([x,y])
    red.sort(reverse=True)
    blue.sort(reverse=True)
    print(red)
    print(blue)
    pair = 0
    for a in range(N):
        flag = False
        for i in range(N):
            for j in range(N):
                if(red[i][0] < blue[j][0] and red[i][1] < blue[j][1]):
                    pair = pair + 1
                    flag = True
                    print(f'{red[i]} {blue[j]}')
                    blue[j][0] = -10000
                    break
                
        if flag:
            break
    print(pair)
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# http://nobuta05.hatenablog.com/entry/2015/11/12/013938

def get_edge(M, u, U=None):

    if U == None:
        for x in M[:]:
            if x[0] == u:
                return x[1]
            elif x[1] == u:
                return x[0]

    else:
        for x in M[:]:
            if x[0] == u and x[1] in U:
                return x[1]
            elif x[1] == u and x[0] in U:
                return x[0]
    return None

def get_nodes(M):
    U = set()
    V = set()
    for x in M:
        U.add(x[0])
        V.add(x[1])
    return (U, V)


def augpath(Si, Ti, M, E):
    (U, V) = get_nodes(M)
    Ti1 = set(x[1] for x in E if x[0] in Si and not x[1] in Ti)
    
    if Ti1 == set():
        return (M, None)

    elif Ti1.difference(V) == set():
        Si1 = set(x[0] for x in M if x[1] in Ti1)
        (M, ui1) = augpath(Si1, Ti.union(Ti1), M, E)

        if ui1 == None:
            return (M, None)

        else:
            v = get_edge(M, ui1)
            M.remove((ui1,v))

            ui = get_edge(E, v, U=Si)
            M.append((ui,v))
            
            return (M, ui)

    else:
        v = Ti1.difference(V).pop()
        u = get_edge(E, v, U=Si)
        M.append((u,v))

        return (M, u)
    

def Hungary(U0, V0, E):
    U_bef = set()
    M = []
    cnt = 0
    length = len(U0)
    
    # CALC
    while True:

        # INIT
        (U, V) = get_nodes(M)
        u = U0[cnt%length]
        cnt = cnt + 1
        S0 = set()
        S0.add(u)
        T0 = set()

        # 終了条件(すべての頂点から始まる増大道を調べて、マッチング数が変わっていなければ、それ以上増えることはない)
        if cnt % length == 0:
            if U.difference(U_bef) == set():
                break
            U_bef = U.copy()

        # 枝刈り(すでにマッチングしている頂点から始まる道は増大道ではない)
        if u in U:
            continue
        
        #CALC
        (M, u) = augpath(S0, T0, M, E)
    
    return M


N = int(input())
AB = [[int(_) for _ in input().split()] for i in range(N)]
CD = [[int(_) for _ in input().split()] for i in range(N)]

E = []

for i in range(N):
    for j in range(N):
        if AB[i][0] < CD[j][0] and AB[i][1] < CD[j][1]:
            E.append((i, j))

M = Hungary(range(N), range(N), E)
print(len(M))

Submission status: Runtime Error

Solution code:
def get_edge(M, u, U=None):

    if U == None:
        for x in M[:]:
            if x[0] == u:
                return x[1]
            elif x[1] == u:
                return x[0]

    else:
        for x in M[:]:
            if x[0] == u and x[1] in U:
                return x[1]
            elif x[1] == u and x[0] in U:
                return x[0]
    return None


def get_nodes(M):
    U = set()
    V = set()
    for x in M:
        U.add(x[0])
        V.add(x[1])
    return (U, V)


def augpath(Si, Ti, M, E):
    (U, V) = get_nodes(M)
    Ti1 = set(x[1] for x in E if x[0] in Si and not x[1] in Ti)
    
    if Ti1 == set():
        return (M, None)

    elif Ti1.difference(V) == set():
        Si1 = set(x[0] for x in M if x[1] in Ti1)
        (M, ui1) = augpath(Si1, Ti.union(Ti1), M, E)

        if ui1 == None:
            return (M, None)

        else:
            v = get_edge(M, ui1)
            M.remove((ui1,v))

            ui = get_edge(E, v, U=Si)
            M.append((ui,v))
            
            return (M, ui)

    else:
        v = Ti1.difference(V).pop()
        u = get_edge(E, v, U=Si)
        M.append((u,v))

        return (M, u)
    

def Hungary(U0, V0, E):
    U_bef = set()
    M = []
    cnt = 0
    length = len(U0)
    
    # CALC
    while True:

        # INIT
        (U, V) = get_nodes(M)
        u = U0[cnt%length]
        cnt = cnt + 1
        S0 = set()
        S0.add(u)
        T0 = set()

        # 終了条件(すべての頂点から始まる増大道を調べて、マッチング数が変わっていなければ、それ以上増えることはない)
        if cnt % length == 0:
            if U.difference(U_bef) == set():
                break
            U_bef = U.copy()

        # 枝刈り(すでにマッチングしている頂点から始まる道は増大道ではない)
        if u in U:
            continue
        
        #CALC
        (M, u) = augpath(S0, T0, M, E)
    
    return M

if __name__ == '__main__':
    # print(explanation)
    E = []

    N = int(input())

    a, b = [], []
    for n in range(N):
        _a, _b = map(int, input().split(' '))
        a.append(_a)
        b.append(_b)

    c, d = [], []
    for n in range(N):
        _c, _d = map(int, input().split(' '))
        c.append(_c)
        d.append(_d)

    U0 = [i for i in range(N)]
    V0 = [i for i in range(N)]

    # 隣接行列
    M = [[0 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if a[i] < c[j] and b[i] < d[j]:
                E.append((i, j))

    # CALC
    edges = Hungary(U0, V0, E)

    # OUTPUT
    print(len(edges))