We hope you liked our problems!
Tutorial
Tutorial is loading...
Code
t = int(input())
for i in range(t):
a, b, c = map(int, input().split())
if c % 2 == 0:
if a > b:
print("First")
else:
print("Second")
else:
if b > a:
print("Second")
else:
print("First")
Tutorial
Tutorial is loading...
Code
#include <bits/stdc++.h>
using namespace std;
int solve(int d, vector<int> x)
{
int ans = 0;
for (int i = 1; i < x.size(); i++)
{
ans += (x[i] - x[i - 1] - 1) / d;
}
ans += int(x.size()) - 2;
return ans;
}
void solve()
{
#define tests
int n, m, d;
cin >> n >> m >> d;
vector<int> r(m);
for (int i = 0; i < m; i++) cin >> r[i];
r.insert(r.begin(), 1 - d);
r.push_back(n + 1);
int ans = 2e9;
vector<int> res;
for (int i = 1; i <= m; i++)
{
int A = r[i] - r[i - 1] - 1;
int B = r[i + 1] - r[i] - 1;
int C = r[i + 1] - r[i - 1] - 1;
int D = C / d - (A / d + B / d);
if (D < ans)
{
ans = D;
res.clear();
}
if (D == ans)
{
res.push_back(r[i]);
}
}
cout << ans + solve(d, r) - 1 << ' ' << res.size() << endl;
}
int main()
{
int t = 1;
#ifdef tests
cin >> t;
#endif
while (t--)
{
solve();
}
}
1858C - Yet Another Permutation Problem
Tutorial
Tutorial is loading...
Code
#include<iostream>
#include<vector>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
int cur = 0;
for (int i = 1; i <= n; i += 2) {
for (int j = i; j <= n; j *= 2) {
a[cur++] = j;
}
}
for (int i = 0; i<n; ++i) {
cout << a[i] << " ";
}
cout << '\n';
}
return 0;
}
Tutorial
Tutorial is loading...
Code
#include <bits/stdc++.h>
#define int long long
using namespace std;
using ll = long long;
void solve();
template<typename ...Args>
void println(Args... args) {
apply([](auto &&... args) { ((cout << args << ' '), ...); }, tuple(args...));
cout << '\n';
}
int32_t main() {
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
int t = 1;
cin >> t;
for (int tc = 0; tc < t; ++tc) {
solve();
}
return 0;
}
void solve() {
int n, k;
cin >> n >> k;
string s;
cin >> s;
vector<int> max0by1(n + 1, -1e9);
vector<vector<int>> max0pref(n + 1, vector<int>(n + 1));
vector<vector<int>> max0suf(n + 1, vector<int>(n + 1));
for (int l = 0; l < n; ++l) {
int cnt1 = 0;
for (int r = l + 1; r <= n; ++r) {
cnt1 += s[r - 1] == '1';
max0pref[r][cnt1] = max(max0pref[r][cnt1], r - l);
max0suf[l][cnt1] = max(max0suf[l][cnt1], r - l);
}
}
for (int r = 0; r <= n; ++r) {
for (int cnt = 0; cnt <= n; ++cnt) {
if (r) max0pref[r][cnt] = max(max0pref[r][cnt], max0pref[r - 1][cnt]);
if (cnt) max0pref[r][cnt] = max(max0pref[r][cnt], max0pref[r][cnt - 1]);
}
}
for (int l = n; l >= 0; --l) {
for (int cnt = 0; cnt <= n; ++cnt) {
if (l + 1 <= n) max0suf[l][cnt] = max(max0suf[l][cnt], max0suf[l + 1][cnt]);
if (cnt) max0suf[l][cnt] = max(max0suf[l][cnt], max0suf[l][cnt - 1]);
}
}
vector<int> ans(n + 1, -1e9);
for (int l = 0; l < n; ++l) {
int cnt0 = 0;
for (int r = l; r <= n; ++r) {
if (r > l) cnt0 += s[r - 1] == '0';
if (cnt0 > k) break;
max0by1[r - l] = max(max0by1[r - l], max0pref[l][k - cnt0]);
max0by1[r - l] = max(max0by1[r - l], max0suf[r][k - cnt0]);
}
}
for (int i = 0; i <= n; ++i) {
for (int a = 1; a <= n; ++a) ans[a] = max(ans[a], i + max0by1[i] * a);
}
for (int i = 1; i <= n; ++i) cout << ans[i] << ' ';
cout << '\n';
}
1858E2 - Rollbacks (Hard Version)
Tutorial
Tutorial is loading...
Code
#include <iostream>
#include <vector>
#include <numeric>
#include <set>
using namespace std;
const int maxn = 1e6 + 1;
int f[maxn];
int get(int i) {
int ans = 0;
while (i >= 0) {
ans += f[i];
i = (i & (i + 1)) - 1;
}
return ans;
}
void upd(int i, int x) {
while (i < maxn) {
f[i] += x;
i = i | (i + 1);
}
}
int a[maxn];
int rev[maxn];
set<int> ids[maxn];
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
fill(rev, rev + maxn, -1);
fill(a, a + maxn, -1);
int q;
cin >> q;
int ptr = -1;
vector<pair<pair<int, int>, int>> changes;
while (q--) {
char t;
cin >> t;
if (t == '?') {
cout << get(ptr) << endl;
} else if (t == '+') {
int x;
cin >> x;
int mem = a[ptr + 1];
if (a[ptr + 1] != -1) {
if (ids[a[ptr + 1]].size()) {
upd(*ids[a[ptr + 1]].begin(), -1);
ids[a[ptr + 1]].erase(ptr + 1);
}
if (ids[a[ptr + 1]].size()) {
upd(*ids[a[ptr + 1]].begin(), 1);
}
}
a[ptr + 1] = x;
if (a[ptr + 1] != -1) {
if (ids[a[ptr + 1]].size()) {
upd(*ids[a[ptr + 1]].begin(), -1);
}
ids[x].insert(ptr + 1);
if (ids[a[ptr + 1]].size()) {
upd(*ids[a[ptr + 1]].begin(), 1);
}
}
++ptr;
changes.push_back({ { 1, mem }, -1 });
} else if (t == '-') {
int k;
cin >> k;
ptr -= k;
changes.push_back({ { -1, k }, -1 });
} else {
if (changes.back().first.first == 1) {
if (a[ptr] != -1) {
if (ids[a[ptr]].size()) {
upd(*ids[a[ptr]].begin(), -1);
ids[a[ptr]].erase(ptr);
}
if (ids[a[ptr]].size()) {
upd(*ids[a[ptr]].begin(), 1);
}
}
a[ptr] = changes.back().first.second;
--ptr;
if (a[ptr + 1] != -1) {
if (ids[a[ptr + 1]].size()) {
upd(*ids[a[ptr + 1]].begin(), -1);
}
ids[a[ptr + 1]].insert(ptr + 1);
if (ids[a[ptr + 1]].size()) {
upd(*ids[a[ptr + 1]].begin(), 1);
}
}
} else {
ptr += changes.back().first.second;
}
changes.pop_back();
}
}
}
Note: At about 20 minutes into the round one of our testers (SomethingNew) came up with a linear solution for problem E2, and jiangly implemented the same solution shortly after the contest! For further details, see 219001999. The main idea (as jiangly pointed out in the comments) is that we can use prefix sums instead of the Fenwick tree.
Auto comment: topic has been updated by pakhomovee (previous revision, new revision, compare).
thanks for fast editorial
no problem
thanks for the quick editorial :)
hope to learn how to solve B, wonder why it had so less solves?
for some reason the authors thought c is harder than b idk how
exactly, was able to understand C, but B was like reading a confusing story :(
i actually saw b easier than c though (maybe because i not good at proving)
imho it is poorly written and hard to understand
Yes!Agree fiercely！
Thanks for super fast editorial. Btw can I reach expert? :)
You did! orz
orz
where is E1?
E1 is an easier version of E2, so any solution that works for E2 will work for E1
Yeah but maybe E2 is too hard to understand/code, and a simpler idea would be nice to know
I explained how to solve it here
Prety explain and after I read it, I impelment it and get accepted.
For problem E2, have you ever tested that 200MB static memory will exceed the 256MB memory limit?
Rollbacks this comment, guess it has something to do with C++'s memory alignment.
Fast editorial!
Amazing! The question title for Problem C was exactly what I was thinking.
Why some recent contests always have C as a number theory problem?
especially permutation
true
The title wrongly mentions the round as 892.
B was a little weird.
is problem B designed to prevent contestants from using ChatGPT?
But human only won't understand the statement.
To be honest I lost interest in B the moment I saw it. It's all about interpreting.
one of the worst problem B i've ever seen :<
Why in B we should set d — 1 for first element, instead of 1. I'm wondering, maybe I got WA because of that
You might be having the same problem as mine. Could you please check the following scenario.
If there's a seller at bench 1, then that seller could be removed. If after its removal, the cookie count is minimum then it would contribute to the answer. Even after the seller at index 1 is removed, Petya would still eat a cookie at index 1.
Try this testcase:
1
7 3 2
1 3 5
Expected output:
4 3
C is similar to A Problem in Chinese OJ — Luogu、will the contest unrated?
I'm afraid that it may will be.
Well contests on codeforces will not be unrated easily, and I think C is just too simple and doesn't make difference. It only affects a small number of Chinese contestants.
However there are several serious mistakes (B is just interpreting, C is too easy, E with 256MB Memory Limit), and the contest may be unrated. Similar problem is not the point.
There is nothing to do with those things to make a round unrated. Almost every div2a, div2b and div2c are probably appeared somewhere before, because authoring a different easy problem is actually a very hard thing. Diffuculty balance or some limits doesn't affect contest's ratedness, also there is nothing to do with them as a participant.
C is the same problem from another OJ。Here's the link
(By the way, the owner of this problem is my friend.)
and I think E1&E2 are 2ez and trivial.
Well I had the solution to E1 and was unable to implement it properly so I guess that the implementation makes it harder ? Also this is a div2 round so I can understand that it's trivial for you but if it isn't for most div2 contestants then that's fine. The problem by itself is good and educative (I think)
you are wrong. E1 and E2 are completely different. that's means you cant solve E2 based on E1's solution.
I only talked about E1, not E2
I mean，E2 is easier than E1.
ehm, my sol (perform dfs on a tree) somehow generalises to E2 I think
Nice contest! Although I think B is a tiny bit too difficult. See you on the next contest!
aku adalah from Makassar South Sulawesi
In B for the last testcase
1000000000 3 20000000 57008429 66778899 837653445shouldn't the answer be 52 after removing the first cookie seller? These are the benches where petya can eat a cookie
1 20000001 40000001 60000001 66778899 86778899 106778899 126778899 146778899 166778899 186778899 206778899 226778899 246778899 266778899 286778899 306778899 326778899 346778899 366778899 386778899 406778899 426778899 446778899 466778899 486778899 506778899 526778899 546778899 566778899 586778899 606778899 626778899 646778899 666778899 686778899 706778899 726778899 746778899 766778899 786778899 806778899 826778899 837653445 857653445 877653445 897653445 917653445 937653445 957653445 977653445 997653445True, that's why you should remove the third cookie seller instead of the first. I guess you misunderstood the problem due to the terrible problem statement.
Oh, thanks! you are right, I misunderstood the problem. I thought we needed to print the index of the cookie seller to be removed. My bad
I didn't participate in this contest, but took a quick look at E1/E2. Why is the memory limit 256 MB? It seems kind of on the edge of what is possible with O(q log(q)) memory, but clearly this was not intended. Why not make the memory limit a lot lower?
Very cool problems, especially problem E, although I think problems B and C should have been swapped.
You don't need a fenwick tree in problem E2, just maintain a prefix sum array and update it when adding number, and then you get a linear solution! 219001999
I think B is the actual C problem rather being original B in this contest was stuck on it for past 45 mins :(
Hope to learn to solve E1. Can someone tell me the observation behind it?
Maybe E should give 512MB.
I think so.I've got a lot of memory limit exceed in the contest.
Hey guys, I'm new to CP and need help understanding the first question.
If example taken is 1 2 2
then the winner in that case should be the first one right ?
Tell us why the winner will be the first one
In B why the test case #7
2 2 2 1 2should print1 1and not1 2Since removing either of the sellers will reduce the cookie count by 1you should print the number of sellers that would make the cookies minimum, not the index
Since Petya hasn't yet eaten a cookie at the 1st bench, removing its seller will not reduce the total cookie count.
my approach for C:
Our goal is to have all pairs (1,2), (2,4), ... (i, 2*i), ..., (n/2, n/2*2) next to each other in the permutation
our first attempt is an array: [n/2,n/2*2, ..., i,2*i, ..., 3,6,2,4,1,2] but the array contains duplicates, and is missing values
let's build our answer array by looping i = n/2 -> 1, and attempt to append values
i,2*ionto the back. Valueiwon't appear in the array since we're looping decreasing, but what if2*iappears in the array (from previously appended pair)?In this case, we can insert value
inext to value2*i(but not in between previous pair2*i,4*i)and at the end, we append all missing values
Maybe you needed 14 more authors to realise that problem B was harder than problem C. Also you missed the number of the round in the name of the blog.
Why so agitated?
Great contest! Really enjoyed problem D, so sad I'm too slow :)
There is an $$$O(q)$$$ solution for E2 that I found after initial testing. However, I did use array of size $$$max(x)$$$, so the solution would be $$$O(qloq(q))$$$ if $$$x$$$ can be arbitrarily large.
This solution use the idea that the states of a data structure can be represented as a tree. The root is the initial state, when we modify the data structure, we add a new node that represent that data structure. When we do rollback, we move to the node that represent the rolled-back-to state.
In this problem, there are actually $$$2$$$ types of rolling back: the actual rollback operation, and the remove $$$k$$$ last numbers operation.
Let's solve the problem without actual rollback first. For the adding $$$x$$$ and removing $$$k$$$, we basically have a "prefix tree" of the states, the array at each node is just all the numbers on the path from the root to that node. When we get a removing $$$k$$$ operation, we just go $$$k$$$ node to the root.
So we need a data structure that support the following operations:
This can be done with binary lifting. You will get MLE if you try to implement the binary lifting with $$$O(nlog(n))$$$ memory, but it won't be a problem if you use the $$$O(n)$$$ memory implementation. You can check this blog out if you're interested: https://codeforces.net/blog/entry/74847
Regardless of how you implement binary lifting, you will get $$$O(log(q))$$$ time per operation, but we can actually do this in $$$O(1)$$$:
There might be different ways to explain it, but we can prove by contradiction:
So after all that, we know that we can get any $$$k$$$-th ancestor of the current node by checking what is the last node that has the target height. This is $$$O(1)$$$ insert and query by just saving the last node at each height whenever we insert a node.
So now we know how to go to the correct node, what about calculating the answer?
Realise that the answer when we insert a new value to the array is just whether this value is new or not. We will use the same idea here, the answer for a node is the answer at the parent node + whether this node is new.
To check if a value is new, we can use some sort of persistent data structure, but this would be $$$O(qlog(q))$$$ time and memory, and would almost certainly give you MLE. The way to check if a value is new is in fact pretty similar to the way to find the $$$k$$$-th ancestor in $$$O(1)$$$:
After all that, we can insert, go to $$$k$$$-th ancestor in $$$O(1)$$$. We also calculate the answer for each inserted node in $$$O(1)$$$. So how to add the actual rollback operation?
We will handle the normal rollback with a stack, this is pretty classic, think of it as the call stack in DSU rollback and such. Whenever we insert or move to a new node, we will add that node to the stack. When rollback, we simply have to go to the previous node. Of course, this introduce the problem of the "last time a height appear" and "last time a value appear" array being wrong.
To solve that, instead of just storing the last value, we also store stacks. When we pop from the rollback state stack, we will check and pop from the corresponding stacks as well. This is of course $$$O(1)$$$ because at each node, we only change at most 1 value in each array.
You can find my implementation here: 219006017
UPDATED: Since this solution also only modify $$$O(1)$$$ values for every operation, you can also just store all the changed value + original value in the stack to do rollback.
My binary lifting with $$$O(n \lg n)$$$ memory passed. $$$10^6 \log 10^6 \times 32$$$ bits $$$\approx 76$$$ MiB only.
Why I am getting WA in C can any one explain 219004421
Your permutation for n=12 doesn't contain the pair (6,12) and hence 6 is missing from the array d.
I think you should use another method to make the E2 an online version of E1, such as encoding the queries.
flushing the result can be super slow in some languages. Actually, i used GPT to translate the code of jiangly's into Python. Problem E1 took only less than 900ms while Problem E2 showed TLE. This is really sad.
i dont get this pandering to different languages aside from a general "not setting constraints too tight" perspective.
is it reasonable in any field to say "you are allowed to do a worse job because you chose a wrong tool?". Ofcourse this doesnt mean problems should only be solvable in c++17, rather that you dont forcefully have to ensure every problem is solvable in python.
I mean, after all, it wouldn't hurt to change the problem to make it possible to solve in different languages. The key to solving the problem doesn't change at all.
In this problem, i believe Python is not that of a "wrong tool" except for its poor performance in flushing, which i think should not be a constraint in solving the problem.
I don't expect any problem to be solvable in any languages like Python, but I think in this problem, the problemsetter can do better.
retarded take
Your code for B doesn't even work for sample inputs.
The problem B reminds me a lot of 1836B. Though I know my difficulty in solving it probably comes down to a lack of skill, I still don't think a problem with such a complicated & unclear statement is suitable, especially for Codeforces contests(strictly limited time).
btw, the tutorial code of problem B can't even pass the example testcase. Not a big deal tho, just a little funny.
For E2 we only need to maintain the first occurence of each number in array $$$a$$$ and the value at each position in $$$a$$$. If we maintain these, then if we delete $$$k$$$ numbers from the back, we only need to set the current length of $$$a$$$ to $$$len-k$$$ and the answer to the answer of length $$$len-k$$$, where $$$len$$$ is the current length. We don't need to rollback all these $$$k$$$ elements. Then when we add an element $$$x$$$, we only need to check if the first occurence of $$$x$$$ is earlier than the current length and the value at the position is indeed $$$x$$$. For rollback operation we only need to simply rollback all modifications of any variables. The modifications can be stored in a stack. Time complexity is $$$O(n)$$$ and the implementation is really simple. 218993941
Here's a very simple solution to E2 that works on $$$O(q)$$$ time. It uses a similar idea to the editorial: we keep a large array $$$A$$$ and a value $$$L$$$ such that $$$a$$$ is exactly the prefix of $$$A$$$ of length $$$L$$$. We also keep two auxiliary arrays, also with large size, with the following invariants:
Then, to delete $$$k$$$ elements, we can simply decrement $$$L$$$ by $$$k$$$.
To insert an element $$$v$$$, we can detect that it's a duplicate iff $$$occ[v] < L$$$. Then, we should set $$$vals[L] \gets v$$$, and $$$distinct[L+1] \gets distinct[L] + [occ[v] \ge L]$$$, and set $$$occ[v] \gets \min(occ[v], L)$$$. We also might need to clear out the original state of $$$occ[vals[L]]$$$: if originally $$$occ[vals[L]] = L$$$, then we should first invalidate that by setting $$$occ[vals[L]] = \infty$$$ (which is legal by our relaxed condition on $$$occ$$$).
These two operations both simply do $$$O(1)$$$ array/integer updates, so we can store all updates in a stack to roll back in also $$$O(1)$$$.
Answering queries is simply printing $$$distinct[L]$$$.
Submission: 219008803 219008852
exactly the same as my solution XD
Problem B was really weird to me and it got even weirder when I saw how many people solved it
I am really confused why there is an easy version of problem E. I kept thinking about the reason behind making the queries offline, while the solution for E2 is somewhat more intuitive xD.
in problem C : can anyone please tell me why I am getting wrong answer 218983298 I have used the idea of printing n, n/2, n-2, n/2 — 1, ... so on and at the end all the missing values.
See the testcase bro on which your code is failing 12 6 10 5 8 4 2 1 3 7 9 11 It has 5 distinct gcds -> 6,2,5,1,4 But it is not optimal permutation for n = 12. Optimal is 1 2 4 8 3 6 12 5 10 7 9 11 It has 6 distinct gcds -> 1,2,4,3,6,5
Was hoping a separate tutorial for E1. Any ideas how to do E1 ?
Here is my implementation of E1: 219013362
The idea is to keep the operations performed on the array in the form of a tree. The root, $$$0$$$, means that you haven't performed any operation. Now when you add $$$v$$$ to the array, you create a new node that has $$$0$$$ as a parent (and you now move to this node as it represents the current state you are in).
At any point in time, the values in nodes from the root to the current node will be the values in the array, in order.
To perform $$$- k$$$ queries, you have to move $$$k$$$ times to your parent. It can be done efficiently by using binary lifting.
Finally, $$$!$$$ just means that you should go back to the previous state of the datastructure (you can just keep a stack of the different states).
You will also remember the node that you were at during the $$$?$$$ queries. Now just perform dfs on the tree, when you arrive on a node you add the value to the array, when you get out of a node you remove it.
Thanks! Looks good. I will try to implement this.
The editorial code for B is giving WA on the 1st test case only lol
Can anyone explain the solution to D?
I got lost after
Now, calculate the new dynamics dplen for the length len=r−l+1 of the segment of ones, which equals the maximum length of a subsegment of zeros that we can obtain. Update this value with max(prefl−1,k−x,sufr+1,k−x)I dont understand too, its weird that the max 0's segment is right after or before the max 1's segment.
Did you understand yet, why those two segments should be adjacent?
It isnt adjacent. The pre[i][j] mean the max 0's segment in [1, i] and use no more than j operations. If you read the tutorial more carefully in the second paragraph, you will see that the author update the pre[i][j] from max 0's segment that end with i and use j operations to max 0's segment in [1, i] and use no more than j operations.
Oh i have understood. The pre, as author has explained, mean the max 0's segment that use no more than j operations and have position no more than i. The suf is similar.
Now return to the problems. You can just calculate the answer by run all l1 can be in the answer (obviously it's just from 0 -> n the string's length is only n how can it be bigger =)) ). with each l1, you will calculate the max l0 if the max 1's segment is l1
How can we calculate it ? we can just assume that the max 1's segment is from l to r. we will check how many operations we need to use to make that segment become all 1. We call the number of operations is x. Obviously we only have k — x operations to make the 0's segment as big as possible. so we will use this k — x operations or in the 1 to l — 1 segment or r + 1 to n segment. if we use k — x operations in 1 to l — 1 segment, the answer is pre[l — 1][k — x]. Similar with r + 1 to n
Tutorial of D: Solutions with complexity O(nk logn) and O(nk) using various optimizations of the dynamics (convex hull trick, D&Q) also exist.
D&Q is probably meant to be D&C (divide and conquer).
author's solution for B is giving me wrong answers when I test it on the sample input, I even tried submitting it (you can check my submissions), am I doing anything wrong?
Author's solution is failing on the first pretest? That sure is SomethingNew (but what does that make the author?)
Why this contest get down vote i think the problems are very good
I think mostly because of the problem B just confuses the hella people out. Other than that the problems seem fine.
Awesome contest , thanks for the authors
Video editorial for problems A&C: https://youtu.be/8HABUgytApk
Thought would be useful for newbies(some of the pupils)
https://codeforces.net/contest/1858/submission/219013214
Can anyone please provide a counter example for my code? I have been trying to find a counter example by stress testing my solution against the correct ones on Codeforces, but I still cannot find a counter example.
UPD: I just fixed it, and the problem was I forgot to consider the case where the optimal ways to plant trees consists of no oaks
Memory limit was tight on D. I failed with a 280MB solution. Also, is there a lag between submission time and when the judge sees the submission as submitted? I submitted around 2-3 seconds before the end of the contest, but by the time it loaded the judging page (10 seconds later), it came with a popup 'contest is over'. At least I did not lose out on an accepted submission because I had overflow there (shorts, used to save memory, were overflowing).
Thanks for fast editorial!
The problem of B is too long.
di=gcd(ai,a(imodn)+1)
How does a((i mod n )+ 1) make sense? We'd mod it and then increase the index by 1, this mean it could go out of bounds right? Can someone explain this statement?
"i" denotes 1 based indexing hence it is in fact correct
I feel proud solving B.
about x13837 participants can solve C but only x5448 participants can solve B
Why put 1 — d in problem B and not 1 initially? She is supposed to eat first cookie at 1st position or not?
Petya would indeed eat a cookie at index 1, no matter what. If you by default put index 1 as a seller, then you would need to differentiate that from the case where you actually are given index 1 as the seller. When you actually have a seller at index 1, it might contribute to the ans (if removing it gives minimum cookie count).
Try this testcase:
1
7 3 2
1 3 5
Expected output:
4 3
deleted
I'm stuck there as well, can you explain it to me please?
intitally, pre[i][j] is equal to max length of segment of 0's ending at and including position i and using exactly j operations.
We want to calculate new pre[i][j] which is equal to max length of segment of 0's till position i (not necessarily including position i) and using at most j operations (and not exactly j operations).
So, we need to update pre[i][j]. Note that when we are trying to update pre[i][j], pre[i-1][j] and pre[i][j-1] have already been updated,i.e., pre[i-1][j] is equal to max length of segment of 0's till position i-1 (not necessarily including position i-1) and using at most j operations (and not exactly j operations)---and similarly for pre[i][j-1].
Now, we can update pre[i][j] using the following 2 lines:
pre[i][j]=max(pre[i][j],pre[i-1][j])
pre[i][j]=max(pre[i][j],pre[i][j-1])
The above 2 lines would work, because the NEW pre[i][j] has only 3 options:
it can be equal to old pre[i][j], which is equal to max length of segment of 0's ending at and including position i and using exactly j operations.
it can be equal to new pre[i-1][j],which is equal to max length of segment of 0's till position i-1 (not necessarily including position i-1) and using at most j operations (and not exactly j operations)
it can be equal to new pre[i][j-1],which is equal to max length of segment of 0's till position i (not necessarily including position i) and using at most j-1 operations (and not exactly j-1 operations)
new pre[i][j] will be max of above 3 options.
Thanks for the detailed answer. I have a basic beginner's question here. How would someone be able to even think of this? What kinds of questions should be solved beforehand in order to even think in such a direction?
For me the following has worked:
I have seen enough solutions (directly, without trying to solve on my own) of many DP problems rated around 1900-2100. So, the moment i saw this problem, i was able to understand that there is a high chance of DP(although i still couldnt solve it in contest), since you can either change a 0 to 1 or 1 to 0 (transitions/choices).
You need to solve many DP problems(or atleast just see the solutions-to familiarise yourself with patterns) in order to identify DP in such questions.
In short, the answer is "just solve problems". There is no other way.
did anyone solve task E1 using binary lifting?
here is my code
Can someone tell what's wrong in 219096582 solution for D?
pakhomovee why does 219102302 gets timeout?
I believe the problem is that your solutions works in $$$O(nk\log{n} + n^{2})$$$ and is implemented using
std::set, which has quite a big constant, and, therefore, slows down your solution :(I'd recommend you to think of an $$$O(nk+n^2)$$$ solution if you haven't read the editorial yet since there are quite many different dynamic programming solutions you can come up with!
Is there a video editorial for E?
Can anyone explain why the number of points where Petya will eat cookies between [a,b] is (b-a-1)/d ?
Sure!
Actually, we want to calculate the number of cookies Petya will it on a half-closed interval $$$[a;b)$$$ if there are no cookie sellers on this interval and there is a cookie seller at point $$$a$$$. He will eat cookies at points $$$a$$$,$$$a+d$$$,$$$a+2d$$$ and so on. The number of cookies Petya will eat is equal to the number of times we can add $$$d$$$ to $$$a$$$ so that $$$a+k\cdot d < b$$$ (plus 1, since he will also eat a cookie at $$$a+0\cdot d = a$$$). Let's write out the numbers $$$a,a+1,a+2,\ldots,b-1$$$ and subtract $$$a$$$ from them. Now we need to calculate how many numbers are divisible by $$$d$$$ (or equal to zero, which is also divisible by $$$d$$$) among $$$0,1,2,\ldots,(b-a-1)$$$. It is easy to see that the number we need is $$$\left\lfloor\frac{b- a - 1}{d}\right\rfloor+1$$$ (there are $$$(b-a-1)$$$ numbers which are greater than zero, and zero which we take into account separately).
Hope this helps!
I tried solving problem $$$E$$$ using persistent segment tree.
I tried to increase the memory limit but I got WA.
can someone tell what is wrong ,here is my submission (the same solution got WA after putting 1000 megabytes memory limit) : 219115174 .
i think d is difficult...
Isn't code of problem D different from that of tutorial? Can anyone tell me what's wrong with my approach? Any short testcase where this code fails? https://codeforces.net/contest/1858/submission/219023351
For test case -
4 1 1101 Your output — 4 5 7 9 Correct — 4 6 8 10
is there any solution of problem D trees and segment using Lichao trees?
B is quite easy to understand, solution is also intuitive. Just another ad hoc number line problem. Why complaints?
in problem D where this greedy approach fails? for $$$j > 1$$$ it is always better to keep longest substring of $$$'0'$$$ because even if we replace one $$$'1'$$$ (which is adjacent to this longest substring of $$$0$$$) with $$$'0'$$$ it results in j — 1 change in answer and since $$$j > 1$$$ so $$$j - 1$$$ is positive.
WA submission
I tried to solve E1 using Trie, however I get WA as the result. Can anyone help me point out where I went wrong?
My submission