Tutorial is loading...
Code
#include <random>
#include <vector>
#include <iostream>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define ll long long
#define pii pair<int, int>
#define pb emplace_back
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
for (auto &c : a) cin >> c;
int mx = 0;
for (int i = 0; i < n - 1; i++) mx = max(mx, a[i]);
cout << mx + a[n - 1] << "\n";
}
return 0;
}
Tutorial is loading...
Code
#include <iostream>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
long long n, a, b;
cin >> n >> a >> b;
if (b <= a) {
cout << n * a << endl;
} else {
long long k = min(b — a + 1, n);
cout << (b — k + 1) * n + k * (k — 1) / 2 << endl;
}
}
}
Tutorial is loading...
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T = 1;
cin >> T;
while (T--) {
int n;
ll k;
cin >> n >> k;
ll max_s = 0;
for (int i = 0; i < n; i++) max_s += abs(n — 1 — i — i);
if (k % 2 != 0 || k > max_s) {
cout << "No\n";
} else {
cout << "Yes\n";
vector<int> p(n);
k /= 2;
iota(p.begin(), p.end(), 0);
for (int i = 0; k > 0; i++) {
if (k >= n — 1 — 2 * i) {
swap(p[i], p[n — 1 — i]);
k -= n — 1 — 2 * i;
} else {
swap(p[i], p[i + k]);
k = 0;
}
}
for (int i = 0; i < n; i++) {
cout << p[i] + 1 << " ";
}
cout << "\n";
}
}
}
Tutorial is loading...
Code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
int n, c;
cin >> n >> c;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
if (n == 1) {
cout << "0\n";
return;
}
int mx = *max_element(a.begin() + 1, a.end());
int mxc = max(a[0] + c, mx);
int winner = mxc == a[0] + c ? 0 : find(a.begin() + 1, a.end(), mx) - a.begin();
ll sum = c;
for (int i = 0; i < n; sum += a[i], ++i) {
int answer;
if (i == winner) {
answer = 0;
} else if (sum + a[i] >= mx) {
answer = i;
} else {
answer = i + 1;
}
cout << answer << " \n"[i == n - 1];
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int test = 1;
cin >> test;
while (test--) {
solve();
}
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;
string s, t;
cin >> n >> s >> t;
auto get_range = [&] (int i) {
if (s[i] == '1') return make_pair(i, i);
int l = -1, r = -1;
if (i > 0 && t[i-1] == '1') l = i-1;
else if (i > 1 && t[i-1] == '0' && s[i-2] == '0') l = i-2;
if (i+1 < n && t[i+1] == '1') r = i+1;
else if (i+2 < n && t[i+1] == '0' && s[i+2] == '0') r = i+2;
if (l == -1) r = -1;
if (r == -1) l = -1;
return make_pair(l, r);
};
vector<int> pref(n+1);
for (int i = 0; i < n; i++) pref[i+1] = pref[i] + (get_range(i).first != -1);
int q;
cin >> q;
while (q--) {
int l, r;
cin >> l >> r;
int ans = 0;
if (r-l <= 5) {
for (int i = l-1; i < r; i++) {
auto [ll, rr] = get_range(i);
if (ll >= l-1 && rr < r) ans++;
}
}
else {
ans = pref[r] - pref[l-1];
for (int j: {l-1, l, r-2, r-1}) {
auto [ll, rr] = get_range(j);
if (ll != -1 && (ll < l-1 || rr >= r)) ans--;
}
}
cout << ans << '\n';
}
}
}
Tutorial is loading...
Code
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
using namespace std;
using ll = long long;
const int MAXA = 1e6;
int n, k;
vector<int> a;
vector<int> primes_x[MAXA + 1];
unordered_map<int, int> last_ind_p;
vector<bool> is_prime(MAXA + 1, true);
vector<int> primes;
void read() {
cin >> n >> k;
a.assign(n, 0);
for (int& elem : a) {
cin >> elem;
}
}
vector<int> p, sz, p_rs;
int col(int A) {
return (A == p[A] ? A : p[A] = col(p[A]));
}
void unique(int A, int B) {
A = col(A); B = col(B);
if (A == B) return;
if (sz[A] < sz[B]) {
swap(A, B);
}
p[B] = A;
sz[A] += sz[B];
}
void solve() {
last_ind_p.clear();
vector<int> aa;
for (int i = 1; i < n; i++) {
aa.push_back(a[i]);
}
for (int i = 0; i < n; i++) {
aa.push_back(a[i]);
}
a = aa;
int n2 = n;
n = a.size();
p.assign(n, -1);
p_rs.assign(n, -1);
sz.assign(n, -1);
for (int i = 0; i < n; i++) {
p[i] = i;
sz[i] = 1;
}
for (int i = 0; i < n2; i++) {
p_rs[i] = i + 1;
p_rs[2 * n2 - 2 - i] = i + 1;
}
vector<int> a2 = a;
sort(a2.begin(), a2.end());
a2.resize(unique(a2.begin(), a2.end()) - a2.begin());
unordered_set<int> to_clean;
for (int elem : a2) {
int cur_elem = elem;
for (ll p : primes) {
if (p * p > elem) break;
if (elem % p == 0) {
primes_x[cur_elem].push_back(p);
if (primes_x[cur_elem].size() == 1) {
to_clean.insert(cur_elem);
}
}
while (elem % p == 0) {
elem /= p;
}
}
if (elem > 1) {
primes_x[cur_elem].push_back(elem);
if (primes_x[cur_elem].size() == 1) {
to_clean.insert(cur_elem);
}
}
}
for (int i = 0; i < n; i++) {
for (int cur_p : primes_x[a[i]]) {
if (last_ind_p.count(cur_p) && i - last_ind_p[cur_p] <= k) {
unique(last_ind_p[cur_p], i);
}
last_ind_p[cur_p] = i;
}
}
for (int i : to_clean)
primes_x[i].clear();
}
void write() {
ll ans = 0;
for (int i = 0; i < n; i++) {
if (p[i] == i) {
if (a[i] > 1) {
ans += 1;
}
else {
ans += p_rs[i];
}
}
}
cout << ans << endl;
}
int main() {
for (ll i = 2; i <= MAXA; i++) {
if (is_prime[i]) {
primes.push_back(i);
for (ll j = i * i; j <= MAXA; j += i) {
is_prime[j] = false;
}
}
}
ios_base::sync_with_stdio(false); cin.tie(0);
int t;
cin >> t;
while (t--) {
read();
solve();
write();
}
}
This was a great contest. Nice problems + superfast editorial + quick system testing.
Thank you for the quality contest and fast editorial. I had fun during this contest. :)
C was harder than DE :(
Agreed but still a good one though :)
Isn't it a bit sus how many people solved C?
It was harder for me
it's possible that this happened out of complete coincidence, but problem C appeared before in last year's ECPC finals which is the Egyptian qualifier for our ICPC regional, it was the exact same problem with just greater constraints for K on today's round which might have given advantages to people who solved it last year and people who upsolved it later on.
Maybe, i guess just skill issue on my part :(
yes, true :(
C isn't that hard. It's just observations.
can you please explain the construction in C; what does "&mdash" mean?
&mdash is the minus sign
C was harder than DEF :(
F xD!
Agreed
D is a good problem! E is not hard. I think this is a very good round.
What is
&mdashin the code of problem B,C ?Usually a formatting issue,
—is equivalent to a minus symbol.Whoa speed!
Fast editorial! Great Contest!
Why is this downvoted?
Fast editorial!
I think C, D, and E were all roughly the same difficulty though. F also seems on the easy side.
How can you explain the $$$length <5$$$ in E? Also C's code has formatting issues.
If you see the given range [l,r], the only only elements which gets affected are a[l], a[l+1], a[r] and a[r-1] and rest of them remains same. So when you check for these indices the range [l,l+1] and [r-1,r] should not cross each other, otherwise single index will be counted twice. Therefore, for len < 5 is done using brute force. One can use len < 7,8 it won't change the answer.
Very useful explanation, thanks
We understand that we should first finish all the type 1 operations, since that will only increase the type 2's chances to increase the count of 1s in a. Consider a segment from [l, r]. Even in this we do the type 1 operation. This does the same affect in b in range l + 1 to r — 1 as when you would consider the whole string for such operations. Now when do b's operations, the range l + 1 to r — 1 then have the same influence on the range l + 2 to r — 2 as in the whole string. So, if we consider a range l to r, we only need to re calculate values which is within 2 length less from both sides. The inbetween can be used from the answer for this range when we calculate for the whole string, which can be precalculated and the count of 1s can be stored as prefix sums. Hence we need to first calculate the ans for the last two numbers from the ends of the range and add the precalc for the inbetween with it. Now, this precalculation obviously only needs to be added when the length of the range is >= 5.
very nice explansion. thanksm
ite watever bro
Can someone explain in Problem C how do we prove that:
" maximum maxk is achieved with the permutation [n,n−1,n−2,...,1]"
For each $$$i$$$ from permutation it can contribute to sum with $$$1$$$ or $$$-1$$$. Same for $$$i$$$ from neutral permutation. There are exactly $$$n$$$ numbers that contribute with $$$1$$$ and $$$n$$$ with $$$-1$$$. It's easy to see that maximal sum is achieved when $$$n$$$ greatest numbers contribute with $$$1$$$ and $$$n$$$ smallest with $$$-1$$$. Also you can see that with permutation $$$[n, n - 1, n - 2, ..., 1]$$$ we get this sum.
Think like this:
If the original identity permutation is : $$$[1,2, \dots , n]$$$, then swapping any indices $$$i$$$ and $$$j$$$ ($$$i < j$$$) would result in score going from 0 to $$$2*(j-i)$$$. So what would be most optimal?
It would be swapping $$$(1,n), (2,n-1), \dots$$$ and so on. This would result in the max ans. This also proves the condition why for k odd, answer won't exist.
In fact it's not so obvious that it would be most optimal. There is at least one permutation with same score:
So proof of optimality is indeed necessary.
To see why this is indeed the max answer, we can see that if we write out the sum for the answer $$$\sum_{i = 1}^{n}|perm[i] - i|$$$, then each i occurs twice, one for the index i and one for the index j where perm[j] = i. If we remove the absolute value and write out the sum with the correct sign, each i occurs twice with either — or + sign, and there are n signs for each kind in front of these 2*n numbers.
Now, collect the terms by sign. When is a sum of kind x = y — z maximized for positive y and z? It's when y is max and z is min => We take the occurrences of larger n numbers with positive signs and smaller n numbers with negative signs => all numbers greater than n/2 are with + sign in the answer, and smaller than n/2 are with — sign.
An interesting consequence of this is that there are $$$(n/2)!^2$$$ such sequences for even n and $$$n*(n/2)!^2$$$ sequences for odd n with the maximum sum.
Edit: Missed a detail
You can apply indirect proof. Suppose that there is a permutation $$$q$$$ other than $$$p = [n,n−1,n−2,...,1]$$$ that gives a higher value. This means that there are indices $$$i$$$ and $$$j$$$, $$$i < j$$$, where $$$q_i < q_j$$$. Now, consider elements $$$|q_i - i| + |q_j - j|$$$, those are elements of sum for $$$q$$$. Look that always $$$|q_j - i| + |q_i - j| \geq |q_i - i| + |q_j - j|$$$. So, if we swap elements and $$$q_i$$$ and $$$q_j$$$ we do not decrease the value of metric. We repeat this procedure until there are any such pairs left in $$$q$$$. If there are not, we reached $$$p$$$ without decreasing value (we always reach p since every swap sort permutation and the process converges), which contradicts the hypothesis and which proves the thesis.
i={1,2,3,4,5}
p={_,_,_,_,_}
We calculate the Manhattan value by dividing into two groups: one where p[i]≥i and the other where p[i]<i.Then, the Manhattan value can be expressed as
(sum of p[i] in the first group + sum of i in the second group) − (sum of i in the first group + sum of p[i] in the second group).
(p[i] in the first group + i in the second group) have n elements.The same applies to the latter term as well.
To maximize the first term and minimize the second, the best assignment is to allocate {n,n,n−1,n−1,…} to the first term and {1,1,2,2,…} to the second. Since both i and p are permutations, this arrangement achieves the maximum possible value. This assignment is indeed feasible.
i={1,2,3,4,5},
p={5,4,3,2,1},
then the first term consists of {5,4,3,4,5} (with n elements), and the second term consists of {1,2,1,2,3} (also with n elements).
sorry if i am wrong.
Example given in D extremely weak imo, maybe intended
took nearly 2 hours to debug after contest
i think there is a typo in the solution of D, since the index starts at 1, for every candidate the possible answer are 0,(i-1) and i. In the editorial u put 0,i and i+1 like index starts at 0.
I think the problems order should be A, B, D, E, C, F because C is really hard on both thinking and implementing. D is only about thinking and E is only implementing :(((
Any tips on how to get better at constructive? I messed up so bad, got -155 delta
I'm not sure if this is a good practice. I usually try to print the output by the brute force to see the pattern in the answer. I'm not very good at thinking of the algos by myself. In C, I printed all the permutations of an array and the respective score.
what would be the rating of C problem?
According to clist, about 1300
whats a clist?
https://clist.by/problems/
how they decide the ratings for problems?
very similar to how codeforces does it
For E, I ended up simplifying to the classic sweep line "how many intervals inside of my interval". Very nice problem!
How so Orz?
I was lazy to type it all, but here it goes:
The first idea is similar to the one in the editorial: We can transform 0s in A -> 1s in B -> 1s in A, in that order. First we compute the 0s in B that can become a 1. Each position will have an "interval" that is needed for that position to become a 1. For example:
A = 010 and B = 000. The 2nd position in B has interval (1, 3), since we need this interval in A to make B = 010.
One more time, we do the same procedure but on A, and we fix the necessary intervals to turn 0s in A into 1s. For positions that are originally 1, their intervals are (i, i), where i is its index.
Finally, the problem becomes: For each query (an interval), how many intervals are there inside of it (since each interval is either (i, i), meaning it was initially a 1 in string A, or some other interval of type (l, r) if it used some operations to make the ith position of A a 1).
To solve that problem, one can use a sweep line with a segment tree. We sort the updates by end_pos, start_pos, and update a segment tree at position start_pos with +1, and the query is a range sum over (l, r) when on time r of events on the line sweep. Overall complexity is O(n log n), for both sorting and segment tree operations.
Got it, thanks :) volta pro simusexo
A good round and fast editorial, thanks! The problems are really good!
for problem C, can anyone help in actually proving why k is odd gives no solution, i just got an intuition on that, couldnt really be very sure until i tried out lot of cases and could see k cannot be odd
Say initially permutation was 1, 2, 3..n This will give minimum result 0, If you make any swap your result always changes in multiple of two
Lets notice that |a — b| = a — b (mod 2). If |a — b| = a — b then it is obvious. If |a — b| = b — a then we need to check that a — b = b — a (mod 2). And its right because 2*(a — b) = 0(mod 2). So if we will look at |a_1 — 1| + |a_2 — 2| + ... + |a_n — n| in mod 2, we can say that |a_1 — 1| + |a_2 — 2| + ... + |a_n — n| = a_1 — 1 + a_2 — 2 + ... + a_n — n (mod 2). Then a_1 — 1 + a_2 — 2 + ... + a_n — n = (a_1 + a_2 + ... + a_n) — (1 + 2 + ... + n). And finally (a_1 + a_2 + ... + a_n) = (1 + 2 + ... + n) because a_1, a_2, ..., a_n is permutation. So, (a_1 + a_2 + ... + a_n) — (1 + 2 + ... + n) = (1 + 2 + ... + n) — (1 + 2 + ... + n) = 0. That means that |a_1 — 1| + |a_2 — 2| + ... + |a_n — n| = 0 (mod 2). So it must be odd :)
Thanks a lot!!!
nice proof bro
can you explain me how |a-b| = a-b(mod 2)
write the permutation as a graph (add a directed edge from p[i] to i), then the k value of that permutation will be the sum of the weights of all its edges if we let w(p[i], i) = |p[i] — i|. since only cycles can contribute to k, let's show that the weight of a cycle is always even: let u be the smallest value of a node in the cycle and let v be the greatest. then the cycle consists of a path from u->v and another path v->u.
claim: both paths have the same parity as (v — u). proof: when the path u->v goes directly from u to v (ex: 1, 3, 5) the proof is easy, but if we go back at some moment (ex: 1, 4, 2, 5), we can think of it the following way: in the example, distance from 2 to 4 will be counted twice so it won't contribute to parity (it's 0 mod 2) so in the more general case whenever we go back we will count that distance twice since we need to get to v somehow. this means its contribution to overall parity will be zero and we can therefore use the parity of u->v which will be (v-u)%2.
for the path v->u the proof is the same.
since adding up two numbers with the same parity yields an even number, k is even.
more about permutation graphs here :)
thanks very much
Good Thread
D is wow! I did not realize that it is enough to remove only maximal element, so I wrote treap descent to find such minimal k, that removing k maximums is optimal: 266013096
пиздатая задача С спс други
Can someone give me a hint for how to make the permutation for C?
I think the yes/no rule is k % 2 == 0 and k <= 3n
Check this out!
I kow how to get the max vlue but how do you get intermediate values?
It's simple right, you keep on subtracting $$$n-1 , n-3, \dots$$$ from $$$k$$$ until it gets to $$$0$$$.
Have a look at my submission: 266032029
alright thank you very much I was very close to solving it in contest
https://youtu.be/paEcHyNKC7A?feature=shared
what is &mdash?
No clue
i didnt like this contest that much, first questions itself didn't click to me and problem B was interesting but I was struggling with TLE and this solution is not helping either.
Same man C was too hard for me and now I am not even able to understand that.
which year are you in?
4th is about to start
cool mine 3rd is about to start, I wanna reach pupil before 3rd starts :(
B and C are really straight forward. Such idiots.
yea dude, you are really smart, keep it up.
why does this solution to E give wrong answer? Can you suggest a countercase?
i'm 18000th number wa 266097206
This was a great contest.
C and D detailed video editorial
C : https://youtu.be/paEcHyNKC7A?feature=shared
D : https://youtu.be/CQ7lUs6s_zc?feature=shared
can someone please explain editorial to D?
Suppose you excluded the candidate with the most votes, his votes will go to the first candidate, whose votes will be of course greater than the current one.
Check my submission 266012471
You can use a suffix max or a set instead of sparse table.
Hmm, i only considered prefix candidates only for the second index, thought that would be enough and that's what i got wrong. Thanks for the lucid explanation.
Charge customers more for no reason. Real nice promotion there, Bob.
C is just greedy.
div 3
Almost gave up on C cuz it didn't click to me at all.
D was Nice. C was harder than D and E.
Дайте-ка угадаю: рабочее название задачи B — "Наедалово"?
The editorial hasnt been added to contest materials yet
Just did virtual, almost AKed them (missed possible overflow on F but got it few minutes after the end).
Feedback: nice problems and solutions, but next time please use "index" instead of "number". Both problems A and D had this issue and I spent more time trying to understand the examples on A than solving the problem. Overall really nice problems
exactly!!!!
why binary search on k from 0 to min(n,b) is not giving correct answer for all testcases?what necessary must be done to make it work all testcases ?
int maxProfit = n*a; int l = 0, r = llmin(n,b), k = 0; while(l <= r) { k = l + (r — l) / 2; int profit = 0; profit += k*b — ((k-1)*k)/2; profit += (n-k) * a; maxProfit = llmax(maxProfit, profit); if(maxProfit <= profit) { l = k+1; } else { r = k-1; } } cout << maxProfit << "\n";
Because it is not a monotonic space in k the function is quadratic in k. Can you tell me what your check function does in your binary search i can explain better if u tell that
it checks,
if profit for current k is greater than previously calculated profit, l = k + 1; i.e. BS in higher values of k.
else if it is less than privously calculated profit, r = k -1; i.e. BS in lower values of k
look for the graph of quadratic function a*x^2 + b*x + c where a is negative its a concave curve in downward direction not linear. So there is no monotonic space for the binary search to begin with. this is a monotonous space i'm talking about
k = 0 1 2 3 4 5 6 7 8 9 10
Y is true and N is false for the check function this is required for binary search this will not occur in this case.
You cannot binary search on k. But you can binary search on the maximum answer if you want with low = 0 and max 1e18 i guess its possible but we may get exceptions
must be doing something wrong as my BS solution was accepted calculate profit at mi d and mid+1 then move accordingly
if(till_mid<after_mid){ st=mid+1; } else{ end=mid-1; } Nice observation, The graph(coins vs k) for any test case will always be subgraph of a downward concave graph. so, This suits well.
I just Used Math. It is Much Easier to solve using Math. 265997636
266121556 Can anyone tell me what's wrong with my problem D solution, it fails in the second test.
I cannot Understand your code. You can check my code and understand the error. 266164533. I calculated the max number and its position and checked the cases. I guess you were missing a case.
Basically, I pre-calculate leftmax array, rightmax array and presum. After reading the tutorial, I find the leftmax array is not needed and presum array space can also be saved with a variable. Finding the intial winner index is enough. But I am still curious why my code is not equivalent to the tutorial, and my code is stuck by what testcase. Anyway, thanks for your kind reply. Have a good day.
Not sure how many of ya got stuck with C so I wanna share my own — practically author's solution but done almost mindlessly.
Full solution: 265984050
I had the weird logical check
k / 2 < maximumReach - ibecause I used $$$k$$$ as an int64 and $$$n$$$ as an int32, and was afraid of overflow issues. If you define everything as int64 anyway, feel free to just definemaximumReach = min(i + k / 2, n - 1 - i)and get rid of the weird if-else stuff. Something like this:One thing I saw some people concerning about was that the uncertainty of the max valid $$$k$$$, and I'd say it's not explicitly required here: if you reached the maxima permutation and your $$$k$$$ is still not yet subtracted to zero, then indeed the original input was beyond valid boundary.
See this comment
Why was c so difficult to solve :'(
cada cuanto hay competencias de programación ?
This contest is an example of why you should not stick to only one problem. I personally feel problem D was easier to do than problem C. I could not get the logic of problem C, but when I read problem D, I was quickly able to do it on the first attempt. Kudos to vaaven for creating such a problematic structure. The editorial is excellent
1978C - Manhattan Permutations i have solved the problem C theory wise in the contest time itself but when i submitted my solution it was showing runtime error in test case 2 (exit code 11) but i am not able to understand why this is happening ,so i am attaching my code submission here 266059429
i know that my approach is not exactly the same as that of the editorial but this is what i came up with so you can just do a debug session with the first test case of the problem in your editor to get a idea of how my algorithm is generating the sequence
thank you in advance
Exit code 11 looks suspiciously likely to be a SIGSEGV/segmentation fault. Try to notice out-of-bound index access, as the most likely cause.
Also I found something else fishy: casting
kfromlongback tointis incredibly dangerous. Ifkis outside of int32 bound, it's certain that in the very first loop it will screw itself up and either make a WA or a different exit-code-11-causing access.can anyone tell me what is error in my logic i have done same as editorial but still cant pass test case 2. my code
thanks i found it
Let's consider what happens if we swap x and 1 in the identity permutation. — what does this means in problem c editorial can anyone help me???
The problem wants us to construct an example permutation that is going to give us a Manhattan score of S lets say. A permutation is simply just [1,2,3...n] array with a few swaps right. So the editorial wants you to think what would happen when you swap lets say 1 and x in the identity permutation [1,2,3,..n] notice that you would get a permutation with a score 2*(x-1) , so basically all even number scores between 0 to n^2/2 (the max attainable score) can simply be constructed by using two pointers and swapping the numbers starting from the Identity permutation.
I really want to know why didnt the author use index instead of number it was confusing for both in d and a
I misunderstand D in the same way.
meaningless and boring problem D!
During the contest I used Mo's algorithm (莫队) to solve E and got accepted. Now I noticed I had made it more complicated. Interesting problems!
In Problem D, the answer of the index i should be either 0, i-1 or i(not 0, i or i+1), because the index in the problem starts from 1 instead of 0.
Does anyone have any idea why this solution for D does not work?
https://mirror.codeforces.com/contest/1978/submission/266203442
It seems to be failing for test case 235. wrong answer 235th numbers differ — expected: '3', found: '4'
Printing out the test case. C=0 and array is 0 1 2 2 0 https://mirror.codeforces.com/contest/1978/submission/266202827
Another approach for problem E using Mo's algorithm
266205187
Solved it with Mo's too, though the complexity is bigger that way.
Can i use Binary search for Prob D ?
Can anyone explain me the 3rd test case of prob D?
6 0
2 2 2 3 3 3
1 1 2 0 4 5
without any deleting the 4th will win, becuase his max & smallest index,
to win 1st anyone can be deleted
to win 2nd the 1st must be deleted (a[0]+a[1]>a[imax])
to win 3rd the 1st&2nd must be deleted
4th win without any deleted
5th can win only when the 4th deleted(becuase he is max with smallest index)
but then first will win, because he get all 4th fans a[0]+a[imax]+c>=a[imax], must delete him,
then second will win because he'll get 1st and 4th fans, so we should delete all chain till 5th
6th the same
Thanks brother, but I wanted to know the 3rd test case , 5 4 3 2 1
So for 2nd one (4), minimum is 1 removal ,but how?
well i understood ,by number they meant the index
Problem D: Elections Video Editorial LINK
Why in problem C k must be even??? |z-x|+|x-y|+|y-z| can be odd for 0<x<y<z<n+1
Suppose Parity(x)= 1 if x is odd and 0 if x is even.
Then Parity(|z-x|+|x-y|+|y-z|)=Parity( Parity(z)+Parity(x)+Parity(x)+Parity(y)+Parity(y)+Parity(z)) = Parity( 2*(Parity(x)+Parity(y)+Parity(y)) ) = 0 indicating it is in fact always even.
Similarly you can do this for more than 3 numbers, every time result will be even.
if you pick ANY permutation, with parity P. after doing any swap between 2 elements on it, it will stay with the same parity.
|a-b|+|c-d| = +-a +-b +-c +-d (doing +- just for generalisation/simplification (it could be + or -))
|c-b|+|a-d| = +-a +-b +-c +-d
by mod 2 , -1 and 1 are the same thing, so +- doesnt change the parity . as such both values have the same parity. so the over all parity didnt change.
as such any number of permutations would not change the parity. and as it starts with parity of 0 then it always stays like so.
C problem is very interesting. Lot of different though processes you could follow to come up at the greedy solution.
Problem E, $$$t$$$ is re-defined (both number of test cases and string).
D and E are easyer than C
For Problem C, we could have an O(1) memory solution by instead realising the following property.
assuming the sum is possible ( k multiple of 2 and less than maxK)
if we select the largest m such as the total sum achieved by [m,m−1,m−2,...,1] is still less or equal to k. we can permute to k by taking the m+1'th number and permuting/shifting it back, each permute/shift back gives +2. so we can pick the difference between this sum and the required sum and divide it by 2 and thats how much we need to "shift" the m+1'th element. lets call that w
so the final answer would be [m,m−1,m−2,..., w+1 , m+1 , w , ... , 1 , m+2 , m+3 , ... , n ] example implementation (could be improved) https://mirror.codeforces.com/contest/1978/submission/266337230
more details:
the sum achieved by [m,m−1,m−2,...,1] can be calculated into the following formula with few observations ( m*m — (m%2) )/2; so we can use binary search to find m
we can prove that each shift back adds +2 to the sum.
Could anyone explain why F is $$$O(n\log\log n)$$$? From what I read, we would first do a sieve to find the primes $$$\leq \max{a[]}$$$, which takes $$$O(\log\log(\max{a[]}))$$$ time. Then, we perform unions with DSU if two entries are divisible by the same prime and are less than or equal to $$$d$$$ apart, which can be done in $$$O(n)$$$. But since we do this for each prime found by the sieve and there are $$$\sim \frac{n}{\log{n}}$$$ primes up to $$$n$$$, this algorithm is $$$O\left(\frac{n^2}{\log{n}}\right)$$$, which is too slow.
Let's say that some prime $$$p$$$ shows up in positions $$$b_{1}, b_{2}, ..., b_{m}$$$, i.e. $$$a[b_i]$$$ is divisible by $$$p$$$. Notice that we only need to do DSU union for the consecutive case, i.e. we only need to unite $$$b_{i}$$$ and $$$b_{i+1}$$$ which is O(m) operations because we can save when a prime last showed up using a set or something (as we are iterating through the array). Furthermore, among all the primes $$$p$$$ that show up as divisors in a[], the sum of all the $$$m$$$'s is $$$O(n \log (\max a[]))$$$, because each a[i] can show up for at most $$$\log (\max a[])$$$ primes.
Tbh, I am not sure how the authors got O(n log log (max a[])), I think this problem is actually O(n log (max a[])).Nevermind, it seems like the unique prime factors of a number is usually $$$O(\log \log n)$$$. It doesn't seem like a strict bound though.Hi, I have a general question: what's the time complex to factorize N if I already have all primes under N?
I got it, it could be logN (https://www.geeksforgeeks.org/prime-factorization-using-sieve-olog-n-multiple-queries/)
Any idea why my soln for C is failing for some edge case? https://mirror.codeforces.com/contest/1978/submission/266668069
I don't know the exact testcase but by hit and trial your code is failing on this test case:
1
16 98
K calculated from your answer is 92 instead of 98.
Thanks a lot @ZombieUser .. Yeah, right, there was a bug in my code that I found out through this test case. Have corrected and submitted the correct soln.
Congrats Bro
D is amazing!
on c test 2 wrong answer Manhattan value isn't equal to k (test case 1215)
can someone explain what condition am I missing here( E ) — submission
I don't think the model solution for F is $$$O(n \log \log n)$$$:
sort(a2.begin(), a2.end());can somebody please help me with this. 1978C - Manhattan Permutations 268102157
Problem B can be solved writing the profit as a function like $$$f(k)$$$ and find the point where the function take the maximum value, with the first derivative. This is the submission 281685276