Problem:


Score : 1200 points

Problem Statement

There are N arrays.
The length of each array is M and initially each array contains integers (1，2，...，M) in this order.

Mr. Takahashi has decided to perform Q operations on those N arrays.
For the i-th (1≤i≤Q) time, he performs the following operation.

Choose an arbitrary array from the N arrays and move the integer a_i (1≤a_i≤M) to the front of that array. For example, after performing the operation on a_i=2 and the array (5，4，3，2，1), this array becomes (2，5，4，3，1).

Mr. Takahashi wants to make N arrays exactly the same after performing the Q operations.
Determine if it is possible or not.

Constraints

2≤N≤10^5

2≤M≤10^5

1≤Q≤10^5

1≤a_i≤M

Input

The input is given from Standard Input in the following format:

N M
Q
a_1 a_2 ... a_Q

Output

Print Yes if it is possible to make N arrays exactly the same after performing the Q operations.
Otherwise, print No.

Sample Input 1

2 2
3
2 1 2

Sample Output 1

Yes

You can perform the operations as follows.

Sample Input 2

3 2
3
2 1 2

Sample Output 2

No

Sample Input 3

2 3
3
3 2 1

Sample Output 3

Yes

You can perform the operations as follows.

Sample Input 4

3 3
6
1 2 2 3 3 3

Sample Output 4

No



Sample input:
2 2
3
2 1 2


Sample output:
Yes

Submission status: Runtime Error

Solution code:
import sys
from itertools import product
readline = sys.stdin.readline

def check1(A):
    K = max(A)
    table = [-1]*(K+1)
    for i in range(Q):
        table[A[i]] = i
    
    if -1 in table:
        return False
    if any(t1-t2 < 0 for t1, t2 in zip(table, table[1:])):
        return False
    return True

INF = 10**9+7
def check2(A):
    stack = []
    used = set()
    for a in A[::-1] + list(range(M)):
        if a not in used:
            used.add(a)
            stack.append(a)
    
    C = dict()
    for i in range(M):
        C[stack[i]] = i
    
    table = [0]*N + [INF]
    for a in A[::-1]:
        if table[C[a]] < table[C[a]-1]:
            table[C[a]] += 1
    
    zero = stack.index(0)
    if all(t2 > t1 for t1, t2 in zip(stack[zero:], stack[zero+1:])):
        for a in stack[zero:]:
            table[C[a]] = N
    

    return  all(t >= N or t == 0 for t in table)

N, M = map(int, readline().split())
Q = int(readline())
A = list(map(lambda x: int(x)-1, readline().split()))

ans = 'Yes'
if not check1(A):
    A = [0]*N + A
    if not check2(A):
        ans = 'No'
print(ans)

Submission status: Runtime Error

Solution code:
def reads(offset = 0):
	return [int(i) - offset for i in input().split(' ')]
def Judge(vector):
	length = len(vector)-1
	for i in range(length):
		if(vector[i] > vector[i+1]):		
			return 0
	return 1
(N, M) = reads()
Q = int(input())
A = reads(1)
pos = [-1] * M
pat = []
freq = [0] * (M+1)
freq[0] = N
found = set()
for i in A[::-1]:
	if (i not in found):
		pat.append(i)
		found.add(i)
		pos[i] = counter
for i in range(M):
	if (pos[i] == -1):
		pat.append(i)		
for i in A[::-1]:
	temp = pos[i]
	if (freq[temp] > 0):
		freq[temp] -= 1
		freq[temp+1] += 1
for i in range(M+1):
	if (freq[i] != 0):
		start = i
		break
print("Yes") if Judge(pat[start:]) else print("No")

Submission status: Runtime Error

Solution code:
from collections import defaultdict
def ReadInput():
	return [int(a) for a in input().split(' ')]
(N, M) = ReadInput()
Q = int(input())
Array = ReadInput()
def ifEqual(x):
	temp = None
	for i in x:
		if (temp == None):	
			temp = x[i]
			continue
		elif (x[i] != temp):
			print('ifEqual is 0')
			return 0
	return temp
def check(Array, N, M, *args):
	Count = defaultdict(int)
	Array.reverse()
	if ("reverse") not in args:
		for i in Array:
			if (i == 1 or Count[i] < Count[i-1]):
				Count[i] += 1
			else:	
				return 0
		Count.pop(N)
		if(ifEqual(Count)):
			return 1
		else:
			return 0
	else:
		for i in Array:
			if (i == N or Count[i] < Count[i+1]):
				Count[i] += 1
			else:
				return 0
		Count.pop(1)
		if(ifEqual(Count) >= M):
			return 1
		else
			return 0
if (check(Array, N, M) or check(Array, N, M, "reverse")):
	print("Yes")
else:
	print("No")

Submission status: Runtime Error

Solution code:
from sys import stdin
from itertools import repeat
def main():
    n, m = map(int, stdin.readline().split())
    q = int(stdin.readline())
    a = map(int, stdin.readline().split(), repeat(10, q))
    a = [x - 1 for x in a]
    l = [[] for i in xrange(q)]
    la = []
    for i in xrange(q - 1, -1, -1):
        x = a[i]
        if not l[x]:
            la.append(x)
        l[x].append(i)
    ok = 1
    b = [q] * n
    f = [0] * m
    xt = 0
    for i, x in enumerate(la):
        j = 0
        for y in l[x]:
            if j < n and y < b[j]:
                b[j] = y
                j += 1
        if j < n:
            ok = 0
            b[j] = -1
        if not ok:
            while f[xt]:
                  xt += 1
            if x != xt:
                print "No"
                return
            f[xt] = 1
        else:
            f[x] = 1
    print "Yes"
main()