i-demand-trial-by-combat-13

After Joeffrey chocked to death, Cercei blamed Tyrian for his death. After seeing his love, Shae betrayed him, he demanded trial by combat. Now this combat is not with swords but with logic and problem solving. Tywin will ask Tyrian questions and he have to answer them correctly.
Tywin asks him this question:
There are n lannisters, out of which some are sitting and some are standing.  After one hour, some of them will sit according to this rule:
Only those lannisters will sit who had both their neighbors sitting the previous hour.  For more clarity refer to sample test case. Now, Tywin asks Tyrian to tell who all are standing and who all are sitting after m hours.
Note: For lannisters on corners there is only 1 neighbor.

[Input]
First line contains an integer t denoting no.of test cases.
Second line contains two integers n,m denoting number of lannisters and no.of hours respectively.
Third line contains n space separated integers either 0 or 1 depending on whether lannister is standing or sitting respectively

[Output]
For each test case output n space separated integers according to the ques. For more clarity see sample test case.
[Constraints]
1 ≤ t ≤ 1000
2 ≤ n ≤ 100
0 ≤ m ≤ 10000

SAMPLE INPUT
2
3 4
1 1 1
6 2
1 0 1 1 0 0

SAMPLE OUTPUT
1 1 1 
1 0 0 0 0 0

Explanation

2nd test case: 
In the first hour the sitting and standing order will be : 0 1 0 0 0 0 because 1st and 6th lannister have no neighbour sitting in the previous hour so they will stand. 2nd lannister have both his neighbours sitting in the previous hour so he will sit. 3rd, 4th and 5th lannister have only one of their neighbour sitting, so they will stand.
In the second hour the sitting and standing order will be: 1 0 0 0 0 0 because only 1st lannister have both his neighbour's sitting in the previous hour. 
Note: For 1st and last person assume only one neighbour.

Difficulty: MEDIUM
Tags: Data structures

Ad-hoc
Skill types: Data structures

Starter code:

Solutions:
import sys

t = int(input())
for i in range(t):
	n, m = [int(value) for value in input().rstrip().split()]
	arr = [int(value) for value in input().rstrip().split()]
	seq = 1
	zeros = 0
	ones = 1
	for j in range(n - 1):
		if arr[j] == arr[j + 1] == 0:
			zeros = 1
			seq = 0
			ones=0
			break
		elif seq == 1 and not ((arr[j] == 0 and arr[j + 1] == 1) or (arr[j] == 1 and arr[j + 1] == 0)):
			seq = 0
		elif arr[j] != 1:
			ones = 0
	if ones == 1 and arr[n-1]==1:
		print(' '.join(map(str, arr)))
	elif seq == 1:
		if m % 2 == 0:
			print(' '.join(map(str, arr)))
		else:
			for k in range(n):
				if arr[k] == 0:
					arr[k] = 1
				else:
					arr[k] = 0
			print(' '.join(map(str, arr)))
	elif n<=m and zeros==1:
		for k in range(n):
			arr[k] = 0
		print(' '.join(map(str, arr)))
	else:
		flag=0
		for j in range(m):
			narr = []
			if arr[1] == 1:
				narr.append(1)
			else:
				narr.append(0)
			for k in range(1, n - 1):
				if arr[k - 1] == arr[k + 1] == 1:
					narr.append(1)
				else:
					narr.append(0)
			if arr[n - 2] == 1:
				narr.append(1)
			else:
				narr.append(0)
			arr = narr

			seq = 1
			zeros = 0
			ones = 1
			for q in range(n - 1):
				if arr[q] == arr[q + 1] == 0:
					zeros = 1
					seq = 0
					ones = 0
					break
				elif seq == 1 and not ((arr[q] == 0 and arr[q + 1] == 1) or (arr[q] == 1 and arr[q + 1] == 0)):
					seq = 0
				elif arr[q] != 1:
					ones = 0
			if ones == 1 and arr[n-1]==1:
				print(' '.join(map(str, arr)))
				flag=1
				break
			elif seq == 1:
				if (m-j+1) % 2 == 0:
					print(' '.join(map(str, arr)))
				else:
					for k in range(n):
						if arr[k] == 0:
							arr[k] = 1
						else:
							arr[k] = 0
					print(' '.join(map(str, arr)))
				flag = 1
				break
			elif n <= m-j:
				if zeros == 1:
					for k in range(n):
						arr[k] = 0
					print(' '.join(map(str, arr)))
					flag = 1
					break
		if flag==0:
			print(' '.join(map(str, arr)))


