We hope you enjoyed the problems!
Rate the contest!
2245A - Кто сторожит свиносторожей?
Solution
Tutorial is loading...
Code
for _ in range(int(input())):
n, k = map(int, input().split())
s = input()
if k * 2 > n:
print(-1)
continue
ans = 0
for i in range(k):
ans += int(s[i] != 'R') + int(s[n - i - 1] != 'L')
print(ans)
Rate the problem!
2245B - Удалить и сконкатенировать
Solution
Tutorial is loading...
Code
for _ in range(int(input())):
n, c = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
for i in range(n):
a[i] -= c
for i in range(n // 2):
a[i] = max(a[i], 0)
print(sum(a))
Rate the problem!
Solution
Tutorial is loading...
Code
for _ in range(int(input())):
n, k = map(int, input().split())
if n == 1:
if k == 1:
print("YES")
print(0)
else:
print("NO")
continue
k ^= n
if k.bit_length() > (n - 1).bit_length():
print("NO")
continue
s = list()
if 0 < k <= n - 1:
s.append(k)
elif k:
s.append(n - 1)
s.append((n - 1) ^ k)
s.append(0)
a = s[:]
for i in range(n):
if i not in s:
a.append(i)
print("YES")
print(*reversed(a))
Rate the problem!
2245D1 - Построение массива (простая версия)
Solution
Tutorial is loading...
Code
#include <bits/stdc++.h>
void solve() {
int n, m;
std::cin >> n >> m;
std::vector b(n, std::vector<int>(n));
while (m--) {
int o, i, j;
std::cin >> o >> i >> j;
i--;
j--;
b[i][j] = b[j][i] = o;
}
std::vector<std::vector<int>> g(n);
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
if (b[i][i] == 1 && b[j][j] == 2) {
if (b[i][j] == 1) g[j].push_back(i);
else g[i].push_back(j);
}
}
std::vector<int> d(n), ans(n);
for (int u = 0; u < n; u++) for (auto v : g[u]) d[v]++;
int cnt = 0;
std::queue<int> q;
for (int u = 0; u < n; u++) if (!d[u]) q.push(u);
while (!q.empty()) {
int u = q.front();
q.pop();
if (b[u][u] == 1) ans[u] = ++cnt;
else ans[u] = -(++cnt);
for (auto v : g[u]) if (!--d[v]) q.push(v);
}
if (cnt == n) {
for (int i = 0; i < n; i++) for (int j = i; j < n; j++) {
if (b[i][j] == 1 && ans[i] + ans[j] < 0) return void(std::cout << "NO\n");
if (b[i][j] == 2 && ans[i] + ans[j] >= 0) return void(std::cout << "NO\n");
}
std::cout << "YES\n";
for (int i = 0; i < n; i++) std::cout << ans[i] << " \n"[i + 1 == n];
} else {
std::cout << "NO\n";
}
}
int main() {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
int t;
std::cin >> t;
while (t--) solve();
}
Rate the problem!
2245D2 - Построение массива (сложная версия)
Solution
Tutorial is loading...
Code
#include <bits/stdc++.h>
void solve() {
int n, m;
std::cin >> n >> m;
std::vector d(2, std::vector<int>(n));
std::vector<std::vector<std::pair<int, int>>> g(n);
while (m--) {
int o, i, j;
std::cin >> o >> i >> j;
o--;
i--;
j--;
g[i].emplace_back(j, o);
g[j].emplace_back(i, o);
d[o][i]++;
d[o][j]++;
}
std::queue<int> q;
std::vector<bool> vis(n);
for (int i = 0; i < n; i++) if (d[0][i] == 0 || d[1][i] == 0) q.push(i), vis[i] = true;
std::vector<std::pair<int, int>> t;
while (!q.empty()) {
int u = q.front();
q.pop();
if (d[0][u] == 0) t.emplace_back(u, -1);
else t.emplace_back(u, 1);
for (auto [v, o] : g[u]) if (!--d[o][v] && !vis[v]) {
vis[v] = true;
q.push(v);
}
}
if (t.size() < n) return void(std::cout << "NO\n");
std::cout << "YES\n";
std::vector<int> ans(n);
std::reverse(t.begin(), t.end());
for (int i = 0; i < n; i++) ans[t[i].first] = (i + 1) * t[i].second;
for (int i = 0; i < n; i++) std::cout << ans[i] << " \n"[i + 1 == n];
}
int main() {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
int t;
std::cin >> t;
while (t--) solve();
}
Rate the problem!
Solution
Tutorial is loading...
Code
#include <bits/stdc++.h>
void solve() {
int n;
std::cin >> n;
std::vector<std::vector<int>> g(n);
for (int i = 0; i < n - 1; i++) {
int u, v;
std::cin >> u >> v;
u--;
v--;
g[u].push_back(v);
g[v].push_back(u);
}
std::vector<bool> vis(n);
long long ans = 0;
int c = 0;
auto dfs = [&](auto&& self, int u) -> void {
vis[u] = true;
for (auto v : g[u]) {
if (g[v].size() & 1) ans += c++;
else if (!vis[v]) self(self, v);
}
};
for (int u = 0; u < n; u++) if (~g[u].size() & 1 && !vis[u]) {
c = 0;
dfs(dfs, u);
}
for (int u = 0; u < n; u++) for (auto v : g[u]) if (v > u) ans += g[u].size() & g[v].size() & 1;
std::cout << ans << "\n";
}
int main() {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
int t;
std::cin >> t;
while (t--) solve();
}
Rate the problem!
Solution
Tutorial is loading...
Code
M = 998244353
N = 501
fac = [0] * N
fac[0] = 1
for i in range(1, N):
fac[i] = fac[i - 1] * i % M
inv = [0] * N
inv[-1] = pow(fac[-1], M - 2, M)
for i in range(N - 2, -1, -1):
inv[i] = inv[i + 1] * (i + 1) % M
def comb(n, k):
if k < 0 or k > n:
return 0
return fac[n] * inv[k] % M * inv[n - k] % M
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
if sum(max(0, v) for v in a) >= n:
print(0)
continue
a.append(-1)
f = [[[0] for _ in range(n)] for _ in range(n + 1)]
g = [[0] * n for _ in range(n + 1)]
for r in range(n):
if a[r + 1] != -1:
for l in range(n):
f[l][r] = [0] * (a[r + 1] + 1)
for i in range(1, n + 1):
f[i][i - 1][0] = 1
g[i][i - 1] = 1
def w(i, k):
if i == k:
return 1 if a[k] <= 0 else 0
else:
return f[i][k - 1][a[k]] if a[k] != -1 else g[i][k - 1]
for l in range(n - 1, -1, -1):
for r in range(l, n):
if a[r + 1] == -1:
for k in range(l, r + 1):
g[l][r] = (g[l][r] + comb(r - l, k - l) * w(l, k) % M * g[k + 1][r] % M) % M
else:
for c in range(1, a[r + 1] + 1):
for k in range(l, r + 1):
f[l][r][c] = (f[l][r][c] + comb(r - l, k - l) * w(l, k) % M * f[k + 1][r][c - 1] % M) % M
print(w(0, n))
Rate the problem!
Solution
Tutorial is loading...
Code
#include <bits/stdc++.h>
std::string query(const std::vector<int>& a) {
std::cout << "? " << a.size();
for (auto v : a) std::cout << " " << v + 1;
std::cout << std::endl;
std::string s;
std::cin >> s;
return s;
}
std::vector<int> work(const std::vector<int>& a, const std::vector<int>& b) {
if (a.empty() || b.empty()) return {};
std::vector<int> s;
for (auto v : a) s.push_back(v);
for (auto v : b) s.push_back(v);
std::string t = query(s);
std::vector<int> r;
for (int i = 0; i < b.size(); i++) if (t[i + a.size()] == '0') r.push_back(b[i]);
return r;
}
void solve() {
int n;
std::cin >> n;
std::vector<std::vector<int>> g(n);
auto find = [&](auto&& self, std::vector<int> a, std::vector<int> b) -> void {
if (a.empty() || b.empty()) return;
if (a.size() == 1) {
for (auto v : b) g[v].push_back(a[0]), g[a[0]].push_back(v);
return;
}
int m = a.size() / 2;
std::vector a1(a.begin(), a.begin() + m), a2(a.begin() + m, a.end());
auto p1 = work(a1, b);
std::set<int> vis(p1.begin(), p1.end());
std::vector<int> nb, p2;
for (auto v : b) {
if (vis.count(v)) nb.push_back(v);
else p2.push_back(v);
}
self(self, a1, p1);
for (auto v : work(a2, nb)) p2.push_back(v);
self(self, a2, p2);
};
auto dfs = [&](auto&& self, std::vector<int> a) -> void {
if (a.size() <= 1) return;
std::string t = query(a);
std::vector<int> p1, p2;
for (int i = 0; i < a.size(); i++) {
if (t[i] == '0') p2.push_back(a[i]);
else p1.push_back(a[i]);
}
self(self, p2);
std::vector<int> col(n, -1);
std::vector<std::vector<int>> b(2);
for (auto w : p2) if (col[w] == -1) {
std::queue<int> q;
q.push(w);
col[w] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
b[col[u]].push_back(u);
for (auto v : g[u]) if (col[v] == -1) {
col[v] = col[u] ^ 1;
q.push(v);
}
}
}
for (int i = 0; i < 2; i++) {
find(find, b[i], work(b[i], p1));
}
};
std::vector<int> a(n);
std::iota(a.begin(), a.end(), 0);
dfs(dfs, a);
std::cout << "!" << std::endl;
for (int u = 0; u < n; u++) for (auto v : g[u]) if (v > u) std::cout << u + 1 << " " << v + 1 << std::endl;
}
int main() {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
int t;
std::cin >> t;
while (t--) solve();
}
Rate the problem!
Solution
Tutorial will be added after the first official (human) solve.
Code
Auto comment: topic has been updated by __baozii__ (previous revision, new revision, compare).
There seems to be some rendering issue with the tutorials. I am trying to fix it.
Edit: The editorial seems to be rendered correctly, I guess this comment is useless now.
I somehow figured out that the syntax for editorial is
[tutorial:(problem index)], so this is the editorial (which was written by __baozii__ of course) for anyone who need (including me lol)B is A bro
my bad.
no problem bro dont excuse
Fast editorial!
Sorry my bad i clicked the register button
couldnt even solve a single problem today!! :(
Me too T_T
wa on tc 17 is basicly AC, can i have points?
that sucks man D:
Because pretests 1-16 are from D1
But I submitted the same code in two problems, then I got AC in D1 and TLE on 16 in D2, why is that?
Sorry I didn't allocated enough memory for the array lol.
But that doesn't make effect if the 16 cases are completely from D1? I don't think they are the same.
The tutorial didn't render correctly, can you fix it please __baozii__?
Edit: maybe the bug is happening only for me
nope not just you
You are not the only one, is also happening to me
Damn D was graph?? never even thought of thinking graph for this.
C was a good problem despite i couldnt solve it
Absolutely amazing contest omg fire job
weird problems, D1 was fun to solve though
D was so good
Solved D1 with topological sort, couldn't get D2
For D2, you can do a topological sort similar to D1, but using $$$a_i$$$ and $$$-a_i$$$ rather than $$$|a_i|$$$.
Since if there exists a solution, there exists one where all values of $$$a_i$$$ and $$$-a_i$$$ are distinct and non-zero, you can build a graph with $$$2n$$$ nodes and each constraint gives some strict inequalities between $$$a_i$$$ and $$$-a_j$$$. Once you get a topological sort, whether $$$a_i$$$ or $$$-a_i$$$ appears first tells you whether $$$a_i$$$ should be positive or negative, and you get a solution.
Funnily enough this was the way I solved D1 as well.
I got AC with this solution: Compute the topological ordering on this graph, and for each $$$x$$$, print
ord[POSITIVE_NODE(x)] - ord[NEGATIVE_NODE(X)]. I wonder if it's correct or just a coincidence.It is correct. Consider you found a topological order and built the solution.
If you must satisfy a constraint $$$a_i + a_j \gt 0$$$, then if both are positive, we are good. Otherwise, say $$$a_i \lt 0$$$, then $$$ord[i] \lt ord[-i]$$$, but by construction of the graph, $$$ord[-j] \lt ord[i]$$$ and $$$ord[-i] \lt ord[j]$$$, so $$$ord[-j] \lt ord[i] \lt ord[-i] \lt ord[j]$$$ and we get $$$a_i + a_j \gt 0$$$.
Similarly, you satisfy constraints $$$a_i + a_j \lt 0$$$ as well.
Simple but elegant !
How can C be solved?
I solved it using XOR basis.
what is the easier approach?
Notice that every sequence f satisfying following conditions is valid:
so you can construct f backward, set f(n-1) = n and place every digit in binary representation of k xor n to f(n-2), f(n-3) and so on, then construct corresponding permutation p.
So, the right way is just constuct k xor n using powers of 2!
I used harder approach, which using xor basis to find these numbers rather than the power of 2's.
Could anyone explain why sorting is used in the official solution for Problem B? The second operation clearly states we can only pick two adjacent elements, which literally refers to elements next to each other in the original array, right? If pairings are restricted to adjacent elements only, sorting the entire array and rearranging its order should not be valid at all. Is there a misunderstanding of the problem statement here?
You can consider it as having some 'negative' numbers (which you want to pair), and some 'positive' which you don't mind pairing. As long as there are at least one of each kind, you can also find an adjacent pair of such as well -- therefore, you don't need to care about their ordering but just about their count(s).
Yes you can only do adjacent pairings. However, you can always construct an order of operations such that you can use the bigger half of the elements as the max. Imagine marking every element as 1 if it's in the bigger half of the elements, and 0 otherwise. No matter what, there is always a 1 next to a zero, and we can remove both.So you can always achieve using the biggest half of the array.
Suppose you mark some elements as 0 and others as 1, and declare that each paired operation removes exactly one of 0 and 1. Then as long as 1 <= number of 0s <= number of 1s, you can always find an adjacent pair regardless of order.
Solved D1 1 minute after contest :<( bruuh
ConstructiveForces
Same! It was a really fun question though
D1 can be solved in really stupid ways (like sorting by number of non-negative sums) that don't generalise well for D2. I'm surprised the points' split was so much in favour of D1.
guessforces
cheatforces
Auto comment: topic has been updated by __baozii__ (previous revision, new revision, compare).
Propose multiple constructions and pure-guess problems won't make your reputation be more positive.
Sincerely to every author who have the very bottom-line sympathy to participants.
Do I propose contests to make my reputation more positive? I author problems because I love authoring problems. I want to share them to the community.
Simply because problems C and D are constructive or problem B is greedy does not make the contest "multiple constructions and pure-guess problems". Is your definition of competitive programming purely data structures?
I suspect that MaxBlazeIceInk (as well as I) doesn't like the variance that increases with tasks like C or D.
Hug you，my honey，MaxBlazeIceInk，Hope your journey in the algorithm competition goes smoothly.
guessforces
What's the purpose of setting memory limit of problem F to 128 mb? don't think there's much difference, since it only prevent using int[500][500][500].
Also O(n^4) solution can actually pass.
Was a massive fan of problem A!
Did anyone else solve B this way?
if i take two elements say , a,b then its either max(a,b)-c or a+b-2c so given that max(a,b)-c>a+b-2c has to satisfy,then c must be greater than the min of the both, so all the values smaller than c must be somewhere matched with greater than c , so it will pair up and so on and did some other proofs to get to the final sol.
Hell, I think the solution to G seems pretty AI-generated.
But A-E are great
Could someone explain the proof of the lemma in D1 in more detail? I didn`t understand it
The point they're trying to make is that $$$\lvert a_i \rvert = \lvert a_j \rvert$$$ for $$$i \neq j$$$ can always be avoided.
An easier way to show this is to bend the rules of the problem a bit and allow for decimals. Suppose that for some valid solution $$$a$$$, we have $$$\lvert a_i \rvert = \lvert a_j \rvert$$$ for $$$i \neq j$$$. Simply add $$$0.1$$$ to $$$a_i$$$. This will keep all non-negative restrictions sound as the sum increases, and no negative restrictions will be broken as $$$0.1$$$ is not enough of a change to go from a negative integer to a non-negative integer.
Since there's an infinite number of decimals between any two integers, we have plenty of freedom in selecting small offests to satisfy all of the conditions.
Now just convince yourself that these decimal values could in fact be scaled up to integers with the correct power of 10.
The editorial follows this idea, but uses carefully chosen integer offsets instead.
Thank you for the wonderful contest!
Alternate solution to C with no casework on K:
If the MSB of $$$(k\oplus n)$$$ is greater than the MSB of $$$(n-1)$$$, then no possible permutation can make the MSB of $$$(k\oplus n)$$$ appear in the final xorsum, so the answer is no.
Otherwise, consider the binary representation of $$$(k\oplus n)$$$. If the $$$i$$$-th bit from the left of $$$(k\oplus n)$$$ is set, mark $$$2^{i-1}$$$ as a "used element". Additionally mark $$$0$$$ as a used element. Then, output all the non-used elements, then the used elements in order.
I used the same approach. Such an elegant solution.
D2 and E are really good problems, enjoyed them so much.
This round will always be special for me.. it got me to Pupil! Huge thanks to __baozii__ for such a wonderful set of problems...
nice contest, loved D2 and E <3
The D2 of doom and despair.
Can someone please explain in detail how to solve B?
First, subtract $$$c$$$ from each $$$A_i$$$. Suppose there are now $$$a$$$ nonnegative numbers and $$$n-a$$$ negative numbers.
We consider two cases. If $$$a \ge n-a$$$, then there must be a nonnegative number adjacent to a negative number. We can delete the pair and obtain a nonnegative contribution. In the end, we can always collect all nonnegative contributions, so we only need to calculate the sum of all nonnegative numbers.
Now consider $$$a \lt n-a$$$. We are inevitably forced to include some negative numbers. We reduce this case to the previous one. First, we delete some negative numbers and take their contributions. If we delete $$$k$$$ negative numbers, then we need
so
Therefore, we take all nonnegative numbers together with the $$$k$$$ largest negative numbers, which solves the problem.
Translated by ChatGPT
The goal is to maximize the sum. Therefore, we keep all elements $$$a_i$$$ such that $$$a_i \ge c$$$ and try to eliminate as many elements with $$$a_i \lt c$$$ as possible.
It is easy to see that any element $$$a_i \lt c$$$ can be eliminated by pairing it with an element $$$a_j \ge c$$$. Therefore, if there are $$$k$$$ elements satisfying $$$a_i \ge c$$$, we can eliminate up to $$$k$$$ elements satisfying $$$a_i \lt c$$$.
After doing so, some elements with $$$a_i \lt c$$$ may still remain. These remaining elements can only be paired among themselves, which means that at most half of them will contribute to the final sum.
actually the main confusion in the solution and the problem statement is that, in the problem statement they say to remove elements in pair which are adjacent, but in the solution somehow the order doesn't matter.
This is not at all intuitive. Even I'm not able to understand this.
Try viewing the sequence as a binary sequence, where $$$1$$$ means that we want to include the corresponding number, while $$$0$$$ means that we want to delete it.
As long as both $$$1$$$ and $$$0$$$ remain, there must be an adjacent pair consisting of a $$$1$$$ and a $$$0$$$. Removing this pair is equivalent to applying the second operation. Repeating this process eventually leaves only some $1$s, which can then be removed using the first operation.
But what about the order of the elements,it is mentioned in the question that we have to take only the adjacent elements.Why we are not taking that into account?
The order of the elements does not matter at all.
Consider the version of the problem where $$$c=0$$$. Suppose there are $$$k$$$ positive elements, where $$$2k \gt n$$$. You want to include all of these positive elements into your answer.
As long as there are both positive and negative elements inside the array, you are guaranteed to have an adjacent pair of positive and negative elements. We are not removing an arbitrary positive element and an arbitrary negative element. It is just there must exist an adjacent pair.
Reduce D to 2-SAT:
Let true represent positive and false represent negative. For each $$$i$$$, $$$j$$$, if $$$o = 1$$$ then at least one of $$$i$$$ or $$$j$$$ needs to be positive, so add a $$$i \lor j$$$ clause, and similarly if $$$o = 2$$$ then at least one of $$$i$$$ or $$$j$$$ needs to be negative, so add a $$$\lnot i \lor \lnot j$$$ clause. Then if this formula is satisfiable we have the signs and can do the topological sort on $$$|a_i|$$$.
The solution is effectively the implication graph of 2-SAT anyways, but this was a nice way for me to
overcomplicate the problem and forget how my 2-SAT template works and then not get it correct until 20 seconds after the contest ended.F drove me crazy!
Auto comment: topic has been updated by __baozii__ (previous revision, new revision, compare).
I often recall the past.
Implemented Recursion on B and got MLE TwT
Waiting for H, as always!
this is the most beautiful and fun contest i've participated in so far
thanks for the great problems
Best round I've ever seen
Please someone explain solution for $$$B$$$ and $$$C$$$ in easy language. I can't understand the editorial solution.
I have a rather easy C solution, it's pure implementation Notice at the end, when you have made the complete array, the last Mex will be N. Say you have a target T, given to you in problem, there will be set of bits set in N say nb1,nb2... Similarly you will have some bits set in T say tb1, tb2..etc The idea is if there are bit position set in both n and t, then we don't have to make that mex, the last mex will be sufficient to produce that, but if a bit is set in any one of n or t, then we need to generate mex either to set that particular bit in result or to remove that bit from result using xor.Initially our result was N,then we do these operation, basically we add power of 2 for bit position with xor = 1, then append it to array, then in reverse order all the remaining elements from 0 to n — 1, then we need to check if all the elements are less than n, if they are, then answer is Yes, return the reverse of this array, if not then NO permutation will exist.
Here is my approach.
Let $$$x = k \oplus n$$$
Observe that $$$f(n - 1) = n$$$. Therefore, we need $$$f(0) \oplus f(1) \oplus \cdots \oplus f(n - 2) = x$$$.
Another important observation is that the position of $$$0$$$ in the permutation matters. If $$$a_i = 0$$$, then $$$f(0) = f(1) = \cdots = f(i - 1) = 0$$$ and $$$f(i) = \text{minimum value on the right of 0}$$$.
Thus, our task reduces to constructing some values whose XOR is equal to $$$x$$$.
Let $$$a = \text{the most significant bit of } x$$$, $$$b = a \oplus x$$$. Since $$$a \oplus b = x$$$, we can place the last three elements of the permutation as:
All remaining numbers can be placed to the left of $$$0$$$ in any order. Then the XOR of the corresponding values will be exactly $$$k$$$.
Of course, there are several edge cases that must be handled separately.
In problem D2,can someone please explain why the editorial reverses t and the signs(-1 for d0=0,1 for d1=0) before assigning values? Why cant I assign a positive value if d[0]=0 and a negative value if d[1]=0 and increase the value for the next one?
d[0][i]==0that actually means that everyjin whicha[i]+a[j]>=0is eliminated and there is all availablejwhich givesa[i]+a[j]<0.. so we are putting larger negative value sequentially for every this kind ofiin whichd[0][i]==0and same logic goes ford[1][i]==0,we will put larger positive value sequentially...so at last the last elements of the order(here it is t) will get smallest value according with sign and first element will get largest elements....so we will start putting large to small if we do not pretend to reverse the order list....if you reverse order list,, it is easy to put values0ton-1according its sign...I had a different approach for D2, worth checking out :
Instead of dealing with negative numbers, let's pretend a_i and -a_i are independent variables. For every number 1 to n, create a graph with 2N nodes: Node P_i represents +a_i Node N_i represents -a_i
In graph theory, an inequality Y >= X + W is modeled as a directed edge X -> Y with weight W. Let's rearrange our given constraints to match this format:
Type 1 (a_i + a_j >= 0): Rearranging gives a_i >= -a_j. In our nodes: P_i >= N_j + 0. Add edges N_j -> P_i and N_i -> P_j with weight 0.
Type 2 (a_i + a_j < 0): Rearranging gives -a_i > a_j, which means -a_i >= a_j + 1. In our nodes: N_i >= P_j + 1. Add edges P_j -> N_i and P_i -> N_j with weight 1.
Notice that weight-0 edges always go N -> P, and weight-1 edges always go P -> N. The graph is perfectly bipartite. This means there are no 0-weight cycles. If topological sort detects any cycle, it's a contradiction ( solution isn't possible ).
Initialize all nodes with in_degree == 0 to a value of 0. Run Kahn's Algorithm (Topological Sort) to compute the longest path (val) to every node. val[nxt] = max(val[nxt], val[curr] + weight). If the number of processed nodes is != 2N, a cycle exists.
If it's a DAG, the final answer for each element is simply the difference between its positive and negative "pressures": a_i = val[P_i] — val[N_i] For a Type 2 constraint : a_i + a_j < 0 --> Our graph has edges P_i -> N_j (weight 1) and P_j -> N_i (weight 1). By the definition of longest paths, this guarantees: val[N_j] — val[P_i] >= 1 and val[N_i] — val[P_j] >= 1 Now plug our formula into the sum: a_i + a_j = (val[P_i] — val[N_i]) + (val[P_j] — val[N_j])
a_i + a_j = -(val[N_j] — val[P_i]) — (val[N_i] — val[P_j]) <= -2
Similarly, it can be proved for Type 1 constraint.
Thank you for your great tutorial!
Dear codeforces
I got a message ragarding accusation for plag --> Attention! Your solution 383003288 for the problem 2245D1 significantly coincides with solutions Jashnoor_gill/382990901, Samsaara/383003288. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.me/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.
I dont know this other user i know there are some same variables used but that is actually common for this tarjans algorithm. I commonly used variables like these in my codes as you can check. Also i confirm i wrote this code by myself and there are many differences between our implementation again based on variable names and my code being without use of structures. I beg you to look into this case as it actually breaks the morale of a user. I can explain the solution based on 2 SAT and tarjan algorithm and had faced similar problems even before.I know that some flow of the implementation looks similar but it is actually instinct to look for this type of logic when facing problem like that.
I understand and respect Codeforces efforts to maintain fair competition, which is why this warning was very discouraging to receive. I have always tried to solve problems honestly, and being accused of plagiarism despite writing the solution myself has been quite upsetting and dissappointing.
please ignore spelling mistakes samsaara
I solved this problem completely on my own during the contest. I did not discuss the problem with anyone, share my code, or look at anyone else's solution. I also did not use any public IDEs or paste sites.
The solution itself is very short and follows the most direct approach: subtract c from every element, sort in descending order, take the first (n+1)/2 elements, and then add the remaining positive ones. Because of this, I think it's natural for independent solutions to look similar.
My submission and the other one also have several differences. I use my own minimal template in VS Code, while the other submission uses a large competitive programming template with debug utilities, different macros, variable names, and formatting.
I write all my code locally in VS Code. I'm happy to email my rough work that can help verify that I solved the problem independently.
I would really appreciate it if my submission could be reviewed manually.
2 years and I still can't consistently solve 4 problems in div2 :(
Come on bro's what's so offending about my comment lol
yeah most ppl that solved it last i checked either used ai or copied ppl who use ai, not a single LGM solve is crazy
Yes exactly! Why did I got downvoted so bad TT
Hey so this is a human solve for H __baozii__ 383620870
(X to doubt), max CM solving problem H hmmm
It's THE kaiboy bro
Late reply, but I have been mulling over 2245D2 - Construct an Array (Hard Version) and I think the editorial skips over a crucial part of the proof, which I want to cover.
(Also the bit about replacing “nonnegative” with “positive” in the editorial is unnecessary.)
Let me recap. From the solution to D1, we know
we can model the problem as a graph problem, where the vertices represent array elements, and edges constraints between them. We direct the edges between negative and nonnegative vertices based on their greater than (or equal to) relationship, and then if the graph contains a directed cycle the problem is unsolvable (since it implies a vertex on the cycle is greater than itself), otherwise, we can topologically sort the vertices and assign values with magnitudes ranging from $$$1$$$ to $$$n$$$ corresponding with the index in the toplogical ordering to satisfy all constraints.
Then for problem D2 we can construct a recursive solution:
Given a problem of size $$$n$$$, we can create a solution where $$$1 ≤ |a_i| ≤ n$$$ for all $$$1 ≤ i ≤ n$$$, which follows from the analysis of D1 above.
Again consider a graph where vertices are array elements and edges are constraints, but this time, the edges are undirected, because we don't know which vertices represent negative or nonnegative elements. We can nevertheless use the following iterative algorithm to construct a solution.
We can continue applying these two operations while we can. The editorial already describes how to do this efficiently, so I won't repeat it here.
The algorithm ends when we cannot apply either operation, which happens in two cases. One is when $$$n = 0$$$ (i.e. the remaining graph is empty) which means we've succesfully assigned all values, and it's not hard to see all constraints must be satisfied.
The other case is when $$$n \gt 0$$$ but all remaining vertices have at least one constraint of each type. In that case there is no solution.
This last part is not proven in the editorial. I will prove it by contradiction.
Assume that in the case where all remaining vertices have a constraint of both types, there is some valid assignment of values to vertices. Let $$$m$$$ be the maximum magnitude of a value, i.e. $$$m = max(|a_i|)$$$.
That means there is either a vertex $$$i$$$ such that $$$a_i = m$$$, or a vertex $$$j$$$ such that $$$a_j = -m$$$ (possibly both, or multiple).
If there is a vertex $$$a_i = m$$$ then we can prove a contradiction, since vertex $$$i$$$ it has a constraint of type 2, meaning there is some vertex $$$j$$$ such that $$$a_i + a_j \lt 0$$$. But since $$$m = max(|a_i|)$$$, $$$a_j \gt -m$$$, which means $$$a_i + a_j ≥ m + -m = 0$$$, so the constraint is not satisfied: a contradiction!
If there is no vertex $$$a_i = m$$$, that means $$$a_i \lt m$$$ for all i, and instead there must be some $$$a_j = -m$$$ (otherwise, $$$m$$$ would not be the maximum magnitude in the array). We can again prove a contradiction, this time using the fact that there is a constraint of type 1, meaning there is a vertex $$$i$$$ such that $$$a_i + a_j ≥ 0$$$, but since $$$a_i \lt m$$$, that means $$$a_i + a_j \lt m + -m = 0$$$, so the constraint is not satisfied: a contradiction!
Both possiblities ended in a contradiction, which proves that if every element has (at least) one constraint of type 1 and one of type 2, no possible value assignment exists, and we can safely return "no solution".
I'm under the impression that 384018980 is a human solution.
Since maspy has already solved H, could you please add the tutorial for it, __baozii__? Thanks!
I will leave a brief hint for Problem H.
For the enumerated pairs, subtract those that are also reachable by a (col, row, col) pattern.
For the (col, row, col) pattern, suppose that, for a fixed pair, the possible rows are $$$r_0,r_1,\ldots,r_n$$$. Then the number of such pairs can be counted by adding +1 for each $$$r_i$$$, and -1 for each pairs $$$r_i,r_{i+1}$$$.
An $$$O(N^2M)$$$ time solution is relatively straightforward, but some care is probably needed to keep both the constant factor and the memory usage under control.