Thanks for participation!
Editorial
Tutorial is loading...
Code
#include<bits/stdc++.h>
using namespace std;
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int tests;
cin >> tests;
while (tests--) {
int n, m;
cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m));
for (auto &i: a) {
for (auto &j: i) cin >> j;
}
if (n * m == 1) cout << "-1\n";
else {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cout << a[(i + 1) % n][(j + 1) % m] << ' ';
}
cout << '\n';
}
}
}
}
Editorial
Tutorial is loading...
Code
#include<bits/stdc++.h>
using namespace std;
void solve() {
int n;
cin >> n;
string s, t;
cin >> s >> t;
for (int i = 0; i < s.size() && s[i] == '0'; ++i) {
if (t[i] != '0') {
cout << "NO\n";
return;
}
}
cout << "YES\n";
}
int main() {
int t;
cin >> t;
while (t--) solve();
}
Editorial
Tutorial is loading...
Code
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int tests;
cin >> tests;
while (tests--) {
int n;
ll x;
cin >> n >> x;
vector<ll> a(n + 1);
for (int i = 1; i <= n; ++i) cin >> a[i];
partial_sum(a.begin() + 1, a.end(), a.begin() + 1);
vector<int> dp(n + 2);
for (int i = n - 1; i >= 0; --i) {
int q = upper_bound(a.begin(), a.end(), a[i] + x) - a.begin();
dp[i] = dp[q] + q - i - 1;
}
cout << accumulate(dp.begin(), dp.end(), 0ll) << '\n';
}
}
Hint
Pigeonhole principle
Editorial
Tutorial is loading...
Code
#include<bits/stdc++.h>
using namespace std;
int main() {
int tests;
cin >> tests;
while (tests--) {
int n;
cin >> n;
vector<int> a(n);
for (auto& i : a) cin >> i;
vector<int> pos(n);
iota(pos.begin(), pos.end(), 0);
vector<pair<int, int>> ans;
for (int i = n - 1; i; --i) {
vector<int> occ(i, -1);
for (auto j : pos) {
if (occ[a[j] % i] != -1) {
ans.emplace_back(j, occ[a[j] % i]);
pos.erase(find(pos.begin(), pos.end(), j));
break;
}
occ[a[j] % i] = j;
}
}
reverse(ans.begin(), ans.end());
cout << "YES\n";
for (auto [x, y] : ans) cout << x + 1 << ' ' << y + 1 << '\n';
}
}
Hint
Solve for one tree
Hint.answer
Answer is size of tree
Hint.proof
Let sizes of deleted subtrees be $$$a_1, a_2, \ldots a_m$$$. We know that $$$a_1 + a_2 + \ldots + a_m = n$$$. Then we know that $$$a_1 | a_2 \ldots a_m \leq n$$$. To proof that lets see bits separately. It will add $$$1$$$ to result, if one of bits is $$$1$$$, $$$0$$$ otherwise, but this is not more than their sum.
Editorial
Tutorial is loading...
Code
#include<bits/stdc++.h>
using namespace std;
void solve() {
int k;
cin >> k;
vector<int> a(k);
for (int i = 0; i < k; ++i) {
cin >> a[i];
for (int j = 0; j < a[i] - 1; ++j) {
int trash;
cin >> trash;
}
}
sort(a.begin(), a.end(), greater<>());
int ans = 0;
for (auto x : a) {
for (int h = 23; h >= 0; --h) {
int ca = ans >> h & 1, cx = x >> h & 1;
if (cx == 0) continue;
if (ca == 0) ans |= 1 << h;
else {
ans |= (1 << h) - 1;
break;
}
}
}
cout << ans << '\n';
}
int main() {
int t;
cin >> t;
while (t--) solve();
}
Editorial
Tutorial is loading...
Code
#include<bits/stdc++.h>
using namespace std;
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int tests;
cin >> tests;
while (tests--) {
int n, m;
cin >> n >> m;
vector<vector<int>> black(n);
vector<int> edg(m);
vector<vector<int>> g(n);
for (int i = 0; i < m; ++i) {
int x, y, c;
cin >> x >> y >> c;
--x, --y;
edg[i] = x ^ y;
g[x].push_back(i);
g[y].push_back(i);
if (c == 0) {
black[x].push_back(i);
black[y].push_back(i);
}
}
vector<int> deg(n);
for (int i = 0; i < n; ++i) deg[i] = g[i].size() & 1;
vector<bool> del(m, false), used(n, false);
auto dfs = [&](auto dfs, int u) -> void {
used[u] = true;
for (auto id : black[u]) {
int to = edg[id] ^ u;
if (used[to]) continue;
dfs(dfs, to);
if (deg[to]) {
del[id] = true;
deg[to] ^= 1;
deg[u] ^= 1;
}
}
};
bool ok = true;
for (int i = 0; i < n; ++i) {
if (used[i]) continue;
dfs(dfs, i);
ok &= !deg[i];
}
if (!ok) {
cout << "NO\n";
continue;
}
auto euler = [&](auto euler, int u) -> void {
while (!g[u].empty()) {
int id = g[u].back();
g[u].pop_back();
int to = edg[id] ^ u;
if (del[id]) continue;
del[id] = true;
euler(euler, to);
}
cout << u + 1 << ' ';
};
cout << "YES\n";
cout << m - accumulate(del.begin(), del.end(), 0) << '\n';
euler(euler, 0);
cout << '\n';
}
}
Hint 1
Think of the most stupid solution you can do
Hint 2
Do memorization and some cuts
Hint 3
Done!
Editorial
Tutorial is loading...
Code
#include <bits/stdc++.h>
using namespace std;
int n, k;
vector<vector<bool>> memo;
string res;
vector<int> cnt;
string s;
bool rec(int i, int cur) {
if (i == k) {
if (cur == 0) {
return true;
}
return false;
}
if (memo[i][cur]) return false;
memo[i][cur] = true;
for (int c = 0; c < 2; ++c) {
int q = cur;
if (c == 0) q += cnt[i];
else q += n - cnt[i];
if ((q & 1) == s[i] - '0') {
if (rec(i + 1, q / 2)) {
res += char(c + '0');
return true;
}
}
}
return false;
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int tests;
cin >> tests;
while (tests--) {
cin >> n >> k;
cin >> s;
reverse(s.begin(), s.end());
cnt = vector<int>(k);
for (int i = 0; i < n; ++i) {
string t;
cin >> t;
reverse(t.begin(), t.end());
for (int j = 0; j < k; ++j) cnt[j] += t[j] - '0';
}
memo = vector<vector<bool>>(k, vector<bool>(n, false));
res = "";
rec(0, 0);
if (res.empty()) cout << "-1\n";
else cout << res << '\n';
}
}
Editorial
Tutorial is loading...
Code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
cout << "? aa" << endl;
int p, v[10];
cin >> p; p--;
cout << "? zzzzzzzzzz" << endl;
int hsh, hsho;
ll nom = 0, cnt = 1;
cin >> hsh;
hsho = hsh;
hsh++;
for (int i = 0; i < 10; i++) {
nom += 26 * cnt;
cnt *= p;
v[i] = 26 - (hsh % p);
hsh /= p;
}
string s;
cnt = 1;
ll ch = 0;
for (int i = 0; i < 10; i++) {
if (v[i] < 1) {
v[i] = 26;
v[i + 1]--;
}
ch += cnt * v[i];
cnt *= p;
s += 'a' + (v[i] - 1);
}
cout << "? " << s << endl;
int ans;
cin >> ans;
cout << "! " << p << ' ' << ans + nom - ch - hsho << endl;
}
int32_t main() {
int t;
cin >> t;
while (t--) {
solve();
}
}
D is a cute problem
na
na
na
na
na
74Traktor never lets me down....
na
na
every dsu problem is a cute problem :3
What is E?
Why are people down voting?
Editorial is so fast.Thank You!
CDE are very nice
the editorial came faster than my girlfriend
thank you for fast editorial
Great editorial for problem G
C is also solvable in $$$O(n)$$$ using two pointers.
Yeah I tried it using two pointers but got wrong answer on 776th number of test case 2. Can you check my code, where am I wrong?
Cant identify exact mistake in code but for input
correct output is $$$15$$$, your code prints $$$14$$$ instead.
Thanks for test case. I will check it.
Bro please share your approach Thank you bro
can you please explain how?
This is my code: 271271875
So if we start at mushroom $$$i$$$ with $$$g=0$$$ before performing any operations we will hit $$$g=0$$$ again at some $$$j\geq{i}$$$.
There might be multiple possible values of $$$j$$$ for $$$i$$$ since $$$g$$$ might become zero multiple times over and over again.
We only need to calculate the smallest such $$$j$$$. Let that number be $$$l_i$$$.
If $$$j$$$ doesn't exist that means we got to the end of the array and still $$$g\leq{x}$$$. In that case we can assign $$$l_i=-1$$$.
Now if we choose $$$l=i$$$, $$$r$$$ can't be $$$l_i$$$ because in that case g will result in zero. Now if we choose $$$l=i$$$, $$$r$$$ can't be $$$l_i$$$ because in that case g will result in zero.
But $$$l_i$$$ is not the only $$$r$$$ we aren't allowed to pick. Lets say we don't pick $$$r=l_i$$$ and instead go further. Next index $$$k$$$ when $$$g$$$ will hit $$$0$$$ will be
$$$l_{l_{i}+1}$$$
Now let $$$dp_i$$$ represent how many values $$$r\geq{i}$$$ we can't pick. The transition is $$$dp_i=1+dp_{l_i+1}$$$. Array $$$dp$$$ can be calculated in $$$O(n)$$$ by for loop going from last to first element.
Now we will for every $$$1\leq{l}\leq{n}$$$ calculate the number of possible values of $$$r$$$. It is equal to $$$n-l-dp_l$$$ (0-indexed). The total sum is the answer.
How will the next index $$$k$$$ when $$$g$$$ will hit $$$0$$$ be $$$l_{l_i +1}$$$?
edit: got it
edit q: how this works? wont the time complexity be $$$O(n^2)$$$?
No, we will go through array $$$a$$$ exactly twice while calculating $$$l$$$ because we know $$$l_i<l_{i+1}$$$ so there is no need to go back to calculate each $$$l_i$$$.
Time complexity for that part will be $$$O(2n)$$$ which is $$$O(n)$$$.
can you explain how you got it
lli+1?i did like this,idk what is the issue
cant we solve problem C like this-
1.first applying sliding window and count all the subarras having toxicity less then equal to x.
now it said process can continue and we have to see if at last it is not zero,so we calculate the min element less then or equal to x from end of the array, let kth posn.
2.and then again applying sliding window from start to kth posn to find all subarray whose sum>x.
then just add both 1 and 2.
Unfortunately that won't work, try to find another solution.
Can u plz tell why?
Wait I didn't fully understand your solution can you explain it little more?
Because it looks like $$$O(n^2)$$$ complexity.
i was writing the soln,but during typing I got what was wrong,thanks!!
by the way i wanted one tip.
i am able to solve problem up to 1100 rating outside contest.but in the contest idk why I cant solve.
and also I take much time I think,is there any way to upgrade my skill and speed
Solving problem in practice and in contest is same so don't think about rating or points while in the contest.
And only way to improve skill and speed is by practicing I guess.
Ok, thanks!!
for B According to given solution if s = 010000 and t = 001111 then answer is "NO" but actually answer is "YES" . Please correct me if I am missing any thing.
no
010000 -> 011111 l = 2, r = 6
011111 -> 001111 l = 1, r = 2
So s can be made into t so correct answer is "YES" right ,why "NO" ?
The answer is no. 0 xor 0 isnt 1.
where is there 0 xor 0(this isn’t 0 indexed)
you can use first 2 values of s to make equals to 2nd string.
0 xor 0 is not 1
010000 001010
how this will yes, can u show the steps as before
l=4,r=5
s = 010000; l = 5, r = 6 => s = 010001; l = 4, r = 5 => s = 010011; l = 3, r = 4 => s = 010111; l = 2, r = 3 => s = 011111; l = 1, r = 2 => s = 001111 = t. The answer is "YES". i = 2 — the position of the first '1' in s, and there are only '0' in the interval [1, i) in t, so, according to given solution the answer is also "YES".
one question, why do we need to do this operation in the reversal order(starting with an end)?
We don't need, we can do l = 2, r = 3, ..., l = 5, r = 6, and then, l = 1, r = 2.
thank you) cause in the editorial, there was written — "acting from the end"
The answer would be "YES". Note that "NO" would be the answer iff there is a '1' in t and '0' in s, and the count of '1' in s before this index is 0.
It is to be noted if '1' appears in s before a particular index, all the elements after the index can be made either '0' or '1'. Self xor is allowed, and thus, we can make any element that's '1' to 0.
In the above example, at index = 1, it's impossible to make '0' to '1' (to match the strings).
Here is my solution, you can have a look: 271233150
Personally, I think $$$E$$$ should be should be placed as $$$C$$$, as it only requires knowing about OR, which is pretty popular as a simple adhoc problem.
this problem is too troll, if it's placed as C i think i can prolly solve it in 10 min lol
hey can you share some resources to study for bitwise operation. I always find it difficult whenever i have to deal with these types of question
after solving it today, i also agree with you. the idea isn't that complicated
I created video editorial for C
Another idea for A:
we use the fact that x != (x+1), so we set b[i][j]=a[i][j]+1 and if a[i][j]=(n*m) we make b[i][j]=1.
[deleted]
this is the best idea i felt till now
Thanks for sharing
I totally did not guess D, and wrote wrong solution for E but luckily I had some bugs so it passed.
Real
Thanks for fast editorial!
Any Minecraft players :D
Easier sol for A: 271203621
can anyone explain the approach of c with two pointers without DP
you have to dp some way or the other
If we choose i as l, we have maximum n-i choices for r. (0<=i<n). When we take i as I and r as n-1 and if we calculate g for all positions from i to n-1, we may encounter ct positions where g is zero. This is a significant finding, as it means there are ct indices that cannot be r if i is chosen as l. To keep track of this crucial information, we introduce an array c[n], which stores the number of zeros encountered when i is chosen as I and r is chosen as n-1. Now, we only need to find array c[n]. Now, we will define an array sum[n], which will store g if we calculate it backward from n-1 to 0. Lets say the resulting array is something like this [-,-,-,-,0,-,-,-,0-,-,-,-] let say the position of zeros be x and y, (y>x). So for all indices x<i<=y, we take i as l and n-1 as r, then we will encounter only one position with g equals zero. Similarly, for all 0<=l<=x and r=n-1, we will encounter two indices with g=0. Extend this to a general case, and we have an array that gives c[i] (number of indices at which g=0 if l=i and r=n-1). Then we have ans=summation(n-i-c[i]).
Editorial of F: "Lets solve independently for each component." Task statement of F: "It is guaranteed that you can reach any house from any other by walking on the roads with NPCs only."
Editorial means to solve for each component consisting of only black edges.
Oh, yeah. My bad
Thank you for fast editorial!
D was a really cool problem. orz
Can somebody please explain why my solution for D is getting accepted. I have literally zero idea (according to me, it should have given TLE).
Here is the link: 271248022
Any help would be appreciated.
help me, why we need to solve from end in problem C ?
dp(i) means count of all good subarrays with i as starting point which is easier to do as transition is O(1) time comp. while if we take for dp(i) as count of good subarrays such that ending at i then transitions are not possible in O(1) but O(n) complexity as there are continuous ranges of index one or more j<=i at which we can always end at i with a nonzero value.
For Problem 1994E - Wooden Game we could also sort tree sizes decreasingly, and then add each one to the answer if it adds bits for all possible highest positions, checking with
(ans | size) == (ans ^ size), and decreasingsizeuntil this requirement is met.as size of the array and arr[i] both are up to 1e6, then how can we say that it won't give TLE ??
Is there any proof for this??
Please share it will he helpful
The sum of all tree sizes (
kandn) is up to 1e6 over all testcases, so in total you will have at most 1e6 decrements.sorting in not required
What's $$$mod$$$ in the editorial to H?
mod is m that we need to find
Then I don't get how querying any string with non-modulus hash in $$$[h_1-a_1-m, h_1-a_1-1]$$$ is enough to find $$$m$$$. Suppose $$$h_1=10^{15}$$$, $$$a_1=0$$$, $$$m=1000$$$ and we ask about some string with real hash equal to $$$999999999999050$$$ and get $$$50$$$ as answer. How can we know that $$$m=1000$$$? It could also be equal to $$$100$$$ for example.
We know that $$$h_2 \ge h_1 - a_1 - m$$$($$$h_2$$$ is hash of found string), so $$$m$$$ can't be $$$100$$$. $$$m = (h_1 - a_1) - (h_2 - a_2)$$$, where $$$a_2$$$ is $$$h_2$$$ $$$mod$$$ $$$m$$$.
if m=100 in this case 999999999999050<h1-a1-m
Huh, ok, I think I get it, thanks.
G < F I think, but I have another solution with simple dp.
Must D has a sulution?Why don't I see "No" in the code of editorial of D?
why is that true? I don't get it
PS: nvm, understood
There always is a solution
Why is this true?
Because there are $$$x + 1$$$ numbers from $$$0$$$ to $$$x - 1$$$.
ah I see so we are looking at $$$a_i \mod x$$$
Idea for D for anyone who is a bit confused :)
The answer will always be possible due to the pigeonhole principle.
For example let’s say we have 5 vertices labeled a, b, c, d, e . We start with the 4th operation. In this case, we are looking at the vertices where the values are taken modulo 4. The possible remainders are 0, 1, 2, and 3. Since we have 5 vertices, at least one remainder must repeat (by the pigeonhole principle).
For example, if vertices a and b both have the same remainder when divided by 4, we can connect these vertices.
What if there is more than one pair of vertices with the same remainder when divided by 4? We can choose any of these pairs. It won’t affect the final answer.
Suppose we connect a and b . We can mark this component as A . Now we have 4 different components: A, c, d, and e . Next, we proceed with the 3rd operation. Using the same logic, we connect two components where vertices share the same remainder modulo 3.
Why Not Start with the First Operation? If we started from the first operation, we might encounter problems. For example, suppose we connect a and b in the first operation and then b and c in the second operation. When we reach the third operation, the remainders modulo 3 for vertices a, b, c, d, and e might be something like 0, 0, 0, 1, 2 . Now we can’t pick any pair of vertices to connect because vertices a, b, and c are already in the same component.
By starting from the (n-1) -th operation and working our way down to the first operation, we ensure that we can always find pairs of vertices to connect, gradually reducing the number of components until the graph is fully connected.
By starting from the (n-1) -th operation and working our way down to the first operation, we ensure that we can always find pairs of vertices to connect, gradually reducing the number of components until the graph is fully connectedhow can we prove this ?
upd: Resolved
How ?
Thanks for explanation :)
Great explanation!
way better explanation than the editorial
Thanks for your explanation, it makes far more sense to me than the editorial one.
But still I have 2 doubts:
"What if there is more than one pair of vertices with the same remainder when divided by 4? We can choose any of these pairs. It won’t affect the final answer." -> Why??
"Now we can’t pick any pair of vertices to connect because vertices a, b, and c are already in the same component." -> why can't such case happen when operations are performed in reverse order?
update: understood by doing dry run in both order.
Thank you so much
I have also used same logic..
Simpler implementation: MY SUBMISSION LINK
why does this code fail for C
Has anyone solved problem D with max-flow?
I’ve tried, but it seems to be wrong.I can’t guarantee that the graph is connected.The graph I make may contain loops.
can someone explain the segtree approach for C ?
C without DP: 271240394
why the loop runs from n-1 and not from start?
reason 1. for any loop dp[i] =function(dp[j],dp[j2],dp[j3].....)
then if all j's are less than i then we have to calculate lesser dp values for lesser i's first in order to do above calculations correctly,so we have to calulate all dp's looping from i=small vale to i=maxvalue
similarly if all j's are greater than this i then we do looping in decreasing order
Thanks for the reply, but still i can't get it.
Can you pls explain your solution? Thanks.
I heard that this contest is hard to remark.
Anyway I didn't sign up for it :D
My submission 271300995 for F got TLE on testcase 81 for some reason. Anyone have any idea why?
I wonder why problem G is much too easy.
74TrAkToR never let me down :))))
In all, being 74 rounds means higher chance of being sponsored but higher chance of low quality.
That is really laughing.
Wait... D has no answer '-1'?
for the first time ever the tutorial code is really clean, also F reminds me of https://cses.fi/problemset/task/2179
The simple solution for problem A is to increase every element by one and n*m integer change into 1.
1994E - Wooden Game
You are given a forest of k rooted trees. Lumberjack Timofey wants to cut down the entire forest by applying the following operation:
Select a subtree† of any vertex of one of the trees and remove it from the tree.
Timofey loves bitwise operations, so he wants the bitwise OR of the sizes of the subtrees he removed to be maximum. Help him and find the maximum result he can obtain.
Why do I think that each operation can only remove one subtree, so it can't get all the numbers from 1 to size?
Start deleting from the leaf nodes one by one . Then as soon as you get the required size, you can delete the entire tree.
During contest in Last 15 minutes site stops working after robot verification starts that causes not able to submit solution have writtens.
C is solvable in O(n) using prefix sum and 2-pointer: https://mirror.codeforces.com/contest/1994/submission/271259457
I have a question about problem E.Think about this test case: 2 trees with size 20 and 12,the shape of size 20 tree doesn't matter and the shape of size 12 tree look like this:
every other vertex is the son of vertex 1.the Editorial code gives the ans = 31,which requries to get a 8-size subtree and a 3-size subtree from the 12-size tree.I don't think it's possible to get both subtree at the same time!
Edit:oh I figured it out.First delete a vertex,then delete the whole tree will do..
can you suggest, how to handle bitwise problem efficiently during contest. They always makes me uncomfortable
[user:man-ray]can you please explain. I'm having same doubt.
.
https://mirror.codeforces.com/contest/1994/submission/271343266
This is my code for pB . I want to know where I wrote it wrong.
The problem only happens when you use char array, suggested by my testings. I still don't know the cause though, if anyone knows please explain, thanks.
The problem occurs when you have an array of size exactly n for an n character long string. If you change from
to
it would work fine. I believe this happens because the last character of an array of char must be '\0' or null character but I don't know the details lol.
Hello Codeforces I have a doubt regarding problem D. I dont understand why this Code is passing the testcases .It should give TLE right? so why it is passing the testcases and getting accepted. Any help would be appreciated. Thank you
can anyone prove or uphack my solution for A? i just try $$$100$$$ different permutation of $$$[1, 2, \ldots, n \times m]$$$ and it got accepted.
I didn't prove, but except for the obvious $$$n=m=1$$$ case it seems like the worst chance for a random permutation to satisfy it is $$$1 \over 3$$$ when $$$n \times m=3$$$, so the chance of not finding an answer with 100 tries is $$$~2.46 \times 10^{-18}$$$. Even if we try hacking it $$$10^9$$$ times it will still almost surely pass.
... I didn't see that the random seed could be hacked, lol
Problem D, why n=1?
I believe upper bound for sum in problem G is n-1, can anybody prove it formally?
submitted code for a 959 A diverse game getting failed testcase on vscode and output is wrong but here it got accepted.how so???
It was a really nice contest.. I don't understand why so many downvote.. Upsolving was really fun.. Especially d, e, and g.. Thanks for such contest
In Editorial D , I think it must be before operation x not after operation x , there will be x+1 connectivity components in the graph .
CAN ANYONE TELL HOW TO APPROACH BIT MANIPULATION PROBLEMS?
is there any theory like how we should approach and all??
there are certain properties of each of the bitwise operation, and bit manipulation problems requires you to implement those properties into your code. Ex: if a XOR b = c, then a XOR c = b, ...
Just learn and solve along the way, I guess
by the way i wanted one tip.
i am able to solve problem up to 1100 rating outside contest.but in the contest idk why I cant solve.
and also I take much time I think,is there any way to upgrade my skill and speed
can someone tell me whats wrong with the code , i have tried to read the editorial of the G question and replicated the same , but it exceeds time limit.
cant we solve problem C like this-
1.first applying sliding window and count all the subarras having toxicity less then equal to x.
now it said process can continue and we have to see if at last it is not zero,so we calculate the min element less then or equal to x from end of the array, let kth posn.
2.and then again applying sliding window from start to kth posn to find all subarray whose sum>x.
then just add both 1 and 2.
For F, it's saying "If a component has an odd number of vertices with odd degree". How this is possible? Shouldn't each connected component always has even degree, since adding or removing an edge adds +2/-2 degree?
nvm, i got it, it's the vertex with odd degree not the whole connected component.
I didn't get the proof of D. Suppose there are two edges that can be formed with a certain x. Suppose the edges are e1 and e2; again with a value less than x we can form one edge that is either of e1 and e2, let's say e1. What if we add edge e1 first with x and then again we have the only choice to add e1. How the solution is getting optimal so that it is passing this?
One more thing... When we are merging nodes why the assignment of parent doesn't matter. Suppose a can be parent of b and b can be parent of a. Why choosing any of them is fine?
The pigeonhole principle suggests that such situation cannot exist. If each of $$$x+1$$$ values are one of $$$x$$$ kinds then there must be at least one value that appears more than once. If there are $$$x+1$$$ components, you can pick any one vertex from each component and perform modulo $$$x$$$, then each value has to be one of $$$0$$$, $$$1$$$, ..., $$$x-1$$$, total of $$$x$$$ kinds, so at least one value should appear on at least two components, so you can add an edge between them.
The merging part is nothing other than a DSU. It's a basic topic so I suggest you to search for it and learn.
Would F be solvable in a similar way if there wasn't the constraint that all houses can be reached using NPC only roads? I got caught up on this case for a while until I reread the constraint.
D is one problem that has a very brilliant solution.
Problem D: "Since the order of operations is not important" Could someone please explain this part?
It means we can add edges for any order of $$$x$$$, not only $$$1,2,3,...,n$$$.
E has a nice bigger friendly solution too. As said in the editorial, we can make any number from 1 till n in a tree with size n, we will try to answer greedily. It is quite clear we will definetely need the largest tree. We can remove it and add it to our answer. After that for every n, we will iterate from $$$ 1 ... n $$$ and we will get two variables $$$ x$$$ and $$$y$$$ such that $$$ x + y = n $$$. Now, we just need to maximize our answer. We can save a previous variable and then the calculation would just be
There is also an overcomplicated implementation by actually storing all the trees in the forest and then doing subtree dp with dfs. Submission
wtf
In Problem E, the editorial says that if we have a bit set in sizes of two trees then we can set all other lower bits using that but this case is not possible if we can't always break the tree in desired size. For example for test case
there are two trees with size 8. but by breaking the second tree we can only obtain 1 tree of size 4 and 4 tree of size 1. Thus breaking that tree into tree of size 4 and size 2 simultaneously is not possible. So the answer for this case should be 13 (8 | 4 | 1).
Someone please correct me if i'm wrong.
the answer for this case will be 15. you can remove one of the trees completely. then you can remove one leaf from second tree and then the remaining 7 nodes. total will be $$$ 8 | 1 | 7 = 15 $$$
The easiest approach for Problem-A is:
To transverse to each and every element of matrix A and decrement it by 1 i.e. A[i][j] -= 1. then find zero and replace it with n*m. AND report the following matrix as B.
271203176
I have made a video explaining the problem C. Hungry Games. Do check it out at:
https://www.youtube.com/watch?v=_FMUfMAVVVw
For problem D, I have a seemly stupid question but I got very confused. Are the integers given distinct in the array? Or does it matter if it is not?
it doesn't matter
first time to see problem like D and E. i have to it's genius idea and i love it so much
splendid round, thanks!
For E the statement “we can make every number from 1 to the size of the tree” of editorial is not correct as some even numbers cannot be made because of or with 1.
correct me if Im wrong.
D is cool