Codeforces Round # 669 (Div. 2) Bacha Review (9/9)
This time's results
Impressions of this time
During the contest, I was bugging for the rest of my life without noticing ** A's gag **. Then I had less time to go to D. It was a vicious circle.
After making a bug in D for the rest of my life, I think I would have spent a total of about 4 hours after the contest if I had solved the D problem properly with little consideration of the problem. It's not good mentally, so this kind of problem should be over immediately.
I couldn't solve ** D, but I really like it **, so I'd like to be able to solve it when similar problems come up in the future.
Problem A
At first, I thought about managing the difference between 0 and 1 with DP, but I felt it was troublesome and could not implement it. When I was watching on Twitter, there were some people who could solve it with DP, so I think that this area is ** not enough spirit **. I will devote myself.
It's easy if you notice the gag.
In the end, there are more than $ \ frac {n} {2} $ left, so consider ** conveniently choosing more than $ \ frac {n} {2} $ **. An easy idea is to ** set all selected elements to 0 **, but this is possible if there are more than $ \ frac {n} {2} $ 0s in it. Also, when 0 is less than $ \ frac {n} {2} $, 1 is $ \ frac {n} {2} + 1 $ or more, but if there are an even number of ** 1, the sum is 0 **. You can output $ \ frac {n} {2} $ or $ \ frac {n} {2} + 1 $ 1s by even number of $ \ frac {n} {2} $.
A.py
for _ in range(int(input())):
n=int(input())
a=list(map(int,input().split()))
if a.count(0)>=n/2:
print(n//2)
print(" ".join("0"*(n//2)))
else:
#At this time, 1 is n//2+1 or more
if (n//2)%2==0:
print(n//2)
print(" ".join("1"*(n//2)))
else:
print(n//2+1)
print(" ".join("1"*(n//2+1)))
Problem B
Since the problem statement is a little complicated, to summarize, for the sequence $ b $ which is the rearranged sequence $ a $, the sequence $ c $ is newly added to $ c \ _i = GCD (b \ _1, b \ _2,…, b \ _i) The problem is to find $ b $ when $ c $ is the maximum in lexicographical order when defined as $. Also, for $ b $, you can find an appropriate one that meets the conditions.
** Since it is in dictionary order, consider increasing it greedily from the first element **. As you can see, the first element of $ b $ is the largest element of $ a $. Also, for the second and subsequent $ i $ th elements, if you ask for the GCD (now) of the first to $ i-1 $ th elements, it is the largest among taking now and GCD. You can select the element of as the next element. In addition, you can take the policy of ** $ O (N ^ 2) $ **, so prepare an array check to save which element you have selected and the element of check [i] = False. You can find the elements that maximize GCD in order.
B.py
from math import gcd
for _ in range(int(input())):
n=int(input())
a=list(map(int,input().split()))
check=[False]*n
b=[0]*n
b[0]=max(a)
check[a.index(max(a))]=True
now=b[0]
for i in range(1,n):
#value,index
max1=[-1,-1]
for j in range(n):
if not check[j]:
if max1[0]<gcd(a[j],now):
max1=[gcd(a[j],now),j]
check[max1[1]]=True
b[i]=a[max1[1]]
now=max1[0]
print(" ".join(map(str,b)))
C problem
I solved an interactive problem for the first time. This problem was not difficult, but I want to be able to solve interactive problems without any resistance.
To summarize this problem, "For an unknown permutation $ p $ made up of 1 ~ $ n $, if you pass $ i, j $, you will get $ p \ _i \ mod \ \ _ {p \ _ j} $. Repeat it at most $ 2n $ times to restore $ p $. "
Here, I thought that it would be decided in order from the largest element or the smallest element. For example, $ p \ _i \ mod \ \ _ {p \ _ j} = n-1 $ is unique only when $ (p \ _ i, p \ _j) = (n-1, n) $ If you use $ mod \ _ {n} $, other elements will be uniquely determined. However, it is difficult to find the elements that are ** $ n-1 $ and $ n $ because it will be $ O (n ^ 2) $ **. I gave up on the smallest element because it seems difficult to determine it uniquely in the first place.
Here, paying attention to $ p \ _i \ mod \ \ _ {p \ _j} $, when ** $ p \ _ j> p \ _i $, $ p \ _i $ is uniquely determined ** I noticed. However, since the size is not uniquely determined only from the value of $ p \ _i \ mod \ \ _ {p \ _j} $, it is combined with ** $ p \ _ j \ mod \ \ _ {p \ _i} $. I thought about deciding the size **.
Assuming $ p \ _j > p \ _i $, $ p \ _i \ mod \ \ _ {p \ _ j} = p \ _i $, $ p \ _ j \ mod \ \ _ {p \ _i The two equations of} \ <p \ _i $ hold. Therefore, it becomes $ p \ _i \ mod \ \ _ {p \ _ j} > p \ _ j \ mod \ \ _ {p \ _i} $. On the contrary, when $ p \ _i \ mod \ \ _ {p \ _ j} > p \ _ j \ mod \ \ _ {p \ _i} $, $ p \ _ j > p \ _i $ and $ p \ Since _i \ mod \ \ _ {p \ _j} = p \ _i $ holds, you can decide $ p \ _i $.
Therefore, by asking ** $ p \ _i \ mod \ \ _ {p \ _ j} $ and $ p \ _ j \ mod \ \ _ {p \ _i} $, the smaller element can be determined **. I understand. Therefore, by doing this for any element, you can define $ n-1 $ elements in $ 2 (n-1) $ times of questions. Also, the last remaining element is the largest element, so it will be $ n $.
Also, in order to ** output immediately **, Python needs to give $ flush = True $ as an argument to the print function. I always use it for interactive problems, so I want to remember it.
C.py
for _ in range(int(input())):
n,k=map(int,input().split())
s=input()
t=[[] for i in range(k)]
for i in range(n):
t[i%k].append(s[i])
#If there is something different, no at that point
ans0,ans1=0,0
ex=0
for i in range(k):
if t[i].count("0")>0 and t[i].count("1")>0:
print("NO")
break
elif t[i].count("0")>0:
ans0+=1
elif t[i].count("1")>0:
ans1+=1
else:
ex+=1
else:
if ex==0:
if ans0==ans1:
print("YES")
else:
print("NO")
else:
if ans0+ex>=k//2 and ans1+ex>=k//2:
print("YES")
else:
print("NO")
D problem
Even though I came up with the correct answer after the contest, ** I spent a lot of time due to the lack of consideration **. I would like to have some time to check if the solution is really correct before implementation.
The discussions during the contest were pretty dirty, so I'd like to consider the ones that look good.
First of all, there is no best pattern to jump from right to left, so if you can ** figure out all the ways to jump from left to right, it's easy to catch the jump as a ** DP transition **. You can ask for.
Also, as a jump, the second ($ max (h \ _ {i + 1},…, h_ {j-1}) \ <min (h \ _ i, h \ j)
Consider the second jump. Easy for $ h \ _i \ leqq h \ _j $, jump from $ i $ to the smallest $ j $ ** that meets ** $ j> i $ and $ h \ _j \ geqq h \ _i $ can. When $ h \ _i \ geqq h \ _j $, you can jump from the maximum $ i $ ** that satisfies ** $ i <j $ and $ h \ _i \ geqq h \ _j $ to $ j $. I can do it.
Considering the third jump in the same way, there are the following four transitions. Also, it holds if $ i <j $ is arbitrary.
(1) Jump from $ i $ to the smallest $ j $ that satisfies $ h \ _i \ leqq h \ _j $
(2) Jump from the maximum $ i $ that satisfies $ h \ _i \ geqq h \ _j $ to $ j $
(3) Jump from $ i $ to the smallest $ j $ that satisfies $ h \ _i \ geqq h \ _j $
(4) Jump from the maximum $ i $ that satisfies $ h \ _i \ leqq h \ _j $ to $ j $
If it is $ O (N ^ 2) $, it can be easily obtained, but it is difficult unless it is about $ O (N \ log {N}) $ due to constraints, so ** the information of the transition destination (or transition source) is efficient. Consider saving well . The set structure that can store elements in ascending order is used below. ( Putting unresolved information in set or multiset ** seems to be typical.)
First, in the case of (1), the information of (height, index) is stored in set. Also, this set has ** elements ** whose transition destination is not determined when looking at the 0th to $ i $ th. Here, when you look at the $ i + 1 $ th element $ h [i + 1] $, for the elements that are less than $ h [i + 1] $ in the set, ** transition destination It can be defined as $ i + 1 $ **. You can define the transition by doing this for any $ i $. Also, in the case of (3), the transition can be determined simply by rephrasing the element that is less than $ h [i + 1] $ with the element that is more than $ h [i +] $.
In case of (2), the information of (height, index) is stored in set. This set has ** $ i $ ~ $ n $ th elements ** whose transition source is not fixed. Here, when looking at the $ i-1 $ th element $ h [i-1] $, for the elements contained in the set that are $ h [i-1] $ or more, ** the transition source It can be defined as $ i-1 $ **. You can define the transition by doing this for any $ i $. Also, in the case of (4), the transition can be determined simply by rephrasing the element that is greater than or equal to $ h [i] $ with the element that is greater than or equal to $ h [i] $.
In the case of (1) and (3), there is a possibility that the transition destinations will overlap **, and in the case of (2) and (4), there is a possibility that the transition sources will overlap. Be careful in the latter case.
Anyway, since we were able to enumerate all the transitions of the second and third patterns by $ O (N \ log {N}) $, we should consider DP together with the transition of the first pattern.
D.cc
//Debugging options:-fsanitize=undefined,address
//Compiler optimization
#pragma GCC optimize("Ofast")
//Include etc.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//macro
//for loop
//The argument is(Variables in the loop,Range of movement)Or(Variables in the loop,First number,Number of ends)、のどちらOr
//If there is no D, the loop variable is incremented by 1, and if it is with D, the loop variable is decremented by 1.
//FORA is a range for statement(If it's hard to use, erase it)
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
#define FORA(i,I) for(const auto& i:I)
//x is a container such as vector
#define ALL(x) x.begin(),x.end()
#define SIZE(x) ll(x.size())
//constant
#define MOD 1000000007 //10^9+7:Congruence law
#define INF 1000000000000 //10^12
#define MAXR 100000 //10^5:The largest range in the array
//Abbreviation
#define PB push_back //Insert
#define MP make_pair //pair constructor
#define F first //The first element of pair
#define S second //The second element of pair
signed main(){
//Code for speeding up input
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll n;cin>>n;
vector<ll> h(n);REP(i,n)cin>>h[i];
vector<ll> move1(n);
vector<ll> move2(n);
vector<vector<ll>> move3(n);
vector<vector<ll>> move4(n);
//Other than just going to the right
//First min
set<pair<ll,ll>> minm;
minm.insert(MP(h[0],0));
FOR(i,1,n-1){
if(SIZE(minm)==0){
minm.insert(MP(h[i],i));
continue;
}
//upper_Bound and dangerous next door! !!(I made a bug for the rest of my life)
auto x=minm.begin();
while(x!=minm.end() and *x<=MP(h[i],n)){
move1[x->S]=i;
x=minm.erase(x);
}
minm.insert(MP(h[i],i));
}
//Then max
set<pair<ll,ll>> maxm;
maxm.insert(MP(h[0],0));
FOR(i,1,n-1){
if(SIZE(maxm)==0){
maxm.insert(MP(h[i],i));
continue;
}
auto x=maxm.lower_bound(MP(h[i],0));
while(x!=maxm.end()){
move2[x->S]=i;
x=maxm.erase(x);
}
maxm.insert(MP(h[i],i));
}
//From the other side(This pattern!)
//First min
set<pair<ll,ll>> mint;
mint.insert(MP(h[n-1],n-1));
FORD(i,n-2,0){
if(SIZE(mint)==0){
mint.insert(MP(h[i],i));
continue;
}
//upper_Bound and dangerous next door! !!(I made a bug for the rest of my life)
auto x=mint.begin();
while(x!=mint.end() and *x<=MP(h[i],n)){
move3[i].PB(x->S);
x=mint.erase(x);
}
mint.insert(MP(h[i],i));
}
//Then max
set<pair<ll,ll>> maxt;
maxt.insert(MP(h[n-1],n-1));
FORD(i,n-2,0){
if(SIZE(maxt)==0){
maxt.insert(MP(h[i],i));
continue;
}
auto x=maxt.lower_bound(MP(h[i],0));
while(x!=maxt.end()){
move4[i].PB(x->S);
x=maxt.erase(x);
}
maxt.insert(MP(h[i],i));
}
vector<ll> dp(n,INF);
dp[0]=0;
REP(i,n-1){
dp[i+1]=min(dp[i+1],dp[i]+1);
dp[move1[i]]=min(dp[move1[i]],dp[i]+1);
dp[move2[i]]=min(dp[move2[i]],dp[i]+1);
FORA(j,move3[i])dp[j]=min(dp[j],dp[i]+1);
FORA(j,move4[i])dp[j]=min(dp[j],dp[i]+1);
}
cout<<dp[n-1]<<endl;
}
After the E problem
I will skip this time
Recommended Posts