2225A - Число между двумя другими
Автор: BledDest
Разбор
Tutorial is loading...
Решение 1 (BledDest)
t = int(input())
for i in range(t):
x, y = map(int, input().split())
good = False
for z in range(x * 2, y, x):
if y % z != 0:
good = True
break
if good:
print('YES')
else:
print('NO')
Решение 2 (BledDest)
t = int(input())
for i in range(t):
x, y = map(int, input().split())
print('YES' if y > 2 * x else 'NO')
Автор: FelixArg
Разбор
Tutorial is loading...
Решение (FelixArg)
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
string s;
cin >> s;
int ans = 0;
for (int i = 0; i < (int)s.size() - 1; i++){
ans += (s[i] == s[i + 1]);
}
cout << (ans <= 2 ? "YES\n" : "NO\n");
}
signed main()
{
#ifdef FELIX
auto _clock_start = chrono::high_resolution_clock::now();
#endif
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int tests = 1;
cin >> tests;
while(tests--){
solve();
}
#ifdef FELIX
cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
chrono::high_resolution_clock::now()
- _clock_start).count() << "ms." << endl;
#endif
return 0;
}
Автор: FelixArg
Разбор
Tutorial is loading...
Решение (FelixArg)
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1'000'000'007;
void solve(){
int n;
cin >> n;
vector<string> d(2);
cin >> d[0] >> d[1];
vector<int> dp(n + 1, INF);
dp[0] = 0;
for (int i = 0; i < n; i++){
dp[i + 1] = min(dp[i + 1], dp[i] + (d[0][i] != d[1][i]));
if (i + 1 < n){
dp[i + 2] = min(dp[i + 2], dp[i] + (d[0][i] != d[0][i + 1]) + (d[1][i] != d[1][i + 1]));
}
}
cout << dp[n] << '\n';
}
signed main()
{
#ifdef FELIX
auto _clock_start = chrono::high_resolution_clock::now();
#endif
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while(t--){
solve();
}
#ifdef FELIX
cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
chrono::high_resolution_clock::now()
- _clock_start).count() << "ms." << endl;
#endif
return 0;
}
2225D - Исключительные отрезки
Автор: FelixArg
Разбор
Tutorial is loading...
Решение (FelixArg)
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 998'244'353;
int get0(int x){
return 1ll + (x >= 3 ? (x - 3) / 4 + 1 : 0);
}
int get1(int x){
return (x >= 1 ? (x - 1) / 4 + 1 : 0);
}
void solve(){
int n, x;
cin >> n >> x;
int l0 = get0(x - 1) % MOD;
int r0 = (get0(n) - l0) % MOD;
int ans = l0 * r0;
int l1 = get1(x - 1) % MOD;
int r1 = (get1(n) - l1) % MOD;
ans += l1 * r1;
ans %= MOD;
cout << ans << '\n';
}
signed main()
{
#ifdef FELIX
auto _clock_start = chrono::high_resolution_clock::now();
#endif
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int tests = 1;
cin >> tests;
while(tests--){
solve();
}
#ifdef FELIX
cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
chrono::high_resolution_clock::now()
- _clock_start).count() << "ms." << endl;
#endif
return 0;
}
Автор: basalov_yurij
Разбор
Tutorial is loading...
Решение (FelixArg)
#include <bits/stdc++.h>
using namespace std;
#define int long long
mt19937 rng(chrono::high_resolution_clock().now().time_since_epoch().count());
void solve() {
int n, r;
cin >> n >> r;
vector<pair<int, int>> p(n);
for (int i = 0; i < n; i++){
cin >> p[i].first >> p[i].second;
}
int w = 2 * r, h = ceil(sqrt(3) * r);
auto is_in_circle = [&](int x, int y, int ox, int oy, int r){
return (ox - x) * (ox - x) + (oy - y) * (oy - y) <= r * r;
};
int cov;
vector<pair<int, int>> ans;
do{
ans.clear();
cov = 0;
int x0 = rng() % 100'000, y0 = rng() % 100'000;
auto check_point = [&](int x, int y){
int nearest_row = (y - y0) / h;
for (int row = nearest_row - 2; row <= nearest_row + 2; row++){
int nearest_col = (x - (x0 + (row % 2) * r)) / w;
for (int col = nearest_col - 2; col <= nearest_col + 2; col++){
int x_lat = x0 + col * w + (row % 2) * r;
int y_lat = y0 + row * h;
if (is_in_circle(x, y, x_lat, y_lat, r)){
ans.emplace_back(x_lat, y_lat);
cov++;
return;
}
}
}
};
for (int i = 0; i < n; i++){
check_point(p[i].first, p[i].second);
}
} while(cov * 100 < 89 * n);
sort(ans.begin(), ans.end());
ans.erase(unique(ans.begin(), ans.end()), ans.end());
cout << ans.size() << '\n';
for (auto [x, y] : ans){
cout << x << ' ' << y << '\n';
}
}
signed main()
{
#ifdef FELIX
auto _clock_start = chrono::high_resolution_clock::now();
#endif
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int tests = 1;
//cin >> tests;
while(tests--){
solve();
}
#ifdef FELIX
cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
chrono::high_resolution_clock::now()
- _clock_start).count() << "ms." << endl;
#endif
return 0;
}
Автор: FelixArg
Разбор
Tutorial is loading...
Решение 1 (FelixArg)
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MODS[] = {some hidden number 1, some hidden number 2};
const int P = some hidden number 3;
int powP[2][1'000'007];
int inv_powP[2][1'000'007];
int bpow(int x, int p, int mod){
int res = 1;
while(p){
if (p % 2 == 1){
res = (res * x) % mod;
}
p >>= 1;
x = (x * x) % mod;
}
return res;
}
void solve(){
int n, l, k;
cin >> n >> l >> k;
string s;
cin >> s;
if (l * k > n){
cout << "NO\n";
return;
}
if (k == 1){
cout << "YES\n";
cout << s << '\n';
return;
}
vector<vector<int>> h(2, vector<int>(n + 1));
for (int i = 0; i < 2; i++){
for (int j = 0; j < n; j++){
h[i][j + 1] = (h[i][j] + (s[j] - 'a' + 1) * powP[i][j]) % MODS[i];
}
}
function<pair<int, int>(int, int)> get_h = [&](int l, int r){
return make_pair((h[0][r + 1] - h[0][l] + MODS[0]) * inv_powP[0][l] % MODS[0],
(h[1][r + 1] - h[1][l] + MODS[1]) * inv_powP[1][l] % MODS[1]);
};
function<int(int, int, int, int)> cmp_substring = [&](int l1, int r1, int l2, int r2){
int len1 = r1 - l1 + 1;
int len2 = r2 - l2 + 1;
int l = 0, r = min(len1, len2) - 1;
while(l <= r){
int m = l + (r - l) / 2;
if (get_h(l1, l1 + m) != get_h(l2, l2 + m)){
r = m - 1;
}
else{
l = m + 1;
}
}
char ch1 = (l < len1 ? s[l1 + l] : 'a' - 1);
char ch2 = (l < len2 ? s[l2 + l] : 'a' - 1);
if (ch1 < ch2){
return -1;
}
if (ch1 > ch2){
return 1;
}
return 0;
};
int la = 0, ra = l - 1;
for (int i = 0; i < n; i++){
int cnt = i / l;
if (i > 0 && cnt == 0){
continue;
}
int len = i + max(0ll, (k - 1) - cnt) * l;
if (n - len >= l){
if (cmp_substring(i, i + n - len - 1, la, ra) == 1){
la = i;
ra = i + n - len - 1;
}
}
}
cout << "YES\n";
cout << s.substr(la, ra - la + 1) << '\n';
}
signed main()
{
#ifdef FELIX
auto _clock_start = chrono::high_resolution_clock::now();
#endif
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
powP[0][0] = powP[1][0] = 1;
inv_powP[0][0] = inv_powP[1][0] = 1;
int inv_p[] = {bpow(P, MODS[0] - 2, MODS[0]), bpow(P, MODS[1] - 2, MODS[1])};
for (int i = 1; i < 1'000'001; i++){
for (int j = 0; j < 2; j++){
powP[j][i] = powP[j][i - 1] * P % MODS[j];
inv_powP[j][i] = inv_powP[j][i - 1] * inv_p[j] % MODS[j];
}
}
int tests = 1;
cin >> tests;
while(tests--){
solve();
}
#ifdef FELIX
cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
chrono::high_resolution_clock::now()
- _clock_start).count() << "ms." << endl;
#endif
return 0;
}
Решение 2 (BledDest)
#include <bits/stdc++.h>
using namespace std;
int n, l, k;
string s;
string cur;
int zf[2000043];
mt19937 rnd(421337);
void z_function(const string& s)
{
int n = s.size();
for(int i = 0; i < n; i++) zf[i] = 0;
for (int i = 1, l = 0, r = 0; i < n; i++)
{
if (i <= r)
zf[i] = min(r - i, zf[i - l]);
while (i + zf[i] < n && s[zf[i]] == s[i + zf[i]])
zf[i]++;
if (i + zf[i] > r)
{
l = i;
r = i + zf[i];
}
}
}
bool read()
{
if (!(cin >> n >> l >> k))
return false;
cin >> s;
return true;
}
string find_best(vector<pair<int, int>> cand)
{
while(true)
{
if(cand.size() == 1)
return s.substr(cand[0].first, cand[0].second);
int lf = cand[0].first;
int rg = cand[0].first + cand[0].second;
for(int i = 1; i < cand.size(); i++)
{
lf = min(lf, cand[i].first);
rg = max(rg, cand[i].first + cand[i].second);
}
auto p = cand[0];
cur = s.substr(p.first, p.second) + "?" + s.substr(lf, rg - lf);
z_function(cur);
vector<pair<int, int>> better;
int len = p.second;
for(int i = 0; i < cand.size(); i++)
{
if(cand[i] == p) continue;
int L = cand[i].first - lf;
int cur_len = cand[i].second;
int lcp = zf[len + 1 + L];
lcp = min(lcp, cur_len);
if(lcp == cur_len || (len > lcp && cur[L + len + 1 + lcp] <= cur[lcp]))
continue;
better.push_back(cand[i]);
}
if(better.empty())
return s.substr(p.first, p.second);
else
cand = better;
}
return "";
}
void solve()
{
if(k * 1ll * l > n)
{
cout << "NO\n";
return;
}
if(k == 1)
{
cout << "YES\n" << s << "\n";
return;
}
vector<pair<int, int>> cand;
for(int i = 0; i < n; i++)
{
if(i > 0 && i < l) continue;
int lf = i / l;
int rg = (n - i) / l;
if(lf + rg < k) continue;
int need_rg = max(0, k - lf - 1);
int len = (n - need_rg * l) - i;
if(len >= l)
cand.push_back(make_pair(i, len));
}
shuffle(cand.begin(), cand.end(), rnd);
if(cand.empty())
{
cout << "NO\n";
}
else
{
cout << "YES\n" << find_best(cand) << "\n";
}
}
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
int tc = 1;
cin >> tc;
while (tc--)
{
read();
solve();
}
}
Автор: basalov_yurij
Разбор
Tutorial is loading...
Решение (BledDest)
#include<bits/stdc++.h>
using namespace std;
int n, m;
vector<int> k;
vector<int> g;
bool read()
{
if(!(cin >> n >> m)) return false;
k.resize(m);
for(int i = 0; i < m; i++) cin >> k[i];
return true;
}
pair<vector<int>, vector<int>> get_chain(int start, int rank)
{
if(rank == 0)
return make_pair(vector<int>({start}), vector<int>());
pair<vector<int>, vector<int>> p = get_chain(start, rank - 1);
int cnt = g[rank - 1] / g[rank];
for(int i = 1; i < cnt; i++)
{
p.second.push_back(k[rank]);
int next_start = (p.first.back() + k[rank]) % k[0];
pair<vector<int>, vector<int>> q = get_chain(next_start, rank - 1);
for(auto x : q.first) p.first.push_back(x);
for(auto x : q.second) p.second.push_back(x);
}
return p;
}
void solve()
{
g = k;
for(int i = 1; i < m; i++)
g[i] = gcd(g[i - 1], k[i]);
if(g.back() != 1)
{
cout << -1 << "\n";
return;
}
if(k[0] == 1)
{
for(int i = 0; i < n; i++)
{
if(i) cout << " ";
cout << i;
}
cout << "\n";
return;
}
pair<vector<int>, vector<int>> chain = get_chain(0, m - 1);
vector<int> classes = chain.first;
vector<int> add = chain.second;
vector<int> ans;
int new_begin = 0;
for(int i = 0; i < classes.size(); i++)
{
int new_end = -1;
for(int j = classes[i]; j < n; j += k[0])
if(j != new_begin)
{
new_end = j;
break;
}
ans.push_back(new_begin);
for(int j = classes[i]; j < n; j += k[0])
if(j != new_begin && j != new_end)
ans.push_back(j);
ans.push_back(new_end);
if(i + 1 < classes.size())
new_begin = new_end + add[i];
}
for(int i = 0; i < n; i++)
{
if(i) cout << " ";
cout << ans[i];
}
cout << "\n";
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while(t--)
{
read();
solve();
}
return 0;
}
Auto comment: topic has been translated by BledDest (original revision, translated revision, compare)
Damn!! Fastest Edu Round editorial
I made video editorial for the key idea behind D. Exceptional Segments.
I also made video editorial for F. String Cutting.
I tried to solve problem G by explicitly building a graph and heuristically finding hamiltonian path in it using approach from this blog, but failed.
Does someone have a heuristic algorithm for finding hamiltonian path which will actually be good enough to solve problem G?
372054437
Very nice contest !
Is the randomness of test36 of E good enough?I use hexagonal close packing centered (0,0)and have roughly 90% accuracy in test2-35 stably,but drop to 78.35% in test36.
The test aims to punish codes that have predictable starting points, I guess.
It is generated in the same way as the other tests. However, this is the first test with $$$x = 10^5$$$, all tests before it use smaller rectangles.
Are your iteration bounds enough for covering the whole square? You can try initially generate more than n circles and then greedily take those with the most points enclosed.
Why can't I hack submissions on problem F?
Tutorial for D is incomplete. The number of required indices for a specific value to the left or to the right of x can be found by simple division, based on the pattern. You have to show how to do this simple division.
We believe that some simpler parts of the solution should be figured out by participants themselves. But if you've tried to do it and got stuck, check out the spoiler
Let $$$f(R, k)$$$ be the number of integers from $$$0$$$ to $$$R-1$$$ which have remainder $$$k$$$ modulo $$$4$$$. Then the number of segments including $$$x$$$ and having $$$pref_{l-1} = pref_r = 0$$$ is $$$f(x, 3) \cdot (f(n+1, 3) - f(x, 3))$$$, and the number of segments including $$$x$$$ and having $$$pref_{l-1} = pref_r = 1$$$ is $$$f(x, 1) \cdot (f(n+1, 1) - f(x,1))$$$.
How do we calculate $$$f(R, k)$$$? Consider the number of full blocks of length $$$4$$$. Every such block has exactly one number giving remainder equal to $$$k$$$, and the number of such blocks is $$$\lfloor \frac{R}{4} \rfloor$$$. However, there might be a partial block in the end, and we have to check whether it contains one more occurrence of a number with remainder equal to $$$k$$$. The length of this last partial block is $$$R \bmod 4$$$, so if $$$R \bmod 4 \gt k$$$, we need to add $$$1$$$.
Thanks
my solution to A was
let y/x be d
y = dx
a number smaller than y but divisible by x can be written as dx-x or y-x
numerator(z) = dx-x (because y-x will always be a multiple of x if y is a multiple of x and greater than x+1) denominator = x
(dx-x)/x = x(d-1)/x = d-1 which means dx-x will always be a multiple of x now let's check the second condition, which is "y is not divisible by z"
dx/dx-x dx/x(d-1) d/(d-1) and we know that 2 consecutive number have hcf of 1, so remainder is not 0 at all
thus we come to conclusion that, z = dx-x, or y-x
but we know that x<z<y, so if here our z or y-x , is not greater than x then it is breaking the order rule, so basically it isnt possible when y-x <= x or not greater than x
and our final solution is
if y-x >x yes, else no
My post contest discussion stream for ABCDF https://mirror.codeforces.com/blog/entry/153161
Youtube VOD
problem E was cool, but now i wonder if it can be possible by using a greedy method, or if hexagonal packing is the only possible way...
same question, since that was my first approach after giving up
where is the tutorial of problem G
first, the aim of the problem is to find a hamiltonian path in the numbers 0..n-1, where i and j have an edge iff |i-j| is divisible by any element in a set of integers k.
clearly, if gcd(k) != 1, there is no solution (cannot link up different sets)
lets say we have the numbers 1..n and a set of integers k. if we choose some element x ∈ k, and we group all nodes that have an edge because |a-b| divisible by x, we get a set of x cliques, where nodes within the cliques all have the same remainder mod x. as these are cliques, we can freely order the nodes within them, so the only nodes that matter are the start and end nodes
now we should look at edges that cross cliques. say clique 0 and clique y have at least 1 edge between them, then so do clique 1 and y+1, clique 2 and y+2 etc (obvious). so this actually looks like the same problem as before, just now on x < n nodes, but the same set k.
so the problem can be solved recursively, let f(n,k) -> vector be a sequence of n-1 "jumps" that is the difference array for a solution with that n and k. f(n,k) = [clique 0] -> [some other clique that 0 has an edge to] -> [clique with an edge to] etc. if there are x cliques, we can determine the cross jumps needed by f(x,k), and the intra jumps by adding x each time
finally to reconstruct the order, notice that for each clique we just care about the entry and exit node, and they need to be different. as k[i] <= n/3, every clique has >= 3 nodes, which is helpful. simple greedy method can be used to choose the entry and exit nodes for each clique
hope it helps
Is the way to do C other than DP is greedily take vertical segments, else try take it horizontally? We have to take min(count from left, count from right)? Please help me if you've done it without DP.
I don't think there will be a greedy solution here as you can easily see that their are two ways , like in first the two horizontal adjacent cells are of same color in both row or the two vertical row are of same color , so what happens here is that after you have decided colors for them you don't care about these choices for the next ones but the issue is that you cannot optimally choose for one of both those choices here and tbh dp was very intuitive idea here and maybe after more practice you will just see dp idea coming intuitively for this one
Yes we can do it greedily
if a[i]==b[i] then regardless of a[i+1] and b[i+1] we choose to pair a[i] and b[i] and increase i by 1
else
if a[i]!=a[i+1] and b[i]!=b[i+1], we pair up a[i] and b[i] and increase ans by 1, i by 1
else if one of the conditions is false we increase ans by 1 and i by 2(horizontal pairing) if both conditions are false then we simply increase i by 2
372033411
Even simpler: When a[i] != b[i], we only need to place two dominoes horizontally if a[i] == a[i+1] and b[i] == b[i+1]. Otherwise, we will need to add 1 or 2 anyway, whichever way we place them, so we can just place one vertically and continue with the next column. 371998802
i think your approach is wrong, what if the input is RR BR your code will give 0 as output, but the right answer is 1 tell me if am i wrong
No, that will work as well. First, it will encounter a[0] == R and b[0] == B. Therefore, it checks whether a[0] == a[1] and b[0] == b[1]. This is not the case. In the code I sent (which got accepted), we count the number of correct dominoes, so we will just continue for i == 0. For i == 1, it finds a[1] == b[1] and thus adds 1 to the count. Then, it returns 2 — 1 = 1 wrong dominoes / tiles that need to be repainted.
Label the columns with three labels — 0 if the two cells are the same, 1 if red is on top, 2 if blue is on top. Then break it into contiguous chunks with the same label.
Chunks with label 0 can be ignored because we can cover them completely with vertical pairs. The other chunks can be covered with horizontal pairs if the length of the chunk is even. Otherwise, we have one column left over which we can flip a cell of so we can cover it with a vertical pair. So the answer is the count of all chunks with odd length that are labeled 1 or 2.
Solution
I first set all vertical pairs that are already equal to some arbitrary character, then set all horizontal equal ones to that same character from both rows one at a time. Then I count, for each vertical pair, how many of those have different characters, and that is the answer. This was a very ad-hoc solution I came up with in contest through multiple iterations and didn't have time to fully prove.
Submission: 372040543
My idea was to find a way to remove already valid pairs such that the number of invalid pairs you are left with is exactly the same as the minimum number you need to repaint for all pairs to be valid. The problem just becomes finding the optimal way of removing pairs, and which pairs you want to count in the 'removed' string. If you remove horizontal pairs first, you might run into a case where you remove 2 horizontal pairs that are stacked on top of each other, but offset by one column, this makes tiling the table impossible with pairs. Maybe some other way of removing vertical and then horizontal equal pairs for each cell also works, but I found that removing all equal vertical pairs first is also optimal. (You can probably prove it with case-by-case analysis)
Counting only vertical pairs after removal works because it is possible to prove that by removing all valid pairs in the order I did, you will only be left with vertical pairs (i.e. all cells which haven't been removed have a cell in the opposite row which also hasn't been removed). Since no two adjacent cells are equal after the removal, you can count pairs in any way that is a valid tiling of the table.
This is my greedy approach submission:
solution
my method was, if the next 2 columns can do horizontal without switching then go horizontal, otherwise just take one column (if it would cost 1 to switch for horizontal then that means there's 3 red 1 blue or vice versa, in which case vertical costs the same so might as well go with that)
E looks quite unique problem and I haven't seen one of its kind anywhere , is there any place we can practice these type of problems and are there some similar problems there online ? Also how to think about these type of problems when solving them for the first time? __
Heuristics problem i think
I was able to use suffix array for F (though I didn't get it in contest): submission
Idea was to go backwards from the end in the suffix array (so in decreasing order of suffix order) and check feasibility of the suffix. If we have found a feasible suffix $$$a$$$, another feasible suffix $$$b$$$ that is earlier in the suffix array can only improve the solution if $$$a$$$ is a prefix of $$$b$$$. So we can keep a running min of the lcp array as we scan over the suffixes to check this condition.
Can anyone explain the constraint "a circle's area is at most $$$\frac{1}{10}$$$ of the rectangle's area". How does it specifically impact the solution for Problem E?
When the area of the circle is too big, the choice of starting point (from which we build the hexagonal pattern) affects the result much more severely. So, it increases the probability that you pick a "bad" starting point in the beginning by making the random less "pure".
But how does this constraint relate to covering 89% of the points? It seems like there should be enough starting positions to cover 89% of the area.
imagine if you place a circle with a large enough radius such that every point is within 2*r of the circle but not necessarily within r of the circle. You can have many points outside that you can't center circles at because they would intersect with the already placed circle. The area constraint makes it so there will generally be a point far enough away from the circle that can be used to center an additional circle at.
My opinion: Because the area of the rectangle is bounded, we can't achieve ~ 90% density using hexagon packing if the radius is too big. On wikipedia they work with the infinite space, and the density converge to ~ 90% regardless of circle radius.
weak pretest for problem F
When finding circles that can contain point p, why do we check the 5 nearest rows and cols and when is checking 3 not enough?
My solution for D, using observation that xor of consecutive 4 numbers with starting number being even number, is always 0. In code, y : number of even numbers before x (inclusive of x). t : total number of odd numbers between x and n (inclusive). z : (when y is odd, in case of even y, answer added for each odd number is same y/2): number of odd number, i between x and n (inclusive) such that (i+1) is divisible by 4. mul : modular binary multiplication function.
include
define mod 998244353