1928A - Rectangle Cutting
Let $$$a \le b$$$. Let's consider several cases:
If $$$a$$$ is even, then we can cut the rectangle into two rectangles of size $$$\frac{a}{2} \times b$$$ and combine them into a rectangle of size $$$\frac{a}{2} \times 2b$$$, which is definitely different from $$$a \times b$$$.
If $$$b$$$ is even and $$$b \ne 2a$$$, then we can cut the rectangle into two rectangles of size $$$a \times \frac{b}{2}$$$ and combine them into a rectangle of size $$$2a \times \frac{b}{2}$$$. Note that here we use the fact that $$$b \ne 2a$$$, because if $$$b = 2a$$$, then we will get the same rectangle of size $$$b \times a$$$.
If $$$a$$$ and $$$b$$$ are both odd, or $$$b = 2a$$$ and $$$a$$$ is odd, then the rectangle is not interesting. It is easy to understand that if we cut the rectangle of size $$$a \times b$$$ into two rectangles of size $$$a \times c$$$ and $$$a \times d$$$, where $$$c \ne d$$$, then we can always only combine the original rectangle (similarly if we cut it into rectangles $$$c \times b$$$ and $$$d \times b$$$). And from here it follows that we must divide one of the sides of the rectangle in half, so at least one side must be even.
#include <vector>
#include <iostream>
#include <numeric>
#include <algorithm>
#include <cassert>
#include <map>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--) {
int a, b;
cin >> a >> b;
if (a > b) {
swap(a, b);
}
if (((a % 2 == 1) && (b % 2 == 1)) || ((a % 2 == 1) && (b == 2 * a))) {
cout << "No\n";
} else {
cout << "Yes\n";
}
}
return 0;
}
1928B - Equalize
Suppose we already know the permutation that needs to be added. Let's consider the elements that will become equal after the addition. Notice that among them there cannot be equal elements, because among the numbers we are adding, there are no duplicates. Thus, only a set of numbers among which there are no equal ones, and the difference between the maximum and minimum does not exceed $$$n - 1$$$, can become equal. It is easy to see that any set of numbers satisfying these conditions can be equalized, and any set of numbers that became equal after adding the permutation satisfies these constraints.
So let's sort the array, remove the equal elements from it. After that, we can use two pointers to find the maximum length subarray where the difference between the maximum and minimum does not exceed $$$n - 1$$$. The answer will be the length of such a subarray. The complexity of the solution is $$$O(n \log n)$$$.
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a.begin(), a.end());
a.resize(unique(a.begin(), a.end()) - a.begin());
int pnt = 0, ans = 0;
for (int i = 0; i < a.size(); i++) {
while(a[i] - a[pnt] >= n) {
pnt++;
}
ans = max(ans, i - pnt + 1);
}
cout << ans << endl;
}
signed main() {
int t = 1;
cin >> t;
for (int i = 0; i < t; ++i) {
solve();
}
return 0;
}
1928C - Physical Education Lesson
All numbers repeat every $$$2k - 2$$$ positions. If the boy Vasya's number is calculated to be $$$x$$$, then it can be at positions of the form $$$(2k - 2) \cdot t + x$$$, or $$$(2k - 2) \cdot t + k + k - x$$$, for some non-negative $$$t$$$. This is true for all $$$x$$$, except for $$$x = 1$$$ and $$$x = k$$$ ~--- for these values, there is only one option left.
Let's fix one of the options, the second one will be analogous. We need to find how many different values of $$$k$$$ satisfy the equation $$$(2k - 2) \cdot t + x = n$$$, for some non-negative $$$t$$$. It is not difficult to see that this holds if and only if $$$n - x$$$ is divisible by $$$2k - 2$$$. Therefore, it is necessary to find the number of \textbf{even} divisors of the number $$$n - x$$$. To consider the second case, it is necessary to proceed similarly with the number $$$n + x - 2$$$. The solution's complexity: $$$O(\sqrt{n})$$$
#include <iostream>
#include <unordered_set>
using namespace std;
unordered_set<int> solve(int a) {
unordered_set<int> candidates;
for (int i = 1; i * i <= a; i++) {
if (a % i == 0) {
if (i % 2 == 0) // segment len should be even
candidates.insert(i);
if ((a / i) % 2 == 0)
candidates.insert(a / i);
}
}
unordered_set<int> answer;
for (int i : candidates) {
answer.insert(1 + i / 2);
}
return answer;
}
int main() {
int t;
cin >> t;
for (int _ = 1; _ <= t; _++) {
int n, pos;
cin >> n >> pos;
unordered_set<int> candidates = solve(n - pos); // bug2
for (int i : solve(n + pos - 2)) { // bug1
candidates.insert(i);
}
int answer = 0;
for (int i : candidates) {
if (i >= pos) {
answer++;
}
}
cout << answer << endl;
}
}
1928D - Lonely Mountain Dungeons
Let's learn how to solve the problem when $$$n = 1$$$. Suppose there is only one race and the number of its representatives is $$$c$$$. Notice that for a fixed $$$k$$$, it is advantageous for us to divide the representatives of the race almost evenly into squads.
If $$$c$$$ is divisible by $$$k$$$, then it is advantageous for us to take exactly $$$y = \frac{c}{k}$$$ beings in each squad. Then the total number of pairs of beings in different squads is equal to $$$\frac{k(k-1)}{2} \cdot y^2$$$ (there are a total of $$$\frac{k(k-1)}{2}$$$ pairs of squads, and for each pair of squads there are $$$y^2$$$ pairs of beings from different squads).
In the general case, when $$$c$$$ may not be divisible by $$$k$$$, let's denote $$$y = \left\lfloor \frac{c}{k} \right\rfloor$$$ and $$$y' = \left\lceil \frac{c}{k} \right\rceil$$$. Then it is advantageous for us to make squads of size $$$y$$$ and $$$y'$$$, where the number of squads of size $$$y'$$$ is equal to $$$c \bmod k$$$ (we essentially make all squads of size $$$y$$$, and then add 1 to some squads from the remaining part). In this case, the total number of pairs of beings in different squads is equal to $$$C_{k - c \bmod k}^2 \cdot y^2 + C_{c \bmod k}^2 \cdot y'^2 + (k - c \bmod k) \cdot (c \bmod k) \cdot y \cdot y'$$$. It remains to notice that it makes no sense to have $$$k > c$$$, so we can simply iterate through $$$k$$$ from $$$1$$$ to $$$c$$$ and choose the optimal one.
When $$$n > 1$$$, we can notice that for a fixed $$$k$$$, we can solve the problem independently for each race. Let the number of representatives of the $$$i$$$-th race be $$$c_i$$$. Then we will iterate through $$$k$$$ from $$$1$$$ to $$$c_i$$$ for it and add the maximum total strength to the value of $$$cnt_k$$$ (the array $$$cnt$$$ is common for all races). Also, notice that for $$$k > c_i$$$, we will get the same total strength as for $$$k = c_i$$$. Then in the additional array $$$add$$$ (again, common for all races), we will add the maximum total strength for $$$k = c_i$$$ to $$$add_{c_i}$$$.
We get the following solution: first, calculate the described arrays $$$cnt$$$ and $$$add$$$. After that, iterate through $$$k$$$ from $$$1$$$ to the maximum $$$c_i$$$. The maximum total strength of the squads for a fixed $$$k$$$ will be equal to $$$(cnt_k + (\text{sum of values } add_i \text{ for } i < k)) \cdot b - (k - 1) \cdot X$$$. From these values, we need to choose the maximum.
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
ll pairs(ll n, ll k){
if (n == 0 || k == 0){
return 0;
}
ll x = n / k;
ll l = n % k;
ll r = k - l;
ll L = (x + 1) * l, R = x * r;
return R * L + (R - x) * R / 2 + L * (L - x - 1) / 2;
}
void solve(){
int m;
long long c, b;
cin >> m >> b >> c;
int n = 0;
vector<int> cnt(m);
for (int i = 0; i < m; ++i) {
cin >> cnt[i];
n = max(n, cnt[i]);
}
vector<long long> pair(n + 1);
vector<long long> add(n + 1);
for (int i = 0; i < m; ++i) {
for (int j = 1; j <= cnt[i]; ++j) {
pair[j] += pairs(cnt[i], j);
}
add[cnt[i]] += pairs(cnt[i], cnt[i]);
}
long long ans = 0;
long long other = 0;
for (int i = 1; i <= n; ++i) {
ans = max(ans, b * (pair[i] + other) - c * (i - 1));
other += add[i];
}
cout << ans << endl;
}
int main(){
int t;
cin >> t;
while (t--){
solve();
}
}
1928E - Modular Sequence
Let's see what the answer will look like: first, there will be a prefix of the form $$$x, x + y, \ldots, x + k\cdot y$$$, and then there will be some number of blocks of the form $$$x \bmod y, x \bmod y + y, \ldots, x \bmod y + k \cdot y$$$.
We can subtract the number $$$x \bmod y$$$ from all the elements of the sequence, and then divide all the elements by $$$y$$$ (all the elements will be divisible by $$$y$$$, since they initially had a remainder of $$$x \bmod y$$$). Let $$$b_1 = \frac{x - x \bmod y}{y}$$$. Then our sequence will start with $$$b_1, b_1 + 1, \ldots, b_1 + k_1$$$, and then there will be blocks of the form $$$0, 1, \ldots, k_i$$$.
Let's calculate these values: $$$dp_i$$$~--- the minimum length of a sequence of blocks of the form $$$0, 1, \ldots, k_j$$$ with a sum of $$$i$$$. This value can be calculated for all numbers from $$$0$$$ to $$$s$$$ using dynamic programming. If we have processed all values from $$$0$$$ to $$$k-1$$$, then for $$$k$$$ we have calculated the minimum length, and we can update the value of $$$dp$$$ for $$$k + 1, k + 1 + 2, \ldots$$$~--- a total of $$$O(\sqrt{s})$$$ values not exceeding $$$s$$$. In this same $$$dp$$$, we can store through which values we were recalculated, for the restoration of the answer.
Now, we can iterate over the length of the first block of the form $$$b_1, b_1 + 1, \ldots, b_1 + k_1$$$. Then we know the sum of the remaining blocks, and using the precalculated $$$dp$$$, we can determine whether the desired sequence can be formed or not.
#include <cassert>
#include <initializer_list>
#include <numeric>
#include <vector>
#include <iostream>
#include <utility>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <math.h>
using namespace std;
#define pii pair<int, int>
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define ll long long
#define pb emplace_back
const int INF = 1e9 + 10;
const ll INFLL = 1e18;
void solve() {
int n, x, y, S;
cin >> n >> x >> y >> S;
vector<int> dp(S + 1, INF);
dp[0] = 0;
for (int k = 1; k <= S; k++) {
for (int l = 2; (l * (l - 1)) / 2 <= k; l++) { // just 0 is never optimal
dp[k] = min(dp[k], dp[k - (l * (l - 1)) / 2] + l);
}
assert(dp[k] <= 2 * k);
}
for (ll k = 0; k < n; k++) {
ll prevSum = (k + 1) * x + (k * (k + 1)) / 2 * y;
if (prevSum > S) {
continue;
}
ll needSum = S - prevSum;
needSum -= (n - k - 1) * (x % y);
if (needSum < 0) {
continue;
}
if (needSum % y != 0) {
continue;
}
needSum /= y;
assert(needSum <= S);
if (dp[needSum] <= n - k - 1) { // we found the answer
vector<int> a(n);
a[0] = x;
for (int i = 1; i <= k; i++) { // construct prefix
a[i] = a[i - 1] + y;
}
for (int i = k + 1; i <= k + (n - k - 1) - dp[needSum];
i++) { // fill the rest like 0 0 0 ...
a[i] = x % y;
}
int i = k + (n - k - 1) - dp[needSum] + 1; // first free index
vector<int> lens; // recover lengths of the segments
while (needSum != 0) {
for (int l = 2; (l * (l - 1)) / 2 <= needSum; l++) {
if (dp[needSum] == dp[needSum - (l * (l - 1)) / 2] + l) {
lens.pb(l);
needSum -= (l * (l - 1)) / 2;
break;
}
}
}
for (auto &len : lens) {
for (int j = 0; j < len; j++) {
a[i] = (x % y) + y * j;
i++;
}
}
cout << "YES\n";
for (auto &c : a) {
cout << c << " ";
}
cout << "\n";
return;
}
}
cout << "NO\n";
}
int main() {
cin.tie(0);
cout.tie(0);
ios_base::sync_with_stdio(0);
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
1928F - Digital Patterns
Let's assume that $$$a_i = a_{i+1}$$$ for some $$$1 \le i < n$$$, then for any $$$1 \le j \le m$$$, the cells $$$(i, j)$$$ and $$$(i+1, j)$$$ will have the same transparency. A similar statement can be made if there is an index $$$j$$$: $$$b_j = b_{j+1}$$$.
Then the positions $$$a_i = a_{i+1}$$$ divide the array $$$a$$$ into \textit{blocks}, in each of which all neighboring pairs are not equal to each other. It is clear that if there is a square $$$(x, y, d)$$$ consisting of cells $$$(i, j)$$$ such that $$$x \le i < x+d$$$ and $$$y \le j < y+d$$$, then the segment $$$[x, x+d-1]$$$ is entirely contained in one of these \textit{blocks} of the array $$$a$$$. Similarly, the array $$$b$$$ can also be divided into blocks, and then the segment $$$[y, y+d-1]$$$ will also be entirely contained in one of the blocks.
Let's try to solve the problem in $$$O(1)$$$ time, if there are no neighboring elements with the same values in the arrays $$$a$$$ and $$$b$$$ (also assuming that $$$n \le m$$$):
This formula can be further transformed by introducing a quadruple of numbers for each natural number $$$n$$$: $$$a_n = 1$$$, $$$b_n = n$$$, $$$c_n = \frac12 n(n+1)$$$, $$$d_n = \frac16 n(n+1)(2n+1) - \frac12n^2(n+1)$$$. Then $$$f(n, m) = d_n a_m + c_n b_m$$$, if $$$n \le m$$$ and $$$f(n, m) = a_n d_m + b_n c_m$$$, if $$$n > m$$$.
But if there are neighboring identical elements in the arrays $$$a$$$ and $$$b$$$, then this means that they are somehow divided into blocks. If these are blocks of lengths $$$n_1, \ldots, n_k$$$ in the array $$$a$$$ and blocks of lengths $$$m_1, \ldots, m_l$$$ in the array $$$b$$$, then the answer to the problem is
Let's learn how to quickly calculate sums of the form $$$f(x, m_1) + \ldots + f(x, m_l)$$$. To do this, we will create 4 segment trees to quickly calculate the sums $$$\sum a_y$$$, $$$\sum b_y$$$, $$$\sum c_y$$$, $$$\sum d_y$$$ over segments of $$$y$$$, taking into account the multiplicity of $$$y$$$ in the array $$$m_1, \ldots, m_l$$$. Now the calculation of $$$f(x, m_1) + \ldots + f(x, m_k)$$$ is reduced to $$$4$$$ segment tree queries:
The sum $$$f(n_1, y) + \ldots + f(n_k, y)$$$ is calculated similarly. Now we just need to put our solution together. We will maintain the blocks of arrays $$$a$$$ and $$$b$$$ in an online mode. It is very convenient to do this by storing the positions $$$a_i = a_{i+1}$$$ in a data structure like std::set, and also by working with the differential array $$$a$$$ (i.e., maintaining not the array $$$a$$$ itself, but the array of differences between neighboring elements $$$c_i = a_{i+1} - a_i$$$). To recalculate the answer, we will count the number of squares that are involved in a specific block of the array $$$a$$$ or $$$b$$$, using the above result. As a result, we have a solution in $$$O((n+q) (\log n + \log m))$$$.
P.S. A solution in $$$O(q \sqrt n)$$$ will not work due to a large constant. I tried very hard to rule it out :D.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pi = pair<int, int>;
struct SegmentTree {
int n;
vector<ll> t;
SegmentTree(int n) : n(n), t(2*n) { }
void Add(int i, ll x) {
for (i += n; i != 0; i >>= 1) t[i] += x;
}
ll Query(int l, int r) {
ll ans = 0;
for (l += n, r += n - 1; l <= r; l >>= 1, r >>= 1) {
if ((l&1) == 1) ans += t[l++];
if ((r&1) == 0) ans += t[r--];
}
return ans;
}
};
struct SegmentContainer {
int side;
SegmentTree sgt_a, sgt_b, sgt_c, sgt_d;
int id;
// sgt_a: sum(1)
// sgt_b: sum(m)
// sgt_c: sum(m*(m+1)/2)
// sgt_d: sum(m*(m-1)*(2*m-1)/6 - m*(m-1)/2*m)
SegmentContainer(int side) : side(side), sgt_a(side), sgt_b(side), sgt_c(side), sgt_d(side) {
}
tuple<ll, ll, ll, ll> GetABCD(ll m) {
return make_tuple(1, m, m*(m+1)/2, m*(m-1)*(2*m-1)/6 - m*(m-1)/2*m);
}
void Insert(int m) {
auto [a, b, c, d] = GetABCD(m);
sgt_a.Add(m-1, +a);
sgt_b.Add(m-1, +b);
sgt_c.Add(m-1, +c);
sgt_d.Add(m-1, +d);
}
void Erase(int m) {
auto [a, b, c, d] = GetABCD(m);
sgt_a.Add(m-1, -a);
sgt_b.Add(m-1, -b);
sgt_c.Add(m-1, -c);
sgt_d.Add(m-1, -d);
}
ll SquaresCount(int n) {
const int mid = min(side, n);
auto sum_a = sgt_a.Query(mid, side); // m > n
auto sum_b = sgt_b.Query(mid, side); // m > n
auto sum_c = sgt_c.Query(0, mid); // m <= n
auto sum_d = sgt_d.Query(0, mid); // m <= n
auto [a, b, c, d] = GetABCD(n);
return d * sum_a + c * sum_b + b * sum_c + a * sum_d;
}
};
struct SegmentMaintainer {
SegmentContainer& my;
SegmentContainer& other;
ll& ans;
set<int> pos_zero;
vector<ll> diff_array;
SegmentMaintainer(vector<int> a,
SegmentContainer& my,
SegmentContainer& other,
ll& ans) :
pos_zero(), diff_array(a.size()), my(my), other(other), ans(ans) {
pos_zero.insert(0);
for (int i = 1; i < a.size(); ++i) {
diff_array[i] = a[i] - a[i-1];
if (diff_array[i] == 0) pos_zero.insert(i);
}
pos_zero.insert(a.size());
for (auto it = pos_zero.begin(); *it != my.side; ++it) {
OnSegmentAppear(*next(it) - *it);
}
}
void OnSegmentAppear(int len) {
my.Insert(len);
ans += other.SquaresCount(len);
}
void OnSegmentDissapear(int len) {
my.Erase(len);
ans -= other.SquaresCount(len);
}
void ChangeBound(int pos, ll dx) {
if (pos == 0 || pos == my.side) return;
bool was_zero = diff_array[pos] == 0;
diff_array[pos] += dx;
bool now_zero = diff_array[pos] == 0;
if (was_zero && !now_zero) {
auto mid = pos_zero.find(pos);
auto prv = prev(mid), nxt = next(mid);
OnSegmentDissapear(*mid - *prv);
OnSegmentDissapear(*nxt - *mid);
OnSegmentAppear(*nxt - *prv);
pos_zero.erase(mid);
}
if (!was_zero && now_zero) {
auto mid = pos_zero.insert(pos).first;
auto prv = prev(mid), nxt = next(mid);
OnSegmentAppear(*mid - *prv);
OnSegmentAppear(*nxt - *mid);
OnSegmentDissapear(*nxt - *prv);
}
}
void RangeAdd(int l, int r, int x) {
ChangeBound(l, +x);
ChangeBound(r, -x);
}
};
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, m, q; cin >> n >> m >> q;
vector<int> a(n), b(m);
for (int& x : a) cin >> x;
for (int& x : b) cin >> x;
ll ans = 0;
SegmentContainer a_segments(n), b_segments(m);
a_segments.id = 1;
b_segments.id = 2;
SegmentMaintainer a_maintainer(a, a_segments, b_segments, ans);
SegmentMaintainer b_maintainer(b, b_segments, a_segments, ans);
cout << ans << '\n';
while (q--) {
int t, l, r, x; cin >> t >> l >> r >> x; --l;
if (t == 1) a_maintainer.RangeAdd(l, r, x);
if (t == 2) b_maintainer.RangeAdd(l, r, x);
cout << ans << '\n';
}
}
Why do the authors set $$$\sum c_i\le 2\cdot 10^5$$$ in problem D? There exists both $$$\mathcal O(n\log \max c_i)$$$ and $$$\mathcal O(n\sqrt{\max c_i})$$$ solutions.
Why do the authors set $$$\sum s \le 2\cdot 10^5$$$ in problem E? A init function can precalc the dp array. And the limit for $$$\sum s$$$ made it hard to hack brute-force solutions, for example, just simply do dfs. And the tests are quite weak that some dfs solutions passed the ST. Most of them can be uphacked with the test:
However, we can't hack 245835914 with the test above, can anyone help to hack it? :)
Anyway, I found most of the problemset nice. Kudos to the authors & coordinator!
Anyway, the difficulty of problems D and E as they are seems adequate for their position.
is the link you provided correct? is seems to be a diffrent problem. is the problem simular to problem d?
Yes, the formula used in that problem is the same up to rescaling.
thank you.
I think nobody proved, frankly it was incredibly intuitive for me.
not to me sadly :( can you explain how you thought of it? I guessed it was convex of course, but i couldn't feel that with my heart.
Me too, but then I wrote linear search and I looked every k, it seemed it was convex. I tried and it worked.
Also, you can see my first linear search submission which gets TLE.
did u solve as indicated in tutorial and got tle?
Bruh ur rating chart is kinda unique tho :)
Thanks, lol :D
Is it even possible to prevent solving problem without proving? besides, there is time penalty for WA verdict. especially in cp, almost no one tries to prove the logic. I think it's the contestant's job to keep the balance between intuition(for time) and proof(to reduce risk of WA, stupid impl) while competing
Its easy to prove , you must find largest k such that f(k)-f(k+1)>=x , that means it has increased rather than decreasing , when you observe change in f at any k its a decreasing function somewhat 1/k*(k+1) .
Perhaps it's difficult to definitively prove it, but it's quite intuitive. One increasing function is how much the power increases, another is how much it decreases, added together they make a convex function.
Additionally, the $$$\sum c_i\le 2\cdot 10^5$$$ allowed a brute force to pass the problem — just by noticing that there are at most $$$\mathcal O(\sqrt{n})$$$ different $$$c_i$$$-s.
Yes, but why is the contribution of each $$$c_i$$$ convex? The only proof we found is the one in the linked comment.
I thought it was well known (I also missed the $$$\sum c_i$$$ constraint), for example, here goes:
Let $$$f(k) = (c \% k)\left\lfloor\frac{c}{k}+1\right\rfloor^2 + (k - c \% k)\left\lfloor\frac{c}{k}\right\rfloor^2$$$ be the function that we want to prove being convex. If we replace $$$c\% k$$$ with $$$c - k\left\lfloor\frac{c}{k}\right\rfloor$$$, then we can consider this as a function not of positive integers, but of positive reals. I claim that this function is now piecewise linear, continuous, and convex.
Indeed, if $$$k\in \left(\frac{c}{a+1}, \frac{c}{a}\right]$$$ for some nonnegative integer $$$a$$$, then $$$\lfloor c/k\rfloor = a$$$, and $$$f(k) = ka^2 + (c - ak)(2a + 1)$$$ is linear in $$$k$$$ on this half-interval with the slope $$$-a(a + 1)$$$. Therefore, if we prove that $$$f$$$ is continuous, then it's convex because the slopes are nondecreasing.
To prove that it's continuous it suffices to check that $$$f(c/a - 0) = f(c/a + 0) = ac$$$ (exercise for the reader).
I think in this problem $$$f(k)=\binom{c \bmod k}{2}\left\lfloor \frac{c}{k} + 1 \right\rfloor^2 + \binom{k - (c \bmod k)}{2}\left\lfloor \frac{c}{k} \right\rfloor^2 + (c \bmod k)(k - (c \bmod k))\left\lfloor \frac{c}{k} + 1 \right\rfloor \left\lfloor \frac{c}{k} \right\rfloor$$$, but I think your proof still works.
And to prove the function is continuous, I think we should check if $$$\lim_{x \to (c/a)^+} f(x) = f(c/a)$$$.
And thanks for the proof anyway, it was very enlightening.
Your expression is how much each race contributes to something that we want to maximize. You can notice that if we split $$$c$$$ guys of a certain race into groups $$$c_1$$$, $$$\ldots$$$, $$$c_k$$$ (in our case they are almost equal), then your value is
so I minimize (not maximize!) the sum of squares instead.
About proving the function is continuous, in this case we should check $$$\lim\limits_{x\to c/a+0} f(x) = f(c / a)$$$, because we already know that the function is continuous from the left at $$$c/a$$$. However, for the same reason we can as well check $$$\lim\limits_{x\to c/a+0} f(x) = \lim\limits_{x\to c/a-0} f(x)$$$, which will in the end turn out to be the same, but here the function could as well be continuous from the right and this would still be the criteria.
How to be you
I only solved D, so I am replying to problem D only.
I think it affects the difficulty of the problem significantly.
I came up with an easy solution that depends on the array's maximum number of different elements, which is feasible due to this constraint.
My idea is that the maximum number of different elements would be achieved by an array that looks like 1 2 3 4 5 .... n. which would sum to n*(n+1)/2. So using the summation constraint you can easily prove that the max number of different elements is about 700.
Which makes trying each possible squad size for every element feasible.
Here is a link to my solution, I hope it helps someone.
https://codeforces.net/contest/1928/submission/245866373
Can you share O(nsqrt(max ci)) solution ?
https://codeforces.net/contest/1928/submission/245915574
Its not O(nsqrt(max ci)) dear
dear 💀
thanks for fast editorial
Great problems overall, but felt that statements were often convoluted and difficult to comprehend. Still, thanks for the great contest.
can anyone hack my solution?
no, it is correct solution (hint: $$$f(k) - f(k-1) \geq f(k+1) - f(k)$$$)
Thanks for fast editorial! :)
bad F :(
Peopls disliking bro's cmnt thinking that he is a newbie
well aren't the people right?
Tell me you are clown, without telling me you are clown.
Can we solve D by binary search?
yes we can do that take minm squads as 1 and maximum can be max(c[i]) then we can easily see that value of our predicate function first increases and then decreases so it's like we have to find peak value in rotated sorted array which could be solved by binary or ternary search ,here is model solution using ternary search https://codeforces.net/contest/1928/submission/245874386 hope it helps
Let's say that we have to calculate the max value of h(k)
where h(k) = f(arr, k)-g(k)
g(k) = (k-1)*x
f(arr, k) is the total number of pairs after optimal distribution.
I get that k will be in the range: [1, max(arr[i])] but cannot understand why h(k) will be a unimodal function. Can you prove?
for each element i of the array (lets name it arr), when you increase the number of squads k, you are distributing the creatures more and more, which means that you are increasing the total number of pairs.
On the other hand, when x is greater than 0, it keeps decreasing the score when k increases.
So, you can see the score as a combination of an increasing function and a decreasing function.
One last thing to observe is that when k increases, the increasing function will increase slower and slower. This is because, for every element i of arr, we cannot distribute the creatures in more than arr[i] squads. Meanwhile, the decreasing function is always constant.
As a conclusion of this, the total score function will either be always decreasing (when the decreasing function keeps decreasing faster than the increasing function even from k=1) or will increase then stop and start decreasing.
I hope this helps you.
While your statements don't imply that the function is unimodal, they still prove why ternary search works(f(x) = f(x + 1) is only possible for x where f(x) is maximum). Thanks a lot!
could you precise why it doesn't imply that the function is unimodal? is there anything wrong? or is it because I didnt formulate my statements well?
Unimodality requires precisely one 'x' for which the function monotonically increases and decreases before and after.
Consider a case where increasing bins adds exactly k to the answer. (For example, take k = difference due to increasing the number of pairs for some x bins). In this case, f(x) = f(x + 1), which means f(x) is not unimodal.
This wouldn't generally work for ternary search because if f(x) = f(x + 1) for some point other than maxima, we might remove the region of interest in the answer. However, since it only happens at maxima in the question(your statement proves this), we never remove the region of interest and ternary search works!
Okay I get it.
I personally used binary search to solve this problem and it worked fine. Why is everyone using ternary search tho?
I understood it in a different way.
h(k) = f(arr,k) + g(k)
We know that f(arr,k) is a concave function. (it inc. and stays const., and never decreases)
g(k) = (1-k)*x, which is a straight line (also a concave function).
the sum of several concave functions is also a concave function.
the sum of several convex functions is also a convex function.
We can use ternary search on concave/convex functions to find max/min.
that's correct. its the same reasoning, you only used more technical words.
It's an upside-down parabola. So ternary search.
is there any way to download the test case where answer is getting wrong ?
one hack is to just output the test case which is causing problem
For example: if test-case 3213 is causing problem
cin>>t while (t--) if (t==total-3213) cout<<input<<endl;
something like this? this solution (1928B — Equalize) getting WA on testcase 3
(i have tried above written code bot it is giving error)
You need to read input has well in the if case then output that input on stdout, also while printing on stdout, make sure there are no spaces, you can put some special character like ':', ',' as delimiter, otherwise CF judge will not show you what's after whitespace
Can you please give me an example Actually I can't understand the syntax
Suppose input is a string and your program fails at tc=3213 and there are 10000 test cases
cin>>t; while (t--) { if (t==10000-3213) { string s; cin>>s; cout<<s; // when this is printed CF online judge will give wrong answer } }
thanks brother hope this will help me a lot
Thanks for fast editorial ! I find my bad math for c question :(
Thank you for crushing my spirits
Problem C: "To consider the second case, it is necessary to proceed similarly with the number n+x−2"
How does it come (n+x-2) for the second case !
(2k − 2)⋅t + k + k − x = n
(2k — 2).t + 2k = n + x
(2k — 2).t + 2k — 2 = n + x — 2
(2k — 2)(t + 1 ) = n + x — 2
You are a pretty good mathematician.
The Problem C bother me in this Round.
Here is a video editorial: https://www.youtube.com/watch?v=AM6pz2H6JzQ&t=29s
You can check out my comment for a very detailed explanation.
D using ternary search: solution
Problem B:
the difference between the maximum and minimum does not exceed n−1 , can become equal.
. Is any mathematical proof available to prove that all such sets can always be satisfied?P.S. Thank you for the fast editorial
We can add permutation of $$$1..n$$$.
$$$max(1..n) - min(1..n)=n-1$$$ $$$\blacksquare$$$
thank you
thanks, it was a very good contest
Can someone help me look at problem B? I can't find my mistake 245895448
Take a look at Ticket 17337 from CF Stress for a counter example.
Thank you very much
Artyom123 Code for problem B has two main functions, probably you could edit that. Thanks for the tutorial!
Please explain C. I have been trying it for like 2 hours and dont get it. The editorial is so unclear
and yeah i HATE the code for it. Was it really necessary to write this way?
The problem could be simplified to "count the number of distinct integers which divide n — x and n + x — 2".
My submission: 245894639
yeah thanks, gonna try it tomorrow
Can u explain why are we checking if factor is greater than x * 2 — 2?
I did it using periodicity of the function. You can see that the whole pattern $$$1,2,3,..,k,k-1,...,2$$$ starts repeating after $$$2k-2$$$ terms. So basically, the graph looks like:
where $$$t$$$ axis denotes the person number $$$(1,2,..)$$$ and $$$y$$$ is the label assigned. So, now for this graph to have intersection with $$$y=x$$$ one condition will be: $$$k \ge x$$$. Now, we have two cases:
$$$1.$$$ $$$x=n$$$ is in one of such "rising" lines. From this, we get an equation like: $$$x+p \cdot (2k-2) = n$$$, where $$$p \in \mathbb{Z}$$$, from here we simply get $$$(2k-2) | (n-x)$$$, now you can find all factors of $$$n-x$$$, and impose two conditions, first it should be even (as $$$2k-2$$$ is even), and second, that $$$k = (f+2)/2 \ge x$$$.
$$$2.$$$ If $$$x=n$$$ in one of the "falling" lines, then you will get $$$2k-x + p \cdot (2k-2) = n$$$, which again can be manipulated as $$$(p+1) \cdot (2k-2) = n+x-2$$$ (not so trivial like the first case) $$$\implies (2k-2) | (n+x-2)$$$, then again you have to check for factors of $$$n+x-2$$$ and do the same thing as in case $$$1$$$ !
I think I thought very mathematically but I guess the logic should be clear to you now!
My submission: 245852020
can you please explain how did you get this equations in brief.Please
It's just applying definitions of a periodic function: $$$f(x)$$$ is periodic with periodicity $$$T$$$ if $$$f(x+n \cdot T) = f(x)$$$ for any $$$n \in \mathbb{Z}$$$.
Now onto my solution: The $$$t$$$ axis is the person number and $$$y$$$ axis is the label assigned (I have shown a continuous graph, but actually it will have points). Now, according to the question we want $$$f(n) = x$$$, where $$$f(1) = 1,..., f(k) =k,...,f(2k-2) = 2, f(2k-1) = 1,..$$$ so you can see $$$f(t+(2k-2)) = f(t) \, \forall t \in \mathbb{N}$$$, so $$$2k-2$$$ is precisely the periodicity of the given function. Now, if I have $$$k < x$$$, then this can never have intersection with the line $$$y=x$$$, hence we need to have $$$k \ge x$$$. After this condition is imposed, if I look in the interval $$$[1,2k-2]$$$, I have two "principle" solutions namely, $$$t = x$$$ and $$$t = 2k-x$$$ (As it is symmetric about $$$t=k$$$). Thus, for the two cases we get two different set of solutions:
$$$x + p \cdot (2k-2) = n$$$
$$$2k-x + p \cdot (2k-2) = n$$$
where $$$p \in \mathbb{Z}_{+}$$$
Side note: $$$sinx$$$ is a periodic function, so the solution for the equation $$$sinx =1$$$ is in an infinite set {$$$\frac{\pi}{2} \pm n \cdot 2 \pi \, ; n \in \mathbb{Z}$$$}, where $$$2 \pi$$$ is the periodicity of $$$sinx$$$ and $$$\frac{\pi}{2}$$$ is a principle solution.
I think, this is the greatest depth I can explain my solution in, if you are still not sure, I would recommend you to read about periodic functions.
thank you
Those who might be confused why we need to check two conditions.
1. 2k-2 is an even divisor you can't express any odd number by this expression.
2. k=(f+2)/2≥x
Assume, we have n = 100, x = 10 for k = 2: 1 2 1 2 1 2 ... for k = 3: 1 2 3 2 1 2 3 ... so on, can we get x number? No.
Can anyone please point out the error in my logic to find out the maximum length of the subarray? Even after doing multiple dry runs i am not able to figure out the logical error. 245902899
On the line 26 of your solution,replace arr with v.
It seems that you confuse arr with v
My (n+m+q)(log(n)+log(m)) collaterally died :(
I had a question regarding problem D. Lets call the array containing count of races "cnt" and sort it. Lets say cnt[3]=3 and cnt[4]=6 in a given test case. Is it ever beneficial for us to select number of squads=4 or 5? What I want to know is that is it ever beneficial for us to choose number of squads!= some cnt[i].
Interesting question! I don't think 4 or 5 squads would be of any use in this case.
Why?
Great solution for D!
Sadly I didn't solve it,I'm too bad:(
any one can help and explain how did they reach the solution of problem B not the solution but how did you reach to that solution?
you need to add a permutation to an array, and you want to maximize the number of equal elements. Since all elements in a permutation are distinct, there is no need to keep duplicates in our intiial array.
Now, suppose we have extracted all distinct elements from our initial array. if we take a look at two different elements at indexes i and j (1<=i,j<=n). if arr[i]<arr[j], we need to add a number x to arr[i] and another number y to arr[j] so that we obtain arr[i]+x=arr[j]+y. Thus, x-y=arr[j]-arr[i]. So, we need to add two numbers x and ythat have the same difference between them as between arr[i] and arr[j].
Now, since we are adding a permutation to our initial array, we are not free to choose any x or y. x and y should be between 1 and n. This implies that x-y<=n-1. since s-=arr[j]-arr[i], then : arr[j]-arr[i]<=n-1.
In conclusion, our task is to calculate the maximum number of distinct elements that have a difference less than or equal to n-1.
Hope that you find this helpful.
In C why divisors of n+x-2
Check my comment !
I will appreciate if someone could either prove or hack this greedy solution to E
https://codeforces.net/contest/1928/submission/245926933
See https://codeforces.net/blog/entry/125652?#comment-1115429 for an explanation of the greedy approach.
Two main functions in solution of B??
:(
Curious to know why there are couple of comments as "bug1" and "bug2" in the code solution of 1928C — Physical Education Lesson. Are there any flaws in the code implementation ?
245940869 my $$$q\sqrt n$$$ works (:
Someday I will definitely learn how to cut off the $$$\sqrt n$$$ ones. The battle is lost, but the war is not over.
For the code solution to problem B, the code contains 2 instances of
signed main()
Just a minor typo though.Another approach for Div2 D [ Note that this approach does not rely on the sum of $$$c_i$$$ being bounded by $$$2e5$$$ ]
Let's notice the formula for a particular $$$c_i$$$ if $$$k$$$ (number of squads) is fixed. If $$$q = c_i / k$$$ and $$$r = c_i \mod k$$$, then the number of extra pairs is $$$c_i(c_i - 1) / 2 - [(k-r)*q*(q-1)/2 + r*q*(q+1)/2]$$$ [Idea: Subtract the bad pairs from total number of pairs). We need to sum this up for all $$$i$$$ from $$$0..(n-1)$$$
The first term is easy, we can precalculate the sum and store it. Focus on the next two terms inside square bracket. Upon simplification: $$$k*q*(q-1)/2 + qr$$$. We have to sum this for each $$$i$$$.
Let's fix $$$k$$$ and all multiples of $$$k$$$ [This can be done easily]. Consider the multiple $$$mk$$$. For all values of $$$c_i$$$ in the range $$$[mk ... (m+1)k)$$$ the quotient is $$$m$$$ and the remainder is $$$c[i] - m*k$$$. We just have to sum them up by plugging in the formula above. The term $$$k*q*(q-1)/2$$$ is easy. It is constant. For $$$q*r$$$, we will need prefix sums of $$$c$$$. Locating the values of $$$c$$$ in the range can be done using binary search
Time complexity: $$$O(\max{c_i} \log (\max{c_i}) \log n)$$$. Iterating through the multiples and doing binary search to find the range of c.
Submission: https://codeforces.net/contest/1928/submission/245957808
What is the name of the category in which problems like D — > Lonely Mountain Dungeons lies? Can someone please share a list of problem of similar nature for practice?
439D - Devu and his Brother has similar 'weight' function and can be solved with similar approach.
Thanks for the help. If you get some more examples do mention them.
.
Sorry, I didn't know (I think it would be faster if didn't choose a random block size)
Can you explain your solution? Could it be that there will be $$$O(q \sqrt[3]{n})$$$ real calculations here?
As in the official solution, we have some (multiset $$$H$$$ of) horizontal blocks and some vertical blocks $$$V$$$. The answer is then
For each $$$s$$$, I maintain $$$h_s = \sum_{x\in H}\max(0, x - s + 1)$$$ and $$$v_s = \sum_{y\in V}\max(0, y - s + 1)$$$, as well as the $$$\sum h_iv_i$$$. Sometimes I have events of sort "one horizontal/vertical block of length $$$x$$$ appeared/disappeared". Each such event is equivalent to the query "for each $$$i$$$ from $$$1$$$ to $$$x$$$, add $$$sgn\cdot (x + 1 - i)$$$ to $$$h_i$$$/$$$v_i$$$", where $$$sgn = \pm 1$$$.
So first I wanted to maintain it with segment tree, storing in each node the following: if the corresponding (horizontal/vertical) blocks on this segment are $$$a_0$$$, $$$\ldots$$$, $$$a_{l-1}$$$, then I store $$$\sum a_i$$$ and $$$\sum i\cdot a_i$$$, and also the dot product $$$\sum h_iv_i$$$. But then it occurred to me that pushing delayed operations is kinda nontrivial. That's why I split everything into blocks of $$$K$$$, and each event is now "add some arithmetic progression to about $$$n/K$$$ whole blocks, and also maybe on the prefix of another block". This can be done quite easily, if we remember for each block the current arithmetic progression to be added (and also what I wanted to store for the segment tree). So yes, this works in something like $$$O(q(n/K + K)) = O(q\sqrt{n})$$$, and I just set $$$K = 300$$$ and submitted. I think $$$K = 600$$$ or so would probably be better, idk.
Can anyone explain what is my mistake in task B? 245838570
You skip too much possible left ends with
k = i
I don’t understand what you mean, can you give me some kind of test?
Thank you!
I realized my mistake!
I was looking at the code for problem C (physical education lesson). I think there's a mistake. while populating the unordered_set answer, it should be answer.insert((i + 2)/2).
(i + 2)/2
and1 + i / 2
are identical:$$$\displaystyle\frac{i + 2}{2}$$$
$$$= \displaystyle\frac{i}{2} + \frac{2}{2}$$$
$$$= \displaystyle\frac{i}{2} + 1$$$
$$$= \displaystyle 1 + \frac{i}{2}$$$
Why are we populating with 1+i/2 at the first place, could you please explain that ? Thank you
we need to count the # of distinct k's we can get by using divisors that can be written in the form 2k — 2
so rewrite 2k — 2 as 2(k-1), and now we know the divisor must be even.
for each i that divides (n-x) or (n+x-2), make sure it's even
if it is, then we know i can be written in the form 2(k-1)
so i = 2(k-1)
i / 2 = k-1
k = i / 2 + 1
Thank you so much
for question B
int l=a.size(); int d=n-1; int s=0,e=l-1;
in this code a is the sorted array of elements after removing repeated elements . why does this give wrong answer in test 3 . logic is to shorten the array from the side having greater difference between consecutive element to accomodate maximum elements within the difference range p.s. int here is long long int
in the problem tag in problem D: there is ternary search. How can we use it in Problem D??
ternary search the number of squads i think.
But how, I don't think the graph formed is unimodal! As per as what i have observed the graph will somewhat be like negetive of sin: -sin(x) type.. Hence how are we doing ternary search. Also this is my submission and it gives tle. Awaiting for ur explaination. https://codeforces.net/contest/1928/submission/245999184
Can anyone check my submission in problem D? I cannot demonstrate my solution clearly.
Thank you and have a good day!
My submission: 245993112
Can someone prove that the function for D is unimodal?
check my comment https://codeforces.net/blog/entry/125740?#comment-1116388
not even kidding , problem 3 was running correctly in contest just because of a single if condition (if divisor is less than x than its possible) , accepted after contest.
Does not the solution to the problem B yield n^2 complexity? Like, for the test case where n = 2x10E5 and a = [1, 2, 3, ... , 2x10E5].
No, in your case the code
will not run.
Problem C video Editorial : Youtube Video Link
If you are not able to understand the Editorial then you can refer to this video....I have explained the complete solution in Hindi
I wrote an in-depth, beginner-friendly solution for 1928A — Rectangle Cutting, complete with detailed explanations and diagrams: https://notes.yxy.ninja/cp/number_theory/(CodeForces)-Rectangle-Cutting. Hopefully someone finds it useful.
Another solution to Problem B if you missed max — min observation
Here is a version of the binary search solution to Problem B, since nobody has written it in the comments even though binary search tag is present.
Basic intent: for a given $$$endpoint\;value$$$, our task is to look at how much we will have to add to each $$$a[i]$$$ to attain the endpoint value. That, is look at differences $$$(endpoint - a[i])$$$. Then, pickup up all unique and eligible differences, i.e differences in range $$$[1,n]$$$. This is the best possible answer for the chosen endpoint.
Issue: We don't know what the best/optimal endpoint that we should choose is.
Greediness: All $$$a[i]$$$'s bigger than a chosen endpoint are simply irrelevant since there is no way to decrement anything. Among all $$$a[i]$$$'s that are smaller than chosen endpoint, it makes sense(greedily) that we will always be adding lesser to the $$$a[i]$$$'s closer to the endpoint and more to the $$$a[i]$$$'s that are farther (or much smaller) than chosen endpoint. Thus chosen endpoints are always of the form $$$(a[i] + 1), \forall i$$$.
Resolution to Issue: If we can somehow reuse the differences we calculated for one chosen endpoint, then we can try out all endpoints while only adding a linear factor to our time complexity.
Combining Everything: Lets sort all $$$a[i]$$$. And, lets begin by considering the max element as the chosen endpoint, i.e $$$endpoint = (a[n] + 1)$$$. Evaluate and store all differences $$$(endpoint - a[i])$$$.
How to reuse differences evaluated: Purely mathematical. In our sorted array of $$$a[i]$$$'s, lets say we transition chosen endpoint from $$$(a[j] + 1)$$$ to $$$(a[k] + 1)$$$ for any $$$(j > k)$$$. Also, lets call $$$a[j] - a[k] = delta$$$.
Then, all differences are related as: $$$endpoint_j = (endpoint_k + delta)$$$.
Also, it follows that if the eligible range of differences that we can pickup are related as: $$$if\; eligible_j = [low,high], \;then\; eligible_k = [low+delta, high+delta]$$$. Thus, we can simply binary search with modified limits in the already calculated differences.
Code1: 246326560
nice contest
How to solve E using graphs?
I wrote an in-depth, beginner-friendly solution for 1928B — Equalize, complete with detailed explanations: https://notes.yxy.ninja/cp/greedy/(CodeForces)-Equalize. Hopefully someone finds it useful.
.