Tutorial
Tutorial is loading...
Solution (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)
Idea: BledDest, preparation: adedalic
Tutorial
Tutorial is loading...
Solution (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
Idea: Ferume, preparation: Ferume
Tutorial
Tutorial is loading...
Solution (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
Tutorial is loading...
Solution (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;
}
Idea: Ferume, preparation: Ferume
Tutorial
Tutorial is loading...
Solution (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;
}
Idea: Ferume, preparation: Ferume
Tutorial
Tutorial is loading...
Solution (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
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
Don't compare the new string t(0011) with "1100", we have to compare it with the original initial string i.e. s = 111100
You did not notice when you delete two '1', the total number of t is four. As a result, you need to focus on the case that '1' will appear on the left and there are many '1' on the left of s.
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.
what is the problem with this knapsack recursive dp solution?
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 positionidx
will 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.
Thanks for explaining.
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
is C being accepted using 0/1Knapsack?
1913A - Rating Increase In problem A-Rating Increase I wrote my solution for the problem but it got stuck at test 2 and the reason because "Jury has the answer but the participant doesn't" on test 5012. I wrote a comparison program to check my program with other AC solutions but I have yet to see any differences between my program and others. Could anyone tell me why my program got the wrong answer? Here is my code
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 5
then in this casedp[5] = dp[4] + dp[3] + dp[2]
and then you stop because3 < 5
.Can anybody help me in problem B — Valera and Fruits , why my code is not working for test case no. 5 https://codeforces.net/contest/441/submission/236088517
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]] < p[i]$$$ and $$$L[i] < 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!
okok,在问题 D 的解中,搜索左边的第一个较大元素,尽管在作者的解决方案中它是第一个较小的元素,这是否正常
include<bits/stdc++.h>
define int long long
using namespace std;
string s; signed main() { std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t; cin>>t; while(t--) { cin>>s; int n=s.size(); int w=0; for(int i=0;i<n;i++) { if(s[i]=='1') w++; } // if(w==n/2) cout<<0<<'\n'; int m=0; int q=0; for(int i=0;i<min(w,n-w)+1;i++) { if(w>=n-w&&s[i]=='0') q++; else if(w<=n-w&&s[i]=='1') q++; } for(int i=0;i<2*min(w,n-w);i++) { if(w>=n-w&&s[i]=='0') { m++; } else if(w<n-w&&s[i]=='1') { m++; } } // if(w!=n-w) if(q!=0) cout<<max(w,n-w)-m<<'\n'; // else cout<<'0'<<'\n'; else cout<<n-min(w,n-w)<<'\n'; } return 0; } This code is wa in test 2 and I can't find my problem
I have a bit of a different approach to C, see at 240040360. Basically, you store results from ADD queries as amounts of 1's in different binary columns, and then for each GET query, you move along the binary columns (from the end) and find how many 1's you could have at that binary column position. By comparing with the binary representation of v, you can see if your answer is YES or NO.
could someone help to find what's wrong with my code for question D?
https://codeforces.net/contest/1913/submission/240014709
I use interval DP with pointers in one edge pointing to another.
my code have passed 25 tests so I think there's no issue with algorithm that I applied(290ms for 3*10^5 inputs so no problem with complexity). But 26th test has raised problem and I don't why as I can't see all the inputs. Do somebody know what vulnerability is 26th test designed for?
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!
I have a solution that is easier. I'm trying to understand the editorial, but it's really complicated; it might require 3 hours of tracing to understand it. My solution uses a map to store the frequency of each number given in type 1 queries. When I have a type 2 query, I just look at the binary representation of the number I want to check and iterate through its binary representation from left to right. Every time I find a bit equal to 1, I need to have that bit in my map. If I don't have it, then I need to have double the amount in the next bit. For example, if I don't have 16, then I need to have 2 * 8, and if I don't have 8 either, then I need 4 * 4. This is the whole idea, and it worked. just keep a variable called required and iterate through the binary representation if at the end required is 0 then we can form that number
I have a question about B. for 1 1 0 why its answer is 1? if we delet only one number of s, such as 1, the string t we got is 1 0. obviously we cna not swap 1 0 to satisfy the 1 1 0.
for 110 is going to be 2 but for 011 is 1
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$$$.
Okay but the deletion operation is done on initial string s on the sample test case 011
Is confusing but when you perform a deleting are on t, not in s. In the second test case s = "011", t = "101" because t is not good, you have to delete it the last one, and the cost will be 1.
For the 4 test case s = "111100" t = "001111" when you compare you realized that you must delete the ones in position 2 and 3 in t doing that you will get the new string t' = "0011" ancompare this new t with the same s. s = "111100" t' = "0011" you again must delete the ones in position 2 and 3 to get t'' = "00" that is good.
In total you do 4 deleting so the cost is 4.