Все задачи ,кроме задачи F, были предложены fcspartakm. Идея задачи F принадлежит BledDest.
Разбор
Tutorial is loading...
Решение
n, s = int(input()), list(input())
ans = 0
for i in range(0, n, 2):
if (s[i] == s[i + 1]):
s[i] = chr(1 - ord(s[i]) + 2 * ord('a'))
ans += 1
print(ans)
print(''.join(s))
Разбор
Tutorial is loading...
Решение
n, a = int(input()), list(map(int, input().split()))
res = []
ans = 0
for i in range(n):
pos = -1
for j in range(n):
if (pos == -1 or a[j] > a[pos]): pos = j
res.append(pos + 1)
ans += i * a[pos] + 1
a[pos] = 0
print(ans)
print(' '.join([str(x) for x in res]))
Разбор
Tutorial is loading...
Решение 1
#include <iostream>
#include <sstream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <string>
#include <cstring>
#include <cassert>
#include <iomanip>
#include <algorithm>
#include <set>
#include <map>
#include <ctime>
#include <cmath>
#define forn(i, n) for(int i=0;i<n;++i)
#define fore(i, l, r) for(int i = int(l); i <= int(r); ++i)
#define sz(v) int(v.size())
#define all(v) v.begin(), v.end()
#define pb push_back
#define mp make_pair
#define x first
#define y1 ________y1
#define y second
#define ft first
#define sc second
#define pt pair<int, int>
template<typename X> inline X abs(const X& a) { return a < 0? -a: a; }
template<typename X> inline X sqr(const X& a) { return a * a; }
typedef long long li;
typedef long double ld;
using namespace std;
const int INF = 1000 * 1000 * 1000;
const ld EPS = 1e-9;
const ld PI = acos(-1.0);
int x1, y1, x2, y2, x3, y3, x4, y4, x5, y5, x6, y6;
inline void read() {
cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4 >> x5 >> y5 >> x6 >> y6;
x1 *= 2, y1 *= 2;
x2 *= 2, y2 *= 2;
x3 *= 2, y3 *= 2;
x4 *= 2, y4 *= 2;
x5 *= 2, y5 *= 2;
x6 *= 2, y6 *= 2;
}
inline bool ok(int x, int y, int x1, int y1, int x2, int y2) {
return x < x1 || x2 < x || y < y1 || y2 < y;
}
inline void solve() {
for (int x = x1; x <= x2; x++) {
if (ok(x, y1, x3, y3, x4, y4) && ok(x, y1, x5, y5, x6, y6)) {
cout << "YES" << endl;
return;
}
if (ok(x, y2, x3, y3, x4, y4) && ok(x, y2, x5, y5, x6, y6)) {
cout << "YES" << endl;
return;
}
}
for (int y = y1; y <= y2; y++) {
if (ok(x1, y, x3, y3, x4, y4) && ok(x1, y, x5, y5, x6, y6)) {
cout << "YES" << endl;
return;
}
if (ok(x2, y, x3, y3, x4, y4) && ok(x2, y, x5, y5, x6, y6)) {
cout << "YES" << endl;
return;
}
}
cout << "NO" << endl;
}
int main () {
#ifdef fcspartakm
freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#endif
srand(time(NULL));
cerr << setprecision(10) << fixed;
read();
solve();
//cerr << "TIME: " << clock() << endl;
}
Решение 2
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <random>
#include <ctime>
#include <string>
#include <iomanip>
#include <set>
#include <map>
#include <queue>
#include <stack>
using namespace std;
typedef long long li;
typedef unsigned long long uli;
typedef pair<int, int> pii;
typedef long double ld;
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define forn(i, n) for(int i = 0; i < int(n); ++i)
#define fore(i, l, r) for(int i = int(l); i < int(r); ++i)
#define forb(i, n) for(int i = int(n) - 1; i >= 0; --i)
#define vi vector<int>
#define x first
#define y second
const int INF = 2e9;
const li INF64 = 1e18;
const int M = 2 * 1000 * 1000;
const int N = 300 * 1000 + 100;
const int MOD = 1e9 + 7;
const double EPS = 1e-9;
const double PI = 3.14159265359;
pair<pii, pii> intersect(pii a, pii b, pii c, pii d) {
int lf, rg, up, dn;
lf = max(min(a.x, b.x), min(c.x, d.x));
rg = min(max(a.x, b.x), max(c.x, d.x));
up = min(max(a.y, b.y), max(c.y, d.y));
dn = max(min(a.y, b.y), min(c.y, d.y));
if (rg <= lf || up <= dn) return { {0, 0}, {0, 0} };
return { { lf, dn }, { rg, up } };
}
li square(pii a, pii b) {
return 1ll * abs(a.x - b.x) * abs(a.y - b.y);
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
vector<pii> p(6);
forn(i, 6)
cin >> p[i].x >> p[i].y;
pair<pii, pii> wb1 = intersect(p[0], p[1], p[2], p[3]);
pair<pii, pii> wb2 = intersect(p[0], p[1], p[4], p[5]);
pair<pii, pii> inter = intersect(wb1.x, wb1.y, wb2.x, wb2.y);
li swhite = square(p[0], p[1]);
li swb1 = square(wb1.x, wb1.y);
li swb2 = square(wb2.x, wb2.y);
li sinter = square(inter.x, inter.y);
if (swhite > swb1 + swb2 - sinter) cout << "YES\n";
else cout << "NO\n";
}
Разбор
Tutorial is loading...
Решение
#include <iostream>
#include <sstream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <string>
#include <cstring>
#include <cassert>
#include <iomanip>
#include <algorithm>
#include <set>
#include <map>
#include <ctime>
#include <cmath>
#define forn(i, n) for(int i=0;i<n;++i)
#define fore(i, l, r) for(int i = int(l); i <= int(r); ++i)
#define sz(v) int(v.size())
#define all(v) v.begin(), v.end()
#define pb push_back
#define mp make_pair
#define x first
#define y1 ________y1
#define y second
#define ft first
#define sc second
#define pt pair<int, int>
template<typename X> inline X abs(const X& a) { return a < 0? -a: a; }
template<typename X> inline X sqr(const X& a) { return a * a; }
typedef long long li;
typedef long double ld;
using namespace std;
const int INF = 1000 * 1000 * 1000;
const ld EPS = 1e-9;
const ld PI = acos(-1.0);
const int N = 200 * 1000 + 13;
int n;
int a[N];
inline void read() {
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
}
inline int gcd(int a, int b) {
while (a != 0 && b != 0) {
if (a > b) {
a %= b;
} else {
b %= a;
}
}
return max(a, b);
}
inline void solve() {
int ma = *max_element(a, a + n);
li sum = 0;
for (int i = 0; i < n; i++) {
sum += a[i];
}
int g = ma - a[0];
for (int i = 1; i < n; i++) {
g = gcd(g, ma - a[i]);
}
li ans = (ma * 1ll * n - sum) / g;
cout << ans << ' ' << g << endl;
}
int main () {
#ifdef fcspartakm
freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#endif
srand(time(NULL));
cerr << setprecision(10) << fixed;
read();
solve();
//cerr << "TIME: " << clock() << endl;
}
1216E1 - Числовая последовательность (простая версия)
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int q;
cin >> q;
while (q--) {
long long k;
cin >> k;
--k;
long long lst = 0;
long long nxtpw = 1;
int numlen = 0;
for (long long i = 1; ; ++i) {
if (i == nxtpw) {
++numlen;
nxtpw *= 10;
}
lst += numlen;
if (k >= lst) {
k -= lst;
} else {
long long nxtpw = 1;
int numlen = 0;
for (long long j = 1; j <= i; ++j) {
if (j == nxtpw) {
++numlen;
nxtpw *= 10;
}
if (k >= numlen) {
k -= numlen;
} else {
cout << to_string(j)[k] << endl;
break;
}
}
break;
}
}
}
return 0;
}
1216E2 - Числовая последовательность (сложная версия)
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
long long get(long long r) {
return (r + 1) * r / 2;
}
long long sumto(long long r, int need) {
long long pw = 1;
long long sum = 0;
long long add = 0;
for (int len = 1; ; ++len) {
if (pw * 10 - 1 < r) {
long long cnt = pw * 10 - pw;
if (need) {
sum += add * cnt + get(cnt) * len;
add += cnt * len;
} else {
sum += cnt * len;
}
} else {
long long cnt = r - pw + 1;
if (need) {
sum += add * cnt + get(cnt) * len;
} else {
sum += cnt * len;
}
break;
}
pw *= 10;
}
return sum;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int q;
cin >> q;
while (q--) {
long long k;
cin >> k;
--k;
long long l = 1 , r = 1e9;
long long res = -1;
while (r - l >= 0) {
long long mid = (l + r) >> 1;
if (sumto(mid, 1) > k) {
res = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
k -= sumto(res - 1, 1);
l = 1, r = res;
long long num = -1;
while (r - l >= 0) {
int mid = (l + r) >> 1;
if (sumto(mid, 0) > k) {
num = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
cout << to_string(num)[k - sumto(num - 1, 0)] << endl;
}
return 0;
}
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n, k;
cin >> n >> k;
string s;
cin >> s;
vector<long long> dp(n + 1);
multiset<long long> mins, vals;
mins.insert(0);
vector<vector<long long>> del(n);
for (int i = n - 1; i >= 0; --i) {
dp[i] = i + 1 + dp[i + 1];
if (i + k + 2 <= n) mins.erase(mins.find(dp[i + k + 2]));
for (auto it : del[i]) vals.erase(vals.find(it));
if (!vals.empty()) dp[i] = min(dp[i], *vals.begin());
if (s[i] == '1') {
long long val = (mins.empty() ? 0 : *mins.begin()) + i + 1;
dp[i] = min(dp[i], val);
vals.insert(val);
if (i - k - 1 >= 0) del[i - k - 1].push_back(val);
}
mins.insert(dp[i]);
}
cout << dp[0] << endl;
return 0;
}
Hey, everything is amazing. But if this is an editorial, why can't you paste clean code?
I mean without shitty part: unnecessary code, too many defines, etc... __ __ __ Thanks for being patient.
Agree with you, I struggle understanding the code with these many defines alot, I prefer writing everything inside the main and without all these defines, It makes the code unreadable for me at least
You can look at the situation from the other side. Some of the solutions that you see in the editorial were written by testers. In this editorial one of such solutions with "all these defines" was written by me, but when I solved these problems, I could not even imagine that my solutions would be published in the editorial, so I did it in the way that was usual and convenient for me. Sorry for this. Perhaps next time I will try to write more understandable and beautiful solutions. And, as you can see, vovuh's solutions (for example, problem F) do not contain unnecessary code and look quite understandable
@nooinenoojno Definitely not your fault, there should be seperate editorialists for contests instead of using Tester's solution the editorialist should write the code !
Editorial authors do not always have enough time to write their own solutions for editorials, they already spend a lot of time thinking up problems, preparing statements, checkers, tests, answering questions and writing explanations for editorial. It is especially difficult when, in addition to preparing a contest, you have to study and work
Maybe having bigger teams for contests could help... All this work should be done by multiple people.
The tutorial of problem E1 is poorly written. Please review it.
See if this explanation makes sense.
For problem D, can someone give a proper proof for why the solution is optimal?
The initial number of Swords is the same. Obviously, the maximum of the stolen swords is the optimal number of swords. If the minimum number of Swords is guaranteed, then the maximum number of swords taken by each person is the largest. That is to find the maximum common factor of the difference between the ai and the maximum except the maximum value.
Let the largest leftover pile be $$$max$$$, and smallest be $$$min$$$. We consider three cases —
The thieves leave at least one pile untouched, and $$$max > min$$$. In this case, $$$x = max$$$, and the number stolen from each pile is $$$x - a_i = max - a_i$$$. To minimize the number of thieves, we want that each one steals as much as possible, and since they all steal the same number of swords, $$$z$$$ must divide all $$$x - a_i$$$ and be as large as possible — meaning $$$z = gcd\ (max - a_1, max - a_2, \dots, max-a_n) = g$$$, and $$$y = \sum_i {\dfrac{max - a_i}{g}}$$$.
The thieves steal from all piles, and $$$max > min$$$. Let the amount stolen from the largest pile $$$max$$$ be $$$q$$$, i.e. $$$x = max + q$$$; and the new gcd of the $$$x-a_i$$$ is $$$g'$$$. If $$$g'$$$ divides $$$q$$$, then we can take away $$$q$$$ from all $$$x - a_i$$$ and the resultant gcd will be $$$g$$$, a multiple of $$$g'$$$. $$$g' = {gcd}_i (x - a_i) \mid {gcd}_i (x - q - a_i) = {gcd}_i\ (max - a_i) = g$$$. By doing this operation, we revert to case 1 and not only get a possibly bigger gcd but also a smaller $$$\sum_i {x - a_i}$$$, which means smaller new $$$y = \frac{1}{g}\sum_i {max - a_i} < \frac{1}{g'}\sum_i {max + q - a_i}$$$. So this case can be omitted from consideration. The only remaining case is when $$$g'$$$ does not divide $$$q$$$, but this is impossible as $$$g'$$$ divides all $$$x - a_i$$$, so it must divide $$$x - max = q$$$.
There is one case when $$$max = min$$$. For case 1, $$$y = 0$$$ and $$$z$$$ is undefined. But for case 2, for any $$$q > 0$$$, $$$z = q > 0$$$ and $$$y = n > 0$$$, so case 1 is still better than case 2.
So in any case, best case scenario will always be in case 1.
why g' | g ?????
Because $$$g' \mid q$$$, and $$$g' |\ (x - a_i)\ \forall i$$$ , so $$$g' |\ (x - q - a_i)\ \forall i$$$, so $$$g' |\ {gcd}_i(x-q-a_i) = {gcd}_i(mx-a_i) = g$$$.
Why we can subtrack q? Is it because of it is constant and a multiple of g'?
Yes. Also, because we want to compare with case 1, and subtracting $$$q$$$ from all $$$x - a_i$$$ make it the same as case 1.
Ok that makes sense but how we can be sure that subtraction won't affect? I didn't get that. And thank you.
Even though I gained rating,but I have to blame this round. For Problem C,my friend write a wrong solution and submit his code. But he passed all the pretests!!! Do you know why he was wrong? We know that we need to consider all the edges of the white rectangle. But he only considered the rows of the white rectangle,and he passed all the pretests!!!! Why?This is amazing,man. What a shame of the pretests.
Pretests were not meant to be complete, though.
But it's really amazing.There's one-half chance of error. The author of this problem let him passed his pretests. I think the author is to blame.
Before blaming the author, consider that he can't add an unlimited number of pretests. Imagine how long solutions will be tested during the round, if each of them will have to go through 100 pretests instead of 30 (the total number of tests for task C is 134). Now imagine the following situation: you are the author and you must predict all the possible mistakes of the participants in order to add 30 pretests that can catch all these mistakes. Is it possible? I highly doubt it. I know how disappointing it is to get the verdict “solution is hacked” (look at my last round (Educational Codeforces Round 67 (Rated for Div. 2)), two of my solutions were hacked). But at the same time, I understand that it is my fault, because I should come up with my own strong tests for my solution before submiting it. Yes, sometimes there are rounds with very really bad pretests (more than 1000 hacks for one problem), but this doesn't mean that it is worth talking about “weak pretests” every time you or your friend have a hacked solution.
I am not getting the solution to E1.
Can someone explain it to me in easy language? Its poorly written
Yes plz explain E1 it's quite unclear from editorial
Check out my solution here — Solution
Essentially we are successively narrowing down in what part of the infinite sequence we are in currently. For each integer $$$i \in \mathbb{N}$$$ we write their decimal representations from $$$1$$$ to $$$i$$$ and then start the process again for $$$i+1$$$.Let us call this process the "run" of $$$i$$$, i.e. the for each $$$i$$$ we are writing the string $$$run(i)$$$. $$$run(1) = \texttt{1}$$$, $$$run(10) = \texttt{12345678910}$$$ and so on. Appending number representations in order gives us a run, and appending these "runs" in the order they are produced gives us the infinite string.
Let $$$len(run(i)) = r_i$$$, and the length of the sequence ending with the $$$i$$$-th run as $$$s_i$$$. If the number of digits in $$$i$$$ is $$$dig_i$$$, we have $$$r_i = r_{i-1} + dig_i$$$. The number $$$dig$$$ stays the same for $$$i$$$ from $$$10^{k}$$$ to $$$10^{k+1} - 1$$$. So we keep the run length $$$r$$$ as an accumulator for $$$dig$$$ ( incrementing $$$dig$$$ at every power of 10 ), and the sequence length $$$s$$$ so far as an accumulator for $$$r_i$$$, i.e. $$$s_i = s_{i-1} + r_i$$$. When $$$s_i \geq k$$$, we now know we want the digit at $$$k - s_{i-1} = l$$$ in $$$run(i)$$$.
We do a similar procedure within $$$run(i)$$$ (we no longer need the accumulator $$$s_i$$$), and when $$$r_j \geq l$$$ we want the digit at position $$$l - r_{j-1} = d$$$ from the left in the representation of the number $$$j$$$. Calculating this, we get the answer.
thanks a ton !.......ur submission is so good as if it is a sculpture
I solved E1 moments ago.It looks very complex but it is just brute force.It's proved to be O(sqrt(k))....much easier than C which I did with implements.if I knew E1 could be brute force in the contest....
I think the code below the tutorial is more comprehensible. I will try to explain it from the perspective of implementation. It is given that the $$$i$$$ th block consists of numbers from $$$1$$$ to $$$i$$$. So the $$$i-1$$$ th block consists of numbers from $$$1$$$ to $$$i-1$$$. Let $$$L_i$$$ be the length of block $$$i$$$. Clearly we have $$$L_i=L_{i-1}+\text{len}(i)$$$, where $$$\text{len}(i)$$$ is the length of number $$$i$$$. So we can set variable $$$lst$$$(presented in code from the solution) to track the length of current block. Note that $$$\text{len}(i)=1, i\in [0,9]$$$ and $$$\text{len}(i)=2, i\in [10,99]$$$, etc. We can find that $$$\text{len}(i)$$$ increases at the positions $$${10,100,1000,...}$$$. So we can use variable $$$nxtpw$$$ as the position where $$$\text{len}(i)$$$ is going to change.So far for each block $$$i$$$, we can get its block length as $$$lst += numlen$$$. Next we are going to find whether the query $$$k$$$ belongs to the current block. We achieve this by judging whether $$$k>=lst$$$ (if true, subtract $$$k$$$ by $$$lst$$$ so that $$$k$$$ is always the relative position of target character with respect to the next block). Once we get some $$$k$$$ such that $$$k<lst$$$, we use the same policy to decide which number in the block position $$$k$$$ belongs to.
orz cmz
I'm very unhappy to know I get a WA on the test31 on C.In the contest I passed all the pretests so I thought I would get an AC but things went wrong anyway.I thought I might be 1500+ rating but today when I got up I found my rating up but my rank in the contest down,so werid but I had to accept the truth.I recommended C to my friends who didn't attend this contest and I was proud to say I passed the pretests.No matter what,it was my fault.I wrote a program which was not to be so acceptable,but I don't want to taste the feeling of getting an WA in the System Test anymore.So could please strengthen the pretests in the next contest?
For problem F, my solution achieved $$$O(n)$$$ through simple approaches.
Let $$$f_i$$$ denote the minimum cost to make rooms from $$$1$$$ to $$$i$$$ to be connected. In this case, $$$f_i$$$ should be non-decreasing. So for each $$$i$$$, the optimal result of $$$f_i$$$ is: 1. install a router in the first room in $$$[i-k, i)$$$ which can be equipped with a router; 2. link directly; 3. wait for the first router after $$$i$$$ to cover this room.
So we can use $$$dp_i$$$ to compute $$$f_i$$$ for the first 2 choices. When dealing with a router, we use current $$$dp$$$ value to update backwards all $$$dp_i$$$ in the segment between last router and current router, to apply the choice 3.
My Submission: 61007600
When you are updating the $$$dp$$$ backwards, shouldn't the condition be $$$j >= i - k$$$ instead of $$$ j >= 0$$$?
It's also right, because router $$$i$$$ can only affect rooms $$$[i-k, i]$$$.
But writing $$$j>=0$$$ can already achieve linear time complexity.
Linear solution for F:
Let's construct the answer from right to left. We denote the minimum cost to connect all rooms, starting from $$$i$$$, as $$$dp_i$$$ (in my solution, rooms are $$$0$$$-indexed, so $$$dp_0$$$ is the answer, and initially $$$dp_n = 0$$$).
Let's suppose we have calculated $$$dp_i$$$, and now we want to update other states using it. If we have already connected all rooms from $$$i$$$ to $$$n - 1$$$, the next room we will have to connect is room $$$i - 1$$$.
There are two ways to connect it. The first is easy — just connect it without any router, so $$$dp_{i - 1} = min(dp_{i - 1}, dp_i + i)$$$.
The second way is to use a router. Which one should we use? First of all, the cost of installing a router and connecting it decreases when we go from right to left, so, to minimize the cost of connecting this room to the Internet, we should choose the leftmost room where a router can be installed that is not too far from the current room. Furthermore, if all rooms from $$$i$$$ to $$$n - 1$$$ were connected and we choose to connect room $$$i - 1$$$ using a router in room $$$x$$$, then afterwards all rooms from $$$x - k$$$ to $$$n - 1$$$ will be connected. So choosing the leftmost router that covers the current room is always beneficial.
So there are only two types of transitions in this dynamic programming:
1) If we have calculated $$$dp_i$$$, update $$$dp_{i - 1} = min(dp_{i - 1}, dp_i + i)$$$;
2) If we have calculated $$$dp_i$$$, find the leftmost room $$$x$$$ such that a router can be installed in this room, and this router will cover room $$$i - 1$$$. Install a router in that room and update $$$dp_{max(0, x - k)} = min(dp_{max(0, x - k)}, dp_i + (x + 1))$$$.
If we precalculate the leftmost router that can affect each room, this solution will work in $$$O(n)$$$. Solution code
Nicely Written..!!
very clear
Thanks BledDest, you made solution crystal clear. :)
Thanks BledDest, very nice explanation!!
In Problem B: For input : 3 20 10 20
output: 43 2 3 1 Is Wrong.Why? We can select any 20, first or last.
because right answer is 3 1 2 or 1 3 2. You need to sort Ai by descending
O(1) solution for E2: http://codeforces.net/contest/1216/submission/61064504
Can some one tell me how to prove this thought is wrong: if the swords in each room before hand is bigger than max(a), so you may have a lagger gcd as a result, and (k1 + k2 + ... + kn) which is y could be smaller.
No, if there are more swords in each room originally than $$$max(a)$$$ then the new gcd must be less than the old gcd (unless all rooms have the same number of swords). Check out this explanation.
Excellent work! thank u sir :)
https://codeforces.net/blog/entry/69984 — разбор решения за O(1) для каждого q.
My alternate solution to F. Lets create a segment tree with lazy updates. The tree basically allows us to perform range updates on an imaginary array v[] in which the i th position stores the cost of connecting the first i rooms to the internet. Now lets iterate from 0 to n — 1. Let s be the inputted string. If s[i] is 0, then update v[i] with min(v[i], v[i — 1] + i + 1) else range update on the segment tree. This does not require any complicated transitions or complicated data structures. Complexity is O(nlogn).
Here is my code: Code
wow..nice approach
In case you got confused reading E2 editorial here: Let's add add⋅cnt+cnt(cnt+1)/2⋅cnt
I think the second summand is cnt(cnt+1)/2 . len I mean its pretty logical I don't get why the editorial says to multiply by cnt.
Also, I think the time complexity is O(log n) for each query. well with some constant of course if optimally implemented.
my problem c solution: https://codeforces.net/contest/1216/submission/61159190
First we check if any corner is outside of both black rectangles, if it is -- then white is visible if all corners are inside black areas, then I check if projection to x is inside black fully and projection to y is inside black fully. if it's not -- then white is visible. If both: horizontal and vertical projections are covered with black projections -- then white is invisible. I believe it is more intuitive.
please tell the algorithm for F question to solve in linear time. if possible please elaborate the editorial given too.
In E2,
add * cnt + ((cnt * (cnt + 1)) / 2) * lenshould be added to the total sum of lengths, notadd * cnt + ((cnt * (cnt + 1)) / 2) * cntSince, for numbers with length equal tolen, number of new digits added to the current string of digits will be(1 * len) + (2 * len) + (3 * len) + ... + (cnt * len)``In Problem-D, how does one prove that there exists an optimal solution $$$y=\dfrac{\sum_{i = 0}^{n-1}(x-a_{i})}{g}$$$ for $$$x=a_{max}$$$ — as in why doesn't one have to check for $$$x>a_{max}$$$? Note that $$$g = gcd(x-a_{0}, x-a_{1}, ..., x-a_{n-1})$$$.
+1
my O(n) solution to F with dp and monotonic stack (actually deque) 211377823