[PYTHON] Codeforces Round # 618 (Div. 2) Bacha Review (9/26)

This time's results

Impressions of this time

(Since I wrote it on 10/4, my memory is a little vague.)

This time it went well without WA. However, I spent too much time on the appearance and readability of the D problem. The other day, ARC also felt overwhelmed by the problem, so I want to get used to the high-difficulty problem and gain confidence so that I can think accurately and unrivaled regardless of the score.

Problem A

Make sure neither the sum nor the product is zero. First, ** the product is easier to think about **, and add +1 to any 0 element included to prevent 0 from being included. Under this, if the total is 0, you can add +1 to an appropriate element (other than -1), and you can find the number of +1 so far.

A.py

for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    ans=0
    for i in range(n):
        if a[i]==0:
            a[i]=1
            ans+=1
    if sum(a)!=0:
        print(ans)
    else:
        print(ans+1)

Problem B

Find the value when the difference between the medians when divided into two odd sequences is minimized. I couldn't come up with a solution right away, but I thought it would be a gag because there were quite a few people passing by. So, I took the difference between the two values in the middle, counting from the smallest, and tried the sample, and it matched, so I submitted it.

I would like to submit it with a certain degree of certainty, but I was impatient and submitted this issue without proof. I won't prove it because I'm not motivated, but I just need to show that one median is below the $ n $ th element and the other median is below the $ n + 1 $ th element. For example, if you make the assumption that the median values are all $ n $ or less, you can show it by reductio ad absurdum **.

B.py

for _ in range(int(input())):
    n=int(input())
    a=sorted(list(map(int,input().split())))
    print(a[n]-a[n-1])

C problem

First, I experimented and thought about it. Also, since it is bitwise or, ** consider bitwise operations **. Now, considering what happens to the calculation of $ f (x, y) = (x | y) -y $ for each bit, it is as follows.

Therefore, the condition that the binary operation $ f (x, y) $ is performed in order from the front and the $ i $ bit is finally conspicuous is ** the bit of the first element is 1 and only 0 is output after that. If it does not come **. First, consider the condition ** that there is only one ** $ i $ bit with 1 as a ** requirement **. By processing this condition, it is possible to prepare a mask bit in which the $ i $ bit stands out when there is only one number in which the $ i $ bit is 1. Then, if you perform a bitwise and operation on the first number ($ n $ street) and its mask bit, you will find the maximum value of the final number **. Also, ** the final number does not depend on the order of the numbers other than the first number **, so you can arrange them appropriately.

C.py

n=int(input())
a=list(map(int,input().split()))
mask=0
for i in range(31):
    if [(j>>i)&1 for j in a].count(1)==1:
        mask+=(1<<i)
#Find the maximum
ans=[-1,-1]
for i in range(n):
    if ans[0]<(a[i]&mask):
        ans[0]=a[i]&mask
        ans[1]=i
realans=[]
realans.append(a[ans[1]])
for i in range(n):
    if i!=ans[1]:
        realans.append(a[i])
print(" ".join(map(str,realans)))

D problem

If you can see it, it's a simple matter. Personally, I found the problem statement very difficult to read.

First, to summarize the problem statement, consider whether the outer frame created when the given figure is translated while including the origin is similar to the original figure. At this time, I thought it would be good if there were edges that were parallel and had the same length ** (e.g. rhombus). This intuitive proof can be seen by illustrating the movement when translating so as to be as far away from the origin as possible, including the origin **. I had a good idea of this in my head, so I illustrated sample 2. Then, it became intuitive, so I will implement this.

For implementation, we take advantage of the fact that points are given counterclockwise, so connecting adjacent points to form an edge, and store the edges (as a vector) in the order given to $ edges $. Also, if ** $ n $ is an odd number, it will not be paired **, so NO is output in advance. Also, there are $ n $ edges, but the edges that are $ \ frac {n} {2} $ apart in $ edges $ are paired so that the pairs are parallel and equal in length. Judge. Since this judgment stores the edges as a vector, it is only necessary to judge whether ** the addition becomes a 0 vector **.

D.py

n=int(input())
points=[]
for i in range(n):
    points.append(list(map(int,input().split())))
if n%2==1:
    print("No")
    exit()
edges=[]
for i in range(n-1):
    edges.append([points[i+1][0]-points[i][0],points[i+1][1]-points[i][1]])
edges.append([points[0][0]-points[n-1][0],points[0][1]-points[n-1][1]])
#print(edges)
for i in range(n//2):
    if edges[i][0]+edges[i+n//2][0]!=0 or edges[i][1]+edges[i+n//2][1]!=0:
        #print(i)
        #print(points[i][0]+points[i+n//2][0])
        #print(points[i][1]+points[i+n//2][1])
        print("No")
        exit()
print("Yes")

E problem

After some consideration, it seemed possible to implement it if there was a segment tree that could add intervals and take the maximum value, but it was impossible because it was not a simple integer that I wanted to put on the segment tree.

I wanted to understand the segment tree because of ACLBC, but I didn't have enough motivation and I haven't taken it yet (I understand RMQ). I also bought an ant book, so I plan to take it soon, and I will save it as an exercise at that time.

F problem

I will skip this time