Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
string s;
cin >> s;
s = s.substr(0, s.size() / 2);
int k = unique(s.begin(), s.end()) - s.begin();
cout << (k == 1 ? "NO" : "YES") << '\n';
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
for _ in range(int(input())):
n, k = map(int, input().split())
a = sorted(list(map(int, input().split())))
ans = 0
pr = [0] * (n + 1)
for i in range(n):
pr[i + 1] = pr[i] + a[i]
for i in range(k + 1):
ans = max(ans, pr[n - (k - i)] - pr[2 * i])
print(ans)
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
for (int& x : a) cin >> x;
n = unique(a.begin(), a.end()) - a.begin();
int ans = n;
for (int i = 0; i + 2 < n; ++i) {
ans -= (a[i] < a[i + 1] && a[i + 1] < a[i + 2]);
ans -= (a[i] > a[i + 1] && a[i + 1] > a[i + 2]);
}
cout << ans << '\n';
}
}
1832D1 - Red-Blue Operations (Easy Version)
Idea: BledDest
Tutorial
Tutorial is loading...
1832D2 - Red-Blue Operations (Hard Version)
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
n, q = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
pr = [10**9 for i in range(n + 1)]
for i in range(n):
pr[i + 1] = min(pr[i], a[i] - i)
s = sum(a) - n * (n - 1) // 2
ans = []
for k in map(int, input().split()):
if k < n:
ans.append(min(pr[k] + k, a[k]))
continue
if k % 2 == n % 2:
ns = s - pr[n] * n
ans.append(pr[n] + k - (max(0, (k - n) // 2 - ns) + n - 1) // n)
else:
nmn = min(pr[n - 1], a[n - 1] - k)
ns = (s + (n - 1) - k) - nmn * n
ans.append(nmn + k - (max(0, (k - (n - 1)) // 2 - ns) + n - 1) // n)
print(*ans)
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int add(int x, int y, int mod = MOD)
{
return ((x + y) % mod + mod) % mod;
}
int mul(int x, int y, int mod = MOD)
{
return (x * 1ll * y) % mod;
}
int binpow(int x, int y, int mod = MOD)
{
int z = add(1, 0, mod);
while(y > 0)
{
if(y % 2 == 1) z = mul(z, x, mod);
y /= 2;
x = mul(x, x, mod);
}
return z;
}
vector<int> psum(vector<int> v)
{
vector<int> ans(1, 0);
for(auto x : v) ans.push_back(add(ans.back(), x));
return ans;
}
int main()
{
int n;
cin >> n;
vector<int> a(n);
cin >> a[0];
int x, y, m, k;
cin >> x >> y >> m >> k;
for(int i = 1; i < n; i++)
a[i] = add(mul(a[i - 1], x, m), y, m);
for(int i = 0; i <= k; i++)
a = psum(a);
long long ans = 0;
for(int i = 1; i <= n; i++)
ans ^= (a[i + 1] * 1ll * i);
cout << ans << endl;
}
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;
struct seg{
int l, r;
};
int n;
vector<long long> dp_before, dp_cur;
vector<vector<long long>> bst;
void compute(int l, int r, int optl, int optr){
if (l > r) return;
int mid = (l + r) / 2;
pair<long long, int> best = {-1, -1};
for (int k = optl; k <= min(mid, optr); k++)
best = max(best, {(k ? dp_before[k - 1] : 0) + bst[k][mid], k});
dp_cur[mid] = best.first;
int opt = best.second;
compute(l, mid - 1, optl, opt);
compute(mid + 1, r, opt, optr);
}
struct node{
long long c0;
int c1;
};
vector<node> f;
void update(int x, int a, int b){
for (int i = x; i < int(f.size()); i |= i + 1){
f[i].c0 += b;
f[i].c1 += a;
}
}
void update(int l, int r, int a, int b){
update(l, a, b);
update(r, -a, -b);
}
long long get(int pos, int x){
long long res = 0;
for (int i = x; i >= 0; i = (i & (i + 1)) - 1)
res += f[i].c0 + f[i].c1 * 1ll * pos;
return res;
}
int main() {
int k, x, m;
scanf("%d%d%d%d", &n, &k, &x, &m);
vector<seg> a(n);
forn(i, n) scanf("%d%d", &a[i].l, &a[i].r);
sort(a.begin(), a.end(), [&](const seg &a, const seg &b){
return a.l + a.r < b.l + b.r;
});
vector<int> pos;
forn(i, n){
pos.push_back(a[i].l);
pos.push_back(a[i].r - m);
}
sort(pos.begin(), pos.end());
pos.resize(unique(pos.begin(), pos.end()) - pos.begin());
int cds = pos.size();
vector<array<int, 4>> npos(n);
forn(i, n){
npos[i][0] = lower_bound(pos.begin(), pos.end(), a[i].l - m) - pos.begin();
npos[i][1] = lower_bound(pos.begin(), pos.end(), a[i].l) - pos.begin();
npos[i][2] = lower_bound(pos.begin(), pos.end(), a[i].r - m) - pos.begin();
npos[i][3] = lower_bound(pos.begin(), pos.end(), a[i].r) - pos.begin();
}
vector<long long> pr(n + 1);
forn(i, n) pr[i + 1] = pr[i] + x - (m + a[i].r - a[i].l);
auto upd = [&](int i){
if (a[i].r - a[i].l >= m){
update(npos[i][0], npos[i][1], 1, m - a[i].l);
update(npos[i][1], npos[i][2], 0, m);
update(npos[i][2], npos[i][3], -1, a[i].r);
}
else{
update(npos[i][0], npos[i][2], 1, m - a[i].l);
update(npos[i][2], npos[i][1], 0, a[i].r - a[i].l);
update(npos[i][1], npos[i][3], -1, a[i].r);
}
};
bst.resize(n, vector<long long>(n, -1));
vector<vector<int>> opt(n, vector<int>(n));
forn(r, n) for (int l = r; l >= 0; --l){
if (l == r) f.assign(cds, {0, 0});
upd(l);
int L = (l == r ? (l == 0 ? 0 : opt[l - 1][l - 1]) : opt[l][r - 1]);
int R = (l == r ? int(pos.size()) - 1 : opt[l + 1][r]);
for (int k = L; k <= R; ++k){
long long cur = pr[r + 1] - pr[l] + get(pos[k], k);
if (cur > bst[l][r]){
bst[l][r] = cur;
opt[l][r] = k;
}
}
}
dp_before.resize(n);
dp_cur.resize(n);
for (int i = 0; i < n; i++)
dp_before[i] = bst[0][i];
for (int i = 1; i < k; i++){
compute(0, n - 1, 0, n - 1);
dp_before = dp_cur;
}
printf("%lld\n", dp_before[n - 1]);
return 0;
}
imbalanceForces
k
In the editorial of $$$E$$$, it is mentioned that $$$c_{i,0}=\sum_{j=1}^{i}{a_j}$$$. Actually, it should be $$$c_{i,0}=\sum_{j=1}^{i+1}{a_j}$$$ (with $$$c_{0,0}=a_1$$$ and $$$c_{n,0}$$$ is not needed).
Reason:
When we say $$$b_i$$$ (at $$$k$$$) $$$=$$$ $$$b_{i-1}$$$ (at $$$k$$$) $$$+$$$ $$$b_{i-1}$$$ (at $$$k-1$$$), this is true only when $$$k>1$$$, because this will cause the last term in both $$$\sum_{j=1}^{j=i}{{i-j \choose k} \cdot a_j}$$$ and $$$\sum_{j=1}^{j=i}{{i-j \choose k-1} \cdot a_j}$$$ to be $$$0$$$ (as $$$0 \choose x$$$ is $$$0$$$ for positive $$$x$$$). However, this is not the case for the $$$2^{nd}$$$ summation when $$$k=1$$$. The last term will not be eliminated as $$${0 \choose 0}=1$$$.
Submission.
Fixed this issue, thank you!
The editorial might take a while to update, but hopefully it will show the new version soon.
SorrowForces
D1
I see applying Operation 2 $$$n$$$ or $$$n-1$$$ times from begin.
then, $$$k-(n-(n+k) ~\text{mod}~ 2)-1$$$ should be $$$k-(n-(n+k) ~\text{mod}~ 2)+1$$$ ?
Or, $$$k-n+1 + (n+k) \text{mod}~2$$$
I don't understand what is 'k — m' maximums, and I don't know what is k when m is the number of operations. Can anyone explain from me pls ??
$$$k$$$ is given in the statement. upd: $$$k$$$ is the total number of operations, $$$m$$$ is the number of operations of the first type (when we delete two minimum elements)
$$$(k-m)$$$ maximums is $$$(k-m)$$$ greatest elements of the array, i. e. $$$(k-m)$$$ last elements in sorted order.
I can't understand how he solved maximum sum. Can someone help me understand it?
The basic idea is that since you need to maximise the sum of the final array, you have to minimise the sum of the removed elements. So, first of all, we sort the array. Then we have to go through all the different combinations of selecting min and max elements. So, we will use a loop in which i will denote the number of starting elements (minimum elements) we will take (multiplied by two, since we have to delete two min elements at once) and k — i will be the number of elements from back (maximum elements). i = 0 means 0*2 = 0 elements from start and k -0 = k elements from end. i = 1 means 1*2 = 2 elements from start and k — 1 elements from end. .... i = k means k*2 elements from start and 0 elements from end.
In each iteration, we need to get the sums of taking i*2 elements from start and k — i elements from the end. To get this sum in O(1) time we will use prefix sum.
You can check my C++ code here https://codeforces.me/contest/1832/submission/205586590
we're from the same college :)
For problem F, quadrangle inequality properties also apply to array partition DP. So we can use Knuth's optimization for a second time on $$$dp$$$, which leads an $$$O(n^2)$$$ algorithm.
This is my submission: https://codeforces.me/contest/1832/submission/206185565.
Hi. can someone please tell me the error in this code which I used without prefix array
It runs correctly for 1st test case but tells that there is wrong answer on test 2
wrong answer 2459th numbers differ - expected: '8', found: '7'
I mean does it really check 2459th number. did the testers even count upto that thing. I doubt it. Link to My SubmissionI dont think that greede solution is correct. But it also O(n*k) and even it be correct, it gets TLE.
Hello guys, I am getting TLE in 1832E - Combinatorics Problem. I don't think I have made any logical errors, but I can't seem to understand why it's giving TLE. Please help :( -> 209759092
hey, you are using too many modulo operators in your add and mul. In spite of you having the right complexity, your constant factor is bad. Here is a fixed version of your code 209761902
Thank you so much man, I didn't know that modulo operation also affected complexity. Got to learn something new. Tysm :)
In Problem C,
Why should we use this?
n = unique(a.begin(), a.end())-a.begin(); int ans = n;
Why doesn't this pass some test cases?
int ans = unique(a.begin(), a.end())-a.begin();
The value of n must be changed appropriately since we are using it in the for loop later.
I like the awoo solutions.. He make the solutions like my friend explaining to me.. Thx man++.
can someone please explain how this test case in problem B maximum sum is giving o/p 46
6 2
15 22 12 10 13 11
please help my code
include <bits/stdc++.h>
using namespace std;
define ll long long
define all(x) x.begin(), x.end()
define pb push_back
define F first
define S second
const int M = 1e9 + 7;
define ll long long
define yes cout << "YES" << endl
define no cout << "NO" << endl
define n1 cout << -1 << endl
int main() { int t; cin >> t; while (t--) { ll int n; cin >> n; int k; cin >> k; vector< ll int> v; for (ll int i = 0; i < n; i++) { ll int x; cin >> x; v.push_back(x); }
}