Codeforces Round # 486 (Div. 3) Bacha Review (9/23)
This time's results
Impressions of this time
** I wasted an hour and a half if I had bugged the D problem forever **. I avoided the E problem because I thought it was troublesome, but as a result, I was able to upsolve it if I properly classified the cases, so I am disappointed. I couldn't find any corner cases or bugs in both D and E problems because I haven't been able to make use of my reflections so far, so I'd like to organize my mind so that I can make use of them next time.
Problem A
Since we want the ratings to be different, we count the number of rating types in the ** set structure and determine if it exceeds ** $ k $. If it is $ k $ or more, appropriate $ k $ pieces are output. I used index here for ease of implementation, but a different method is better in terms of computational amount (I won't show it here, but you can do it with $ O (k) $).
A.py
n,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(set(a))
if len(b)>=k:
print("YES")
ans=[]
for i in range(k):
ans.append(a.index(b[i])+1)
print(" ".join(map(str,ans)))
else:
print("NO")
Problem B
When there is an order of strings that satisfies the subject, any string (except the first string) has the previous string as a substring, so ** this string order is in ascending order of length ** (It can be shown by the $ \ because $ absurdity method).
Therefore, the given character string should be corrected in ascending order of length, and it should be judged by in whether each is included in the immediately preceding character string. At this time, the amount of calculation is $ O (N ^ 2) $.
B.py
n=int(input())
a=[input() for i in range(n)]
a.sort(key=lambda x:len(x))
for i in range(n-1):
if a[i] not in a[i+1]:
print("NO")
break
else:
print("YES")
for i in range(n):
print(a[i])
C problem
Select two sequences and extract one element from each to find the one with the same sum. Here, there are $ n \ _i $ sums for extracting one element from the sequence of $ i $ th length $ n \ _i $ depending on which element is extracted. Also, from the constraint, $ \ sum \ _ {i = 1} ^ {k} {n \ _i} \ leqq 2 \ times 10 ^ 5 $, so ** this sum can be enumerated in its entirety **.
Here, the sum when the $ j $ th element of the $ i $ th length $ n \ _i $ sequence is extracted is (the sum of the $ i $ th sequence)-(the $ j $ th element). Value), and if the sum of each sequence is calculated in advance, it can be calculated by $ O (\ sum \ _ {i = 1} ^ {k} {n \ _ i}) $. Also, if you put the dictionary $ m $ as a vector that stores the key as the sum value of the sequence and the value as "the value (index of the sequence, index of the extracted element)", the sum of the sequence obtained earlier can be ordered in order. Can be stored. Also, at this time, if there are two or more ** sequences with the same key but different indexes **, it can be output as an answer. On the contrary, if there is no one with two or more, No should be output.
(I didn't realize it, but I could write it in Python. Why did I write it in C ++ ...?)
C.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 INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:Congruence law
#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 k;cin>>k;
map<ll,vector<pair<ll,ll>>> m;
REP(i,k){
ll ni;cin>>ni;
vector<ll> a(ni);REP(j,ni)cin>>a[j];
ll s=0;REP(j,ni)s+=a[j];
REP(j,ni){
m[s-a[j]].PB(MP(i+1,j+1));
}
}
FORA(i,m){
if(SIZE(i.S)>1){
map<ll,ll> x;
//Eliminate the same sequence
FORA(j,i.S){
x[j.F]=j.S;
}
if(SIZE(x)>1){
auto y=x.begin();
cout<<"YES"<<endl;
cout<<y->F<<" "<<y->S<<endl;
y++;
cout<<y->F<<" "<<y->S<<endl;
return 0;
}
}
}
cout<<"NO"<<endl;
}
D problem
(The operation by UnionFind is regarded as a constant and the amount of calculation is shown.)
If you do it with the image of selecting a subset from the whole, you may be addicted to the swamp. Note that the distance between the two points is $ 2 ^ d $ and the maximum is $ 2 \ times 10 ^ 9 $, so you only need to look at ** $ d = $ 0 ~ 30 **.
At this time, consider finding the largest subset ** for each $ d $. Also, when paying attention to a certain point $ x $, the points separated by $ 2 ^ d $ are $ x-2 ^ d, x + 2 ^ d $, and if all points are managed by set, they are ** separated You can check if there is a point with $ O (\ log {n}) $ ** ($ O (n \ log {n}) $ if you check at any point). Therefore, by using ** UnionFind to connect points that are $ 2 ^ d $ apart, ** you can create some subsets of points as shown below.
Also, I would like to say that all the points included in the subset in the above figure are included in the subset that satisfies the subject, but ** I can only include up to 3 points **. This is because if the points are larger than 3, there will always be a set of points whose distance is not a power of 2.
From the above, perform Union Find for each of $ d = $ 0 to 30 (when the elements in the set are arranged in ascending order, the distance between the coordinates is $ 2 ^ d $) to find the disjoint set system, and a set with three or more elements is obtained. If there is at least one, ** three adjacent points ** are output when the set is arranged in ascending order, and if there is at least one with 2 elements (which does not meet the above conditions), the set Two points included in are output, and in other cases, an appropriate one point should be output.
Also, since I wanted to specify the index when uniting points, I prepared ʻindas a map ** that gives an index to the value, and changed the index to the element value at the time of output. I preparedvalas a vector. Also, since the set obtained by UnionFind is in ascending order of index **, it is necessary to change **val in ascending order and store it in ʻind ** to match the ascending order of values. there is. (I didn't notice that I didn't sort in ascending order, and it took me several hours to debug ... It was a mistake I noticed at the discussion stage, so when I'm impatient, I want to ** compare it with my own thoughts ** .)
9/25 postscript
In fact, if you pay attention only to the fact that there are at most three, you can implement it lightly and at high speed just by looking sideways. I wish I had noticed this. See the second Python code.
D.cc
//Debugging options:-fsani
//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 INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:Congruence law
#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
//Below, the disjoint sets and the tree represent the same thing.
class UnionFind {
public:
vector<ll> parent; //parent[i]Is the parent of i
vector<ll> siz; //An array representing the size of the disjoint sets(Initialize with 1)
map<ll,vector<ll>> group;//Associative array managed for each disjoint set(key is the parent of each disjoint set, value is an array of elements of that disjoint set)
ll n;//Number of elements
//constructor
UnionFind(ll n_):parent(n_),siz(n_,1),n(n_){
//Initialize as the root of all elements is itself
for(ll i=0;i<n;i++){parent[i]=i;}
}
//Get the root of the tree to which the data x belongs(Also performs path compression)
ll root(ll x){
if(parent[x]==x) return x;
return parent[x]=root(parent[x]);//Since the value of the assignment expression is the value of the assigned variable, the route can be compressed.
}
//Merge x and y trees
void unite(ll x,ll y){
ll rx=root(x);//root of x
ll ry=root(y);//root of y
if(rx==ry) return;//When in the same tree
//Merge small set into large set(Merged from ry to rx)
if(siz[rx]<siz[ry]) swap(rx,ry);
siz[rx]+=siz[ry];
parent[ry]=rx;//If x and y are not in the same tree, add y root ry to x root rx
}
//Determine if the tree to which x and y belong is the same
bool same(ll x,ll y){
ll rx=root(x);
ll ry=root(y);
return rx==ry;
}
//Get the size of the disjoint sets of x
ll size(ll x){
return siz[root(x)];
}
//Group each disjoint set
void grouping(){
//Perform route compression first
REP(i,n)root(i);
//Manage with map(Use default build)
REP(i,n)group[parent[i]].PB(i);
}
void clear(){
for(ll i=0;i<n;i++){parent[i]=i;}
siz=vector<ll>(n,1);
group.clear();
}
};
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll n;cin>>n;
set<ll> x;
//Ind for value
map<ll,ll> ind;
//Value for ind
vector<ll> val(n);
REP(i,n){
ll y;cin>>y;
x.insert(y);
val[i]=y;
}
sort(ALL(val));
REP(i,n){
ind[val[i]]=i;
}
vector<ll> v(1,0);
pair<ll,vector<ll>> ans=MP(1,v);
UnionFind uf(n);
REP(i,31){
uf.clear();
FORA(j,val){
if(x.find(j+(1LL<<i))!=x.end()){
uf.unite(ind[j],ind[j+(1LL<<i)]);
}
}
uf.grouping();
for(auto j=uf.group.begin();j!=uf.group.end();j++){
if(SIZE(j->S)>ans.F){
//Does not exceed 3
//Not sorted(val is)huh? ?? ?? ?? ?? ?? ??
if(ans.F==1){
if(SIZE(j->S)==2){
vector<ll> w(2);
w={j->S[0],j->S[1]};
ans=MP(2,w);
}else{
cout<<3<<endl;
cout<<val[j->S[0]]<<" "<<val[j->S[1]]<<" "<<val[j->S[2]]<<endl;
return 0;
}
}
if(ans.F==2){
if(SIZE(j->S)>2){
cout<<3<<endl;
cout<<val[j->S[0]]<<" "<<val[j->S[1]]<<" "<<val[j->S[2]]<<endl;
return 0;
}
}
}
}
}
cout<<ans.F<<endl;
REP(i,ans.F){
if(i==ans.F-1){
cout<<val[ans.S[i]]<<endl;
}else{
cout<<val[ans.S[i]]<<" ";
}
}
}
D.py
n=int(input())
x=list(map(int,input().split()))
y=set(x)
ans=[x[0]]
for d in range(31):
e=2**d
for i in range(n):
if x[i]-e in y and x[i]+e in y:
print(3)
print(x[i]-e,x[i],x[i]+e)
exit()
elif x[i]-e in y:
ans=[x[i],x[i]-e]
elif x[i]+e in y:
ans=[x[i],x[i]+e]
if len(ans)==2:
print(2)
print(ans[0],ans[1])
else:
print(1)
print(ans[0])
E problem
It's not difficult to think about, but I found it a tedious problem to complete the implementation.
First, the condition for being a multiple of 25 is when the last two digits are one of $ 00,25,50,75 $. It's also self-evident that you should ** swap and bring the numbers as close as possible **. However, if there is a number given in the most significant digit **, 0 may come in the most significant digit, so it is necessary to separate the cases at this time. Also, in the case of $ 00 $, only two of the same number must be considered and there is no number given to the most significant digit, so I decided to ** consider it separately from the other three **.
First, if there is only one digit, it is troublesome to distinguish between cases, so -1 is output in advance. And even if it consists of two digits, ** it was difficult to distinguish cases ** (WA was also issued), so 0 is output for $ 25,75,50 $ and 1 is output for $ 52,57 $.
Based on this, find the minimum number of swaps required to bring $ 25,50,75 $ to the least significant digit. Here, the function for finding the minimum number of times is $ calc1 $, and the arguments are $ x, y $ ($ (x, y) = (2,5), (5,0), (7,5) $) .. First, when swapping, we want to know how far it is from the least significant digit, so we see the given number as an array of numbers and flip it (let's call it $ m $). Here, if neither $ x nor y $ is included in the digit, the minimum number of times does not exist and $ inf $ is returned. Based on this, find the index of $ x, y $ in $ m $ as $ ix, iy $. Also, if neither ** $ x, y $ is on the far right (most significant digit) **, it is best to swap in order from the one closest to the least significant digit (the smaller of $ ix, iy $). If $ ix <iy $, the least significant digit is inverted as it is, so one more swap is required.
Next, consider ** if either is on the far right **, but since both $ x and y $ are the same operation except for swap between the least significant digits, $ x $ is on the far right. The time of is considered below. When $ x $ is on the far right, look from the most significant digit to the last digit, select the first element that is not ** 0 and its index is not $ iy $, and swap with the most significant digit. Since ** is the optimum number of times, swap it. Also, if there is no element that is not 0 and its index is not $ iy $, it returns $ inf $ ($ 25,75,50,52,57 $, which was initially excluded as a case, ** does not satisfy this, so first The case was divided into **.). And if this digit is $ i $, the number of exchanges with the most significant digit can be easily calculated. Also, if ** $ i <iy $, then $ iy- = 1 $ will be swapped when carrying $ i $ to the upper digit **, so be careful. Therefore, if you can swap with the most significant digit, you can swap $ iy $ and then swap $ ix $, and count the total number of swaps.
Also, if you want to set the least significant digit to $ 00 $, you can find the index of $ 00 $ that is closest to the least significant digit and move it closer to the least significant digit, which is easy because swap does not occur due to different least significant digits. It will be an implementation.
From the above, the minimum number of times for each case of $ 00, 25, 50, 75 $ can be calculated, and the minimum number of times can be calculated, but if the minimum number of times is $ inf $, -1 is output. need to do it.
Surprisingly, it was a problem that was not so heavy to implement. I would like to do my best to implement such problems ** involuntarily.
E.py
n=[int(i) for i in input()]
l=len(n)
#Even if the length is 2
if len(n)==1:
print(-1)
exit()
#In this case only
if n in [[2,5],[7,5],[5,0]]:
print(0)
exit()
if n in [[5,2],[5,7]]:
print(1)
exit()
inf=10**12
#If it's on the far left, it's annoying, so I'll separate the cases.(Reverse)
#00 is also divided into cases
def calc1(x,y):
global n,l,inf
m=n[::-1]
if x not in n or y not in n:
#print(x,y,0)
return inf
ix,iy=m.index(x),m.index(y)
#If not on the far right
if max(ix,iy)<l-1:
if iy<ix:
#print(x,y,1)
return iy+(ix-1)
else:
#print(x,y,2)
return iy+(ix-1)+1
else:
ret=0
#print(ix,iy)
if ix==l-1:
#Look from the right and look to the left(0 and not the other choice)
for i in range(l-2,-1,-1):
if m[i]!=0 and i!=iy:
break
else:
#print(x,y,3)
return inf
if i<iy:
iy-=1
ret+=(l-1-i)
ix-=1
ret+=(iy+(ix-1))
#print(x,y,4,ret)
return ret
else:
ret+=iy
ret+=(l-1-i)
ix-=1
ret+=(ix-1)
#print(x,y,5,ret)
return ret
else:
#Look from the right and look to the left(0 and not the other choice)
#The only possibility of the other one to choose(Eliminate first)
#Do it outside
for i in range(l-2,-1,-1):
if m[i]!=0 and i!=ix:
break
else:
#print(x,y,6)
return inf
if i<ix:
iy-=1
ret+=(l-1-i)
ix-=1
ret+=(iy+(ix-1)+1)
#print(x,y,7,ret)
return ret
else:
ret+=iy
ret+=(l-1-i)
ix-=1
ret+=((ix-1)+1)
#print(x,y,8,ret)
return ret
#At 00
def calc2(x,y):
#Absolutely not on the far right
global n,l,inf
if n.count(0)<2:
return inf
m=[l-1-i for i in range(l) if n[i]==0][::-1]
return m[0]+m[1]-1
ans=min([calc1(2,5),calc1(7,5),calc1(5,0),calc2(0,0)])
#print([calc1(2,5),calc1(7,5),calc1(5,0),calc2(0,0)])
print(-1 if ans==inf else ans)
F problem
I will skip this time
Recommended Posts