Problem:


Score : 1600 points

Problem Statement

Snuke has permutations (P_0,P_1,\cdots,P_{N-1}) and (Q_0,Q_1,\cdots,Q_{N-1}) of (0,1,\cdots,N-1).

Now, he will make new permutations A and B of (0,1,\cdots,N-1), under the following conditions:

For each i (0 \leq i \leq N-1), A_i should be i or P_i.

For each i (0 \leq i \leq N-1), B_i should be i or Q_i.

Let us define the distance of permutations A and B as the number of indices i such that A_i \neq B_i.
Find the maximum possible distance of A and B.

Constraints

1 \leq N \leq 100000

0 \leq P_i \leq N-1

P_0,P_1,\cdots,P_{N-1} are all different.

0 \leq Q_i \leq N-1

Q_0,Q_1,\cdots,Q_{N-1} are all different.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
P_0 P_1 \cdots P_{N-1}
Q_0 Q_1 \cdots Q_{N-1}

Output

Print the maximum possible distance of A and B.

Sample Input 1

4
2 1 3 0
0 2 3 1

Sample Output 1

3

For example, if we make A=(0,1,2,3) and B=(0,2,3,1), the distance will be 3, which is the maximum result possible.

Sample Input 2

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

Sample Output 2

8

Sample Input 3

32
22 31 30 29 7 17 16 3 14 9 19 11 2 5 10 1 25 18 15 24 20 0 12 21 27 4 26 28 8 6 23 13
22 3 2 7 17 9 16 4 14 8 19 26 28 5 10 1 25 18 15 13 11 0 12 23 21 20 29 24 27 6 30 31

Sample Output 3

28



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


Sample output:
3

Submission status: Wrong Answer

Solution code:
import networkx as nx
from networkx.algorithms.flow import dinitz
import sys
def input():
	return sys.stdin.readline()[:-1]

G = nx.Graph()

n = int(input())
p = list(map(int, input().split()))
q = list(map(int, input().split()))

G.add_nodes_from(list(range(2*n+2)))
S, T = 2*n, 2*n+1
INF = 10**6

for i in range(2*n):
	if i < n:
		if p[i] != i:
			G.add_edge(p[i], i, capacity=INF)
			if p[i] == q[i]:
				G.add_edge(i+n, i, capacity=1)
		else:
			G.add_edge(S, i, capacity=INF)
		G.add_edge(i, i+n, capacity=1)
			
	else:
		if q[i-n] != i-n:
			G.add_edge(i, q[i-n]+n, capacity=INF)
		else:
			G.add_edge(i, T, capacity=INF)

R = dinitz(G, S, T)
cut = int(R.graph['flow_value'])
#print(cut)
ans = n - cut
print(ans)

Submission status: Wrong Answer

Solution code:

from collections import deque

# 枝を表すクラス
# altは逆の枝を表す
class Edge:

    def __init__(self, from_v, to_v, cap):
        self.from_v = from_v
        self.to_v = to_v
        self.cap = cap
        self.alt = None
        
# 頂点を表すクラス
class Vertex:

    def __init__(self, id):
        self.id = id
        self.edge_list = []
        
# グラフを表すクラス
class Graph:

    # 初期化する
    # vnumは頂点数を表す
    # s_vは始点、t_vは終点を表す
    def __init__(self, vnum):
        self.__vertex_list = [Vertex(i) for i in range(vnum + 2)]
        self.__edge_list = []
        
    # 枝を追加する
    def add_edge(self, from_id, to_id, cap):
        from_v = self.vertex(from_id)
        to_v = self.vertex(to_id)
        normal_edge = Edge(from_v,to_v, cap)
        reverse_edge = Edge(to_v, from_v, 0)
        normal_edge.alt = reverse_edge
        reverse_edge.alt = normal_edge
        
        from_v.edge_list.append(normal_edge)
        to_v.edge_list.append(reverse_edge)
        self.__edge_list.append(normal_edge)
        self.__edge_list.append(reverse_edge)
        
    def vertex(self, id):
        return self.__vertex_list[id]

    # 辺の状況をprintする
    def print_edge(self):
        for i in range(len(self.__edge_list)):
            print("[f_v={}, ".format(self.__edge_list[i].from_v.id),end = "")
            print("t_v={}, ".format(self.__edge_list[i].to_v.id),end = "")
            print("cap={}]".format(self.__edge_list[i].cap))

        
        
