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

This time's results

Impressions of this time

I have fallen into a bad pattern again. The policy was correct, but I gave up completely because I couldn't solve it. Basically, the level problems that appear in div2 can be solved if the consideration is solidified, so I want to ** keep my concentration **. After that, if I feel like I'm addicted to the swamp, I'll try to ** clear my thoughts and then think **.

Problem A

Think about whether everything can be the same. At this time, ** the number of times each alphabet appears should be a multiple of $ n $ **. Therefore, after connecting all the character strings that appear, I changed it to a list and sorted it, and decided to put the same things together with the groupby function. I've noticed it since the end, but I think it's easier to implement if you use Counter instead of the groupby function.

A.py

from itertools import groupby
for _ in range(int(input())):
    n=int(input())
    s=""
    for i in range(n):
        s+=input()
    s=list(s)
    s.sort()
    for i,j in groupby(s):
        if len(list(j))%n!=0:
            print("NO")
            break
    else:
        print("YES")

Problem B

If you have trouble with the first problem, you are more likely to fail, so try to tackle the first problem as carefully as possible.

(It is assumed that $ a \ _i $ is arranged in ascending order.)

First, if you increase $ c $ for $ c ^ i $, it will increase exponentially, so I think that the value of ** $ c $ will not increase that much **.

Considering this point, it is as follows. In the following, $ \ sum $ is in the range of $ i $ = 0 ~ $ n $ -1.

First,c=1When, all values are 1becomea\_i \geqq 1So\sum{|a\_i-c^i|}=\sum{(a\_i-1)}It will be. Therefore,\sum{c^i} < \sum{a\_i}+(\sum{(a\_i-1)})You can look for it under(\becauseWhen this is not met\sum{|a\_i-c^i|} \geqq \sum{(a\_i-1)}It will be.).. Also, at this rate**cDifficult to find the upper limit of**Therefore, the following formula transformation is applied.

\begin{align}
&\sum{c^i} < \sum{a_i}+(\sum{(a_i-1)}) \\
&\rightarrow c^{n-1}< 2\sum{a_i}-n\\
&\rightarrow c< \sqrt[n-1]{2\sum{a_i}-n}\\
\end{align}

Therefore, we were able to set the upper limit of $ c $. Also, we can see from experiments that this does not grow too much under the conditions of this problem **. I made a mistake in transforming the formula here and wasted too much time.

B.py

n=int(input())
a=list(map(int,input().split()))
a.sort()
ans=10**18
for c in range(2,int((2*sum(a)-n)**(1/(n-1)))+1):
    x=1
    ans_sub=abs(a[0]-x)
    for i in range(n-1):
        x*=c
        ans_sub+=abs(a[i+1]-x)
    ans=min(ans,ans_sub)
print(min(ans,sum(a)-n))

C problem

I personally like this problem because I was able to consider it well.

It's a construction problem, so I'm thinking of ** abstracting the operation nicely **. As a result of experimenting by looking at the sample, if all the numbers can be made multiples of $ n $ in two operations, ** select the whole in the final operation ** and all the numbers can be set to 0. I noticed. Furthermore, if you select a segment of length $ n-1 $ and perform the operation, ** $ n-1 $ and $ n $ are relatively prime, so you can make any number a multiple of $ n $ from the Chinese Remainder Theorem. I noticed that **. Therefore, consider simulating the operation concretely.

In the following, we will consider selecting and operating a segment with a length of $ n $ → a segment with a length of 1 → a segment with a length of $ n-1 $.

(1) When a segment with a length of $ n $ is selected The operation should make $ a [i] + n \ times x $ a multiple of $ n-1 $ ($ n \ times x $ is the number to add to that element). Here, when the formula is transformed, it becomes $ (a [i] + x) + (n-1) \ times x $, so $ x = (n-1) -a [i] % (n-1) You can make $ a [i] + n \ times x $ a multiple of $ n-1 $ by using $. Do this for any $ i $.

(2) When a segment of length 1 is selected Depending on the operation, any number will be a multiple of $ n-1 $, but since the length of the last selectable segment is $ n-1 $, one element must already be set to 0. Here, the first element is set to 0.

(3) When a segment with a length of $ n-1 $ is selected From (1) and (2), all segments with length $ n-1 $ (excluding the first element) are $ n-1 $, so you can operate them.

Also, if ** $ n = 1 $, division by zero will occur, and if $ n = 2 $, it will behave unexpectedly if it is your own implementation **, so in these cases it is different as a corner case. I will process it.

C.py

n=int(input())
a=list(map(int,input().split()))
#first
if n==1:
    print(f"1 1")
    print(f"{-a[0]}")
    print(f"1 1")
    print("0")
    print(f"1 1")
    print("0")
    exit()
if n==2:
    print(f"1 1")
    print(f"{-a[0]}")
    print(f"2 2")
    print(f"{-a[1]}")
    print(f"1 1")
    print("0")
    exit()
print(f"1 {n}")
x=[(n-1-a[i]%(n-1))*n for i in range(n)]
print(" ".join(map(str,x)))
print(f"1 1")
print(f"{-a[0]-x[0]}")
print(f"2 {n}")
print(" ".join(map(str,[-(a[i]+x[i]) for i in range(1,n)])))

D problem

If you think about the image that ** you only have to avoid the worst situation until the final stage **, the problem of the game may work (although I am not very good at it).

Here, let's assume that there are two stone towers left over at the end, and let the number of each stone be $ x, y $. At this time, the person who selects the tower with the most ** wins . Because each person can only choose the tower that was selected first, the person who runs out of stones first loses. Also, since it was a comparison between two towers here, the person who chose the most towers would win, but even if there are multiple towers, the number of stones in the tower with the most stones is the other. You can win if you have more than the total number of stones in the tower ( if the number of stones in a tower exceeds a majority of the total number of stones **). In other words, ** when in this state from the beginning ** is the victory of the preceding $ T $. Also, when $ n = 1 $, it is obvious that $ T $ wins.

In other cases, it is best for each other to ** act so that there are no more than half of the stones ** ($ \ leftrightarrow $ ** select from the tower with the most stones **). Therefore, by repeating this, only two towers will be left and the number of remaining stones will be $ 1,1 $. At this time, you can choose each other, so the person who took the last stone wins. In other words, ** consider the oddness of the total number of stones **, and if it is odd, it will be the first $ T $ victory, and if it is even, it will be the second $ HL $ victory.

D.py

for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    if n==1:
        print("T")
    elif max(a) > sum(a)//2:
        print("T")
    else:
        print(["T","HL"][(sum(a)-1)%2])

After the E problem

I will skip this time