Идея: BledDest
Разбор
Tutorial is loading...
Решение (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (auto& x : a) cin >> x;
sort(a.begin(), a.end(), greater<int>());
int sum = 0;
for (auto& x : a) {
if (sum + x <= k) sum += x;
else break;
}
cout << k - sum << '\n';
}
}
2042B - Игра с цветными шариками
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
scanf("%d", &t);
for(int _ = 0; _ < t; _++)
{
int n;
scanf("%d", &n);
vector<int> c(n);
for(int i = 0; i < n; i++)
{
scanf("%d", &c[i]);
--c[i];
}
vector<int> cnt(n);
for(auto x : c) cnt[x]++;
int exactly1 = 0, morethan1 = 0;
for(auto x : cnt)
if (x == 1)
exactly1++;
else if(x > 1)
morethan1++;
printf("%d\n", morethan1 + (exactly1 + 1) / 2 * 2);
}
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n, k;
string s;
cin >> n >> k >> s;
vector<int> vals;
int sum = 0;
for (int i = n - 1; i > 0; --i) {
sum += (s[i] == '1' ? 1 : -1);
if (sum > 0) vals.push_back(sum);
}
sort(vals.begin(), vals.end());
int ans = 1;
while (k > 0 && !vals.empty()) {
k -= vals.back();
vals.pop_back();
++ans;
}
cout << (k > 0 ? -1 : ans) << '\n';
}
}
Идея: adedalic
Разбор
Tutorial is loading...
Решение (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())
struct Seg {
int l, r;
bool operator< (const Seg &oth) const {
if (l != oth.l)
return l < oth.l;
return r < oth.r;
};
};
void solve() {
int n;
cin >> n;
vector<Seg> seg(n);
for (int i = 0; i < n; i++)
cin >> seg[i].l >> seg[i].r;
vector<int> ans(n, 0);
for (int k = 0; k < 2; k++) {
vector<int> ord(n);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&seg](int i, int j){
if (seg[i].l != seg[j].l)
return seg[i].l < seg[j].l;
return seg[i].r > seg[j].r;
});
set<int> bounds;
for (int i : ord) {
auto it = bounds.lower_bound(seg[i].r);
if (it != bounds.end())
ans[i] += *it - seg[i].r;
bounds.insert(seg[i].r);
}
for (auto &s : seg) {
s.l = -s.l;
s.r = -s.r;
swap(s.l, s.r);
}
}
map<Seg, int> cnt;
for (auto s: seg)
cnt[s]++;
for (int i = 0; i < n; i++)
if (cnt[seg[i]] > 1)
ans[i] = 0;
for (int a : ans)
cout << a << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int t; cin >> t;
while (t--)
solve();
return 0;
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
vector<vector<int>> g;
struct LCA {
vector<vector<pair<int, int>>> st;
vector<int> pw;
void build(vector<pair<int, int>> a) {
int n = a.size();
int lg = 32 - __builtin_clz(n);
st.resize(lg, vector<pair<int, int>>(n));
st[0] = a;
for (int j = 1; j < lg; ++j) {
for (int i = 0; i < n; ++i) {
st[j][i] = st[j - 1][i];
if (i + (1 << (j - 1)) < n)
st[j][i] = min(st[j][i], st[j - 1][i + (1 << (j - 1))]);
}
}
pw.resize(n + 1);
for (int i = 2; i <= n; ++i)
pw[i] = pw[i / 2] + 1;
}
vector<int> d, fst, par;
vector<pair<int, int>> ord;
int lca(int v, int u) {
int l = fst[v], r = fst[u];
if (l > r) swap(l, r);
++r;
int len = pw[r - l];
assert(len < int(st.size()));
return min(st[len][l], st[len][r - (1 << len)]).second;
}
void init(int v, int p = -1) {
if (fst[v] == -1) fst[v] = ord.size();
ord.push_back({ d[v], v });
for (int u : g[v]) if (u != p) {
par[u] = v;
d[u] = d[v] + 1;
init(u, v);
ord.push_back({ d[v], v });
}
}
LCA(int r = 0) {
int n = g.size();
d.resize(n);
fst.assign(n, -1);
par.assign(n, -1);
ord.clear();
init(r);
build(ord);
}
};
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int n;
cin >> n;
vector<int> a(2 * n);
forn(i, 2 * n){
cin >> a[i];
--a[i];
}
g.resize(2 * n);
forn(i, 2 * n - 1){
int v, u;
cin >> v >> u;
--v, --u;
g[v].push_back(u);
g[u].push_back(v);
}
vector<int> l(n, -1), r(n, -1);
forn(i, 2 * n){
if (l[a[i]] == -1) l[a[i]] = i;
else r[a[i]] = i;
}
vector<char> res(2 * n, 1);
forn(rt, 2 * n) if (a[rt] == 0){
LCA d(rt);
vector<int> state(2 * n, 0);
auto mark = [&](int v){
while (v != -1 && state[v] != 1){
state[v] = 1;
v = d.par[v];
}
};
auto markdel = [&](int v){
queue<int> q;
q.push(v);
state[v] = -1;
while (!q.empty()){
int v = q.front();
q.pop();
mark(l[a[v]] ^ r[a[v]] ^ v);
for (int u : g[v]) if (u != d.par[v] && state[u] == 0){
state[u] = -1;
q.push(u);
}
}
};
forn(i, n) mark(d.lca(l[i], r[i]));
for (int i = 2 * n - 1; i >= 0; --i) if (state[i] == 0)
markdel(i);
vector<char> cur(2 * n, 0);
for (int i = 0; i < 2 * n; ++i) if (state[i] == 1)
cur[i] = 1;
reverse(cur.begin(), cur.end());
res = min(res, cur);
}
reverse(res.begin(), res.end());
cout << count(res.begin(), res.end(), 1) << '\n';
forn(i, 2 * n) if (res[i])
cout << i + 1 << " ";
cout << '\n';
return 0;
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (Neon)
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); ++i)
const int N = 200 * 1000 + 13;
const int K = 5;
using li = long long;
using mat = array<array<li, K>, K>;
const li INF = 1e18;
int n, q;
li a[N], b[N];
mat t[4 * N];
mat init(li a, li b) {
mat c;
forn(i, K) forn(j, i + 1) c[j][i] = -INF;
c[0][0] = c[2][2] = c[4][4] = 0;
c[0][1] = c[2][3] = a + b;
c[0][2] = c[2][4] = a + b + b;
c[1][1] = c[3][3] = a;
c[1][2] = c[3][4] = a + b;
return c;
}
mat combine(mat a, mat b) {
mat c = init(-INF, -INF);
forn(i, K) forn(j, i + 1) forn(k, j + 1)
c[k][i] = max(c[k][i], a[k][j] + b[j][i]);
return c;
}
void build(int v, int l, int r) {
if (l + 1 == r) {
t[v] = init(a[l], b[l]);
return;
}
int m = (l + r) / 2;
build(v * 2 + 1, l, m);
build(v * 2 + 2, m, r);
t[v] = combine(t[v * 2 + 1], t[v * 2 + 2]);
}
void upd(int v, int l, int r, int p) {
if (l + 1 == r) {
t[v] = init(a[l], b[l]);
return;
}
int m = (l + r) / 2;
if (p < m) upd(v * 2 + 1, l, m, p);
else upd(v * 2 + 2, m, r, p);
t[v] = combine(t[v * 2 + 1], t[v * 2 + 2]);
}
mat get(int v, int l, int r, int L, int R) {
if (L >= R) return init(-INF, -INF);
if (l == L && r == R) return t[v];
int m = (l + r) / 2;
return combine(
get(v * 2 + 1, l, m, L, min(m, R)),
get(v * 2 + 2, m, r, max(m, L), R)
);
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> n;
forn(i, n) cin >> a[i];
forn(i, n) cin >> b[i];
build(0, 0, n);
cin >> q;
forn(_, q) {
int t, x, y;
cin >> t >> x >> y;
--x;
if (t == 1) {
a[x] = y;
upd(0, 0, n, x);
} else if (t == 2) {
b[x] = y;
upd(0, 0, n, x);
} else {
auto res = get(0, 0, n, x, y);
cout << res[0][4] << '\n';
}
}
}
did anybody solved problem C using greedy or binary search only if yes then please provide the code..
.
why is that you only search for those 2 solutions? are you scared of learning a new thing, and a new approach to problems? accept that some problems are weird and require unique solutions. this question cant be binary searched because m+1 does not always yield a better answer than m, and m does not always yield a better answer than m+1. also it cant be solved greedily as you have to consider all suffix differences. stop forcing algorithms just because you're lazy to learn more of them
Thanks for the reply, I coded a greedy solution for the problem but was unsure that i made all observations correctly , just wanted to make sure where i was lacking on greedy solution, but trust me even though I am not good at making mathematical observation yet I enjoy them a lot.. Since you are an expert can you please have a look at my profile and tell where I am going wrong ,I have solved over 400 problems but Still didnt made to pupil even though i am practising questions tougher than my level? I would be grateful to you!
Look at what this idiot did.
Instead of using set upper_bound and lower_bound functions, this guy wrote a whole specialized segment tree. https://codeforces.me/contest/2042/submission/294446705 And it PASSED with only a single penalty.
Guess this is what happens when you solve too many range query problems.
what's the issue, the segtree most likely does have smaller constants, it's not a totally unreasonable decision if you know I think (also idk who asked)
that is me. I am the idiot.
I wrote the segtree because I forgot that lower_bound and upper_bound exist.
Solved too many segtree problems on cses.
.
In problem C tutorial, shouldn't it be $$$0⋅s_{a_1}+(1-0)⋅s_{a_2}+(2-1)⋅s_{a_3}+⋯+s_{a_m}$$$ the resulting sum?
I'd like to add that..
notice you only pick indexes to start a new group where str[i]=='1' and that group can go from i to the end or you can fraction that group into small groups, but for every index you pick to start a new group, the resultant score (diff bob and alice from i to end) or s[i] is positive cuz even if you divide a group into small groups at index i, you will keep the score of s[i]. Example:
$$$n=9, k = 5$$$
011100101Array $$$s$$$ will be $$${_, 2, 1, 0, -1, 0, 1, 0, 1}$$$, but you are only interested on making groups at indexes where s[i] have positive values. Now you can make a group at index where $$$s[i] = 2$$$ cuz it's the greatest in $$$s$$$. so you make a group between $$$i-1$$$ and $$$i$$$ where $$$i = 1$$$ and we get two points of score, but even if you don't keep the last group you made $$$[i:n)$$$, you'll still keep those two points: now you have groups [0:0] and [1:9). As we still have values on $$$s$$$, let's take the next greatest. Now you have groups [0:0], [1:1], [2:9), cuz in group [2:9) you have +1 of score, and you are still keeping the previous +2 points, even if you divided the [1:9) group.
For problem C, can't we use a prefix array to achieve the same result? Let aj denotes where the jth segment ends.
Then, the sum can be expressed as: 0*pa1 + 1*(pa2 — pa1) + 2*(pa3 — pa2) + .... + (m-1)*(pam — pam-1)
Simplifying, this becomes: -(pa1 + pa2 + ... + pam-1) + (m-1)*pam However, I am unable to eliminate the last m in the equation above. Can someone help?
Waiting for alternative way of problem D solution (Not using trees... ordered set in C++ or SortedList in python).
Could someone explain the solution of problem C, or someone give a different approach to problem C
read the comment I wrote above
we can use suffix sums for the same. check out my solution for it
Copy of problem C: 1175D - Разделение массива
For Problem-C, you should use int64.
Problem E can be solved in $$$\Theta(n)$$$ without requiring an $$$O(1)$$$ LCA computation. Instead, we precompute two properties for each subtree: (1) whether it contains all $$$n$$$ distinct values, and (2) whether it contains duplicate values. Using these properties, we can decide whether to select a vertex directly in order.
To facilitate the precomputation, we use the DFS order to represent each subtree as a range and then translate the constraints for a subtree into constraints for its corresponding range. Both properties can be checked in $$$\Theta(n)$$$ using a simple two-pointer technique on the range.
294738728
i tried c using binary search, but couldn't figure out the mistake.. :(
https://shorturl.at/043Sb
For problem C, can't we use a prefix array to achieve the same result? Let aj denotes where the jth segment ends.
Then, the sum can be expressed as: 0*pa1 + 1*(pa2 — pa1) + 2*(pa3 — pa2) + .... + (m-1)*(pam — pam-1)
Simplifying, this becomes: -(pa1 + pa2 + ... + pam-1) + (m-1)*pam However, I am unable to eliminate the last m in the equation above. Can someone help?
For Problem D: What is the reason of the tle ?