#        print(self.__edge_list.from_v)
#        print(self.__edge_list.to_v)
#        print(self.__edge_list.cap)
#        print(self.__edge_list.alt)


class MaxFlow:

    # 
    def __init__(self, graph, s_id, t_id):
        self.graph = graph
        self.s_v = graph.vertex(s_id)
        self.t_v = graph.vertex(t_id)
        self.dq = deque()
        self.from_dict = dict()

    def calc(self):
        f = 0
        while self.find_path():
              f += 1
              
              # デバッグ用
              self.graph.print_edge()
              print("f = {}".format(f))
#              self.from_dict.clear()
#              self.from_dict = dict()
              
        return(f)

    # sからtへのパスを一つ見つけ、そのパス上の枝の容量を0にし、
    # 逆の枝の容量を1にする
    # 経路が見つかればTrue,見つからなければFalseを返す
    def find_path(self):
        # -1はfrom_idとして不正な値
        self.put_q(self.s_v, None)
        s_id = self.s_v.id
        t_id = self.t_v.id
        
        while len(self.dq) > 0:
            v = self.dq.popleft()
            v_id = v.id

#            print(self.from_dict)
            
            if v_id == t_id:
                # from_dictを使ってs_vまでの経路をたどる
                while v_id != s_id:
                    n_e = self.from_dict[v_id]
                    r_e = n_e.alt
                    n_e.cap = 0
                    r_e.cap = 1
                    v_id = n_e.from_v.id
                return True
            
        
            # vに接続した枝eのうち、以下の条件を満たしたものを探す
            # * eの容量が1である
            # * e.toがfrom_dictに含まれていない
            for e in v.edge_list:
                if e.cap == 0:
                    continue
                if e.to_v in self.from_dict:
                    continue
                self.put_q(e.to_v, e)

        return False
    
            
    # vをqに積む、from_dictにvに至る枝eを記録する
    def put_q(self, v, e):
        self.dq.append(v)
        self.from_dict[v.id] = e

if __name__ == "__main__":
    

    def make_graph1():
        g1 = Graph(2)
        s1 = 0
        t1 = 1
        g1.add_edge(s1, t1, 1)
        return g1, s1, t1
    g1, s1, t1 = make_graph1()
    mf1 = MaxFlow(g1, s1, t1)
    f1 = mf1.calc()
    print("f1 ={}".format(f1))

    def make_graph2():
        g = Graph(4)
        s = 0
        a = 1
        b = 2
        t = 3
        g.add_edge(s, a, 1)
        g.add_edge(s, b, 1)
        g.add_edge(a, b, 1)
        g.add_edge(a, t, 1)
        g.add_edge(b, t, 1)

        return g, s ,t

    g2, s2, t2 = make_graph2()
    mf2 = MaxFlow(g2, s2, t2)
    print("f2 = {}".format(mf2.calc()))

Submission status: Wrong Answer

Solution code:
n = int(input())
list_a = input().split(' ')
list_b = input().split(' ')

tmp_a = 0
tmp_b = 0
tmp_c = 0

for i in range(0, n):
  
    if list_a[i] != str(i):
        tmp_a += 1

    if list_b[i] != str(i):
        tmp_b += 1

    if list_a[i] != list_b[i]:
        tmp_c += 1

max = tmp_a

if max < tmp_b:
    max = tmp_b

if max < tmp_c:
    max = tmp_c

print(max)

Submission status: Wrong Answer

Solution code:
import numpy as np
import copy

N = int(input())
P = list(map(int,input().split()))
Q = list(map(int,input().split()))
PR = copy.deepcopy(P)
QR = copy.deepcopy(Q)
PR.sort()
QR.sort()


answer = [0,0,0]
for i in range(N):
  if P[i] != Q[i]:
    answer[0] += 1
  if PR[i] != Q[i]:
    answer[1] += 1
  if P[i] != QR[i]:
    answer[2] += 1

