Thanks for participating in my contest 
. I hope you liked the problems. I would love to hear your feedback in the comments.
If you find anything wrong in the editorial which is more likely to happen because I have written a rather long editorial to make you understand the solutions better, then comment below.
Also, don't forget to upvote to pay for the editorial. See you in my next contest!
Tutorial is loading...
Code
#include<bits/stdc++.h>
using namespace std;
int main() {
int t; cin >> t;
while (t--) {
int n; cin >> n;
int ans = 0;
for (int i = 1; i <= n; i++) {
int k; cin >> k;
ans = max(ans, k - i);
}
cout << ans << '\n';
}
return 0;
}
Tutorial is loading...
Code
#include<bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t; cin >> t;
while (t--) {
int n; cin >> n;
vector<int> a(n + 1);
bool inc = true;
for (int i = 1; i <= n; i++) {
cin >> a[i];
inc &= a[i] > a[i - 1];
}
if (n % 2 == 0 or !inc) {
cout << "YES\n";
}
else {
cout << "NO\n";
}
}
return 0;
}
Tutorial is loading...
Code
#include<bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t; cin >> t;
while (t--) {
int n; cin >> n;
bool ok = true;
for (int i = 1; i <= n; i++) {
int x; cin >> x;
bool found = false;
for (int j = i + 1; j >= 2; j--) { // this loop will run not more than 22 times, in practice its much lower than that
if (x % j) {
found = true;
break;
}
}
ok &= found;
}
if (ok) {
cout << "YES\n";
}
else {
cout << "NO\n";
}
}
return 0;
}
Tutorial is loading...
Code
#include<bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t; cin >> t;
while (t--) {
int x, y; cin >> x >> y;
if (x <= y) {
cout << y - y % x / 2 << '\n';
}
else {
cout << x + y << '\n';
}
}
return 0;
}
Tutorial is loading...
Code
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9, mod = 998244353;
vector<int> v[2];
int dp[2][N];
int a[N];
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t; cin >> t;
while (t--) {
int n; cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
long long ans = 0;
for (int i = n; i >= 1; i--) {
int k = i & 1;
v[k].push_back(a[i]);
dp[k][a[i]] = 1;
int last = a[i];
for (auto x: v[k ^ 1]) {
int y = dp[k ^ 1][x];
int split = (a[i] + x - 1) / x;
int st = a[i] / split;
ans += 1LL * (split - 1) * y * i;
dp[k][st] += y;
if (last != st) {
v[k].push_back(st), last = st;
}
}
for (auto x: v[k ^ 1]) dp[k ^ 1][x] = 0;
v[k ^ 1].clear();
ans %= mod;
}
cout << ans << '\n';
for (auto x: v[0]) dp[0][x] = 0;
for (auto x: v[1]) dp[1][x] = 0;
v[0].clear(); v[1].clear();
}
return 0;
}
Tutorial is loading...
Code (1D1D DP)
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
const long long inf = 1e12;
using ll = long long;
int phi[N];
void totient() {
for (int i = 1; i < N; i++) phi[i] = i;
for (int i = 2; i < N; i++) {
if (phi[i] == i) {
for (int j = i; j < N; j += i) phi[j] -= phi[j] / i;
}
}
}
ll a[N], s1[N][320], s2[N][320];
int root[N];
ll c(int l, int r) {
if (l > r) return inf;
ll ans = 0;
if (r / l <= root[r]) {
return s1[r][r / l] - a[r / l] * (l - 1 - r / ((r / l) + 1));
}
else {
return s2[r][l];
}
return ans;
}
ll dp[N][17];
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
totient();
for (int i = 1; i < N; i++) {
a[i] = a[i - 1] + phi[i];
}
for (int i = 1; i < N; i++) {
root[i] = 0;
for (int j = 1; j * j <= i; j++) {
s1[i][j] = s1[i][j - 1] + a[j] * (i / j - i / (j + 1));
root[i] = j;
}
s2[i][i / (root[i] + 1) + 1] = s1[i][root[i]];
for (int j = i / (root[i] + 1); j >= 1; j--) {
s2[i][j] = s2[i][j + 1] + a[i / j];
}
}
int n = 100000;
dp[0][0] = 0;
for (int i = 1; i <= n; i++) {
dp[i][0] = inf;
}
for (int k = 1; (1 << k) <= n; k++) {
dp[0][k] = 0;
vector<pair<int, int> > v; // (start pos, best j)
v.push_back(make_pair(0, 0));
for (int x = 1; x <= n; x++) {
int j = (--lower_bound(v.begin(), v.end(), make_pair(x + 1, 0)))->second;
dp[x][k] = dp[j][k - 1] + c(j + 1, x);
for (int i = (int)v.size() - 1; i >= 0; i--) {
int y = v[i].first, oldj = v[i].second;
if (y > x && dp[x][k - 1] + c(x + 1, y) < dp[oldj][k - 1] + c(oldj + 1, y)) v.pop_back();
else {
int l = y + 1, r = n + 1;
while (l < r) {
int mid = (l + r) / 2;
if (dp[x][k - 1] + c(x + 1, mid) < dp[oldj][k - 1] + c(oldj + 1, mid)) r = mid;
else l = mid + 1;
}
if (r != n + 1) v.push_back(make_pair(r, x));
break;
}
}
if (v.size() == 0) v.push_back(make_pair(0, x));
}
}
int q; cin >> q;
while (q--) {
int n, k; cin >> n >> k;
if (k >= 20 or (1 << k) > n) {
cout << n << '\n';
}
else {
cout << dp[n][k] << '\n';
}
}
return 0;
}
Code (D&C DP)
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
const long long inf = 1e12;
using ll = long long;
int phi[N];
void totient() {
for (int i = 1; i < N; i++) phi[i] = i;
for (int i = 2; i < N; i++) {
if (phi[i] == i) {
for (int j = i; j < N; j += i) phi[j] -= phi[j] / i;
}
}
}
ll a[N];
ll c(int l, int r) {
if (l > r) return inf;
ll ans = 0;
for (int i = l, last; i <= r; i = last + 1) {
last = r / (r / i);
int x = 0;
if (i >= l) x = last - i + 1;
else if (last >= l) x = last - l + 1;
ans += a[r / i] * x;
}
return ans;
}
ll dp[N][17];
void yo(int i, int l, int r, int optl, int optr) {
if(l > r) return;
int mid = (l + r) / 2;
dp[mid][i] = inf;
int opt = optl;
ll cost = c(min(mid, optr) + 1, mid);
for(int k = min(mid, optr); k >= optl ; k--) {
ll cc = dp[k][i - 1] + cost;
if (cc <= dp[mid][i]) {
dp[mid][i] = cc;
opt = k;
}
if (k <= mid) {
if (cost == inf) cost = a[mid / k];
else cost += a[mid / k];
}
}
yo(i, l, mid - 1, optl, opt);
yo(i, mid + 1, r, opt, optr);
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
totient();
for (int i = 1; i < N; i++) {
a[i] = a[i - 1] + phi[i];
}
int n = 100000;
dp[0][0] = 0;
for (int i = 1; i <= n; i++) {
dp[i][0] = inf;
}
for(int i = 1; i <= n; i++) dp[i][1] = 1LL * i * (i + 1) / 2;
for(int i = 2; i <= 16; i++) yo(i, 1, n, 1, n);
int q; cin >> q;
while (q--) {
int n, k; cin >> n >> k;
if (k >= 20 or (1 << k) > n) {
cout << n << '\n';
}
else {
cout << dp[n][k] << '\n';
}
}
return 0;
}
Tutorial is loading...
Code
#include<bits/stdc++.h>
using namespace std;
const int N = 205;
int mod;
int power(long long n, long long k) {
int ans = 1 % mod; n %= mod; if (n < 0) n += mod;
while (k) {
if (k & 1) ans = (long long) ans * n % mod;
n = (long long) n * n % mod;
k >>= 1;
}
return ans;
}
int dp[N][N][40], fac[N], ifac[N];
int vis[N][N][40];
int n, a1;
/*
number of solutions to the equation b1 + b2 + ... bn <= a1
s.t. 0<=bi<=n+1-a1
and there is at least 1 number >= n + 1 - a1,
at least 2 numbers >= (n - a1), ..., at least (n - a1) numbers >= 2
*/
int yo(int i, int sum, int k) { // k <= 2 * sqrt(n)
if (i == n) return fac[n];
if (k == 0) return 1LL * fac[n] * ifac[n - i] % mod;
if (vis[i][sum][k] == a1) return dp[i][sum][k];
vis[i][sum][k] = a1;
int &ans = dp[i][sum][k];
ans = 0;
int r = (a1 - sum) / k;
for (int cnt = r; cnt >= 0; cnt--) {
if (k > 1 and i + cnt < n - a1 + 1 - k + 1) continue;
ans += 1LL * yo(i + cnt, sum + cnt * k, k - 1) * ifac[cnt] % mod;
ans %= mod;
}
return ans;
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> mod;
fac[0] = 1;
ifac[0] = 1;
for (int i = 1; i < N; i++) {
fac[i] = 1LL * fac[i - 1] * i % mod;
ifac[i] = power(fac[i], mod - 2);
}
int ans = 0;
int lim = 2 * sqrt(n) + 1;
for (a1 = max(1, n - lim); a1 <= n; a1++) {
ans += yo(0, 0, n + 1 - a1);
ans %= mod;
}
ans %= mod;
cout << ans << '\n';
return 0;
}
Tutorial is loading...
Code
#include<bits/stdc++.h>
using namespace std;
const int N = 1e7 + 9, mod = 998244353;
template <const int32_t MOD>
struct modint {
int32_t value;
modint() = default;
modint(int32_t value_) : value(value_) {}
inline modint<MOD> operator + (modint<MOD> other) const { int32_t c = this->value + other.value; return modint<MOD>(c >= MOD ? c - MOD : c); }
inline modint<MOD> operator - (modint<MOD> other) const { int32_t c = this->value - other.value; return modint<MOD>(c < 0 ? c + MOD : c); }
inline modint<MOD> operator * (modint<MOD> other) const { int32_t c = (int64_t)this->value * other.value % MOD; return modint<MOD>(c < 0 ? c + MOD : c); }
inline modint<MOD> & operator += (modint<MOD> other) { this->value += other.value; if (this->value >= MOD) this->value -= MOD; return *this; }
inline modint<MOD> & operator -= (modint<MOD> other) { this->value -= other.value; if (this->value < 0) this->value += MOD; return *this; }
inline modint<MOD> & operator *= (modint<MOD> other) { this->value = (int64_t)this->value * other.value % MOD; if (this->value < 0) this->value += MOD; return *this; }
inline modint<MOD> operator - () const { return modint<MOD>(this->value ? MOD - this->value : 0); }
modint<MOD> pow(uint64_t k) const { modint<MOD> x = *this, y = 1; for (; k; k >>= 1) { if (k & 1) y *= x; x *= x; } return y; }
modint<MOD> inv() const { return pow(MOD - 2); } // MOD must be a prime
inline modint<MOD> operator / (modint<MOD> other) const { return *this * other.inv(); }
inline modint<MOD> operator /= (modint<MOD> other) { return *this *= other.inv(); }
inline bool operator == (modint<MOD> other) const { return value == other.value; }
inline bool operator != (modint<MOD> other) const { return value != other.value; }
inline bool operator < (modint<MOD> other) const { return value < other.value; }
inline bool operator > (modint<MOD> other) const { return value > other.value; }
};
template <int32_t MOD> modint<MOD> operator * (int64_t value, modint<MOD> n) { return modint<MOD>(value) * n; }
template <int32_t MOD> modint<MOD> operator * (int32_t value, modint<MOD> n) { return modint<MOD>(value % MOD) * n; }
template <int32_t MOD> istream & operator >> (istream & in, modint<MOD> &n) { return in >> n.value; }
template <int32_t MOD> ostream & operator << (ostream & out, modint<MOD> n) { return out << n.value; }
using mint = modint<mod>;
mint pw[N];
mint genius(int n, int k) {
if (k == 0) return 1;
vector<mint> c(k, 0), d(k + 1, 0);
d[k] = 1;
for (int i = k - 1; i >= 0; i--) {
c[i] = pw[i] * d[i + 1];
d[i] = (pw[i] - 1) * d[i + 1];
}
mint ans = 0, pwn = mint(2).pow(n), cur = 1;
for (int i = 0; i < k; i++) {
ans += ((k - 1 - i) & 1 ? mod - 1 : 1) * c[i] * cur;
cur *= pwn;
}
return ans;
}
mint f(int n, int k) {
if (k == 0 or n > k) return 0;
mint ans = 1;
for (int i = 0; i < n; i++) {
ans *= pw[k] - pw[i];
}
return ans;
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
pw[0] = 1;
for (int i = 1; i < N; i++) {
pw[i] = pw[i - 1] * 2;
}
int t; cin >> t;
while (t--) {
int n, k, x; cin >> n >> k >> x;
if (x) {
cout << genius(n, k) << '\n';
}
else {
cout << f(n, k) << '\n';
}
}
return 0;
}
1B was shit
Problems like div2 D(div1 B) which only requires some stupid mathematical observations makes me lose all hope from Codeforces.
The process that worked for me to solve it was:
Do a brute force for $$$x < y$$$ case, see all the possible answers for a few hand-made tests.
Look at one of an ends of the answers sequence (upper end works).
Observe that the number is close to $$$y$$$.
Think of the solution in the form $$$n = y - \varepsilon$$$ where $$$\varepsilon$$$ is very small.
Then $$$y \bmod n = y \bmod (y - \varepsilon) = \varepsilon$$$.
And $$$n \bmod x = (y - \varepsilon) \bmod x = y \bmod x - \varepsilon$$$.
The two are equal, so $$$2 \cdot \varepsilon = y \bmod x$$$.
So, yeah, some amount of observation was required, but it mostly followed from looking at the brute-forced list of all possible answers.
I solved it by very straightforward solution. 133667090
if y < x, then ab = 0, just return x + y
I don't know why it works. Hope someone can proof it or hack it.
It's correct but you need to carefully check whether the factorization leads to a valid answer. a=floor(y/x), b=1, r=(y-ax)/2 is a solution (since x, y are both even, r will be integer).
That' it! I divided from 1, so always got the answer you mentioned. Thanks.
In the 3rd statement returning (x+y) was just an observation or you calculated. Can you elaborate plz
A view of it:
The expression $$$n \bmod x = y \bmod n$$$ is complex.
And $$$n$$$ can be up to $$$2 \cdot 10^{18}$$$ according to the statement.
But if $$$n$$$ was large enough, the formula will transform into just $$$n \bmod x = y$$$, which is simple.
So let us think about large enough $$$n$$$.
When $$$x > y$$$, the expression $$$n \bmod x = y$$$ means we can use $$$n = x \cdot k + y$$$ for any large enough integer $$$k$$$.
Turns out $$$k = 1$$$ is fine.
Ohh got it. Thanks a lot Gassa.
Hey Gassa, can you please explain why ymod (y-e) = e ?
Try to imagine it with concrete numbers:
Let $$$y = 1\,000\,000$$$ and $$$\varepsilon = 5$$$. Then
$$$1\,000\,000 \bmod 999\,995$$$ is simply
$$$1\,000\,000 - 999\,995 = 5$$$.
Generally, the equation
$$$y \bmod (y - \varepsilon) = y - (y - \varepsilon)$$$
holds for $$$0 \le \varepsilon \le y / 2$$$.
Hello! I was unable to come up with this kind of solution. What do you suggest to do if I want to solve problems like this in a real contest. Should I take this problem seriously regarding the approach you took like I could understand the things you wrote and they were pretty much justified in them so no doubt in that.
My div1B experience:
struggle >1 hour writing equations to find n with rigurous maths.
in the last 15 minutes: look at random particular cases of x and y and try to guess the formula. I actually got AC with a half-guessed formula 1 minute before the round ended... Perfectly balanced guessforces problem
#mathsforces #adhocforces
you are alt of spacetime , aren't you ?
stalker
Great Contest! Was able to solve 3 and 4th went off in nick of time.
Completely Mathforces
And thanks for the fast editorial.
My DIV2B didn't get AC though it's the same as you described
a[i]<=a[i-1] would probably get you ac
Editorial be like:
For 1603A - Di-visible Confusion we can also go from the end of an array and try to remove each item, and after each removal repeat the process. If you passed the whole array and didn't find an element to remove, the answer is
NO. It can be shown that in the worst case you will pass each element no more than21-22times (you proved it in the editorial), so this solution is also possible.The only sad thing about this solution is that you need to calculate an actual index of your element, and in order to do that you may need Fenwick tree.
Solution: 133626329
I think we do not need a Fenwick tree in this solution: simply shift each element after the removed one. (The complexity is good since each element is shifted at most 21 times.)
Code: 133622802
Or just use linked lists
P-A Ignore
In the editorial for problem C it is written that "must be divisible by at least one integer from 2 to i+1", I guess it should have been "not divisible by". thanks. btw, great contest.
UPD: It is updated now.
did anton also write the
Thanks to Anton for writing editorial for this problem.These cringy math symbols are going to give me nightmare tonight
Whoa, i've got a simple solution for div.1 C, though i don't know how to prove its correctness (so maybe it's wrong).
We use brute force set r from n to 1, and move l to the left, when minimal hasn't changed we skip it.
And it passed (right now)!!!
133667648
I think this solution is actually provable, cause every iteration you increase the value of one of the elements of cut array. And since there are O(sqrt(i)) possible values of cut[i] the total number of iterations is O(n*sqrt(n)).
Was this submission hackable? It's technically wrong because there might be overflow but I think all integers coming from this overflow have 9 digits or more, so none could divide the numbers, which is unfortunate.
I solved Div1F with a different formula: the answer is
where
is a gaussian binomial coefficient (https://en.wikipedia.org/wiki/Gaussian_binomial_coefficient).
I have an $$$O(n\log^3 n)$$$ solution for D1D which sadly I wasn't able to debug during contest because of wasting time on A:
Just use segtrees to optimize calculating $$$f(n,K)$$$. Precalculate $$$g(n,k)$$$ which is the number of $$$l$$$s such that $$$gcd(n,l)=k$$$, and mainting a segtree with range add and range minimum. When we encounter $$$n$$$, we insert $$$f(n-1,k-1)$$$ into segtree, and go over all $$$n$$$'s divisors $$$d$$$ and add $$$[1,d]$$$ by $$$g(n,d)$$$.
My solution is similar to you.
And it is the only problem I do during the contest.I submit with another account (
Enough Math for today. errrrrr
Alternative solution for Div1A/Div2C:
notice, that it is always beneficial to erase last element if possible — it won't ever affect any other number in the array and it have to be removed at some point. Why not now?
If you can't remove the last element, then it's beneficial to erase second-to-last element, if possible. The proof is by similar argument to the previous one.
...
In other words -- find the first element in reversed array that we are capable of removing. Execute this simple rule in a loop until array is empty (output YES) or no more elements can be removed (output NO).
Convince yourself that each element will be checked only a handful of times -- it's pretty hard to select a number that will be divisible by many of the indices $$$i + 1$$$, $$$i$$$, $$$i - 1$$$, ... . As the original editorial proved, it's at most 21 times.
Implement code using $$$\texttt{std::list}$$$ and $$$\texttt{std::find_if}$$$ (notice that
find_ifbreaks when it finds first occurence) -- 133627167. Total complexity: $$$\mathcal{O}(21n)$$$It just felt like a math contest or something, I wish I had seen more algorithm-oriented problems.
There is another solution to problem C as well:
Start from the end, if the last number is not divisible by (i+1) then erase it as it will not affect other elements. Now, find all the indexes which satisfy the given divisibility condition and store them in a priority queue. It is always good to delete elements (if possible) from the right. Also, calculate the count of consecutive values which will divide the number and we don't need to check this for more than 12-13 times.
Now delete the first element of the priority queue and update the values of all the indexes greater than the current deleted element and you are sure that you will not need to traverse each element more than 12-13 times, so it's fine.
End when the priority queue becomes empty (as this tells that all the divisible elements are removed) and check if all the elements are deleted or not.
My code : https://codeforces.net/contest/1604/submission/133638614
math
math
every
where
Here is how the donation amount looks like:
FYI I will get 400 USD for this contest. So the donation amount is indeed half of this as I have estimated before the contest, although didn't think that it would be this accurate.
I will update you again when I get the money from Codeforces, more likely after a few months as I haven't received my previous contest's payment yet which happened 3 months ago!
Also, thanks for being a part of this. You have just helped someone who is in need (I mean after I distribute the money).
Where will the money be donated?
I will update you when I get my payment. I will mostly distribute them to some poor people from the street. If you have some suggestions let me know.
just a suggestion try to donate to someone asking for help in ketto or something like that(means who r suffering from medical crises)
It's fine. I feel like it is the best way to do it, having no third parties involved will make sure that the money will be given to those who really need it.
TeamSeas
It's actually cool that the guess was so close!
A contest full of maths is really boring.
And Honey when you solve it within a minute.
Can you provide a proof for D&C Div 1 D time complexity? I belive you should rely on the properties of this specific dp, because otherwise you can make a test where at the bottom level you would have something like $$$opt_i = i - \frac{n}{2}$$$, which would lead to $$$O(n \sqrt n)$$$ time complexity for one layer.
The Editorial is quite long, it would be nice if you had used spoiler type as u did for code.
PS: I GOT FST!
For Div.2 C what I did was for every $$$i$$$, finding the nearest $$$j$$$ such that $$$j + 1$$$ is not divisible by $$$a[i]$$$ and pushing the index $$$i$$$ to $$$mp[i - j]$$$. Here, $$$mp$$$ is a map of vectors. $$$mp[d]$$$ eventually stored the indices that become erasable after $$$d$$$ elements from their left gets erased.
Obviously we need to start by erasing some element in $$$mp[0]$$$. Here, starting with the rightest element $$$x$$$ is the optimal because minimum number of elements gets negatively affected from this operation. So we erase $$$x$$$ from $$$mp[0]$$$. After erasing $$$x$$$ we have to check whether there are new erasable elements to the right of $$$x$$$ and such elements can only be in $$$mp[1]$$$. Thus we check whether the rightest element of $$$mp[1]$$$ (let's call it $$$y$$$) is bigger than $$$x$$$. If not, we have to keep erasing from $$$mp[0]$$$. If yes, it is a good idea to first erase $$$y$$$ along with the indices that get erasable after erasing $$$y$$$ (It is a recursive process). Only after that we can continue with erasing from $$$mp[0]$$$.
Eventually all the vectors should become empty in $$$mp$$$. If they are empty then the answer is "YES", otherwise the answer is "NO".
Here is some in-contest ugly code but it failed the system test :( 133669599
What the code does is there is a function
solve(k, iterator)andkmeans the rightest element we have deleted before calling this function and the iterator basically finds the most recent non-empty vector waiting for their elements to get erased. Can anybody help me what is wrong with my solution?Why Itst_boyfriend's submissions are being shown out of contest?
i think his code matched with others unfortunately and he was removed from the contest
In Div2 D, in case of (x<y) why can't n be (x+y)/2. For example, if x=2 & y=4, n can be 3 which is equal to (2+4)/2. In this case, n%x = 1 and y%n is also 1. Can anyone tell me the case where this condition fails. Thanks in advance!
x=4,y=14. It will fail on lot of cases like this.
Seems like the solution of maths question paper.
Here is a simpler solution to div1C:
Assume that we want to calculate the extreme value of $$$a_1, a_2, \dots, a_i$$$. Let $$$t[j]=$$$ how many numbers $$$a_j$$$ is divided into, $$$v[j]=$$$ the smallest number $$$a_j$$$ is divided into. We know $$$t[j]=\lceil\frac{a_j}{v[j+1]}\rceil$$$, $$$v[j]=\lfloor\frac{a_j}{t[j]}\rfloor$$$. It can be observed that the extreme value of $$$a_j, a_{j+1}, \dots, a_i$$$ is $$$\sum_{k=j}^i (t[j]-1)$$$.
For $$$i$$$ from $$$1$$$ to $$$n$$$, calculate $$$t[j]$$$ and $$$v[j]$$$ for all $$$j \leq i$$$. When we add a new element $$$a_i$$$ at the back, we can update $$$t[j]$$$ and $$$v[j]$$$ from $$$i-1$$$ to $$$1$$$ by brute force, but we stop the procedure when $$$t[j]$$$ is not changed. It seems to be an $$$O(n^2)$$$ solution, but for a certain $$$j$$$, $$$t[j]$$$ can be up to only $$$O(\sqrt C)$$$ different values, so we only update a value at most $$$O(\sqrt C)$$$ times, the solution is in $$$O(n \sqrt C)$$$ time.
Code: 133689083
My solution (133668323) is similar to this.
The worst test case for this I found locally is
100000 99999 99998 ... 3 2 1, where the inner loop body is executed ~35 million times. It is a bit more than $$$100\,000 \cdot \sqrt{100\,000}$$$, but still far from that amount doubled, which is the theoretical upper bound. I wonder if there is a more clever test to push the count further.It may be a dumb question but I don't see why it's ok to stop when $$$t[j]$$$ is not changed.
The values $$$t[j]$$$ and $$$v[j]$$$ together fully define what happens to the left of them.
For example, when you separate $$$10$$$ into three parts, you know the best way to do it is $$$10 = 3 + 3 + 4$$$. Going to the left of this position, all you need to know is that all the parts have to be $$$\le 3$$$. So, if you have already calculated what is the optimal solution on the left for parts $$$\le 3$$$, there is no need to do it again.
It's like memoization but without recursive calls.
Sorry I didn't notice the part to the left is still added to the answer when we stop. I wrongly thought we weren't adding it again. I got it now, thank you.
That's a nice solution, imo nicer than the editorial.
I think an important point you didn't mention is that the value of t[j] is non-decreasing for increasing i
I have an alternate solution for Div 2C that I personally find easier. I found a simple solution where I simply store an array of numbers to represent how many positions each value of a must be shifted to no longer be divisible by i+1, then I walk through the array and ensure that each value is less than the amount of numbers preceding it in the array. This works because it can be proved that as long as the sequence can be reduced, there is always an optimal move that does not negatively affect any of the other positions, so you do not need to worry about shifting a number from a non-divisible status to a divisible status. Apologies for any confusion as I am not too familiar on how to format comments and I am not too skilled at describing algorithms. My code is here: https://codeforces.net/contest/1603/submission/133704780
Very cool contest! I personally quite enjoyed the observation/logic side... I don't think the maths were too difficult either, although I couldn't figure out 2D for x<y. Thank you for the fun problems.
Any intuition behind div2 D in the second part where y >= x
YouKn0wWho
Div1 F — The explanation has many off-by-one errors. In particular, the answer for $$$X\neq 0$$$ should actually be
Shouldn't $$$n$$$ be $$$k$$$ here?
It's also worth noting that counting the number of length-$$$N$$$ sequences such that the resulting subspace has dimension $$$k$$$ for each $$$k\in [0,K]$$$ is given by
This can be computed with the q-binomial theorem (with $$$q=2$$$). After computing these, the answer will be
Code: 133694728
I was not aware that evaluating
was doable but it seems that rainboy managed to find this link during the contest, congrats!
The formula can be obtained by disturbing the GF. Let $$$F(t)=\prod_{i=0}^k \frac1{1-q^it}$$$, then we have $$$(1-t)F(t) = (1-q^{k+1}t)F(qt)$$$, hence a recurrence.
Not totally sure which formula you are referring to. Could you elaborate on how $$$(1-t)F(t)=(1-q^{k+1}t)F(qt)$$$ allows us to determine the coefficients of $$$F(t)$$$?
EDIT: Ok, if we define
then
from which the result follows. Thanks!
Consider the $$$[t^n]$$$ of two sides of the equation, then it gives a recurrence of $$$[t^n]F$$$.
1D : Isn't $$$c(x,2x-1)=x$$$?
All pair like $$$(i,i)\ (x\leq i \leq 2x-1)$$$ satisfy $$$gcd(i,j)>=l$$$.
Upd : And the editorial's difination of $$$c(i,j)$$$ is diffent from statement's.
Really Mathforces.
An alternate solution for div2D/div1C (quite similar in idea though)
Perhaps the editorial for Div1 D,E are the clearest ones I've ever seen.
The problems are truly nice.
There is a mistake in the Proof of the observation 3 in problem E. Perhaps the author mistook i as j:(
You are right. I will update asap.
woo, the author's just got so crazy at sqrt that it appears at the overall complexities of three adjacent problems!
The Editorial of Div1E is really detailed and easy-understanding.
Thank you!
Why my submission is giving wrong answer not runtime error? submission 133743503 , I have checked "assert(ans%x == y%ans && ans <= 2000000000000000000LL && ans >= 1);". Am I missing something ?
You have modified the value of x before your assert function.
For 1603C - EXTREME EXTENSION - Extreme Extension, the space can be reduced to O(sqrt(M)) where M = 100,000, the maximum possible input value. This is using the observation that if we have a quotient x/k, then min(k, x/k) ≤ sqrt(x), so instead of a single vector of length M, we can use two vectors of length sqrt(M) (one of the values of k, one for the values of x/k).
The solution still takes O(N sqrt(M)) time.
Code: https://codeforces.net/contest/1603/submission/134607321
I'm a bit confused about all the downvotes. What did I do wrong?
(Note: edited the above post to show how the problem can be implemented as an on-line algorithm, i.e., without allocating an N-element array upfront.)
Excellent Contest. I think observations are important for CP rather than implementing the same algorithms continuously in more or less the same way to solve the questions. All Of CP is actually Mathematics only so I personally liked all the problems.
I have a doubt in regards to the editorial for Div1 C. Shouldn't $$$b_{1}=a_{i+1}\mod a_{i}$$$? If we set $$$b_1$$$ to what is mentioned in the editorial, won't the updated value for $$$a_1$$$ be wrong for the array $$$[10, 3]$$$? As far as I understand, the updated value for $$$a_1$$$ should be $$$1$$$ here, but according to the editorial it seems to be $$$2$$$.
Can someone please clarify?
It should be $$$2$$$, because $$$2$$$ is greater and it is possible to achieve this using $$$3$$$(the minimum) operations: $$$[10, 3] \rightarrow [2, 2, 3, 3, 3]$$$. In your case, it is $$$[1, 3, 3, 3, 3]$$$ using $$$3$$$ operations. But if we can achieve $$$2$$$ why bother with $$$1$$$ which is lower?
Oh I see now. Thanks!
There is a much cleaner solve for div2C/div1a (my solve is 133995726). Basically you find the highest non-divisor of a_i under i + 1 and check if that is less than 2. If any of these are less than 2 then the answer is NO, otherwise it is YES.
The reason this works is because the only time we cannot remove a number is when there are not enough numbers before it to get it to a value where it is not divisible. Otherwise it is enough to just remove the rightmost number that can be currently removed, which will always exist.
div1A(2C)can be greedily deleted from the back, and then simulated with the stack?I passed the question like this, but I don't know whether greed is correct
It is indeed correct.
Problem 1C, why $$$\sum\limits_{k=l}^r\sum\limits_{i=1}^{\lfloor \frac rk\rfloor}\sum\limits_{j=i+1}^{\lfloor \frac rk\rfloor}=\sum\limits_{k=l}^r\sum\limits_{i=1}^{\lfloor \frac rk\rfloor}\phi(i)$$$?
I think it should be $$$\sum\limits_{k=l}^r\sum\limits_{i=1}^{\lfloor \frac rk\rfloor}\sum\limits_{j=i+1}^{\lfloor \frac rk\rfloor}=\sum\limits_{k=l}^r\sum\limits_{i=2}^{\lfloor \frac rk\rfloor}\phi(i)$$$.
I agree.
I've discovered a much simpler sulotion with $$$n^3\sqrt n$$$ time complexity for problem E.
It's currently the fastest solution on codeforces:Link
I have a question with the time complexity of Div1.E.
In the observation 7,the solution improved the time complexity from $$$\mathcal O(n^5\log n)$$$ to $$$\mathcal O(n^3\sqrt{n}\log n)$$$ by only enumerating $$$a_i$$$ from $$$n-2\sqrt{n}$$$ to $$$n$$$. But we still have $$$\mathcal O(n^2\sqrt{n})$$$ states，and the complexity of transfering is $$$\sum_{k=1}^{n-a_1+1}\dfrac{a_1}{k}$$$ ，which is still $$$\mathcal O(n\log n)$$$ . So I think the time complexity is $$$\mathcal O(n^4\log n)$$$ ，and I don't know why my understanding is wrong. Can someone help me sort this out?
I'm sorry that I found the mistake in my understanding. In fact,the complexity of transfering which is $$$\mathcal O(n\log n)$$$ is actually the sum of transfering $$$dp(i,j,1),dp(i,j,2),\dots,dp(i,j,k)$$$ ，so the whole time complexity is $$$\mathcal O(n^2)\times \mathcal O(n\log n)\times \mathcal O(\sqrt{n})=\mathcal O(n^3\sqrt{n}\log n)$$$. Sorry for wasting your time.
1D and 1E was so great! I really like it.
Problem F is an amazing problem. I have two solutions not listed in the editorial or in the comments.
I will prove the following claim: let $$$f(n,l)$$$ be the number of $$$n$$$-tuples of vectors in $$$\mathbb{Z}_2^k$$$ such that the spanning set of these vectors has size $$$2^l$$$. Then
First proof, by recursion and bashing. First observe that
This is true by considering whether the last case increases the spanning set or not.
Now we induct on n and $l$.
Base Case: $$$n=l$$$. Clear.
Inductive Step: It suffices to show that
We first cancel out the
on both sides. This is equivalent to showing
Now we expand the left hand side to get
Dividing both sides by
yields the desired result.
The motivation for the first proof is that the numbers have a nice form.
Second proof, via polynomial. We first count the number of
-element spans (S such that there exist $x_1,\cdots,x_l$ such that $$$S$$$ contains all and only elements of the form $$$v_1x_1 \bigoplus \cdots \bigoplus v_lx_l$$$ for $$$v_i\in {0,1} \forall 1\le i\le l$$$ in $$$\mathbb{Z}_2^k$$$.
On one hand, there are $$$\prod\limits_{i=0}^{l-1} (2^k-2^i)$$$ ways to pick $$$l$$$ linearly independent elements. On the other hand, there are $$$\prod\limits_{i=0}^{l-1} (2^l-2^i)$$$ ways to select the same span.
Now, fix a span. We use inclusion-exclusion to find the number of ways to pick $$$n$$$ vectors such that their span has size $$$2^l$$$. It is not hard to show that this is a polynomial of degree at most $$$l$$$ in $$$2^n$$$ (i.e. the answer for $$$n$$$ is $$$P(2^n)$$$ for some $$$\deg P\le l$$$). Furthermore, for $$$n=0, 1, \cdots, l-1$$$, the answer is 0, which implies $$$P(x)=c\prod\limits_{i=0}^{l-1} (x-2^i)$$$. For $$$n=l$$$ the answer is $$$\prod\limits_{i=0}^{l-1} (2^l-2^i)$$$, implying $$$c=1$$$, as needed.
Now the answer is simply
because the probability that an element is in a randomly selected span of $$$2^l$$$ elements is $$$\frac{2^l-1}{2^k-1}$$$
I tried to format this, but sometimes the dollar signs don't render (they render on the overleaf compiler) and I have to use double dollar signs.
I think the editorial has a typo in 1C.
The contribution term near the end currently says $$$i \cdot dp(i + 1, x) \cdot \left(\lceil \frac{a_i}{a_{i+1}} \rceil - 1 \right)$$$. I believe the $$$a_{i+1}$$$ should be $$$x$$$.
Here's my algorithm for Moderate Modular Mode.
If x = y, then just print x If x < y, then print (x + y) /2 If x > y, then print x + y
I'm having trouble finding edge cases for this algorithm. Here's my code if needed
143933295
For Div2E, I was stuck at the following part --> how do you find the smallest k for which $$$\lceil \frac{a_i}{k} \rceil \leq a_{i+1}$$$. Turns out this is just $$$\lceil \frac{a_i}{a_{i+1}} \rceil$$$. Somehow not that intuitive to me, so I was binary searching and thus getting TLE. Is there some easy ways to work with such kind of inequalities.
Hello,
In Problem 1603B - Moderate Modular Mode for the second case (when
x ≤ y), can't we simply take the average ?Because if
nthe average ofxandy, it will be the same distance fromxtonand fromntoy...Is there any Counter Example ??
This only works if n % x == n — x and y % n == y — n, which is not always true. Consider x = 4 and y = 30, for example. If we use your strategy, n = (4 + 30) / 2 = 17. But 17 % 4 = 1 not 13.
Div1 E Complexity seems to be actually $$$O(n^3\sqrt n)$$$ with a constant of $$$\frac{\pi^2}{18}$$$.
By eliminating all unnecessary transits, the result will look something like this:
The former $$$\sum(mn-j)j$$$ sums up to $$$O(n^3\sqrt n)$$$ because $$$mn\in [n-2\sqrt{n},n]$$$ with a constant of about $$$1/3$$$, and the latter $$$\sum \frac{1}{k^2}$$$ sums up to less than $$$\zeta_2=\frac{\pi^2}{6}$$$. The total constant is therefore $$$\frac{\pi^2}{18}$$$.
I tested it with the following code, in which
Cnt=469601774whenn=400andCnt=1054688268whenn=500, which matches the result quite well (the actual constant is a little smaller because of other optimizations)