[PYTHON] Codeforces Round # 675 (Div. 2) Bacha Review (10/30)

This time's results

Impressions of this time

I couldn't understand the problem statement of problem A well, and I made a silly mistake in the experiment of problem C, and I had a lot of trouble.

I need to switch over here the most, so I will practice repeatedly to improve the accuracy.

Problem A

A non-degenerate $ n $ polygon can be created by connecting the $ n $ points appropriately if they are not on a straight line. Also, since $ \ leftrightarrow $ (not on a straight line) (the longest edge is less than the sum of the other edges), $ d = a + b + c- for the given $ a, b, c $. It should be 1 $.

A.py

for _ in range(int(input())):
    x=list(map(int,input().split()))
    print(sum(x)-1)

Problem B

** It suffices if the palindrome is in the row and column directions **. Therefore, ** up to 4 places ** must have the same number. Also, for the $ (i, j) $ component, when $ n $ is odd and $ i = [\ frac {n} {2}] $, there is no component that needs to be the same number in the column direction, and $ m It is also ** note ** that when $ is odd and $ j = [\ frac {m} {2}] $, there are no components that need to have the same number in the row direction.

Therefore, according to the above rule, ** divide by component that has the same number (✳︎1) **, and then ** (✳︎) which component has the same number so that it is equal to the median. The number of operations can be minimized by operating +1 or -1. Therefore, the total of these should be the answer.

(✳︎1)… To separate the same components, just save the unchecked components in a matrix and scan the components of all the matrices.

(✳︎2)…f(x)=\sum_{i} |a\_i-x|To minimizea\_iTo the median when arranging in ascending orderxIt's time to do. I can prove this, but I will omit the proof because it is famous.

B.py

for _ in range(int(input())):
    n,m=map(int,input().split())
    mat=[list(map(int,input().split())) for i in range(n)]
    check=[[0]*m for i in range(n)]
    segments=[]
    for i in range(n):
        for j in range(m):
            if check[i][j]==0:
                seg_sub=[]
                check[i][j]=1
                seg_sub.append(mat[i][j])
                if n%2==0 or i!=n//2:
                    check[n-1-i][j]=1
                    seg_sub.append(mat[n-1-i][j])
                    if m%2==0 or j!=m//2:
                        check[i][m-1-j]=1
                        check[n-1-i][m-1-j]=1
                        seg_sub.append(mat[i][m-1-j])
                        seg_sub.append(mat[n-1-i][m-1-j])
                else:
                    if m%2==0 or j!=m//2:
                        check[i][m-1-j]=1
                        seg_sub.append(mat[i][m-1-j])
                segments.append(seg_sub)
    ans=0
    for i in segments:
        seg=sorted(i)
        m=len(seg)//2
        for i in seg:
            ans+=abs(i-seg[m])
    print(ans)

C Problem

(Hereafter, when the $ i $ digit is mentioned, it is 0-indexed and the value of that digit is $ s [i] $.)

For such problems ** it is good to consider the contribution of each digit **. When the $ i $ digit is $ 10 ^ k $ in $ i \ geqq k $, the contribution can be calculated from the figure below.

From the above figure, the contribution is $ k \ times 10 ^ k \ times s [i] $. Therefore, for any $ i $ and $ k $:

\sum_{k=0}^{n-2} \sum_{i=k}^{n-1} k \times 10^k \times s[i] \leftrightarrow \sum_{k=0}^{n-2} k \times 10^k \sum_{i=k}^{n-1} s[i]

Therefore, ** the calculation of the inner sum does not depend on $ k , so it can be precalculated **, and the cumulative sum from the opposite side can be considered ( O (n) $). Also, if the pre-calculation is done, the outer sum can be calculated with $ O (n) $, so the total amount of calculation is $ O (n) $.

C.py

mod=10**9+7
s=list(map(int,input()))[::-1]
n=len(s)
if n==1:
    print(0)
    exit()
#10^k-th power
po=[1]
for i in range(n):
    po.append(po[-1]*10%mod)
#S_Cumulative from reverse i
si=[0]*n
si[n-1]=s[n-1]
for i in range(n-2,-1,-1):
    si[i]=si[i+1]+s[i]
ans=0
for k in range(n-1):
    ans+=((k+1)*si[k+1])*po[k]
    #print(ans)
    ans%=mod
for k in range(n-1):
    ans+=s[k]*((n-1-k)*(n-1-k-1)//2+(n-1-k))*po[k]
    #print(ans)
    ans%=mod
#print()
print(ans)

After D problem

I will not solve this time.