print(max(answer))

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
a = np.array(list(map(int,input().split())))
b = np.array(list(map(int,input().split())))

c = (a - b)
d = [s for s in c if s != 0]
print(len(d))

Submission status: Wrong Answer

Solution code:
N = int(input())
Pn = list(map(int, input().split(" ")))
Qn = list(map(int, input().split(" ")))

#print(Pn)
#print(Qn)

GenPn = [x for x in range(N)]
#print(GenPn)

def distance(Pn, Qn):
    d = 0
    for i in range(len(Pn)):
        if Pn[i] != Qn[i]:
            d = d + 1
    return d

answer = distance(Pn, Qn)
answer = max(answer, distance(Pn, GenPn))
answer = max(answer, distance(GenPn, Qn))

print(answer)

Submission status: Wrong Answer

Solution code:
def mapcount(n):
    if n != 0:
        return 1
    else:
        return 0

import numpy as np
N = int(input())
P = list(map(int,input().split()))
Q = list(map(int,input().split()))
V = [i for i in range(N)]

npP = np.array(P)
npQ = np.array(Q)
npV = np.array(V)


countPQ = sum(map(mapcount,npP-npQ))
countQV = sum(map(mapcount,npQ-npV))
countVP = sum(map(mapcount,npV-npP))

print(max([countPQ,countQV,countVP]))

Submission status: Runtime Error

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]
from collections import deque
class Dinic:
	def __init__(self, n):
		self.n = n
		self.g = [[] for i in range(n)]

	def add_edge(self, fr, to, cap):
		#[to, cap, rev]
		forward = [to, cap, None]
		forward[2] = backward = [fr, 0, forward]
		self.g[fr].append(forward)
		self.g[to].append(backward)

	def add_bidirectional_edge(self, v1, v2, cap1, cap2):
		edge1 = [v2, cap1, None]
		edge1[2] = edge2 = [v1, cap2, edge1]
		self.g[v1].append(edge1)
		self.g[v2].append(edge2)

	def bfs(self, s, t):
		self.level = level = [None]*self.n
		deq = deque([s])
		level[s] = 0
		g = self.g
		while deq:
			v = deq.popleft()
			lv = level[v] + 1
			for w, cap, _ in g[v]:
				if cap and level[w] is None:
					level[w] = lv
					deq.append(w)
		return level[t] is not None

	def dfs(self, v, t, f):
		if v == t:
			return f
		level = self.level
		for e in self.it[v]:
			w, cap, rev = e
			if cap and level[v] < level[w]:
				d = self.dfs(w, t, min(f, cap))
				if d:
					e[1] -= d
					rev[1] += d
					return d
		return 0

	def flow(self, s, t):
		flow = 0
		INF = 10**30
		g = self.g
		while self.bfs(s, t):
			#*self.it, = map(iter, self.g)
			self.it = list(map(iter, self.g))
			f = INF
			while f:
				f = self.dfs(s, t, INF)
				flow += f
		return flow

n = int(input())
p = list(map(int, input().split()))
q = list(map(int, input().split()))

G = Dinic(2*n+2)
S, T = 2*n, 2*n+1
INF = 10**6

for i in range(2*n):
	if i < n:
		if p[i] != i:
			G.add_edge(p[i], i, INF)
			if p[i] == q[i]:
				G.add_edge(i+n, i, 1)
		else:
			G.add_edge(S, i, INF)
		G.add_edge(i, i+n, 1)
			
	else:
		if q[i-n] != i-n:
			G.add_edge(i, q[i-n]+n, INF)
		else:
			G.add_edge(i, T, INF)
print(n - G.flow(S, T))

Submission status: Runtime Error

Solution code:
import networkx as nx
from networkx.algorithms.flow import dinitz
import sys
def input():
	return sys.stdin.readline()[:-1]

G = nx.Graph()

n = int(input())
p = list(map(int, input().split()))
q = list(map(int, input().split()))

#G.add_nodes_from(list(range(2*n+2)))
S, T = 2*n, 2*n+1
INF = 10**6

