Educational Codeforces Round 89 Bacha Review (9/8)
This time's results
Impressions of this time
I wasn't very careful about the D problem, but I'm glad I was able to recover it later. It's good to rebuild, but I'm far from setting a highly accurate policy, which is my goal, so I'd like to devote myself to it.
Problem A
If you make $ shovel $ by $ x $ and $ sword $ by $ y $, then $ 0 \ leqq 2x + y \ leqq a $ and $ 0 \ leqq x + 2y \ leqq b $. At this time, the sum of both formulas gives $ 0 \ leqq x + y \ leqq \ frac {a + b} {3} $.
Also, since I want to find $ x + y $, I want to assume that $ [\ frac {a + b} {3}] $ is the maximum value, but ** $ [\ frac {a + b} {3 }] $ must be less than or equal to $ a $ and less than or equal to $ b $ ** (because $ \ because x, y $ is greater than or equal to 0). Therefore, we want $ min ([\ frac {a + b} {3}], a, b) $.
A.py
for _ in range(int(input())):
a,b=map(int,input().split())
print(min((a+b)//3,a,b))
Problem B
It was dangerous because I misread it halfway. Kodofo's English sometimes has a problem that is difficult to read ...
Think about how many indexes can be finally set to 1 while swapping. Also, you can swap in the range from $ l \ _i $ to $ r \ _i $. Since we want to find out all the indexes that can be 1, we can find the solution by finding the range of indexes that can be 1 at the time of $ i $ and gradually expanding the range.
In other words, start with $ [x, x] $ and start with the smallest $ i $. It is easier to understand if you write it in a diagram, so I will explain it in a diagram from here.
As a result, the intervals that can be set to 1 are obtained in order as described above, so the length of the finally obtained section can be obtained as the solution.
B.py
for _ in range(int(input())):
n,x,m=map(int,input().split())
ans=[x,x]
for i in range(m):
l,r=map(int,input().split())
if r<ans[0] or l>ans[1]:
continue
else:
ans=[min(ans[0],l),max(ans[1],r)]
print(ans[1]-ans[0]+1)
C problem
Codeforces seems to have a lot of BFS and DFS. I'm happy because I'm not used to implementing it personally. If you think about it, you can ask for this problem without using BFS.
(For convenience of explanation, the square is changed to 0-indexed.)
** It becomes symmetric ** when the numbers written in the squares traced for any path are arranged. First, from the condition ** for any path **, when tracing from $ (0,0) $ to $ (n-1, m-1) $, ** all cells at the same distance have the same number. It becomes **. Furthermore, from the condition of ** symmetry **, the number of squares with a distance of $ i $ and the number of squares with a distance of $ n + m-2-i $ are the same **. Therefore, for each of the $ n \ times m $ cells, ** search for cells with the same distance ** with BFS and store them in cand for each cell. Actually, when it is at $ (i, j) $, the distance is $ (i, j) $, so it can be calculated without using BFS.
After finding by BFS, the cells with the distance of $ i $ and the cells with the distance of $ n + m-2-i $ are further combined in cand, and the number of 0s and 1s in it. Count and match the smaller one to the larger one. Also, when $ (n + m) % 2 = 0 $, the cell with a distance of $ \ frac {n + m-2} {2} $ is ** the center of any path, so which cell is it? The number is also good **.
Implementation is not difficult if you are aware of ** dividing the implementation into the part that divides the mass for each depth and the part that calculates for each depth **.
C.py
from collections import deque
def bfs(dep):
global a,n,m,ans,d,check,cand
while len(d):
cand.append(list(d))
l=len(d)
for i in range(l):
p=d.popleft()
if p[1]<m-1:
if not check[p[0]][p[1]+1]:
d.append([p[0],p[1]+1])
check[p[0]][p[1]+1]=True
if p[0]<n-1:
if not check[p[0]+1][p[1]]:
d.append([p[0]+1,p[1]])
check[p[0]+1][p[1]]=True
for _ in range(int(input())):
n,m=map(int,input().split())
a=[list(map(int,input().split())) for i in range(n)]
d=deque([[0,0]])
check=[[False]*m for i in range(n)]
check[0][0]=True
cand=[]
bfs(0)
ans=0
for i in range((n+m-1)//2):
x=[a[j[0]][j[1]] for j in cand[i]+cand[n+m-1-1-i]]
ans+=min(x.count(0),x.count(1))
print(ans)
D problem
It caused a miracle of passing TL 2000ms in 1949ms. I thought it would pass, but it was dangerous.
First, consider whether there are $ d \ _1 $ and $ d \ _2 $ such that $ gcd (d \ _1 + d \ _2, a \ _i) = 1 $. Here, when factoring into prime numbers **, if you have only one prime number **, $ d \ _1 $ and $ d \ _2 $ are both multiples of that prime number, so $ gcd (d \ _1 + d \ _2, It will be a \ _i) \ neq 1 $.
Therefore, in the following, we consider the conditions when there are two or more prime numbers when $ a \ _i $ is factored into prime numbers. At this time, I thought that ~~ ** should be selected and added to any prime numbers ** ~~, but it is a complete mistake.
Here, I came up with the case classification by even and oddness, paying attention to ** addition . First, in the case of an odd number, the smallest $ a, b $ can be selected from the prime numbers (odd numbers) included in the prime factorization, and the sum is even. Furthermore, this even number can be expressed as $ \ frac {a + b} {2} \ times 2 $, but is less than $ \ frac {a + b} {2} $ and is included in the prime factorization of $ a \ _i $. The prime number is only $ a $, but $ \ frac {a + b} {2} $ and $ a $ are relatively prime, and 2 is not included in the prime factorization of $ a \ _i $, so such $ a, b $ is the solution $ d \ _1, d \ _2 $ ( pay attention to the extreme case of small numbers! **).
Next, in the case of an even number, if you select an odd number for both $ d \ _1 and d \ _2 $, the sum will be an even number, so $ d \ _1 $ is 2, $ d \ _2 $ is a convenient odd number. You need to choose. At this time, you can select (multiply all odd numbers other than 2) for $ d \ _2 $ (** pay attention to the extreme case of a large number! **). This is because, at this time, $ d \ _1 + d \ _2 $ cannot be divided by any prime number included in the prime factorization of $ a \ _i $.
(It was self-evident for odd numbers, but it may be difficult to interpret the condition that it is ** different from any prime number ** for even numbers. This area seems familiar.)
From the above, we know the cases of even numbers and odd numbers, so we can find the solution. Also, although not mentioned above as self-explanatory, the speed is increased by the Eratosthenes sieve in order to make the calculation amount of prime factorization logarithmic.
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 INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:Congruence law
#define MAXR 10000000 //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
//MAXR=10^Note that it is 5
#define PN 1 //The prime number mark is 1
vector<ll> PN_chk(MAXR+1,PN);//0-indexed(0~MAXR)
//A set that stores the prime numbers included in the prime factorization
set<ll> prime;
//O(MAXR)
void init_eratosthenes(){
ll MAXRR=sqrt(MAXR)+1;
//It does prime factorization of 2 or more numbers and can be ignored.
PN_chk[0]=0;PN_chk[1]=0;
FOR(i,2,MAXRR){
//A prime number if it is assumed to be a prime number when you arrive
//Mark a multiple of a prime number because it is divisible by that prime number
if(PN_chk[i]==1) FOR(j,i,ll(MAXR/i)){PN_chk[j*i]=i;}
}
}
//O(logn)
//Since it is a map, prime is already sorted
//There are only two
void prime_factorize(ll n){
if(n<=1) return;
//if(SIZE(prime)==2)return;
//If 1, n is a prime number
if(PN_chk[n]==1){prime.insert(n);return;}
//Marked numbers are prime numbers
prime.insert(PN_chk[n]);
//Consider the number of marked numbers divided by n
prime_factorize(ll(n/PN_chk[n]));
}
signed main(){
//Code for speeding up input
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
init_eratosthenes();
ll n;cin>>n;
vector<ll> a(n);REP(i,n)cin>>a[i];
vector<ll> ans0(n,-1);
vector<ll> ans1(n,-1);
REP(i,n){
if(a[i]%2==1){
prime_factorize(a[i]);
if(SIZE(prime)>1){
ans0[i]=*prime.begin();
ans1[i]=*++(prime.begin());
}
prime.clear();
}else{
prime_factorize(a[i]);
if(SIZE(prime)>1){
ans0[i]=2;ans1[i]=1;
for(auto j=++prime.begin();j!=prime.end();j++){
ans1[i]*=(*j);
}
}
prime.clear();
}
}
REP(i,n){
if(i==n-1)cout<<ans0[i]<<"\n";
else cout<<ans0[i]<<" ";
}
REP(i,n){
if(i==n-1)cout<<ans1[i]<<"\n";
else cout<<ans1[i]<<" ";
}
}
E problem
I couldn't solve it in the contest, so I thought about it after the contest. It wasn't as difficult as I expected, so I want to be able to leave plenty of time before the E problem.
During the experiment, I noticed that ** the limit of the range that the end of the divided section can take is quite strict **. Also, since it is difficult to think where $ min $ will appear when considering from the smaller $ j $ of $ b \ _j $, we will consider ** from the larger $ j $ of ** $ b \ _ j $ . ( Scan from the other side! **).
At this time, the possible range of the value at the left end of the interval can be determined ** independently and uniquely **.
(1) What is on the far right? ** $ a \ _i = b \ _j $ holds, and the largest $ i $ ** is on the far right. Also, when $ a \ _i <b \ _j $ holds in a place larger than $ i $, the condition of $ min $ is not satisfied, so there are 0 ways.
(2) What is on the far left? (Under the condition that it is the same as or to the left of the rightmost) ** $ a \ _i <b \ _j $ is the first to hold $ i $ plus +1 ** is the leftmost .. Also, when this holds with $ j = 0 $, the condition of $ min $ is not satisfied, so there are 0 ways.
Also, note that when ** $ j = 0
Paying attention to the above corner cases, if you find the interval of the leftmost possible value in each $ j $, you can find the solution by multiplying it.
E.py
mod=998244353
n,m=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
ans=1
i=n-1
for j in range(m-1,-1,-1):
l,r=-1,-1
while i!=-1:
if a[i]<b[j]:
print(0)
exit()
if a[i]==b[j]:
r=i
break
i-=1
else:
print(0)
exit()
while i!=-1:
if a[i]<b[j]:
l=i+1
if j==0:
print(0)
exit()
break
i-=1
else:
if j!=0:
print(0)
exit()
if j!=0:
ans*=(r-l+1)
ans%=mod
#print(l,r)
print(ans)
After the F problem
I will skip this time
Recommended Posts