Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
for _ in range(int(input())):
n, k, x = map(int, input().split())
if x != 1:
print("YES")
print(n)
print(*([1] * n))
elif k == 1 or (k == 2 and n % 2 == 1):
print("NO")
else:
print("YES")
print(n // 2)
print(*([3 if n % 2 == 1 else 2] + [2] * (n // 2 - 1)))
Idea: adedalic
Tutorial
Tutorial is loading...
Solution (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
#define x first
#define y second
typedef long long li;
typedef pair<int, int> pt;
pt A, B, C;
inline bool read() {
if(!(cin >> A.x >> A.y))
return false;
cin >> B.x >> B.y;
cin >> C.x >> C.y;
return true;
}
int dist(const pt &A, const pt &B) {
return abs(A.x - B.x) + abs(A.y - B.y);
}
inline void solve() {
cout << (dist(A, B) + dist(A, C) - dist(B, C)) / 2 + 1 << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cout << fixed << setprecision(15);
int t; cin >> t;
while (t--) {
read();
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
import sys
for _ in range(int(sys.stdin.readline())):
s = [int(c) for c in sys.stdin.readline().strip()]
n = len(s)
m = int(sys.stdin.readline())
l = sys.stdin.readline()
r = sys.stdin.readline()
mx = 0
for i in range(m):
li = int(l[i])
ri = int(r[i])
nmx = mx
for c in range(li, ri + 1):
cur = mx
while cur < n and s[cur] != c:
cur += 1
nmx = max(nmx, cur)
mx = nmx + 1
print("YES" if mx > n else "NO")
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
using li = long long;
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
li delta = 0, ans = 0;
li sum = 0, mx = 0;
for (int i = 0; i < n; ++i) {
li x; cin >> x;
sum += x;
mx = max(mx, sum);
if (sum - mx < delta) {
delta = sum - mx;
ans = mx;
}
}
cout << ans << '\n';
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int MOD = int(1e9) + 7;
int add(int a, int b){
a += b;
if (a >= MOD)
a -= MOD;
return a;
}
int main() {
int n, k;
scanf("%d%d", &n, &k);
vector<int> a(n);
forn(i, n) scanf("%d", &a[i]);
int lim = 1;
while (lim * (lim + 1) < k * 2) ++lim;
vector<vector<vector<int>>> dp(2, vector<vector<int>>(2 * lim + 1, vector<int>(k + 1)));
dp[0][lim][0] = 1;
forn(ii, n){
int i = ii & 1;
int ni = i ^ 1;
dp[ni] = vector<vector<int>>(2 * lim + 1, vector<int>(k + 1));
forn(j, 2 * lim + 1) forn(t, k + 1) if (dp[i][j][t]){
forn(z, 2){
int nj = j + z - a[ii];
int nt = t + abs(nj - lim);
if (nt <= k) dp[ni][nj][nt] = add(dp[ni][nj][nt], dp[i][j][t]);
}
}
}
int ans = 0;
for (int t = k & 1; t <= k; t += 2)
ans = add(ans, dp[n & 1][lim][t]);
printf("%d\n", ans);
return 0;
}
Idea: adedalic
Tutorial
Tutorial is loading...
Solution (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define forn(i, n) for(int i = 0; i < int(n); i++)
#define sz(a) int((a).size())
#define x first
#define y second
typedef long long li;
typedef pair<int, int> pt;
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
return out << "(" << p.x << ", " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
fore(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
const int INF = int(1e9);
const li INF64 = li(1e18);
const int LOGN = 19;
const int N = (1 << LOGN) + 555;
struct comp {
double x, y;
comp(double x = .0, double y = .0) : x(x), y(y) {}
inline comp conj() { return comp(x, -y); }
};
inline comp operator +(const comp &a, const comp &b) {
return comp(a.x + b.x, a.y + b.y);
}
inline comp operator -(const comp &a, const comp &b) {
return comp(a.x - b.x, a.y - b.y);
}
inline comp operator *(const comp &a, const comp &b) {
return comp(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
}
inline comp operator /(const comp &a, const double &b) {
return comp(a.x / b, a.y / b);
}
namespace FFT {
const double PI = acosl(-1.0);
vector<comp> w[LOGN];
vector<int> rv;
void precalc() {
forn(st, LOGN) {
w[st].resize(1 << st);
forn(i, 1 << st) {
double ang = PI / (1 << st) * i;
w[st][i] = comp(cos(ang), sin(ang));
}
}
rv.assign(1 << LOGN, 0);
fore(i, 1, sz(rv))
rv[i] = (rv[i >> 1] >> 1) | ((i & 1) << (LOGN - 1));
}
inline void fft(comp a[N], int n, bool inv) {
int ln = __builtin_ctz(n);
forn(i, n) {
int ni = rv[i] >> (LOGN - ln);
if(i < ni) swap(a[i], a[ni]);
}
for(int st = 0; st < ln; st++) {
int len = 1 << st;
for(int k = 0; k < n; k += (len << 1))
fore(pos, k, k + len) {
comp l = a[pos];
comp r = a[pos + len] * w[st][pos - k];
a[pos] = l + r;
a[pos + len] = l - r;
}
}
if(inv) {
forn(i, n)
a[i] = a[i] / n;
reverse(a + 1, a + n);
}
}
comp aa[N], bb[N], cc[N];
inline void multiply(int a[N], int sza, int b[N], int szb, int c[N], int &szc) {
int ln = 1;
while(ln < (sza + szb)) // sometimes works max(sza, szb)
ln <<= 1;
forn(i, ln)
aa[i] = (i < sza ? a[i] : comp());
forn(i, ln)
bb[i] = (i < szb ? b[i] : comp());
fft(aa, ln, false);
fft(bb, ln, false);
forn(i, ln)
cc[i] = aa[i] * bb[i];
fft(cc, ln, true);
szc = ln;
forn(i, szc)
c[i] = int(cc[i].x + 0.5);
}
}
const int MOD = int(1e9) + 7;
int norm(int a) {
while (a >= MOD)
a -= MOD;
while (a < 0)
a += MOD;
return a;
}
int mul(int a, int b) {
return int(a * 1ll * b % MOD);
}
li l, t;
int n;
vector<int> v;
inline bool read() {
if(!(cin >> l >> t >> n))
return false;
v.resize(n);
fore (i, 0, n)
cin >> v[i];
return true;
}
int mu[N], minD[N];
vector<int> divs[N];
void precalcDivs(int N) {
fore (d, 1, N) {
for (int v = d; v < N; v += d)
divs[v].push_back(d);
}
mu[1] = 1;
fore (d, 2, N) {
if (minD[d] == 0)
minD[d] = d;
if (minD[d] != minD[d / minD[d]])
mu[d] = -mu[d / minD[d]];
for (int v = 2 * d; v < N; v += d) {
if (minD[v] == 0)
minD[v] = d;
}
}
}
int vs[2][N], res[N], ps[N];
li mxk[N];
inline void solve() {
FFT::precalc();
fore (i, 0, n) {
vs[0][v[i]] = 1;
vs[1][v[i]] = 1;
}
int sz = 1 + *max_element(v.begin(), v.end());
int szRes = 0;
FFT::multiply(vs[0], sz, vs[1], sz, res, szRes);
fore (i, 0, szRes) {
if (!(i & 1) && vs[0][i >> 1] > 0)
res[i]--;
if (res[i] > 0) {
ps[i] = 1;
}
}
memset(vs[1], 0, sizeof vs[1]);
fore (i, 0, n)
vs[1][sz - 1 - v[i]] = 1;
FFT::multiply(vs[0], sz, vs[1], sz, res, szRes);
fore (i, sz, szRes) {
if (res[i] > 0) {
ps[i - sz + 1] = 1;
}
}
precalcDivs(2 * sz);
int ans = 0;
for (int i = N - 1; i > 0; i--) {
if (ps[i] > 0)
mxk[i] = max(mxk[i], t * 1ll * i / (2ll * l));
for (int d : divs[i]) {
// ans += mu[d] * (mxk[i] / d);
ans = norm(ans + mu[d] * int((mxk[i] / d) % MOD));
mxk[i / d] = max(mxk[i / d], mxk[i] / d);
}
}
cout << ans << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cout << fixed << setprecision(15);
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
i learnt a lot from this contest. Thanks a lot for such a educational one.
please enlighten me what you learnt?
This is a very interesting competition. No matter how you look at the Harbour Space University competition, they are all very interesting. Every awoo competition and its teams are useful. Thank you awoo and your team!!!
Except that one — "Educational Codeforces Round 153".
I could just solve 2 questions but the the problems were really educational. Thanks for the preparation.
Maybe you shoule've set n,k <= 2500 or sth for problem E, because this way many were able to make the n^2k pass while others (myself included) didn't even try it even with the idea in mind
I think the problem is that even with the current constraints, solutions that run in O(N×K^1.5) aren't guaranteed to pass.
During the contest I submitted a O(N×K^1.5) solution that used a std::unordered_set which was too slow (admittedly, std::unordered_set is known for having a high constant factor). After the contest I rewrote it to use only arrays, but even then it still takes 4.773 seconds, which is quite close to the 5 second time limit: 211663856.
Honestly there isn't a lot of fat to trim there. So I don't think they could have increased the bounds by much without failing reasonable solutions.
Is the problem in its current form even solvable in a language other than C++? Maybe Java?
I tried submitting your code. Submission 2, 5 use #define int int64_t while submission 1, 3, 4 don't. I am not very sure as to which compiler should be used for which cases but from my past experience it feels like using 64-bit compiler for 64-bit maths is better.
Oh interesting! I had no idea that the “G++17” compiler ran in 32-bit mode, and I had been avoiding the “G++20” compiler because it mentioned ”winlibs” and I don't know what it meant so I was afraid it was Windows-specific somehow.
It sounds like I should switch to using G++20 for all my submissions from now on! Thanks for the tip!
I am not able to understand anything about E the statement seemed simple but I am not able to understand anything about E can you please help ?
Take a look at 211973366.
This solution won't pass because it's too slow, but that's not the point. It is intended to show how to enumerate all the possible sequences that can be constructed with at most K moves, recursively.
Once you understand this principle, the challenge is to rewrite the recursive solution as an iterative dynamic programming solution that runs within the time and space limits. This is fairly mechanical. If you don't know how to do this, you should read a dynamic programming tutorial first.
I still don't understand. Can you help? So you say that the sum of
excess
must be 0 at the end, but even in the example you've given at the start of your submission the sum is-1 + -2 + -1 + 0 + 0 + 1 + 0 = -3
which is not 0, although the numbers of balls ingoal
and inA
are equal. Do I miss something?It's the final value of
excess
that must be zero, not the sum of the values.excess
represents the number of balls pushed to the right (if positive) or borrowed from the right (if negative).I'll give you two detailed examples to explain the logic of the recursive solution (and them I'm giving up!)
Let's say we want to transform
A=[1,1,0,0]
intoB=[0,0,1,1]
. Imagine the boxes are lined up in a row and I'm physically moving from the left to the right of the array, trying to make things right, keeping track of how many balls I have to carry from left to right (which is the minimum number of swaps I can do, since a swap moves a ball from bin i to i+1 or vice versa).Initially, I'm at index 0. A[0] = 1 but I want it to be B[0] = 0, so I pick up the ball (I now have 1 ball), and then I move to the right (moving 1 ball with me).
I'm at index 1. A[1] = 1 but I want it to be B[1] = 0, so I pick up that ball too (I now have two balls), and then I move to the right (moving 2 balls with me).
I'm at index 2. A[2] = 0 but I want it to be B[2] = 1. Luckily I have two balls, so I put one of them down here, and then I move to the right (moving 1 ball with me).
I'm at index 3. A[3] = 0 but I want it to be B[3] = 1. I still have 1 ball left so I put it down, and then I move to the right, and I'm at the end of the array with no balls left.
excess
represents the number of balls I move to the right at each step, soexcess = [1,2,1,0]
and the total number of times I had to move a ball one space was 1 + 2 + 1 = 4.In that example, I only had to move balls to the right. What if I need to move balls left, let's say by transforming
A=[0,0,1,1]
toB=[1,1,0,0]
? It's clear the optimal solution is to move the balls at A[2] and A[3] two spaces to the left each. I can use the same algorithm as above if I introduce the idea that I can borrow balls from the right. It looks like this:Initially, I'm at index 0 and A[0] = 0 but I want it to be B[0] = 1. Since I don't have a ball, I remember that I need one and move the right (I'm 1 ball short that I need to move from box 1 to 0).
I'm at index 1 and A[1] = 0 but I want it to be B[1] = 1. Since I still don't have any balls, I remember that I need another one and move the right (I'm 2 balls short that I need to move from box 2 to 1).
I'm at index 2 and A[2] = 1 but I want it to be B[2] = 0, so I pick up the ball. That's one of the balls I can pass to the left (throwing it in box 0), but I'm still 1 ball short as I move to the right.
I'm at index 3 and A[3] = 1 but I want it to be B[3] = 0, so I pick up that ball. That's the last ball I needed to pass to the left (throwing it in box 1). So now I can move to the right (at the end of the array) and I have no balls left nor am I short any balls, so I've found a solution.
In this example,
excess = [-1,-2,-1,0]
, the negative numbers representing the number of balls I was short. Just like before, the total number of times I had to move a ball one space was |-1| + |-2| + |-1| = 4, except the balls moved to the left instead of to the right.(I didn't prove that this algorithm is optimal, but it's not too difficult to convince yourself that it is.)
If the above explanation isn't enough to understand the problem, I suggest you let it go for now, practice on other problems, and come back to it later.
Thank you very much for such a detailed explanation. Now I get it
yaya, nice to see the nk^1.5 solution, was wondering about that from seeing all the fast submissions
I had a different solution for E that runs in $$$O(n^2 \sqrt{k})$$$ and is adapted from the slow dp:
Let $$$m$$$ be the number of balls and let $$$pos_i$$$ be the position of the $$$i$$$th ball. Then, we can calculate $$$dp[i][k][j]$$$, the number of ways to put the first $$$i$$$ balls in the first $$$j$$$ bins, the cost is $$$k$$$. I order like $$$i, k, j$$$ for cache purposes. This is just a standard dp, where the transitions are $$$dp[i][k][j] = dp[i][k][j-1] + dp[i][k-|pos_i-j|][j-1]$$$.
We can observe the following fact: the position of the $$$i$$$th ball is limited to the range of $$$[pos_{i-\sqrt{k}-1}, pos_{i+\sqrt{k}+1}]$$$, where negative indices are filled with 0 and indices above $$$m$$$ are filled with $$$n$$$. This is true because if the ith ball went beyond this range, at least $$$\sqrt{k}+1$$$ balls would have to move at least $$$\sqrt{k}+1$$$ distance.
This optimization is important because the distance between balls is roughly $$$n/m$$$, so the size of the average range among the balls is $$$\sqrt{k} \cdot n/m$$$. Over all of the balls, and over all costs, the total number of positions we will look at in our dp will be $$$O(m \cdot n \cdot (\sqrt{k}\cdot n/m)) = O(n^2 \sqrt{k})$$$.
For the implementation, we can store a table $$$range[i][k] = [pos_{i-\sqrt{k}-1}, pos_{i+\sqrt{k}+1}]$$$, which is the range of $$$j$$$ that $$$dp[i][k][j]$$$ is calculated for. The dp values before this range are 0, and the dp values afterward are just the dp value of right endpoint of the range. This allows us to avoid traversing all $$$j$$$ from 1 to $$$n$$$ for every $$$i, k$$$, and only traverses the ranges that we care about.
Submission: https://codeforces.net/contest/1845/submission/211638320
can C be done using digit DP?
can be done using DP not digit DP exactly.
Can u explain the intuition of dp
dp[i][j] : 'ith' pos subsequence we can make using first 'j' characters of string formed .
-> maintain an array of index for each digit and using bs to get next current digit index.
-> jth character = (a[j] <= b[j])
base :- dp[n][..] = true;
sample link :- https://codeforces.net/contest/1845/submission/211716711
Why I am getting WA on D? Can someone Help me? Tried 2 different approaches.
Approach 1 : https://codeforces.net/contest/1845/submission/211638397
Approach 2 : https://codeforces.net/contest/1845/submission/211644844
In both the approaches, you are trying to find the highest possible net rating before the last time there is a drop (i.e., a[i] is negative). However, this might not always give the correct answer.
Consider the test case:
1
4
3 -2 7 -1
Here, the answer would be 3, since by fixing k=3, you can achieve a final rating of 9. However, your approach returns k=8 as the answer, due to which the final rating would be 8 only.
Can you explain the correct solution , because I didn't get it yet
Why is the explanation for B so sub quality? No definition for bounding box, "since d(X,B)+d(X,C) is constant and equal to d(A,B) if X is in the bounding box. " Randomly stating facts
sad
Another idea for B is to split the problem regarding the X-axis and the Y-axis and take the minimum out of the specific coordinates for the axis and add it to the answer if both are walking in the same direction. (after you've made A the origin).
Here's another solution for C. The idea is to count the #of unique valid passwords of length m in the password database. Then if the #of unique valid passwords is less than the total #of valid passwords, there is guaranteed to be at least one password that we can use for our answer. You can count the #of unique valid passwords of length m in the database using dp.
211486674
great observation
Does anyone know of a good resource that explains how to use FFT to solve problems like 1845F - Swimmers in the Pool from scratch, i.e., without assuming I already know what a FFT is and how it applies to problems like this?
This may help FFT Lecture
Some key observations in problem D:
From now on we try to reduce the complexity from N^2 to N
These observations derive the fact that for index i
maximum answer by keeping k as pref[i-1] = pref[i-1] + max(0, pos + neg) + confirmPos
sorry for poor english, I tried my best to explain what I understood from the problem :)
Submission Link
Nicely explained ! A question w.r.t editorials explanation in particular for D, they say the pfirst point where value goes less than k and last point where it goes below k is the sub segment we need to remove. But whatever that first point is which determines if the value goes below k, does that not also change what was the next point at which the value would go below k again ,I.e since we capped it to k subsequent positive operations would take the value higher and maybe it won't fall below K as it previously did ? Don't we need to simulate and see ?
Nvm I figured it out , it relies on the fact that at the end of minimum subarray the rating is still K (else it wouldn't be min subarray it can be empty though), and the prefix before min subarray is maximum so you would want to retain that , also note minimum subarray has to be negative(sum total of it) so once you make sure you avoid this subarray the suffix left will only increase the rating from max prefix which you found to something bigger which is max possible at the end, so K will be max prefix.
TL;DR avoiding minimum subarray sum will make sure prefix before it is preserved and only increase till the end.
Can anyone help me to remove the RE in 3rd Question
It seems the ind might be -1. Try with the following case:
I have added an assert into your code and also fixed the indentation.
Hello Sir, Can you explain these things to me or from where I can learn them; Basically, I never heard of "mdash" you used!!
Thank You for your solution
Those are formatting errors when I added the code in the comment. I have fixed them. Please have a look again. That's your code and I just added an assertion.
the code is still giving WA
That means the code is not giving RE which you originally requested, isn't it? Check your code, find out for which cases your code is not generating correct inputs and read the editorial if necessary. Have a great solving!
Hi can anyone explain why binary search on k does not work for D? I kept thinking of counterexamples but I cannot seem to find any.
How will do you a binary search on k , it doesn't guarantee that if you would increase k it would only lead to maximum sum, it can so happen binary search skips parts on range of k which would contribute to maximum sum
My submission: https://codeforces.net/contest/1845/submission/211518101
Sorry I do not really understand; do you have any counterexamples?
1 2 1000 -5
Can someone please explain why using kadane's algorithm for Q. D. 'Rating System' is wrong? or is my idea correct but wrong implementation?
My submission
Thank you
Kadane's algorithm is in fact right for the D problem.
However, in your solution, you have made the mistake while selecting the value of K. By Kadane's algorithm, you are trying to find the most negative subarray in the given array. You can then select K to be the value before the start of that subarray. Your solution will fail when you get multiple negative subarrays. eg:
1 8 -5 100 -5 -10 4 -10 -10 -10
your mn will be set to -5 at the start and then the value to starting will be 3 instead of 2 and the solution will give wa.
You can check this solution for Kadane's: 211474733
Hope this helps.
Can anyone explain binary search solution to C?
I think the questions in this game are very good
Why the time limit of problem E is 5s?
211713164 My solution is $$$O(n^2k)$$$,it only executed 1029ms
Here is another idea for D: consider the following question: what the rating change will be (if we can simplify it) after applying a list of rating changes a[1], a[2], ... , a[n]. Observe that:
After applying transformation above on initial rating changes list, the size of result list will be at most 2. So we can enumerate every index i, to check:
To get simplified rating change list for each index i, we can calculate backwards from index n to index 1.
Some of the results will be invalid, since for some R[i], the rating on previous steps may reach k (=R[i]) and then drop below k (=R[i]), so use R[i] as initial rating with k=R[i] is actually wrong. But in such cases the result got from the step that "reach k" will always be better, so we can just ignore such (wrong) cases.
Can someone please tell me why my solution is so slow, although it is accepted? I used $$$dp[i][j][k]$$$ =number of ways to store first $$$i$$$ balls in first $$$j$$$ boxes such that minimal cost for it is $$$k$$$. Transition looks like:
$$$dp[i][j][k]=dp[i][j-1][k]+dp[i-1][j-1][k-|pos[i]-j|]$$$ , there $$$pos[i]$$$ is position of $$$i$$$th ball on the beginning. Solution would be sum of $$$dp[m][n][i]$$$ for each $$$i$$$ of same parity as $$$k$$$,where $$$m$$$ is the number of balls. Also I used that for $$$i$$$th ball set of possible positions $$$j$$$ on which we can move it belongs to interval $$$[pos[i-\sqrt{k} -1],pos[i+\sqrt{k}+1]]$$$.
In this comment https://codeforces.net/blog/entry/117791?#comment-1042133 was explained why time complexity should be $$$O(n^2\sqrt{k})$$$. Most of solutions have runtime up to $$$1000ms$$$, but mine is more than $$$3700ms$$$, so I would be grateful if someone can tell me why is it so? This is my submission: https://codeforces.net/contest/1845/submission/211839395
$$$\textbf{Upd}$$$ I got it, only need to change from long long to int
I want to add something about problem F.
I didn't really understand what the P.S. in the tutorial for this problem means, maybe it is exactly what I want to say, then I am sorry.
I just wanted to say that I think that Möbius transform is too hard of a concept for situations as described in the problem. Here we have a situation where we have some array $$$a_i$$$ consisting of sums of answers over all divisors of $$$i$$$, and we would like to get the actual answer array $$$b_i$$$. So we know $$$a$$$ and we know that $$$a_i = \sum_{j \vert i} b_j$$$. In situations like this indeed one could use Möbius but it is not actually needed.
Let's imagine that instead we actually have the array $$$b$$$, and we would like to calculate the array $$$a$$$. How would we do it? Well, for every number just go through all the divisors and sum up the corresponding $$$b$$$ values. As going through dividends is easier, we would probably do that instead. And if we want to recalculate it in-place, we need to go in the decreasing order of $$$i$$$ to not add things many times. The code would look something like this:
If you found my explanation not so clear, I just want you to realize that this is a very natural and obvious way to do the job we want. If you were asked to do this, you would come up with exactly the same solution. Just add the value to all dividends but be careful with the order (the same way as with the knapsack problem).
Now we have an algorithm that transforms the array $$$b$$$ into the array $$$a$$$. "And what? We want the opposite!" you will say. Exactly! We want to do exactly the opposite. Just imagine in your head that you have the array $$$b$$$ and run this algorithm. Step-by-step. And now comes the key idea: just imagine that you have a weird time machine that allows you to reverse time. If you reverse time, the algorithm will run in the opposite direction and it will go back from the array $$$a$$$ to array $$$b$$$. This is exactly what we want! Now it remains to understand how to code an algorithm that reverses the time. It is easy. We should just undo all the actions in the reversed order. If we have a cycle, we should reverse it. If we add something, just subtract! Here is the solution:
You may notice that I did not reverse the inner cycle. I didn't do it because the actions that are performed inside this cycle are independent of each other: we just subtract $$$b[i]$$$ from all its dividends. You can actually think about this as just one single action that we reversed. I did it because it is just a bit more complicated to go through dividends in descending order, and it is actually not needed here. And now we indeed have an algorithm that transforms the array $$$a$$$ into the array $$$b$$$! And no math is needed! We just used a very generic idea. The beauty of it is that we don't even need to understand what the algorithm we are trying to reverse does. It is a very manual low-level job: reverse and inverse all the actions.
Yes, indeed you can analyze it and understand that it does exactly the same thing as the Möbius transform, but well... Yes... But I claim that this is more understandable, easier to reproduce, less magical, and you don't need to calculate the $$$\mu$$$ function.
Some more notes: this idea of reversing time can be used in many settings. The most common one is DSU with rollbacks. You just remember all the things that changed and undo the actions. But here we actually performed all these actions, and after that reverse them. In our situation, we only imagine that these actions were performed. So in the DSU with rollbacks we can do any actions we want, for example, we do something like updating parents of some vertices: $$$p_u = v$$$, and remembering what was the old parent of $$$u$$$ (well, in this case, it was $$$u$$$, so we don't need to remember it, but whatever). And later we can just go back and replace $$$p_u$$$ with the old value. Our situation is different: we don't know what was the old value, and we want to find it. For it to be possible, the actions that we perform should be inversible. So, for example, in our case, we add one number to another number. It is an inversible action: we can just subtract back to undo it. But if the action is, for example, assignment or taking the maximum of two values, it is not inversible, and we would not be able to do our trick if we had such actions. This idea is similar to the fact that prefix sums allow us to find sums and bitwise xors of segments but not minimums and bitwise ors.
You may argue that DSU with rollbacks only somewhat uses the same concept. It is not exactly the same. And I would agree. But there are other situations where we can use exactly the same idea. FFT, Walsh-Hadamard transform, sum over subsets (SoS-dp), sum over supersets, etc. If you look closely, for all of them, if we already know the convolution one way, the inverse can be obtained without knowing anything about the math behind these algorithms by simply reversing the time. And actually, the thing that we wanted to calculate can be called a sum over divisors. All these are some transformations that can be used for convolutions. FFT can be used for $$$+$$$-convolution, Walsh-Hadamard for xor-convolution, sum over subsets for or-convolution, etc.
And at the end of this long comment, I will leave you with two simple exercises: - if all of these transformations before could be used to get a convolution, what kind of a convolution does our transformation give? - use the method we discussed to get an inversed sum over dividends. What convolution does it give?
I was talking about the following: suppose, you have a task:
Build all fractions $$$\frac{1}{i}, \dots, \frac{a_i}{i}$$$ for each $$$1 \le i \le n$$$ and calculate the number of unique fractions. Looks like you can't calculate it with pretty tricks without using Mobius.
This trick works here because
EASY DP SOLUTION FOR C
In F tutorial, what's the "easy system of equation" mentioned in the second paragraph?
Not sure whether to call the below a system of equations since it’s just one equation. WLOG assume $$$v_i > v_j$$$.
For the case where they are moving in the same direction, between two times that people meet, person $$$i$$$ must have traveled $$$2l$$$ more than person $$$j$$$, giving the equation $$$xv_i - 2l = xv_j$$$
For the case where they are moving in opposite directions, the sum of the two distances must equal $$$2l$$$, giving $$$xv_i + xv_j = 2l$$$.
I guess both cases also count the times when the people meet at the endpoints of the pool.
I personally prefer to visualize it as two vertices (one for each end of the pool) and two arcs connecting the two nodes. Meeting in the opposite direction will correspond to one person swimming clockwise and another swimming counterclockwise, while meeting in the same direction will correspond to both people swimming clockwise.
Can anyone tell me why my solution gives WA for problem D. 211601552
Thanks You
Can someone help me in this interactive problem, couldn't figure out why I'm getting a TLE. https://codeforces.net/gym/101021/problem/1
My submisision: 212177668
import sys from os import path
if(path.exists('input.txt')): sys.stdin = open("input.txt","r") sys.stdout = open("output.txt","w")
def listInp(): return list(map(int,input().split()))
def mapInp(): return map(int,input().split())
l = 1 r = int(1e6)
while l<r: mid = (l+r)//2 print(mid, flush=True) x = input() if x == '<': r = mid-1 else: l = mid
print(f"! {l}", flush=True)
Can someone elabortae more on the greedy approach for problem C. Specifically, I don't understand how it allways leads to the correct answer.
The way I originally solved should not pass since it is $$$O(N^2K)$$$, but it passes anyways :). Simply do what the editorial says naively, but either take the string $$$s$$$ or the complement of the string $$$s$$$, whatever is faster. (So define balance as either # of ones or # of zeroes depending on which is smaller). And this halves the runtime more or less, enough to get it to pass.
Can you tell me what is meant by balance in the editorial
I think by balance, the editorial means # of ones (not really sure). At least, that was the DP state I used.
The solution to problem D is the Maximum subarray problem using Kadane's algorithm
Can somebody explain the editorial of B in better detail? I am having trouble understanding it.
Can someone explain me the transitions in problem E
Can someone explain to me in more detail why in problem C, the running time is O(m + nD) in the editorial? I understand the reduction from O(m + nD) to O(nD). "O(m) comes from the outer loop over digits that you can't really get rid of" this part I am not sure of.
I think C was a great problem, i kinda fell in the DP way to do it and didn't think the simple greedy. Probably a new way for me to look at subsequences.