ikshu-and-his-new-year-matrix

Ikshu and his prime matrix

Ikshu is in love with prime numbers. He has a matrix of size N X N and wants atleast 5 prime numbers in that matrix arranged like a cross as shown in figure. Let us call this matrix "new year matrix"
X   X   X   X    X
If matrix is not a "new year matrix" he can alter it with the operation as described below:

1) Choose an element from the matrix.

2)  Increment the value at the element by K assuring that value of
   element does not exceed 10000.

Above operation can be applied any number of times.

Example :

Let matrix be:
2 2 3
4 5 6
7 8 9
and k be 1

He can perform 2 operations on (3,3) to get a cross centered at (2,2) with prime numbers = [2,3,5,7,11]

constraints:
1 ≤ N ≤ 1000
1 ≤ K ≤ 5
1 ≤ any element of matrix ≤10000

Input:
First line on input contains two integer N and K which is the size of the matrix, followed by N X N matrix.
N is the size of the matrix
and K is the value which is allowed to be add to any element of matrix.

Output: 
First line of output contains "yes" if such cross is possible else it contains "no".
If answer is possible, second line contains the minimum number of operations and third line contains the co-ordinate of center of cross(assuming indexing to be 1-based)
If many such answers are possible, print the one with minimum row index, if many answers are possible with same minimum row index print the one with minimum col index

SAMPLE INPUT
3 1
2 2 3
4 5 6
7 8 9

SAMPLE OUTPUT
yes
2 
2 2

Difficulty: MEDIUM
Tags: Fundamentals

Complete search

Dynamic programming

Number theory

Ad-hoc
Skill types: Dynamic programming

Complete search

Starter code:

Solutions:
N = 10001
isPrime = [1] * N
isPrime[0] = 0
isPrime[1] = 0
for i in range(2, N):
	if isPrime[i]:
		for j in range(i + i, N, i):
			isPrime[j] = 0
primes = [i for i in range(2, N) if isPrime[i]]
minOps = [1 << 30] * N
n, K = map(int, input().split())
A = [list(map(int, input().split())) for i in range(n)]
for i in range(N):
	for p in primes:
		if p >= i and (p - i) % K == 0:
			minOps[i] = min(minOps[i], (p - i) // K)
minCount = 1 << 30
for i in range(n - 2):
	for j in range(n - 2):
		count = 0
		for dx, dy in ((0, 0), (1, 1), (2, 2), (2, 0), (0, 2)):
			count += minOps[A[i + dx][j + dy]]
		if count < minCount:
			minCount = count
			pos = (i + 2, j + 2)
if minCount == 1 << 30:
	print('no')
else:
	print('yes')
	print(minCount)
	print(pos[0], pos[1])


import math
def getPrime(Max):
	used = [0] * Max
	for i in range(4, Max, 2):
		used[i] = 1
	used[1] = 1
	for i in range(3, int(math.sqrt(Max) + 1), 2):
		if used[i] == 1:
			continue
		for j in range(i * i, Max, i):
			used[j] = 1
	return used
def main():
	N, K = map(int, input().strip().split())
	A = []
	Max = 0
	for _ in range(N):
		A.append(list(map(int, input().strip().split())))
		temp = max(A[-1])
		Max = max(Max, temp)
	DP = [0] * (Max + 1)
	used = getPrime(10001)
	length = 10001
	for i in range(1, Max + 1):
		if used[i] == 0:
			continue
		if K > 1 and i % K == 0:
			DP[i] = 10 ** 10
			continue
		j = i
		cnt = 0
		while j < length:
			if used[j] == 0:
				DP[i] = cnt
				break
			j += K
			cnt += 1
		if j >= length:
			DP[i] = 10 ** 10
	for i in range(N):
		for j in range(N):
			A[i][j] = DP[A[i][j]]
	MinStep = 10 ** 10
	X = -1
	Y = -1
	for i in range(1, N - 1):
		for j in range(1, N - 1):
			Sum = 0
			if A[i][j] == 10 ** 10:
				continue
			if A[i - 1][j - 1] == 10 ** 10:
				continue
			if A[i - 1][j + 1] == 10 ** 10:
				continue
			if A[i + 1][j - 1] == 10 ** 10:
				continue
			if A[i + 1][j + 1] == 10 ** 10:
				continue
			Sum = A[i][j] + A[i - 1][j - 1] + A[i - 1][j + 1] + A[i + 1][j - 1] + A[i + 1][j + 1]
			if MinStep > Sum:
				MinStep = Sum
				X = i + 1
				Y = j + 1
	if MinStep != 10 ** 10:
		print('yes')
		print(MinStep)
		print(X, Y)
	else:
		print('no')
if __name__ == '__main__':
	main()