t = eval(input())

for _ in range(0, t):
	n, m = list(map(int, input().split()))
	l = [i_v1[0] for i_v1 in [i_v for i_v in enumerate(map(int, input().split())) if i_v[1] == 1]]	# read in the list of 1's and 0's
												# and convert it into a list of indexes	of 1's
	t = []
	for c in range(0, m):
		for i in range(0, len(l)):
			if l[i] == 1:
				t.append(0)
			elif i>0 and l[i] - l[i-1] == 2:	# e.g. when 0, 2; append 1
				t.append(l[i]-1)
			elif i>1 and l[i] - l[i-2] == 2:	# e.g. when 0, 1, 2; append 1
				t.append(l[i]-1)
			if l[i] == n-2:
				t.append(n-1)

		l = sorted(t)
		t = []
		if len(l) == 0 or len(l) == n:			# all 0's or all 1's will never change
			break

		alt_c = n / 2	# count of 1's (people sitting down) for alternate pattern of "1 0 1 0..." or "0 1 0 1 0..." to be present
				# it could be 1 extra for odd n (handled by the next if condition)
		alt = False
		if 0 <= (len(l) - alt_c) <= 1:
			alt = True
			for i in range(0, len(l)-1):	# check if alternate pattern exists
				if l[i+1] - l[i] != 2:
					alt = False
					break

		if alt:		# if alterenate pattern exists, flip it if necessary and break the loop
			rem = m - (c + 1)		# get count of remaining hours and flip alt pattern if it is odd
			if rem % 2 == 1:
				if l[0] == 0:
					l = [x+1 for x in l]
					if n % 2 == 1: del l[-1]
				else:
					l = [x-1 for x in l]
					if n % 2 == 1: 
						l.append(n-1)
			break

	print(' '.join(['1' if i in l else '0' for i in range(0, n)]))



t = eval(input())

for _ in range(0, t):
	n, m = list(map(int, input().split()))
	l = [i_v1[0] for i_v1 in [i_v for i_v in enumerate(map(int, input().split())) if i_v[1] == 1]]
	#print ' '.join(map(lambda i : '1' if i in l else '0', range(0, n)))

	t = []
	for c in range(0, m):
		for i in range(0, len(l)):
			if l[i] == 1:
				t.append(0)
			elif i>0 and l[i] - l[i-1] == 2:
				t.append(l[i]-1)
			elif i>1 and l[i] - l[i-2] == 2:
				t.append(l[i]-1)
			if l[i] == n-2:
				t.append(n-1)

		l = sorted(t)
		t = []
		#print len(l)
		if len(l) == 0 or len(l) == n:
			break

		alt_c = n / 2
		alt = False
		if 0 <= (len(l) - alt_c) <= 1:
			alt = True
			for i in range(0, len(l)-1):
				if l[i+1] - l[i] != 2:
					alt = False
					break

		if alt:
			#print 'ALT'
			#print ' '.join(map(lambda i : '1' if i in l else '0', range(0, n)))
			rem = m - (c + 1)
			if rem % 2 == 1:
				if l[0] == 0:
					l = [x+1 for x in l]
					if n%2 == 1: del l[-1]
				else:
					l = [x-1 for x in l]
					if n%2 == 1: 
						l.append(n-1)
			break

		'''if sorted(l) == lc:
			print 'cycle'
			break
			import time; time.sleep(3)'''

	#print 'it:', c
	print(' '.join(['1' if i in l else '0' for i in range(0, n)]))



for _ in range(eval(input())):
	N, M = list(map(int, input().split()))
	A = list(map(int, input().split()))

	P, P2 = [], []
	for _ in range(M):
		ans = [A[1]]
		for j in range(1, N - 1):
			if A[j - 1] and A[j + 1]:
				ans.append(1)
			else:
				ans.append(0)

		ans.append(A[N - 2])
		A = ans[:]
		if ans == P:
			break
		elif ans == P2:
			y = M - _+1
			if y % 2 == 0:
				break
			else:
				A = P
				break
		P2 = P
		P = A

	print(' '.join([str(i) for i in A]))