for i in range(2*n):
	if i < n:
		if p[i] != i:
			G.add_edge(p[i], i, capacity=INF)
			if p[i] == q[i]:
				G.add_edge(i+n, i, capacity=1)
		else:
			G.add_edge(S, i, capacity=INF)
		G.add_edge(i, i+n, capacity=1)
			
	else:
		if q[i-n] != i-n:
			G.add_edge(i, q[i-n]+n, capacity=INF)
		else:
			G.add_edge(i, T, capacity=INF)

R = dinitz(G, S, T)
cut = int(R.graph['flow_value'])
#print(cut)
ans = n - cut
print(ans)

Submission status: Runtime Error

Solution code:

from collections import deque

# 枝を表すクラス
# altは逆の枝を表す
class Edge:

    def __init__(self, from_v, to_v, cap):
        self.from_v = from_v
        self.to_v = to_v
        self.cap = cap
        self.alt = None
        
# 頂点を表すクラス
class Vertex:

    def __init__(self, id):
        self.id = id
        self.edge_list = []
        
# グラフを表すクラス
class Graph:

    # 初期化する
    # vnumは頂点数を表す
    # s_vは始点、t_vは終点を表す
    def __init__(self, vnum):
        self.__vertex_list = [Vertex(i) for i in range(vnum + 2)]
        self.__edge_list = []
        
    # 枝を追加する
    def add_edge(self, from_id, to_id, cap):
        from_v = self.vertex(from_id)
        to_v = self.vertex(to_id)
        normal_edge = Edge(from_v,to_v, cap)
        reverse_edge = Edge(to_v, from_v, 0)
        normal_edge.alt = reverse_edge
        reverse_edge.alt = normal_edge
        
        from_v.edge_list.append(normal_edge)
        to_v.edge_list.append(reverse_edge)
        self.__edge_list.append(normal_edge)
        self.__edge_list.append(reverse_edge)
        
    def vertex(self, id):
        return self.__vertex_list[id]

    # 辺の状況をprintする
    def print_edge(self):
        for i in range(len(self.__edge_list)):
            print("[f_v={}, ".format(self.__edge_list[i].from_v.id),end = "")
            print("t_v={}, ".format(self.__edge_list[i].to_v.id),end = "")
            print("cap={}]".format(self.__edge_list[i].cap))

        
        
#        print(self.__edge_list.from_v)
#        print(self.__edge_list.to_v)
#        print(self.__edge_list.cap)
#        print(self.__edge_list.alt)


class MaxFlow:

    # 
    def __init__(self, graph, s_id, t_id):
        self.graph = graph
        self.s_v = graph.vertex(s_id)
        self.t_v = graph.vertex(t_id)
        self.dq = deque()
        self.from_dict = dict()

    def calc(self):
        f = 0

        while self.find_path():
              f += 1
              
              # デバッグ用
              self.graph.print_edge()
              print("f = {}".format(f))
              self.from_dict.clear()
              
        return(f)

    # sからtへのパスを一つ見つけ、そのパス上の枝の容量を0にし、
    # 逆の枝の容量を1にする
    # 経路が見つかればTrue,見つからなければFalseを返す
    def find_path(self):
        # -1はfrom_idとして不正な値
        self.put_q(self.s_v, None)
        s_id = self.s_v.id
        t_id = self.t_v.id
        
        while len(self.dq) > 0:
            v = self.dq.popleft()
            v_id = v.id
            
            if v_id == t_id:
                # from_dictを使ってs_vまでの経路をたどる
                while v_id != s_id:
                    n_e = self.from_dict[v_id]
                    r_e = n_e.alt
                    n_e.cap = 0
                    r_e.cap = 1
                    v_id = n_e.from_v.id
                return True
            
        
            # vに接続した枝eのうち、以下の条件を満たしたものを探す
            # * eの容量が1である
            # * e.toがfrom_dictに含まれていない
            for e in v.edge_list:
                if e.cap == 0:
                    continue
                if e.to_v in self.from_dict:
                    continue
                self.put_q(e.to_v, e)

        return False
    
            
    # vをqに積む、from_dictにvに至る枝eを記録する
    def put_q(self, v, e):
        self.dq.append(v)
        self.from_dict[v.id] = e

