Codeforces Round # 663 (Div. 2) Bacha Review (8/13)
This time's results
Impressions of this time
I didn't understand the C problem after thinking about it for 10 minutes, so when I jumped to the D problem, I kept making bugs in the implementation **. When I solved the C problem after finishing it, I could solve it in less than 10 minutes, so I made a mistake in solving the problem ... Later, when I saw my friend's standings, I was impatient, so I would like to try to eliminate such impatience.
Problem A
It was a gag problem ...
First, $ p $ is from the permutation of $ 1 $ ~ $ n $, and the maximum value contained in $ p \ _i, p \ _ {i + 1},… p \ _ {j-1}, p \ _j $ is at least It will be $ j-i + 1 $. Also, for any non-negative integer $ A, B $, from $ A \ or \ B \ geqq A, B $, $ p \ _i \ or \ p \ _ {i + 1} \ or \… \ or \ p \ _ {j-1} \ or \ p \ _ j \ geqq j-i + 1 $ holds. Therefore, the condition holds for any sequence, so you can output an appropriate permutation.
A.py
for _ in range(int(input())):
n=int(input())
print(" ".join(map(str,range(1,n+1))))
Problem B
I was wondering if I would do it with BFS etc. because it changes the grid, but it was a gag problem following the A problem.
Consider moving only to the right or down and reaching (n, m) from any square. Here, ** patterns that cannot be reached ** are patterns that penetrate downward or to the right. Therefore, to avoid such a pattern, all the cells on the far right are D and all the cells on the bottom are R. Also, if you can change these squares, you can always reach (n, m) even if other squares are the starting points.
From the above, the answer is (the rightmost cell is the number of R) + (the bottommost cell is the number of D).
B.py
for _ in range(int(input())):
n,m=map(int,input().split())
a=[input() for i in range(n)]
ans=0
for i in range(m-1):
ans+=(a[n-1][i]=="D")
for i in range(n-1):
ans+=(a[i][m-1]=="R")
print(ans)
C problem
I had a policy during the contest, but when I threw it out and solved the D problem, I ran out of time. ** I will try to solve the problem that seems to be solved **.
First, it is assumed that two undirected sides of the subject can be drawn for a certain $ i $ ($ (i, j_1), (i, j_2) $) **, and so on.
From the above figure, (the number of parts ①), (the number of parts ②), $ i <j \ _1, j \ _2 $ are established. Also, since either $ j \ _1 <j \ _2, j_2 <j_1 $ holds, you can also draw an undirected edge with $ (j_1, j_2) $, and $ i, j \ _1, j \ _2 $ You can cycle between.
Therefore, let us consider a sequence (** complementary event **) that does not have a cycle. Here, since the above result holds for any $ i $, there is no cycle in the sequence ** where there is no minimum $ i $. Such sequences are not only monotonous sequences such as $ 1,2,3,4 $, but also sequences such as $ 1,4,3,2 $ that have only one maximum value. Also, when there is a maximum value, the number is $ N $. Furthermore, if the maximum value comes to the $ i $ th position, it will be as shown in the figure below.
Here, the order of the numbers that come to the $ 1 $ ~ $ i-1 $, $ i + 1 $ ~ $ N $ th is uniquely determined by selecting each number, so the maximum value $ N $ is the $ i $ th. The number is arranged according to $ \ _ {N-1} C \ _ {i-1} $ when it comes. Also, if you find the sum of $ i = 1 $ ~ $ N $, then $ \ _ {N-1} C \ _ {i-1}, \ _ {N-1} C \ _ {i-1}, …, \ _ {N-1} C \ _ {i-1} = 2 ^ {N-1} $.
From the above, the sequence without cycles is $ 2 ^ {N-1} $, and the total number of permutations is $ N! $, So $ N! -2 ^ {N-1} $ is the answer.
C.py
n=int(input())
def modpow():
ret=1
for i in range(n-1):
ret*=2
ret%=(10**9+7)
return ret
def perm():
ret=1
for i in range(n):
ret*=(i+1)
ret%=(10**9+7)
return ret
print((perm()-modpow())%(10**9+7))
D problem
The problem is to find the minimum number of times to change the number so that all the numbers of 1s in a square submatrix of any even length are odd.
Here, if you combine four square matrices with a length of 2, you can create a square matrix with a length of 4, but when the number of 1s in a square matrix with a length of 2 is odd, the length is The number of 1s in a square matrix with a 4 is even. Therefore, when it is $ n, m \ geqq 4 $, it is necessary to output -1. In the following, consider the case of $ n <4 $ or $ m <4 $. Also note that it is $ n \ leqq m $ (I didn't notice it during the contest).
(1) When $ n = 1 $
Since there is no even-length square submatrix, there is no need to change it, just output 0.
(2) When $ n = 2,3 $
There is always a minimum number of times in these cases (proof is omitted). At first, I thought I would use the greedy algorithm to decide the columns in order **, but I gave up the greedy algorithm because the case classification was complicated and the ** greedy algorithm could not be justified **. I did.
Here, ** DP **, considering that ** columns are decided in order ** and that each column is only $ 2 ^ n $ from $ n = 2,3 $ ** I think you can come up with the idea. DP can be defined as follows:
$ dp [i] [j]: = $ (Minimum number of changes when the $ i $ column is fixed and the $ i $ column becomes $ j $ when viewed as a binary number)
Here, consider the transition of DP from $ dp [i-1] [j] $ to $ dp [i] [k] $. Since $ 1 \ leqq j, k \ leqq 2 ^ n $, the transition is represented by a double loop (** there are multiple states! **). Also, when $ j and k $ are determined, it is calculated in advance whether the number of 1s contained in the square matrix whose length is 2 in the $ i-1 $ column and the $ i $ column are all odd numbers. Can be done (bitcheck [j] [k]). In addition, the number of trials required to change from $ a [i] $ to $ k $ can be pre-calculated (bitcalc [a [i]] [k] as a binary number). Based on this, the transition of DP is as follows.
When $ bitcheck [j] [k] = True $, $ dp [i] [k] = dp [i-1] [j] + bitcalc [a [i] $ bit notation $] [k] $
Also, TL is pretty strict and ** a lot of input **, so you need to use ʻinput = sys.stdin.readline` to speed up the input (maybe not if the implementation is good). Hmm.).
D.py
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
a=[[int(j) for j in input()[:-1]] for i in range(n)]
if n>=4 and m>=4:
print(-1)
exit()
if n==1 or m==1:
print(0)
exit()
inf=10000000000000
if n==2 or m==2:
bitcheck=[[0]*4 for i in range(4)]
for j in range(4):
for k in range(4):
for i in range(1):
if (((j>>i)&1)+((k>>i)&1)+((j>>(i+1))&1)+((k>>(i+1))&1))%2==0:
bitcheck[j][k]=False
break
else:
bitcheck[j][k]=True
bitcalc=[[0]*4 for i in range(4)]
for j in range(4):
for k in range(4):
for i in range(2):
if ((j>>i)&1)^((k>>i)&1):
bitcalc[j][k]+=1
if n==2:
n,m=m,n
b=[list(x) for x in zip(*a)]
else:
b=[i for i in a]
dp=[[inf]*4 for i in range(n)]
for i in range(n):
if i!=0:
for j in range(4):
for k in range(4):
if bitcheck[j][k]:
dp[i][k]=min(dp[i][k],dp[i-1][j]+bitcalc[b[i][0]+b[i][1]*2][k])
else:
for k in range(4):
dp[i][k]=bitcalc[b[i][0]+b[i][1]*2][k]
print(min(dp[n-1]))
exit()
if n==3 or m==3:
bitcheck=[[0]*8 for i in range(8)]
for j in range(8):
for k in range(8):
for i in range(2):
if (((j>>i)&1)+((k>>i)&1)+((j>>(i+1))&1)+((k>>(i+1))&1))%2==0:
bitcheck[j][k]=False
break
else:
bitcheck[j][k]=True
bitcalc=[[0]*8 for i in range(8)]
for j in range(8):
for k in range(8):
for i in range(3):
if ((j>>i)&1)^((k>>i)&1):
bitcalc[j][k]+=1
if n==3:
n,m=m,n
b=[list(x) for x in zip(*a)]
else:
b=[i for i in a]
dp=[[inf]*8 for i in range(n)]
for i in range(n):
if i!=0:
for j in range(8):
for k in range(8):
if bitcheck[j][k]:
dp[i][k]=min(dp[i][k],dp[i-1][j]+bitcalc[b[i][0]+b[i][1]*2+b[i][2]*4][k])
else:
for k in range(8):
dp[i][k]=bitcalc[b[i][0]+b[i][1]*2+b[i][2]*4][k]
print(min(dp[n-1]))
exit()
After the E problem
I will skip this time
Recommended Posts