Разбор
Tutorial is loading...
Решение (awoo)
for _ in range(int(input())):
ab = input()
for i in range(1, len(ab)):
if ab[i] != '0' and int(ab[:i]) < int(ab[i:]):
print(ab[:i], ab[i:])
break
else:
print(-1)
Идея: BledDest, подготовка: adedalic
Разбор
Tutorial is loading...
Решение (adedalic)
for _ in range(int(input())):
s = input()
cnt = [0, 0]
for i in range(len(s)):
cnt[int(s[i])] += 1
for i in range(len(s) + 1):
if (i == len(s) or cnt[1 - int(s[i])] == 0):
print(len(s) - i)
break
cnt[1 - int(s[i])] -= 1
1913C - Игра с мультимножеством
Идея: Ferume, подготовка: Ferume
Разбор
Tutorial is loading...
Решение (awoo)
from sys import stdin, stdout
LOG = 30
cnt = [0 for i in range(LOG)]
ans = []
for _ in range(int(stdin.readline())):
t, v = map(int, stdin.readline().split())
if t == 1:
cnt[v] += 1
else:
nw = 0
for i in range(LOG):
r = (v % (2 << i)) // (1 << i)
if r > nw + cnt[i]:
ans.append(0)
break
v -= r
nw = (nw + cnt[i] - r) // 2
else:
ans.append(nw >= (v >> 30))
stdout.write('\n'.join(["YES" if x else "NO" for x in ans]))
Разбор
Tutorial is loading...
Решение (Roms)
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int normalize(long long x) {
x %= MOD;
if (x < 0) x += MOD;
return x;
}
int main() {
int t;
cin >> t;
for (int tc = 0; tc < t; ++tc) {
int n;
cin >> n;
vector <int> a(n);
vector <int> nextMin(n);
vector <int> dpSum(n + 2);
vector <int> dpNext(n);
for (int i = 0; i < n; ++i)
cin >> a[i];
stack <int> stMin;
nextMin[n - 1] = n;
dpSum[n] = 1;
for (int pos = n - 1; pos >= 0; --pos) {
while(!stMin.empty() && a[stMin.top()] > a[pos])
stMin.pop();
nextMin[pos] = stMin.empty() ? n : stMin.top();
stMin.push(pos);
int nxtPos = nextMin[pos];
int dpPos = normalize(dpSum[pos + 1] - dpSum[nxtPos + 1]);
if (nxtPos != n) {
dpPos = normalize(dpPos + dpNext[nxtPos]);
dpNext[pos] = normalize(dpSum[nxtPos] - dpSum[nxtPos + 1] + dpNext[nxtPos]);
}
dpSum[pos] = normalize(dpPos + dpSum[pos + 1]);
//cout << pos << ' ' << nxtPos << ' ' << dpPos << endl;
}
int res = 0;
int mn = a[0];
for(int i = 0; i < n; ++i) {
mn = min(mn, a[i]);
if (a[i] == mn) {
res = normalize(res + dpSum[i] - dpSum[i + 1]);
}
}
cout << res << endl;
}
return 0;
}
Идея: Ferume, подготовка: Ferume
Разбор
Tutorial is loading...
Решение (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int N = 111;
struct edge
{
int y, c, w, f;
edge() {};
edge(int y, int c, int w, int f) : y(y), c(c), w(w), f(f) {};
};
vector<edge> e;
vector<int> g[N];
int rem(int x)
{
return e[x].c - e[x].f;
}
void add_edge(int x, int y, int c, int w)
{
g[x].push_back(e.size());
e.push_back(edge(y, c, w, 0));
g[y].push_back(e.size());
e.push_back(edge(x, 0, -w, 0));
}
int n, m, s, t, v;
pair<int, long long> MCMF()
{
int flow = 0;
long long cost = 0;
while(true)
{
vector<long long> d(v, (long long)(1e18));
vector<int> p(v, -1);
vector<int> pe(v, -1);
queue<int> q;
vector<bool> inq(v);
q.push(s);
inq[s] = true;
d[s] = 0;
while(!q.empty())
{
int k = q.front();
q.pop();
inq[k] = false;
for(auto ei : g[k])
{
if(rem(ei) == 0) continue;
int to = e[ei].y;
int w = e[ei].w;
if(d[to] > d[k] + w)
{
d[to] = d[k] + w;
p[to] = k;
pe[to] = ei;
if(!inq[to])
{
inq[to] = true;
q.push(to);
}
}
}
}
if(p[t] == -1) break;
flow++;
cost += d[t];
int cur = t;
while(cur != s)
{
e[pe[cur]].f++;
e[pe[cur] ^ 1].f--;
cur = p[cur];
}
}
return make_pair(flow, cost);
}
int get_sum(const vector<int>& v)
{
int sum = 0;
for(auto x : v) sum += x;
return sum;
}
int main()
{
cin >> n >> m;
s = n + m;
t = n + m + 1;
v = n + m + 2;
int sum_matrix = 0;
vector<int> A(n), B(m);
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
{
int x;
cin >> x;
sum_matrix += x;
if(x == 1)
add_edge(i, j + n, 1, 0);
else
add_edge(i, j + n, 1, 1);
}
for(int i = 0; i < n; i++)
{
cin >> A[i];
add_edge(s, i, A[i], 0);
}
for(int i = 0; i < m; i++)
{
cin >> B[i];
add_edge(i + n, t, B[i], 0);
}
auto res = MCMF();
if(res.first != get_sum(A) || res.first != get_sum(B))
cout << -1 << endl;
else
cout << sum_matrix - res.first + res.second * 2 << endl;
}
1913F - Палиндромы и изменения
Идея: Ferume, подготовка: Ferume
Разбор
Tutorial is loading...
Решение (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define x first
#define y second
using namespace std;
struct sparse_table {
vector<vector<int>> st;
vector<int> pw;
sparse_table() {}
sparse_table(const vector<int> &a) {
int n = a.size();
int logn = 32 - __builtin_clz(n);
st.resize(logn, vector<int>(n));
forn(i, n)
st[0][i] = a[i];
for (int j = 1; j < logn; ++j) forn(i, n) {
st[j][i] = st[j - 1][i];
if (i + (1 << (j - 1)) < n)
st[j][i] = min(st[j][i], st[j - 1][i + (1 << (j - 1))]);
}
pw.resize(n + 1);
pw[0] = pw[1] = 0;
for (int i = 2; i <= n; ++i)
pw[i] = pw[i >> 1] + 1;
}
int get(int l, int r) {
if (l >= r) return 1e9;
int len = pw[r - l];
return min(st[len][l], st[len][r - (1 << len)]);
}
};
struct suffix_array {
vector<int> c, pos;
vector<pair<pair<int, int>, int>> p, nw;
vector<int> cnt;
int n;
void radix_sort(int max_al) {
cnt.assign(max_al, 0);
forn(i, n) ++cnt[p[i].x.y];
for (int i = 1; i < max_al; ++i) cnt[i] += cnt[i - 1];
nw.resize(n);
forn(i, n) nw[--cnt[p[i].x.y]] = p[i];
cnt.assign(max_al, 0);
forn(i, n) ++cnt[nw[i].x.x];
for (int i = 1; i < max_al; ++i) cnt[i] += cnt[i - 1];
for (int i = n - 1; i >= 0; --i) p[--cnt[nw[i].x.x]] = nw[i];
}
vector<int> lcp;
sparse_table st;
int get_lcp(int l, int r) {
l = c[l], r = c[r];
if (l > r) swap(l, r);
return st.get(l, r);
}
suffix_array(const string &s) {
n = s.size();
c = vector<int>(s.begin(), s.end());
int max_al = *max_element(c.begin(), c.end()) + 1;
p.resize(n);
for (int k = 1; k < n; k <<= 1) {
for (int i = 0, j = k; i < n; ++i, j = (j + 1 == n ? 0 : j + 1))
p[i] = make_pair(make_pair(c[i], c[j]), i);
radix_sort(max_al);
c[p[0].y] = 0;
for (int i = 1; i < n; ++i) c[p[i].y] = c[p[i - 1].y] + (p[i].x != p[i - 1].x);
max_al = c[p.back().y] + 1;
}
lcp.resize(n);
int l = 0;
forn(i, n) {
l = max(0, l - 1);
if (c[i] == n - 1)
continue;
while (i + l < n && p[c[i] + 1].y + l < n && s[i + l] == s[p[c[i] + 1].y + l])
++l;
lcp[c[i]] = l;
}
pos.resize(n);
forn(i, n)
pos[i] = p[i].y;
st = sparse_table(lcp);
}
};
int main() {
string s;
int n;
cin >> n;
cin >> s;
string t = s;
reverse(t.begin(), t.end());
auto sa = suffix_array(s + "#" + t + "$");
vector<vector<int>> ev0(n), ev1(n);
long long base = 0;
vector<long long> dt(n + 2);
vector<int> d1(n);
forn(i, n){
int len0 = sa.get_lcp(i, 2 * n - i + 1);
base += len0;
dt[i - len0] += 1;
dt[i] -= 1;
dt[i + 1] -= 1;
dt[i + len0 + 1] += 1;
if (i - len0 - 1 >= 0 && i + len0 < n){
ev0[i - len0 - 1].push_back(i);
ev0[i + len0].push_back(i);
}
int len1 = sa.get_lcp(i, 2 * n - i);
d1[i] = len1;
dt[i - len1 + 1] += 1;
dt[i + 1] -= 2;
dt[i + len1 + 1] += 1;
base += len1;
if (i - len1 >= 0 && i + len1 < n){
ev1[i - len1].push_back(i);
ev1[i + len1].push_back(i);
}
}
vector<long long> dx(n + 1);
long long curt = 0, val = 0;
forn(i, n){
curt += dt[i];
val += curt;
dx[i] = val;
}
long long ans = base;
int pos = -1, nc = -1;
bool gr = false;
forn(i, n) forn(c, 26) if (c != s[i] - 'a'){
long long cur = base;
for (int j : ev0[i]){
if (j <= i && c == s[2 * j - i - 1] - 'a')
cur += 1 + sa.get_lcp(i + 1, 2 * n - (2 * j - i - 2));
else if (j > i && c == s[2 * j - i - 1] - 'a')
cur += 1 + sa.get_lcp(2 * j - i, 2 * n - (i - 1));
}
for (int j : ev1[i]){
if (c != s[2 * j - i] - 'a') continue;
if (j < i)
cur += 1 + sa.get_lcp(i + 1, 2 * n - (2 * j - i - 1));
else
cur += 1 + sa.get_lcp(2 * j - i + 1, 2 * n - (i - 1));
}
cur += d1[i];
cur -= dx[i];
bool upd = false;
if (cur > ans){
upd = true;
}
else if (cur == ans){
if (c < s[i] - 'a'){
if (pos == -1 || gr)
upd = true;
}
else{
if (pos < i && gr)
upd = true;
}
}
if (upd){
ans = cur;
pos = i;
nc = c;
gr = c > s[i] - 'a';
}
}
cout << ans << endl;
if (pos != -1) s[pos] = nc + 'a';
cout << s << endl;
return 0;
}
Is it normal that in the solution of problem D the first larger element on the left is searched for, although in the author's solution it is the first smaller element?
I also think the author made a mistake in writing.Largest and smallest are written backwords.
I understand :). It's just misleading.
It may even be easier to understand the solution for maximums at first (hard tutorial), and then solve the problem yourself with a minimum
good D
that's what she said
in problem B in 4th case, where s=111100 we can delete first 2 1's in cost 2 and we can swap rest of the 0's and 1's, it will cost only 2 but author is calculating for cost 4.
original string — 1111 | 00 can you explain this statement?
The original string was "111100" and the new string is "1100" compare the first 4 characters now
original string:"111100" after deleting s becomes="1100" right.Now for t you can swap s1,s4 and s2,s3 to get "0011" , Now when you compare string t with string s : "1100" and "0011" they dont match , so the answer should be 2 I guess not 4
I mean do you really think the given test case can be wrong? given that the contest ended and thousands of users solved it. Try to find a flaw in your logic
I created video editorial for D: Array Collapse.
I also created some practice problems on the prerequisites for this problem (Montonic Stacks + DP), details of which can be found here.
Problem Hanoi Factory on the same idea.
Can anyone please explain how to arrive at the formula: no. of operations = sum_matrix — res.first + res.second?
In promble E:
add a directed edge from C_j to T with capacity A_i and cost 0.
Why is the capacity A_i instead of B_j？
Alternative solution for problem D:
We can break down the problem recursively. If we look at some range
[l,r]of the array, let the index of the minimum element ofa[l...r]to beidx, we can notice that the ranges[l,idx-1]and[idx+1,r]are independent, because no matter what operations we do (in[l,r]), the element at positionidxwill never be erased, so it acts like a wall between the left part and the right part.Then, we can define
solve(l,r)as the answer for a[l,r], and compute it by calculatingsolve(l,idx-1)*solve(idx+1,r).One more detail is that when we are looking at
[l,r], we need to know if the minimum element above us (from the previous recursion) is to the right or to the left (or both), because when this happens we can erase any suffix/prefix in[l,r], including the minimum element, so we have to add in our answer to[l,r]the answer to[l,idx-1]or to[idx+1,r](or both). We do that with a 2 bits mask.Code snippet:
Obs: if the previous minimums comes from both left and right (i.e. the mask is equals to 3), we subtract 1 from the current answer because we counted the empty array twice.
This solution works in O(n log(n)) because of the sparse table build.
Full code: 238167605
Understood the recursive spliting part. Now trying to process remaining parts. [The above explanation should be added in the editorial]
Can you explain your code a little bit like how you are Calculating ret variable
Omg I've accidentally deleted my answer :P, I'll type it again
Imagine this testcase: 10 4 2 5 3 6 1 9 7 8
The important thing to note is that subarrays to the left and to the right of element 1 are independent, so I just calculate the answer for them and multiply those values.
[10 4 2 5 3 6] is L
[9 7 8] is R
Let's look at L: [10 4 2 5 3 6]
You agree with me that I can't arbitrary erase the 10 in the beginning? But I do can arbitrary erase the 6 at the end, because there is a 1 on the right of it. In fact, I can erase any suffix of the subarray [10 4 2 5 3 6].
When I split this [10 4 2 5 3 6] into [10 4] 2 [5 3 6], and look at [5 3 6], now I can erase both the beginning and the end of this subarray, because to the left of it we have the 2, and to the right of it we have the 1.
The variable dir is a bitmask that tells me this, if there is a previous minimum element to the left or right of my current range. If there is some, I need to sum in my ret variable the value of L or R (or both).
If there is both a left and a right minimum element (i. e. the mask is 3), I subtract 1 from the ret variable because in this case I counted the empty subarray twice.
I'm sorry if it's still confusing, but feel free to ask more.
Take a look at the full code to see if it clears out a little bit: 238167605
There is also this submission 237782371 from Ayalla which is very similar but with some slightly difference on the base case of the recursion and in the calculation of variable ans (he doesn't need to subtract 1 from ans when mask is equals to 3), it may be more intuitive this way.
I still don't get why you add L or R if there is a previous minimum element
Imagine you have some array
[3 4 2 1 5 6], obviously $$$1$$$ is the minimum element, so we can break intoL = solve([3 4 2])andR = solve([5 6]), alright? I can't erase any prefix/suffix of this array, because there's no one in the left or right of my array to erase it.But, if I'm recursively going down and at some point I look at something like this:
... 1 ... [3 5 2 8] ...I mean, I'm looking to the range between values $$$3$$$ and $$$8$$$, but I have a $$$1$$$ in my left (which was a minimum element from previous recursions, and I know it exists by looking at the variable $$$dir$$$)
When I'm computing the answer to the subarray
[3 5 2 8], I'll break it in 2 parts splitting in the minimum element and multiplying those L and R values, this will count the number of reachable subarrays that contains my current minimum element (which happens to be 2). But, as I have a previous minimum element on my left, I need to count the number of subarrays that don't contains my current minimum element. I need to count this because I can erase any prefix of my current subarray (with the previous minimum element) and delete my current minimum, so I add variable R to my current answer.Is that clear? I know that it's kinda tricky to fully understand this solution
Thanks, it's a lot clearer now!
upd:nevermind, I am wrong
I debug D for hours just to realize i forget to change the mod value -_-
For Problem D, can someone explain what is meant by this?
It is easy to see that it is enough for all these elements to be smaller than the fixed one. Then they can be removed one by one from left to right. If there is at least one larger element, then the maximum of such elements cannot be removed.But the problem statement says thatyou can choose a contiguous subsegment of p and remove all elements from that subsegment, **except** for the minimum element on that subsegment.So my interpretation would be that it the condition should be that all of the elements be larger than the fixed one? Since the fixed one is the minimum, we can always remove the element adjacent to it. And if there is a smaller element, then we can't remove that element. I don't understand the usage of maximum and minimum in the tutorial and in my interpretation they are reversed.e.g. Let 1 be fixed in 1 2 3 4 5 6. 1 is the minimum element, so the elements after it are larger and can be removed one-by-one. I am interpreting the tutorial as saying the opposite?
You are right, if you have for example the 1-indexed array
10 3 10 12 5then in this casedp[5] = dp[4] + dp[3] + dp[2]and then you stop because3 < 5.An alternate editorial for Problem D
Let us define:
The answer that we are looking for is $$$res[n]$$$.
Let $$$L[i]$$$ be the largest integer such that $$$p[L[i]] \lt p[i]$$$ and $$$L[i] \lt i$$$, then we will have the following transitions.
If $$$L[i]$$$ does not exist, i.e. $$$p[i]$$$ is the smallest in the prefix of length $$$i$$$ then:
For the $$$dp$$$ part, we can remove all elements except the $$$i$$$-th element $$$(+1)$$$ and we can also "attach" the $$$i$$$-th element to the previous element $$$(\sum_{k=1}^{i-1} dp[k])$$$.
For the $$$res$$$ part, since we cannot remove $$$p[i]$$$ that means the $$$i$$$-th element will always be inside all reachable arrays of prefix length $$$i$$$, therefore $$$res[i]=dp[i]$$$.
If $$$L[i]$$$ exist, then:
Similar to the previous explanation.
For the $$$dp$$$ part, we can remove all the positions between $$$L[i]+1$$$ and $$$i-1$$$ $$$(res[L[i]])$$$ and we can also attach the $$$i$$$-th element from $$$L[i]+1$$$ to $$$i-1$$$ $$$(\sum_{k=L[i]+1}^{i-1} dp[k])$$$
For the $$$res$$$ part, we can decide to remove the $$$i$$$-th element $$$(res[L[i]])$$$ or we can decide to keep the $$$i$$$-th element $$$(dp[i])$$$
We can use monotonic stack and prefix sums for the transitions.
Here is my submission.
I personally find this editorial better than the original one! Thanks muhammadhasan01!
Excellent, precise, and very clear solution!
You can also optimize DP in D with RURQ.
I found by far easier to understand C solution by ordering the weights in non-ascending order instead. I found really confusing to follow the explanation with non-descending order, is anyone able to share a more detailed explanation of how it works? would be really appreciated!
1913B - Swap and Delete Why in the sample test case 111100 have output 4 and not 2? Please explain.
Like we can swap two 1's from two 0's and delete rest of 1's and the operation cost will be 2 only. Example:- 111100(in input). - delete first two 1's. String will be 1100 and cost will be 2. - swap the rest 1's with 0's. cost 0 and total cost will remains 2. - Now the string s = 1100 and t=0011.
The problem statement says: "Note that you are comparing the resulting string $$$t$$$ with the initial string $$$s$$$." So in your case, $$$s$$$ does not change and remains $$$111100$$$.
An alternate solution for C: 321746737
problem b made me lose my braincells