if __name__ == "__main__":
    

    def make_graph1():
        g1 = Graph(2)
        s1 = 0
        t1 = 1
        g1.add_edge(s1, t1, 1)
        return g1, s1, t1
    g1, s1, t1 = make_graph1()
    mf1 = MaxFlow(g1, s1, t1)
    f1 = mf1.calc()
    print("f1 ={}".format(f1))

    def make_graph2():
        g = Graph(4)
        s = 0
        a = 1
        b = 2
        t = 3
        g.add_edge(s, a, 1)
        g.add_edge(s, b, 1)
        g.add_edge(a, b, 1)
        g.add_edge(a, t, 1)
        g.add_edge(b, t, 1)

        return g, s ,t

    g2, s2, t2 = make_graph2()
    mf2 = MaxFlow(g2, s2, t2)
    print("f2 = {}".format(mf2.calc()))

Submission status: Runtime Error

Solution code:

from collections import deque

# 枝を表すクラス
# altは逆の枝を表す
class Edge:

    def __init__(self, from_v, to_v, cap):
        self.from_v = from_v
        self.to_v = to_v
        self.cap = cap
        self.alt = None
        
# 頂点を表すクラス
class Vertex:

    def __init__(self, id):
        self.id = id
        self.edge_list = []

# グラフを表すクラス
class Graph:

    # 初期化する
    # vnumは頂点数を表す
    # s_vは始点、t_vは終点を表す
    def __init__(self, vnum):
        self.vertex_list = [Vertex(i) for i in range(vnum)]
        self.s_v = Vertex(vnum)
        self.t_v = Vertex(vnum + 1)

    # 枝を追加する
    def add_edge(self, from_id, to_id, cap):
        from_v = self.vertex_list[from_id]
        to_v = self.vertex_list[to_id]
        normal_edge = Edge(from_v,to_v, cap)
        reverse_edge = Edge(to_v, from_v, 0)
        normal_edge.alt = reverse_edge
        reverse_edge.alt = normal_edge
        
        from_v.edge_list.append(normal_edge)
        to_v.edge_list.append(reverse_edge)

    def add_edge_from_s(self, to_id, cap):
        self.add_edge(self.s_v.id, to_id, cap)

    def add_edge_to_t(self, from_id, cap):
        self.add_edge(from_id, self.t_v.id, cap)
        
class MaxFlow:

    def __init__(self, graph):
        self.graph = graph
        self.dq = deque()
        self.from_dict = dict()

    def calc(self):
        f = 0

        while self.find_path():
            f += 1
            
        return(f)

    # sからtへのパスを一つ見つけ、そのパス上の枝の容量を0にし、
    # 逆の枝の容量を1にする
    # 経路が見つかればTrue,見つからなければFalseを返す
    def find_path(self):
        # -1はfrom_idとして不正な値
        self.put_q(self.graph.s_v, None)
        s_id = self.graph.s_v.id
        t_id = self.graph.t_v.id
        
        while len(self.dq) > 0:
            v = self.dq.popleft()
            v_id = v.id
            
            if v_id == t_id:
                # from_dictを使ってs_vまでの経路をたどる
                while v_id != s_id:
                    n_e = from_dict[v_id]
                    r_e = n_e.alt
                    n_e.cap = 0
                    r_e.cap = 1
                    v_id = n_e.from_v.id
                return True
            
        
            # vに接続した枝eのうち、以下の条件を満たしたものを探す
            # * eの容量が1である
            # * e.toがfrom_dictに含まれていない
            for e in v.edge_list:
                if e.cap == 0:
                    continue
                if e.to in self.from_dict:
                    continue
                self.put_q(e.to, e)

        return False
    
            
    # vをqに積む、from_dictにvに至る枝eを記録する
    def put_q(self, v, e):
        self.dq.append(v)
        self.from_dict[v.id] = e



graph = [[0,1],[0,4],[1,2],[1,4],[2,3],[4,3],[3,5]]
g = Graph(6)

for i in range(len(graph)):
    g.add_edge(graph[i][0],graph[i][1],1)

    
g.add_edge_from_s(0,1)

g.add_edge_to_t(5,1)

MaxFlow(graph).calc()