Many thanks to infinitepro, BledDest and alimq for helping me write the editorials.
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
#define int long long
int solveTestCase() {
int n;
cin >> n;
string s = "989";
if (n <= 3)
return cout << s.substr(0, n) << "\n", 0;
cout << s;
for (int i = 3; i < n; i++)
cout << (i - 3) % 10;
cout << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
cin >> t;
while (t--)
solveTestCase();
}
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 3e5;
int a[N], n;
int isValley(int i) {
return (i > 0 && i < n - 1 && a[i] < a[i - 1] && a[i] < a[i + 1]);
}
int isHill(int i) {
return (i > 0 && i < n - 1 && a[i] > a[i - 1] && a[i] > a[i + 1]);
}
int solveTestCase() {
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i];
int is[n] = {};
int s = 0;
for (int i = 1; i < n - 1; i++) {
if (isHill(i) || isValley(i))
is[i] = 1, s++;
}
int ans = s;
for (int i = 1; i < n - 1; i++) {
int temp = a[i];
a[i] = a[i - 1];
ans = min(ans, s - is[i - 1] - is[i] - is[i + 1] + isHill(i - 1) + isValley(i - 1) + isHill(i) + isValley(i) + isHill(i + 1) + isValley(i + 1));
a[i] = a[i + 1];
ans = min(ans, s - is[i - 1] - is[i] - is[i + 1] + isHill(i - 1) + isValley(i - 1) + isHill(i) + isValley(i) + isHill(i + 1) + isValley(i + 1));
a[i] = temp;
}
cout << ans << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
cin >> t;
while (t--)
solveTestCase();
}
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 3e5;
vector<vector<int>> a(3, vector<int>());
vector<int> n(3, 0);
int calc() {
int ans = 0, m1 = a[1][0], m2 = a[2][0], s1 = 0, s2 = 0;
for (int i : a[0]) ans += i;
for (int i = 1; i < n[1]; i++) s1 += a[1][i];
for (int i = 1; i < n[2]; i++) s2 += a[2][i];
ans += max({s2 - m1 + s1 - m2, m2 + s2 - m1 - s1, m1 + s1 - m2 - s2});
return ans;
}
int solveTestCase() {
cin >> n[0] >> n[1] >> n[2];
a[0].resize(n[0]);
a[1].resize(n[1]);
a[2].resize(n[2]);
for (int i = 0; i < 3; i++) {
for (int j = 0; j < n[i]; j++)
cin >> a[i][j];
sort(a[i].begin(), a[i].end());
}
int ans = -1e18;
ans = max(ans, calc());
swap(a[0], a[1]), swap(n[0], n[1]);
ans = max(ans, calc());
swap(a[0], a[2]), swap(n[0], n[2]);
ans = max(ans, calc());
cout << ans;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
//cin >> t;
while (t--)
solveTestCase();
}
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5005, mod = 1e9 + 7;
int dp[N][N], cnt[N], a[N], q, n, k;
void pre() {
for (int i = 0; i < n; i++)
dp[i][0] = 1;
for (int j = 1; j < N; j++) {
dp[0][j] = dp[1][j - 1];
for (int i = 1; i < n - 1; i++)
dp[i][j] = (dp[i - 1][j - 1] + dp[i + 1][j - 1]) % mod;
dp[n - 1][j] = dp[n - 2][j - 1];
}
for (int i = 0; i < n; i++) {
for (int j = 0; j <= k; j++)
cnt[i] += dp[i][j] * dp[i][k - j], cnt[i] %= mod;
}
}
void solveTestCase() {
int ans = 0;
for (int i = 0; i < n; i++)
cin >> a[i], ans += a[i] * cnt[i], ans %= mod;
while (q--) {
int i, x;
cin >> i >> x;
i--;
ans -= (a[i] * cnt[i]) % mod, ans += mod, ans %= mod;
a[i] = x;
ans += (a[i] * cnt[i]), ans %= mod;
cout << ans << "\n";
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> k >> q;
pre();
int t = 1;
//cin >> t;
while (t--)
solveTestCase();
}
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5;
vector<int> adj[N];
int a[N], par[N], n;
map<int, vector<int>> v, times;
int euler[N * 2 - 1], tin[N], tout[N], c = 0;
set<pair<int, int>> g;
int dp[N], ans;
void dfs(int v, int p = -1) {
par[v] = p;
tin[v] = c;
euler[c++] = v;
for (int i : adj[v]) {
if (i == p)
continue;
dfs(i, v);
euler[c++] = v;
}
tout[v] = c - 1;
}
void examine(int v) {
int sum = 0;
for (int i : adj[v]) {
if (i == par[v])
continue;
int count = upper_bound(times[a[v]].begin(), times[a[v]].end(), tout[i]) - lower_bound(times[a[v]].begin(), times[a[v]].end(), tin[i]);
if (count > 0)
g.insert({v, i});
sum += count;
}
sum = times[a[v]].size() - sum - 1;
if (sum)
g.insert({v, par[v]});
}
int setup(int v) {
for (int i : adj[v]) {
if (i != par[v])
dp[v] += setup(i);
}
return dp[v] + g.count({v, par[v]});
}
void reroot(int v) {
if (dp[v] == g.size())
ans++;
for (int i : adj[v]) {
if (i == par[v])
continue;
dp[v] -= dp[i];
dp[v] -= g.count({i, v});
dp[i] += dp[v];
dp[i] += g.count({v, i});
reroot(i);
dp[i] -= g.count({v, i});
dp[i] -= dp[v];
dp[v] += g.count({i, v});
dp[v] += dp[i];
}
}
int solveTestCase() {
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i];
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
u--, v--;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(0);
for (int i = 0; i < n; i++)
v[a[i]].push_back(i);
for (auto i : v) {
if (i.second.size() == 1)
continue;
for (int j : i.second)
times[i.first].push_back(tin[j]);
sort(times[i.first].begin(), times[i.first].end());
for (int j : i.second)
examine(j);
}
setup(0);
reroot(0);
cout << ans;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
//cin >> t;
while (t--)
solveTestCase();
}
UPD: Also, have a look at this comment for an explanation of the sample test case of C.
My sincere apologies for misjudging the difficulty of B. Most of the testers solved it hence I thought it was fine for a div2B. Hope you all enjoyed the other problems.
It was just unusual, I guess people (of course including me) fell for some short greedy type approaches. Problems were nice.
In hindsight it was fine. It gives the impression that it suffices to reduce the input to a sequence of -1, 0, 1, and work on that. At least I did that — and it felt really clever — until I got WA.
Fcuk off to you and your problem setting.
This comment that's your account, right?
Fuck you is right.
I disagree. Although I didn't solve it and it ruined my contest, I think This is an excellent problem for Div 2 B. It requires a one simple observation and then can easily be solved by doing a case by case analysis.
it's trivial to calc the initial intimidation, init.
then, by the key fact that changing a_i affects at most 3 elements,
our output = init — delta, where delta = 3, 2, 1, or 0.
I like it. thank you.
I applied the same concept. However, I have missed some case. Can you let me know some easy test case so that I can figure out my mistake? I am getting WA in test case 3 (23rd token)
23rd Token : 23 16 9 4 14 9 4
Can you let me know some easy test case or points that I missed so that I can figure out my mistake? I am getting WA in test case 3 in DIV2B(163rd token). Thank you.
2 6 1 5 10 4 6 12 6 10 8 5 15 7 6
answer — 1 1
how did you find the 23rd case?
add this:"if(count==23) {cout<<n<<' ';for(int i=0;i<n;++i) cout<<e[i]<<' ';} in your submitted code and you can get the 23th case in the WA report.See what your code output.
its alright, This will help us improve even more.
I have a doubt regarding the solution for the problem 2. What I did was that I found the max consecutive extremes(hill or valley) then from the total sum I subtracted the min(3,consecutive). So basically if there are 3 consecutive extremes then we can neutralize it and reduce it by 3. Similarly if there are 2 consecutive extremes then we can change the vaues and reduce the sum by 2. If there is atleast extreme then we can reduce it by at least 1. Please tell me what is wrong with this logic? Where have I gone wrong, so that I can improve in the next contest.
Thank you
I also did same during the contest but run your code on this test case 23 16 9 4 14 9 4. I think your code will give 0 but answer is 1.
I found my mistake overnight it was just the index when I was checking how my change affected the integer on my left... Like instead of setting i>=3 (thus the integer on my left has an integer on its left) I said i>=2 and in 5 hours of debugging I could not see it.
The problem for ranking up from Expert or Specialist to CM is not the concept of the problems. The problem is actually being able to write code with 0 bugs. Like I understand how to improve myself when it comes to the concept of problems (learn more algorithms and solve more problems) but I don't see how can I improve myself into not making mistakes while coding, I do believe solving more problems won't really help one stop making mistakes when implementing a solution.. The focus one has when implementing IMO comes from 3 importnat factors genetics, sleep and food. I will search for medication that can help one stay more focused like royal jelly and see if it makes any difference.
Hi dude, I did not participate into the actual contest but tried div2 2 in practice and spend 2 hours trying to figure out why I got WA on Test case 3 and it was a simple index error, I was having a hill_or_valley(i) function and I was assumming that i is between 2 and n — 1, but that was not always the case.
Totally agree that you can practice algorithms and logic, for example this div2 c idea has completely caught me off guard, but I also believe that you can practice not making mistakes. You can take for example WA submissions to div2 b and try to find the mistake in other people's code.
Yes I do agree that you can partially improve your debugging skills but here is the thing: Even spending a minute in debugging is costing. I'd rather spend 5 more minutes writing the correct code rather than loosing a submission (which may cost 10 minutes penalty in some cases) and then have to debug that 1 extra minute. I bought coffee for tomorrow and we will both see if the experiment will fail or succeed.
In problem div 2 C in 1ST LINE OF PROOF IN EDITORIAL::: DS007
IT SHOULD BE CRITERIA 1 NOT 2 ...PLEASE CORRECT IT.
No, I don't see what wrong in the editorial.
Please fix this => "Unable to parse markup [type=CF_MATHJAX]" in problem C and also I am not able to see the submissions.
The editorial will be translated to Russian tomorrow.
bruh
I can't view any of the author's submissions. It gives me the error:
You are not allowed to view the requested page.UPD: Fixed!
Hard, but nice quality contest! Learned the techinique of multiplying two dp values and adding them leading to the answer in D. Thanks :)
Can u explain to me that part about multiplying dp[i][j] * dp[i][k-j] where 0=<j<=K for each i in order to get the number of occurrences for each i
How does that tell us that a particular element at index i occurs in a path where it is not the beginning or the end of it
Really great explanation to C, probably one of the most beautiful problems in recent rounds. The graph modeling approach is amazing!
ScrappyDoo Can you please explain the idea ?
I'll suppose that the part about vertices and edges is clear. Suppose that we draw a rooted tree for the following example:
Notice that a-(b-c) is actually equal to a-b+c. This corresponds to the following graph example:
First we remove b, and change c for b-c, then we get the following tree:
Then we remove (b-c) and change a for a-(b-c) leading to:
This implies that we will be calculating our final answer as difference of sums of elements on even levels and sums on odd levels.
Because nodes can connect only elements from different sets we observe that we can create a tree with at least 3 levels, which turns out to be just enough to get all the nodes in a tree. Here's an example of such tree using the previously mentioned sets:
What do we see? We can include just two elements from two different sets on our odd levels and all other elements on even levels. So if mn1 and mn2 are the two smallest values that don't belong to the same set (one belongs to 1. and other to 2., one belongs to 2. and other to 3., or one belongs to 1. and other to 3. set) the answer in this case is:
As we already counted mn1 and mn2 in total sum we have to remove them twice. There's another case where we'll store one complete set on the second level and two other sets on level 1 and level 3 (I'll leave it as an exercise for you). Again we take the minimum of those three cases and compare them to our answer.
I hope this explanation was clear. TBH I'm not too good at doing these, so feel free to ask about any part of my solution.
Here's a sample implementation I've done for you to understand completely:
https://mirror.codeforces.com/contest/1467/submission/103829704
ScrappyDoo Thank you for the wonderful explanation. This is indeed a beautiful problem :)
No problem, glad you found it helpful! :)
Great explanation, but I think there is an error in the tree for a-b+c. The tree would be:
a
|
b
|
c
Yeah, I see I messed that part now. Thanks for the correction!
Hi, I thought about it a lot but still can't figure out how to determine when to add the whole set. Could you please give an example of it?
UPD: I think I figured it out.
Here we can do this,
So, we subtract d and g. But we could have also done,
Here we are able to construct the tree and delete all items from bag 2 (d, e, f).
If removing the whole bag gives a better result than removing 2 items from different bags then we remove the whole bag. i.e. if (d + e + f) < (d + g) and so on.
I think that you are overcomplicating the substraction of whole set, here's a simpler idea I've come up with.
Put single element from first set on the first level (say a).
Put all the elements from second set on the second level (d, e, f) and connect them with the only element from the first level.
Lastly connect all the remaining elements with any of the elements from second level and put them on the third level.
Here's one of approaches which solves your provided input:
We know that all the elements from last level belong to either first or third level so we can connect them with any of the elements that belong to second level (as they belong to the second set). The story is same for the first two levels.
But yes, your approach also works as there are many ways to construct a tree here.
And answer to your second comment — No problem, glad I could help!
I have a different solution for problem E. I'll explain it here. Let me know if you have any questions.
Root the tree arbitrarily. Let's define $$$x[u]$$$ as the number of paths starting at node $$$u$$$ such that the value of the node at the other end of the path exists multiple times in the path. A node $$$u$$$ is distinctive iff $$$x[u] = 0$$$. Suppose you know $$$x[u]$$$ for some node. What paths could change the answer for a child $$$c$$$? There are two possible types:
Using these facts, run a dfs starting from the root. You can pre-calculate the number of paths starting at each node of types one and two using a map. Using this, we can calculate $$$x[u]$$$ given $$$x[parent of u]$$$ (you add all paths of type 1 and subtract all paths of type 2). The answer is the number of nodes $$$u$$$ with $$$x[u] = 0$$$. Here's a link to my accepted submission: 103931989
This fails on 4 1 2 1 1 1 2 2 3 3 4 (Test 104)
It's because the '1,1' path in the subtree of 2 isn't accounted for by your two possible types.
I've edited my code to account for those paths. The general idea is still the same. Lmk if you find another hack test.
Edit: This submission was hacked too, I'll try to fix it again.
Edit 2: I fixed it, it was a small mistake (I had to swap the order of two lines)
Try printing out the pv values in your dfs2 method on this case: 12 1 3 3 1 1 1 1 1 1 1 3 1 1 2 2 10 1 3 3 4 7 9 3 5 5 7 7 8 1 11 11 12 3 6
You should see that many of these values are greater than 11 (which shouldn't be possible because given some fixed vertex, there are at most 11 other nodes a path can end at).
While your code technically gives the correct answer on this case (as it's trivially 0), for your type 2 paths, you only want to consider the number of paths starting from c which end at a node that's not in c's subtree and have exactly 2 nodes with the same value along the path (similar to the condition in type 1). Not accounting for this results in massive over-counting which accumulates in the pv values.
I'm not sure how you'd actually efficiently compute this in one dfs.
I realized that too, but it doesn't actually matter. The only cases in which I over counted don't actually matter, since everything in that subtree isn't distinctive anyway. On an unrelated note, the tests in this problem are apparently pretty weak considering my first solution was hacked on a really simple test case (but you can't really blame the authors for this since there are so many possible solutions).
Thanks a lot
Problem E is obviously a lot of ways to do it.
Can you say how you solve it ?
Can anyone explain/provide test case of why the noob method of finding cases of decreasing 1,2,3 hills/valleys and writing if statements for it does not work in problem B .
My submission
cases like this also run fine
1
6
1 3 5 2 4 6
There's something else Im missing.
update : 2,22,23,14,18,18 is the case that breaks my code
thanks :)
same doubt my submission
1 3 5 2 4 6 You have (3 5 2) and (5 2 4) but you can't fix them both without producing extra one
thanks:)
These cases are handled in my code, there something else I'm missing. Any other test case ?
Here is a test case that fails the method you describe:
23 16 9 4 14 9 4
I think my method was the same as yours. Under our method, it seems that, since the first 4 is part of valley 9-4-14 and hill 4-14-9, that we can eliminate both of those hills/valleys by simply changing the 4. However, that is not possible, since eliminating the 4-14-9 hill requires 4 to be increased to at least 14, which will create a new hill (a 16-9-x hill).
I think this corner case can be summarised as destruction of a hill compulsively creates a new valley or hill and vice versa.
For these types of cases, my code runs fine. For the input you gave my output is 1. Any other test case?
what is your answer for test case 1 3 1 3 5?
the code works for this test case its output is 0. The test case that would fail is:
2,22,23,14,18,18(Conditions for handling hv and vh pattern fail).
thanks :)
Can you tell me the intuition behind the condition. I couldn't figure it out.
It's just observation/hit and trial ..also there is a better way to solve this (the tutorial one) without caring about the corner cases.
0 . I guess its right
Can someone plz explain c in easy way ?
Ignoring the proofs of my claims, first, you calculate the sum of all numbers in all the bags. Then from this, you subtract 2 * min(sum of the 2 smallest numbers such that they appear in different bags, minimal sum of all numbers in one bag).
But what is reason behind this? Can u just give a brief ..bcz i am unable to get editorial
I have put the best proof that we could come up with in the editorial. If you want to look at it from a different perspective, try to work out how the numbers would change after an operation, and how you can make the net effect of some number positive.
Let's say that you choose bag 1 as the final bag. Then all numbers in bag 1 can be made positive. Now we try to make all elements in bag 1 positive by passing them through the minimum number in bag 2 and vice versa. However, if the net effect of this turns out to be negative, then we just flip the signs of all these numbers.
DS007 are there any similar problems to Div2C? I am encountering this variety of problem for the first time.
I found the explanation in the editorial not super intuitive (though it makes for a nicer proof).
Less formal: Essentially, you pick one number to be your final number. Then you can add any number to it, buy passing it off twice. Now you have to empty two bags, so you cannot pass the last number in the bag and therefore you subtract the minimum (instead of adding it, therefore *2). Alternatively, you can also do what happens in the first example test case and subtract one complete bucket if that is cheaper than the smallest sum of two minima.
My first idea to the problem was, that we subtract one big number from some small number, then subtract that negative difference from another big number to get a "bigger" number, than subtract that from some small number, to subtract that negative number again... and so on.
And I still not get the prove why this is not the optimal strategy. Or is it, somehow?
I went along the same lines and decided I need to create the largest possible negative numbers in two bags then finally add it to the positive numbers in the third bag. Got WA on 6. Will try some more and check if it takes me anywhere.
UPD : This does work,just got an AC. First observation is we keep one bag aside and create two big negative numbers in each of the other two bags. If you can reach this stage the answer is the sum absolute values of all the numbers.
The following is how to create these big negative numbers. Let's say the sum — minimum(note not just sum so asm + amin = sum of numbers in a) and minimum of the last two bags is asm,amin,bsm,bmin.
Now we compare bmin with asm and bsm with amin. We are trying to keep as much of the sums as possible by subtracting against the smallest number in other bag. We take abs(bmin-asm) and abs(bsm-amin) as it is possible that the minimum turns out to be larger than the other bags sm. These two are our large negatives.
There is one edge case to handle however if either of the bags happen to have just 1 element. We take abs(sum of a — sum of b) as our only negative.
How to choose which two bags to do the operations on? Just try all 3 possibilities.
Here is my solution https://mirror.codeforces.com/contest/1467/submission/103854808
I think it's correct, tho you have not mentioned your entire approach but I think, I've done something similar, maybe if this helps. 103844818
In my opinion, the easiest method to understand this problem is by analyzing the process. It's easy to see that each method of combining all the elements to obtain one single element can be reduced to some arithmetic expression.
For example If I'm having three sets of form
a1, a2 b1 c1, c2
if I try to move c2, a1, a2 to the second set, and then everything to the third set the answer will be : c1 — (b1 — c2 — a1 — a2) = c1 — b1 + c2 + a1 + a2.
From now on, if you do some kind of brute force where you try every possible way of combining the elements you will observe that there are two possible types of outputs :
1) Two random elements from dfferent sets gets subtracted from the sum of the other elements. (or twice subtracted from the total sum).
2) A whole initial set gets subtracted from the sum of the other elements (or twice subtracted from the sum).
I know this is kind of a dumb way of observing the pattern but actually I do think it might help a lot of times.
Hi, could you please explain how you determined the point 2 (1 whole initial set gets subtracted) ?
https://youtu.be/Q8mVSk9VBlc if anyone is stuck in C.
The solution code in problem C is incorrect. If you submit it to CF, it gives the verdict Runtime Error. To fix this, change the return type of the
solveTestCasefunction tovoid.I had tried all the solutions in c++17 before writing the blog, and they all gave me AC. Which version of c++ did you submit in?
I submitted in 64 bit. Here's a link to my submission: 103831188
An identical issue is answered in the stackoverflow thread
what a land contest
what a land person
Sorry but i'm confused with answer for problem D. I understand the building of dp but i dont understand the build of a[i][j] because when you take number of paths that end with i (dp[i][j]) why does it mean that the answer will be that multiplied with number of pats starting with i(because some of the paths in dp[i][j] may have a[i] several times so doesn't that change things?) Thanks in advance for the answer
dp[i][j] = number of paths of length j that start or end at i.
a[i][j] = number of paths of length k where i appears after exactly j moves.
To achieve such a path, you must start from a path of length j that ends at i. From here, you have multiple choices to complete the path. For every path of length j that ends at i, you can complete it in dp[i][k-j] ways by starting at i and moving the remaining k-j moves. Hence a[i][j] = dp[i][j] * dp[i][k-j]
Oh okay i get it now. Thanks for thr explanation :)
I am not getting how the formula of cnt[i] is valid for the case when robot moves back and forth about a[i].can you pls explain giving examples.
Yes, it's a very common confusion on such problems.
When use "cnt[i]+=(dp[i][j]*dp[i][k-j])", it's possible that the robot walk on a[i] more than once in its first (j-1) steps or its last (k-j) steps? And the answer is: absolutely yes.
But it doesn't matter, when we use "cnt[i]+=(dp[i][j]*dp[i][k-j])", it means the number of paths whose j-th step are on the a[i], and iterate for j we can get the sum of the ways. For example, if there is a path which stay at a[i] in its 1st step and 3rd-step, you may think this path contribute 2 for a[i](and it's correct), but in our method, this path contribute 1 while we calculate "cnt[i]+=dp[i][1]*dp[i][k-1]" and contribute another 1 while we calculate "cnt[i]+=dp[i][3]*dp[i][k-3]".
To conclude, cnt[i] in this problem can be decomposed by paths(yours) or j-th step(editorail's). Both are correct but only the later one works for this problem.
can you please explain a little, why dp[i][k-j] is multiplied? Thanks
Hint: dp[i][j] means not only "paths with length=j START at i", but also "paths with length=j END at i" (consider reverse the paths).
thanks understood :)
Thank you so much fried-chicken for the explanation!
No problem :)
WA on Pretest 3 of Div2B must be the biggest pandemic of 2021. Unfortunate :(
I don't understand what's wrong in my sols, I'm also getting WA on pretest 3.
Your help would be appreciated!
https://mirror.codeforces.com/contest/1467/submission/103802598
the testcase is
i believe
My solution for problem C failed on test case 17. Can anyone please suggest an easier case on which this solution is failing?
1 2 3
7
8 9
4 10 12
Solution: 36
(Ex: Subtract everything but 4 from 7 and then subtract this result from 4)
Ans = 4 - (7 - (8 + 9 + 10 + 12) ) = 36
Your code's output: 28
Got it! Thank you!
Oh, I just got it... What a brute force way for problem B, never thought like that before. I just thought to check every continuous 5 elements and check if they affect the answer by 0,1,2 or 3, and how to check is just divided them into many cases and the contest was in the evening and I just was confused by many cases by myself.
Nice problem bro.
Div2B was pretty similar to a problem from a recent contest.
I don't remember the exact problem or its code. But this is what we had to do.
We had to make a swap to minimize/ maximize the total number of minima/maxima/(minima+maxima).
I finished a DSU-on-tree solution for problem E during the contest. Here is the reviewed code with comments to explain the idea.
Problem C can be solved in another angle of thought.
Without loss of generality, lets assume that the final element will belong to bag A.
Now, think of the problem as ans = a1 + a2 + ...an + -b1 + b2 + ...bn + -c1 + c2 + ... cn
(Move all but 1 element in A to B. Move all but 1 in C to B. Move all but one in B to C. Now move all back to A. So all the elements except the ones unmoved in B and C will have a -(-) positive contribution to the sum.
There is one more possibility. Assume c1 was infinite, so a -c1 is not affordable. So we move all Cs to B and then to A, and ignore moving B twice.
Answer in this case will be Sum(A) + Sum(C) — Sum(B). Swap A, B, C and find the max case. 103801386
→ Reply
Finally became EXPERT !!!
same
Same
I can't seem to figure out the problem in my code for Hills And Valleys Problem.
I first count all the hills and valleys. Then I check if any Hill-Valley-Hill or Valley-Hill-Valley combination occurred. If this is true, I decrement the counter by 3. If not true, then I search for Hill-valley or Valley-Hill pair, In this case, I decrement the counter by 2. Else final answer is Counter -1.
It is giving me the wrong answer on the 3rd test case 21 token expected 1 found 0. Can someone tell me what am I doing wrong
1 3 5 2 4 6 check for this case
It's answer should be 1?
Can anybody help me figure out why I am getting WA for tc3 in Problem C 103860085
It took a long time to figure out and in the end it turned out to be overflow of integer.
Since each value can be 1e9 their sum can be near 1e14.
Here
10 10 10
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
Problem C. The solution looks interesting yet I find it very hard to understand it.
So we want to build a rooted tree ?
There is an additional node that is the root ? Any node is a leaf except the root ?
What is the definition of valid in : "the constructed rooted tree is valid" ?
It would be nice to have a simple example or some references : books, article, similar problems ...
https://mirror.codeforces.com/contest/1467/submission/103855499
Can anyone please tell me, what I did wrong here. It is giving this verdict on 3rd test case "wrong answer 8th numbers differ — expected: '0', found: '1'"
Nice editorial for Problem C
.
Can anyone tell me the 23rd case of test case 3?I am just curious to know what's wrong in my code!
Maybe similar with this
2
6
10 4 2 10 4 3
6
2 4 10 2 3 4
1
1
0
0
Legend how did u get it
I just thought of some test case for which my code could get wa.
Nice and clean editorial solution code! for div 2 B. Thanks.
Actually your code of problem B shouldn't take AC, (int a[N]) and (int tmp = a[i]) tmp and a[i] should be long at least according to the constraints !!
Nevermind this stupid comment
REALLY GREAT CONTEST !! NOW, AFTER STRUGGLING WITH A , I HAVE SOLVE IT NICELY AND I AM BECOME PUPIL NOW.
Can anyone please explain problem E. And also some of the topics related to it, which might help in solving it.
You can check out my editorial.It is not the best tutorial but it can give you a rough idea.
https://mirror.codeforces.com/blog/entry/86601
Can anyone explain me the below line ? and what is the role of is[] array ??
ans = min(ans, s — is[i — 1] — is[i] — is[i + 1] + isHill(i — 1) + isValley(i — 1) + isHill(i) + isValley(i) + isHill(i + 1) + isValley(i + 1));
is[i] denotes whether index i was a hill or a valley initially.
In the line that you have mentioned, I remove the contribution of indices i-1,i,i+1 to the intimidation value of the unchanged sequence. Then I find whether these indices have now become hills or valleys and update it accordingly.
Can anyone explain for me that why in prob B the answer is equal to (count of hill and valley) — x with x = 0/1/2/3?
because if you change $$$a_i$$$,only $$$a_{i-1},a_i,a_{i+1}$$$ can be effected,so x can not be greater than 3.And if there's no hills and valleys,x can not be less than 0.So x is a integer in [0,3].
Wow I don't know how do people solve problems like C. Greedy is certainly not one of my skills. Was it just a blind guess or do you actually find an intuitive way to "prove" your approaches?
I found problem D easier to approach, maybe a little bit harder to code but no so much. In fact I had to skip C during contest.
Nice problems!
I was close to solving C on my own — just made a mistake wifh the case with the whole array (I thought it can only happen when whole array has length of 1). I come up with conclusion that we should look for the biggest negative number. By blindly guessing I've realized that we can always connect two elemnents from two groups with all the other elements (e. g. erase all elements besides three twice and than erase them again which ends up being addition, than add one element and erase two that are left), I've even sketched out the edges. The thing is that they weren't supposed to create a graph, I was just tracking what I've used so far. Lmao, turns out I was right.
So I'd say I've guessed the graph modeling approach, bu t did so greedily, without any proof, but knew that it was impossible to erase only one element, shich would end up being the intended solution. I've talked to 5-6 people that have solved it — all of them did so without a proof...
VIDEO TUTORIAL FOR DIV 2 PROBLEM B WITH IN DETAIL EXPLANATION OF CREATIVE TESTCASES AND LINE BY LINE CODE HERE IS THE LINK : https://www.youtube.com/watch?v=I4oSzeygRzs HOPE YOU GUYS WILL ENJOY THE VIDEO !!!!
I didn't get this part from problem D, how is it the same?
$$$dp_{i,j}$$$ is the number of good paths of length $$$j$$$ that end at cell $$$i$$$, then the reverse of those paths are paths of length $$$j$$$ that start at cell $$$i$$$
Oh, that makes sense, I'm wondering how did I miss thinking about the reverse part.
Thank you :)
Задача B: Затем для каждого валидного индекса i посчитаем, как поменяется кол-во холмов/долин среди {ai−1,ai,ai+1}
Почему так получается? Ведь по условию задачи мы меняет не один элемент, а все элементы с таким числом. Допустим, в этой ситуации мы меняем число 2 под индексом 2 на своего соседа, убрав, например, 1 холм, но при этом создав холм+равнина где-то в другом... Никак не могу понять это решение.
"Ведь по условию задачи мы меняет не один элемент, а все элементы с таким числом." нигде в условии этого не сказано
Nice contest
can somebody easily explain C. Three Bags problem??
You can check out my editorial.It is not the best tutorial but it can give you a rough idea.
https://mirror.codeforces.com/blog/entry/86601
thank you
Can anyone explain this paragraph of editorial of Problem D?
Let ai,j denote the number of times cell i appears after exactly j moves in all valid paths of length k. Well ai,j=dpi,j∗dpi,k−j because we can split a path of length k into two paths of length j and length k−j, with the first path ending at cell i and the second path starting at cell i.
For each i, we want to calculate how many times the cell i occur in all good paths, right ? this is the goal. Let f[i] denote that.
Consider a good path of length k [x_0, x_1, x_2, ..., x_k].
Do you see that f[i] is equal to the SUM of the following:
'
'
So, the task now, for each j in [0, k], we need to calculate how many times a cell i occur in a good path in position j = " After j move" ? Let a[i][j] denote that.
Let's now consider how we can calculate a[i][j] for specific i and j.
Consider a good path of length k in which cell i appeared after j move, It will look like this
[x_0, x_1, ....., cell i , ......x_k]
Do you see that this path can be broken down into 2 paths:
a path of length j which ends with cell i
a path of length k — j which starts with cell i
Let dp_en[i][j] denote number of paths of length j ending at cell i
Let dp_st[i][j] denote number of paths of length j starting at cell i
we know that any path of the first type can be joined with any path of type 2 to make a length-k path that contain cell i after j move. meaning a path that we should count it in when calculating a[i][j].
Hopefully, It's clear now that
a[i][j] = dp_en[i][j] * dp_st[i][k-j]. This is the key conclusion.
now one extra unnecessary observation is that dp_en[i][j] = dp_st[i][j] for all i and j
which means that
a[i][j] = dp_en[i][j] * dp_en[i][k-j]
The task now is to calculate dp_en[i][j], This is a simple dynamic programming task.
Given dp_en[i][j] -> a[i][j] -> f[i] -> ans
If any thing is not clear, please tell me
Very well explained , Thank You :)
Problem D
I didn't understand solution. But I am now.
Bye !
I highly doubt about Problem C solution: the summation of given data should overflow 32bit integer. Any thoughts?
define int long long
Ah. Thanks.
Problem E honestly feels like it should be 2000/2100, here is an alternate brainless solution:
Observations:
Let us call the region between red nodes (which contains distinctive roots wrt this value of x), a "good zone". Now, we can just do a dfs while maintaining the set of current good zones we are in. Any node $$$u$$$ which is in the good zone of all the values which have $$$ \gt 1$$$ occurences, will be a distinctive root.
Implementation: link
can you add this hack for E?
my wrong submission 288000968 which ACed. My code prints 1, but answer is 0.