Всем спасибо за участие! 👊👊👊
Разбор
Tutorial is loading...
Решение
#include<bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--) {
int n, s;
cin >> n >> s;
vector<int> x(n);
for (int i = 0; i < n; i++) cin >> x[i];
int ans = min(abs(s - x[0]), abs(s - x.back())) + x.back() - x[0];
cout << ans << '\n';
}
return 0;
}
Разбор
Tutorial is loading...
Решение
#include<bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
string s;
cin >> s;
vector<int> cnt(26, 0);
for (auto c : s) cnt[c - 'a']++;
int flag = 0;
for (int i = 0; i < 26; i++) {
if (cnt[i] >= 3) flag = 1;
else if (cnt[i] == 2 && (s[0] - 'a' != i || s.back() - 'a' != i)) flag = 1;
}
if (flag) cout << "Yes" << '\n';
else cout << "No" << '\n';
}
return 0;
}
Разбор
Tutorial is loading...
Решение
#include<bits/stdc++.h>
using namespace std;
main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
vector<vector<int>> a(n, vector<int> (m));
int mx = 0, cnt_mx = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> a[i][j];
if (a[i][j] > mx) {
mx = a[i][j], cnt_mx = 1;
} else if (a[i][j] == mx) {
cnt_mx++;
}
}
}
vector<int> r(n), c(m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (a[i][j] == mx) {
r[i]++;
c[j]++;
}
}
}
int flag = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (r[i] + c[j] - (a[i][j] == mx) == cnt_mx) {
flag = 1;
}
}
}
cout << mx - flag << '\n';
}
return 0;
}
Разбор
Tutorial is loading...
Решение
#include<bits/stdc++.h>
using namespace std;
main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n), b(n);
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++) cin >> b[i];
vector<pair<int, int>> ans;
for (int i = 0; i < n; i++) {
for (int j = 1; j < n; j++) {
if (a[j - 1] > a[j]) {
swap(a[j - 1], a[j]);
ans.push_back({1, j});
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 1; j < n; j++) {
if (b[j - 1] > b[j]) {
swap(b[j - 1], b[j]);
ans.push_back({2, j});
}
}
}
for (int i = 0; i < n; i++) {
if (a[i] > b[i]) {
ans.push_back({3, i + 1});
}
}
cout << ans.size() << '\n';
for (auto [x, y] : ans) cout << x << " " << y << '\n';
}
return 0;
}
Разбор
Tutorial is loading...
Решение
#include<bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--) {
string l, r;
cin >> l >> r;
if (l == r) {
cout << 2 * l.size() << '\n';
continue;
}
int ptr = 0;
while (ptr < l.size() && l[ptr] == r[ptr]) ptr++;
if (l[ptr] + 1 < r[ptr]) {
cout << 2 * ptr << '\n';
} else {
int res = 2 * ptr + 1;
for (int i = ptr + 1; i < l.size(); i++) {
if (l[i] == '9' && r[i] == '0') res++;
else break;
}
cout << res << '\n';
}
}
return 0;
}
Разбор
Tutorial is loading...
Решение
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int const maxn = 2e5 + 5;
int a[maxn];
ll pref[maxn], s;
main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--) {
int n, x;
cin >> n >> s >> x;
for (int i = 1; i <= n; i++) {
cin >> a[i];
pref[i] = pref[i - 1] + a[i];
}
ll ans = 0;
map<ll, int> cnt;
int lef = 1;
for (int r = 1; r <= n; r++) {
if (a[r] > x) cnt.clear(), lef = r + 1;
else if (a[r] == x) {
while (lef <= r) {
cnt[pref[lef - 1]]++;
lef++;
}
}
ans += cnt[pref[r] - s];
}
cout << ans << '\n';
}
return 0;
}
Разбор
Tutorial is loading...
Решение
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int const maxn = 2e5 + 5;
int pref[maxn];
main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
string s;
cin >> s;
ll ans = 0;
for (int i = 0; i < n; i++) {
pref[i + 1] = pref[i];
if (s[i] == '0') pref[i + 1]--;
else pref[i + 1]++;
}
for (int i = 1; i <= n; i++) {
ans += (ll)i * (n - i + 1);
}
sort(pref, pref + n + 1);
for (int i = 0; i <= n; i++) {
ans += (ll)pref[i] * (i - (n - i));
}
cout << ans / 2 << '\n';
}
return 0;
}
Разбор
Tutorial is loading...
Решение
#include<bits/stdc++.h>
using namespace std;
main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
multiset<int> dp;
for (int i = 1; i <= n; i++) {
int l, r;
cin >> l >> r;
auto it = dp.upper_bound(r);
if (it != dp.end()) {
dp.erase(it);
}
dp.insert(l);
cout << dp.size() << " ";
}
cout << '\n';
}
return 0;
}
speedyy voventa
speedyy voventa
Speedyy voventa
Speedyy voventa
speedyy voventa
speedyy voventa
H code in the tutorial is smaller than my A's . Wth :/. nvm good questions
E can also be solved by randomly sampling 1000 numbers per testcase and seeing what the minimum score of these numbers is. Enjoy :D 324927463
What did you just do?
bro solved using probabilities, absolute legend.
I see you tried hacking me. Keep going :)
look at the guy right below you. youre prob his next target LOL
cool, it's unhackable, I don't exactly care.
.
the chance of digits not matching are higher than the chance of matching
in simpler terms there are multiple x/answer for the values, which are more than the wrong answers by a very big margin
Would 4500 iterations of selecting random x work well? I'm curious :3
TLE.
u guys are genius
what's wrong with my solution submission link :- https://codeforces.me/contest/2121/submission/337553309
For $$$E$$$, I generated $$$100$$$ random numbers $$$x$$$ in the range $$$[l, r]$$$ and took the minimum $$$f(l, x) + f(x, r)$$$ over all of them. I think that the worst-case probability that some $$$x$$$ works is $$$(\frac{4}{5})^9$$$ (or around $$$13\%$$$) because, in most cases, it seems like each digit of $$$x$$$ has a $$$\frac{4}{5}$$$ chance of not being equal to either of the corresponding digits of $$$l$$$ and $$$r$$$. So the probability that the solution fails a testcase might be $$$(1 - (\frac{4}{5})^9)^{100} \approx 5 \cdot 10^{-7}$$$.
Posting suspicious solutions in chat before the hacking round is over invites attention. :)
Yeah lol I'm pretty sure my numbers are wrong. But even if they weren't, each test would still have a $$$\approx \frac{1}{200}$$$ chance of failing, so if someone were really dedicated, they could make it fail. Can I ask what your $$$l, r$$$ were?
303120507 589565053
Found through randomized search / offline simulation.
can you try hacking me?
Interesting. I might be wrong, but it looks like $$$300\,000\,000 \,\, 599\,999\,999$$$ would be an optimal hacking testcase. That is because there is a $$$\frac{1}{3}$$$ chance of getting a $$$4$$$ (as opposed to a $$$3$$$ or a $$$5$$$), and then a $$$(\frac{4}{5})^8$$$ chance of satisfying all of the other digits. So the chance of any one $$$x$$$ producing the answer is $$$\frac{1}{3} \cdot (\frac{4}{5})^8 \approx 5.5\%$$$. So the probability of failing this testcase is $$$(1 - \frac{1}{3} \cdot (\frac{4}{5})^8)^{100} \approx 0.3\%$$$, which is really not good for $$$10^4$$$ testcases.
And, unless there's a better testcase out there, I guess there's not a snowball's chance in hell you will be able to hack macaquedev, as $$$(1 - \frac{1}{3} \cdot (\frac{4}{5})^8)^{1000} \approx 10^{-25}$$$.
Your analysis looks accurate to me.
Can you share your intuition behind this method? Like, how did you even think this could work in the first place?
yes — I just realised that given a random number, it's more likely NOT to match than to match — therefore if you generate 1000 numbers, you have a very very low probability of not getting an optimal number at least once. Also I just couldn't be bothered to solve it properly.
Crazy
Dk what u mean exactly but it sounds super cool!
I mean exactly what I said. It's quite trivial to calculate score given l, r and some number x between l and r. You just implement what's written in the problem statement — compare each digit. Then, you generate 1000 random values of x, and with almost 100% certainty, at least one of them will have the minimal possible score. This is not hackable.
in problem D why simply sorting a and b and then swaping is enough. can someone explain me clearly why swaping in last will not violate our conditions .?
Let $$$a$$$ and $$$b$$$ be the arrays after sorting, but before swapping.
Then for any $$$i$$$, we have that $$$\min(a_i, b_i) \leq a_i, b_i$$$. But at least one of $$$a_i$$$ or $$$b_i$$$ must be smaller than $$$\min(a_{i+1}, b_{i+1})$$$, because one of them was placed before $$$\min(a_{i+1}, b_{i+1})$$$ whilst sorting. So we have that the mins are increasing.
By similar reasoning, for any $$$i$$$, we have that $$$\max(a_i, b_i)$$$ is less than at least one of $$$a_{i+1}$$$ or $$$b_{i+1}$$$ because $$$\max(a_i, b_i)$$$ was placed before one of them whilst sorting. Since we have that $$$a_{i+1}, b_{i+1} \leq \max(a_{i+1}, b_{i+1})$$$, we have that the maxes are increasing.
So we have that $$$\min(a_1, b_1) \lt \min(a_2, b_2) \lt \dots \lt \min(a_n, b_n)$$$ and $$$\max(a_1, b_1) \lt \max(a_2, b_2) \lt \dots \lt \max(a_n, b_n)$$$, so if we place all of the mins in $$$a$$$ and all of the maxes in $$$b$$$, both arrays remain sorted.
After sorting, we have:
-
a[i] < a[i+1]for alli-
b[i] < b[i+1]for alliNow, when we decide to swap because
a[i] > b[i], we need to verify that the swap won't violate the sorted order of either array.Swapping
b[i]intoa:We're putting
b[i]in place ofa[i]. Since we originally hadb[i] < a[i] < a[i+1], it follows thatb[i] < a[i+1], so insertingb[i]intoawon't break the increasing order ina.Swapping
a[i]intob:This is more subtle. It's possible that
a[i] > b[i+1], which would break the sorted order inb. However, sinceb[i+1] < a[i] < a[i+1], on the next iteration (i+1), we will again encountera[i+1] > b[i+1], and thus perform another swap. This chain reaction will make sure that the arrays remain valid.countful thanks!! xD
Well explained countful
simple proof for
min(a[i], b[i]) < min(a[i + 1], b[i + 1])d1 = a[i + 1] - a[i], d1 > 0d2 = b[i + 1] - b[i], d2 > 0min(a[i], b[i]) < min(a[i] + d1, b[i] + d2)because both arguments of min have increasedDEF were easier compare to normal div 3 , Instantly knew solution of D,E here (this doesnt happen usually)
how did you easily get D?
u just had to make sure your operation wont exceed 1709 and max array size was 40. even at worst case you wouldnt need more than 780 swaps to sort single array , to sort both arrays 780+780 and if a[i]>b[i] then lets take 40 more operation they are within range , its brute force literally
My solution was just to have odd numbers in a and even numbers in b, and move them one by one to the correct places in order, 1, 2, 3, etc.:
My submission just simulates this process.
Too much implementation based questions, I think 2.5 hours for this would've been better, the explanations are pretty short which is fine when someone who is experienced is reading them, but for most people it might easily not come to them. Hope next div 3 is better
It's actually crazy how beautiful the solution to H is...
can u explain it.. can't figure out ,been thinking 'bout it for like 2 hours straight. a strong hint is also welcome ,like don't explain everything but only what u feel is the critical optimization part.
Alternate solution for problem G:
Let
dp[i]denote the sum of functionf()over all substrings in prefix ofi, i.e, $$$\sum f(s_l,s_{l+1},...,s_r)$$$$$$\forall$$$ l, r s.t. $$$1 \le l \le r \le i$$$. Letans[i]denote the sum of functionf()over all substrings ending at indexi, i.e, $$$\sum f(s_l,s_{l+1},...,s_i)$$$$$$\forall$$$ l s.t. $$$1 \le l \le i$$$. Letpre[i]denote the prefix sum till index i, i.e, $$$pre[i] = \sum_{j = i}^{i} (s[j] == 1)$$$.Final answer will be
dp[n]and base case isdp[1] = 1andans[1] = 1(assuming 1 based indexing).Now suppose the $$$i^{th}$$$ character is a
1(small change in sign when $$$s_{i} = 0$$$), then:$$$dp[i] = dp[i - 1] + ans[i - 1] + \sum_{j = 1}^{i} (pre[i] - pre[j - 1] \gt i - j + 1 - pre[i] + pre[j - 1])$$$
$$$ans[i] = dp[i] - dp[i - 1]$$$
The summation equation basically accounts for all the +1's we do when attach $$$s_i$$$ to $$$s_{1, 2, ..., i-1}$$$.
We can rearrange the summation equation and then use (ordered) set optimization to quickly compute the dp :)
can you explain the ans[i-1] + part? i dont get it.
suppose s[i]='1' then ans[i] stores the answer for all substrings ending at i now you can see that this value wont change a lot from ans[i-1] it only changes when adding the last element to a subset increases the majority and this increase is only by 1 so you just have to add this number of subsets to ans[i-1] to get ans[i].
so find all such subsets using the difference in count of 0 and 1
let pref[i] be count(1)-count(0) till i;
then at all previous places where pref[j] < pref[i] form the required answer; ordered set does it quickly
similarly you can derive it for when s[i]='0'
sumit sir :)
Problem G has solutions for O(n)
I a bit overkilled this task and wrote this O(n) solution that uses 2 stacks to recalculate the answer using information about the answer on the previous prefix. If you are interested in analyzing it, here is the code: 324911499.
But I found a more interesting and simpler for understanding solution that reaches O(n), written by Kilo_5723. This solution implements the same logic as the author's, but counts the sum of modules of the prefix with asymptotic O(n), instead of O(nlogn): 324868540
That's a clever approach. Thanks for sharing it.
I wanted to point out that the tutorial's solution can also be made $$$O(n)$$$ trivially by using a counting sort instead of a comparison-based sort, since all the elements are between $$$-n$$$ and $$$n$$$.
In fact, you can think of Kilo_5723's solution as doing an online counting sort: at the end of the loop, the array
valcontains a count of the elements ofprefin the tutorial. The “online” part is that he updates the total for each character processed, which is why there are only additions/subtractions and no multiplications.https://codeforces.me/contest/2121/submission/325347841
Here's mine also with O(n) time
Seems a little simpler
Could you please explain how it works?
Basically, when you have the answer to some prefix that is n characters long, to find the answer to prefix that is n+1 characters long(either adding a 1 or 0), all you need to know is what ranges have what ever character added as the (n+1)th as the most common character or have both 1 and 0 as the most common character. We can have an array of size n*2 +1 and have a middle index and move it up or down depending on if a character is 0 or 1, for instance down if 0, up if 1 as the most we can move up or down is n. In this case in the array whatever index we start on we can increment it, and keep track of how many increments (or just the sum) of the array on the left and right sides of the 'middle' index as for all the increments that where previously done on the right side, if the new character is 0, that new character is increasing the value of those sequences as those subsets had 0 most common character. The inverse is true for the left side. This is like dp where we are using our previous answer and adding onto it, with each new encounter during our iteration through the list.
https://codeforces.me/contest/2121/submission/326062731
Thanks bro!
Господи, храни Гуфа
Solution for problem E, using digit DP
324944536
UPDATE.
Solution Explanation: Comment
When will be the ratings updated? today i gave my first contest so
After the Hacking period is over, everyone's submissions will be finalized. I would expect them to be back by early morning EST.
Does anyone have another way to solve H? The editorial is too hard for me XD
I simply used a Lazy Segment Tree; after compressing all values, let $$$\mathrm{dp}[k][v]$$$ be the maximum length of a non-decreasing subsequence using the first $$$k$$$ intervals and ending in $$$v$$$.
Initially (for $$$k = 0$$$), the maximum length is always $$$0$$$. For a fixed $$$k$$$, all non-decreasing subsequences ending in $$$[0; l]$$$ can be "extended" by one by simply appending $$$l$$$ to it. At the same time, all subsequences ending in $$$v \in [l; r]$$$ can be "extended" by $$$v$$$; two operations that can be easily implemented for a Segment Tree!
So in the end, you simply maintain a Lazy Segment Tree containing all possible ending values and update that for each step in $$$\mathcal O(\log n)$$$ time.
Submission: 324887791
Can anyone please tell why my solution is getting memory limit exceeded :(
https://codeforces.me/contest/2121/submission/324913725
I dont see anything to worry about. I guess its from the vectors. I beilive they dont deallocate themselves. I dont know to help you with this one. Try
long long a[]insead of vectorsYou're using inbuilt swap function which stores the elements it is swapping and since you're swapping around 1600 pairs worst case for every test case. for 100 test cases it will add and you'll have to store 160000 pairs which is causing the memory limit exceed. you can instead of using inbuilt swap function swap them manually and it should pass
no bro, it is still not working
your code is going on an infinite loop for the 1st test of test case 6. Possible issue according to me is that in the while loop you're checking if ac[i]==a[i] and then finding the jth index in ac but updating a instead which might create a cycle for a, and hence causing infinite loop.
170ms -> TLE ??? What the fucking original tests ???
170ms -> TLE ??? What the fucking original tests ???
Liked C
C can be solved with minimal efforts if you have 2D Sparse Table template in hand
Thanks
your code is difficult. It can be solved easier
For problem F, I got a solution that uses sparse table + binary search. I thought that
max[i -> x]for somexis monotonic. To my calculations, the time complexity should beO(n*log(n) + n*log^2(n)). But that gave tle on test 24 for some reason. Can anyone check my solution if I did calculate time complexity wrong or are there some bug in the code because I couldn't find anything https://codeforces.me/contest/2121/submission/324921228Не смог решить задачу F, не знаю, почему моё решение не работало, хотя код был очень похож на код в разборе. 2 моё решение не прошло по времени :(
hi voventa I have solved the problem F and it also accepted but after system testing it showing TLE(time limit exceed) on test case 24 why ?
Maybe not :) hah
The problem G is the same as https://www.codechef.com/problems/SUMFSUB. There's not even a single change. The problem is fairly recent as well. I tried putting the problem statement of G in http://yuantiji.ac/en/ and it did not show me SUMFSUB. I can understand that no one is at fault here, but we need more powerful tools so that this does not happen in the future.
I believe I have another approach for Problem D (324890440) where we construct the first row as:
$$$1, 2, 3, \ldots, N$$$
and the second row as:
$$$N+1, N+2, N+3, \ldots, 2N$$$.
Here's an analysis of the worst-case scenario for my solution:
1. Fixing the first row
We need to sum the moves required for each element, which correspond to $$$ 40 + 38 + 36 + \ldots + 2 + 2 + 4 + 6 + \ldots + 40 $$$
This sum is equal to $$$420 + 420 = 840$$$, so the total number of moves is: $$$20 \times 21 \times 2=840$$$
2. Fixing the second row
After the top row is sorted, the bottom row becomes:
$$$2N, 2N-1, ..., N+1$$$
This is a reverse-sorted sequence of size $$$N = 40$$$. Sorting it (e.g. via bubble sort or selection sort) in the worst case takes: $$$\frac{40 \times 39}{2} = 780$$$
Total moves: $$$840+780=1620$$$ moves.
ItsNotMeItsYou I have also did the same thing in contest but got FST on system test-13 can you please tell me why it is failing My submission : My Submission
You use operation 3 in the final step; I do it first.
Now it is taking more operations
On that tc:13 previously it was taking 1810 op but not 2160
For the first row, try using 2, 3, and finally 1, in that order. Also, please add a spoiler for your code.
I like problem F
Overthinking did me a lot of harm in BCD...
Hi voventa, can you please add this blog to the contests materials? I didn't know this blog before I open the announcement that editorial is out
The (very neat) idea for problem H can also be used to solve this problem, and the code is not so different
Very nice contest!!!
Why does my solution 326223855 for F is giving tle despite being nlogn? Update : Missed the auto& it.
G can also be easily solved with a segment tree. First, get the sum of max counts for every substring containing the number at index 0. Keep track of the number of positive and negative relative one/zero counts for every substring. Then, we can remove the numbers from the left one by one. If we remove a 1, then decrease our result by the number of positive net sums and decrease all net sums by 1. If we remove a 0, then decrease our result by the number of negative net sums and increase all net sums by 1. Then the answer is the sum of each result after removing each number from the left n times.
Code: 326714584
Here is my O(n) solution for problem G.
Did anyone solve G using divide and conquer? I feel like it is possible but I am struggling with the implementation.
G is perfact，very interesting
damn good editorial
Problem H also can just be solved with segment tree beats, submission: https://codeforces.me/contest/2121/submission/358456170
Instead of checking the difference for each digit, we build each number from left to right, i.e. $$$12345$$$ becomes $$$1, 12, 123, 1234, 12345$$$ — we can do this by multiplying the current number by $$$10$$$ then adding the $$$i$$$-th digit
Denote the answer $$$f$$$. For each number of digits, if $$$l = r$$$, $$$f = f + 2$$$; if $$$l = r - 1$$$, $$$f = f + 1$$$, else break
Time complexity is $$$O(\log{r})$$$
Python code: 368146164
This is my first time doing this so sorry if it's unclear
Task G can be solved using cartesian tree https://codeforces.me/contest/2121/submission/376262585 (I just again overkilled cause I didnt come up with anything simpler)