15 Jan 2021
— Tags: greedy
— URL
This is a slight modification of the classical greedy interval scheduling.
Sort intervals, $l, r$, based on their maximum ending time, $r$.
We can greedily pick the $ith$ interval’s position by the first $j \geq l$
that is free.
Time complexity: $O(n \log{n})$
Memory complexity: $O(n)$
Click to show code.
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using vi = vector<int>;
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int n;
cin >> n;
vector<iii> a(n);
int maxr = 0, i = 0;
for (auto &[r, l, ix] : a)
{
cin >> l >> r;
ix = i++;
maxr = max(maxr, r);
}
sort(begin(a), end(a));
vi used(maxr + 1, 0), ans(n);
for (auto [r, l, i] : a)
{
while (used[l])
l++;
ans[i] = l;
used[l] = true;
}
for (auto x : ans)
cout << x << " ";
cout << endl;
return 0;
}
14 Jan 2021
— Tags: segment_tree,data_structures
— URL
For a given query $(l, r)$, we are dividing the string into three parts:
- left: $(1, l - 1)$
- mid: $(l, r)$
- right: $(r + 1, n)$
Note that removing mid will essentially decrease right by the net change in
mid.
Furthermore, note that for any range $l, r$, we may know the number of unique
elements in that range by finding the maximum and minimum on that range
(since every movement either increases or decreases by 1).
This suggests a data structure problem we can solve using segment tree.
For each range, store the maximum, minimum and the net change and query the
three ranges described beforehand.
Reverse the net change of the mid range to the right range (by subtracting it
from right’s min and max).
Finally, merge the left range with the right range if they overlap, otherwise
count them separately. If they don’t contain $0$ increase the answer by $1$.
Time complexity: $O(m \log{n})$
Memory complexity: $O(n)$
Click to show code.
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
using pll = pair<ll, ll>;
ll const INF = 1e15;
struct S
{
ll mn, mx, delta;
};
S op(S a, S b) { return {min(a.mn, b.mn), max(a.mx, b.mx), a.delta + b.delta}; }
S e() { return {INF, -INF, 0}; };
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int t;
cin >> t;
while (t--)
{
int n, m;
cin >> n >> m;
string s;
cin >> s;
using SegmentTree = atcoder::segtree<S, op, e>;
vector<S> a(n);
int cur = 0, delta;
for (int i = 0; i < n; ++i)
{
delta = (s[i] == '+' ? +1 : -1);
cur += delta;
a[i] = {cur, cur, delta};
}
SegmentTree st(a);
auto intersect = [](pll a, pll b) {
if (a.first > b.first)
swap(a, b);
return a.second >= b.first;
};
while (m--)
{
int l, r;
cin >> l >> r, l--;
S left = st.prod(0, l), mid = st.prod(l, r), right = st.prod(r, n);
vector<pll> intervals;
if (left.mn != INF)
intervals.emplace_back(left.mn, left.mx);
if (right.mn != INF)
intervals.emplace_back(right.mn - mid.delta,
right.mx - mid.delta);
ll ans = 0;
if (none_of(begin(intervals), end(intervals),
[](ii lr) { return lr.first <= 0 and 0 <= lr.second; }))
ans += 1;
if (intervals.size() == 2 and intersect(intervals[0], intervals[1]))
{
intervals[0] = {min(intervals[0].first, intervals[1].first),
max(intervals[0].second, intervals[1].second)};
intervals.pop_back();
}
for (auto [ll, rr] : intervals)
ans += rr - ll + 1;
cout << ans << endl;
}
}
return 0;
}
14 Jan 2021
— Tags: constructive
— URL
This comment
explained it well.
Time complexity: $O(n)$
Memory complexity: $O(1)$
Click to show code.
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int t;
cin >> t;
while (t--)
{
int n, k;
cin >> n >> k;
for (int i = 1; i <= 2 * k - n - 1; ++i)
cout << i << " ";
for (int i = k; i >= 2 * k - n; --i)
cout << i << " ";
}
return 0;
}
14 Jan 2021
— Tags: implementation
— URL
Note that our lcm string, has to have size $lcm(a, b)$. Let’s just extend
both $a$ and $b$ so that they have that size and then compare them.
Time complexity: $O(n)$
Memory complexity: $O(n)$
Click to show code.
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int t;
cin >> t;
while (t--)
{
string a, b;
cin >> a >> b;
int n = a.size(), m = b.size(), l = lcm(n, m);
a.resize(l), b.resize(l);
for (int i = n; i < l; ++i)
a[i] = a[i % n];
for (int i = m; i < l; ++i)
b[i] = b[i % m];
cout << (a == b ? a : "-1") << endl;
}
return 0;
}
14 Jan 2021
— Tags: greedy
— URL
If all elements are less than $d$, then no change is need to be made. Assume
otherwise.
Note that the optimal strategy is to pick the two smallest values as $a_j$
and $a_k$ and replace every $a_i > a_j + a_k$ with their sum. Iff $a_j + a_k
\leq d$ then it is possible.
Time complexity: $O(n \log{n})$
Memory complexity: $O(n)$
Click to show code.
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
bool solve(vi a, int d)
{
sort(begin(a), end(a));
if (a.back() <= d)
return true;
if (a.size() > 1 and a[0] + a[1] <= d)
return true;
return false;
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int t;
cin >> t;
while (t--)
{
int n, d;
cin >> n >> d;
vi a(n);
for (auto &ai : a)
cin >> ai;
cout << (solve(a, d) ? "YES" : "NO") << endl;
}
return 0;
}
13 Jan 2021
— Tags: greedy,implementation
— URL
For each block of consecutive zeros (with one on both ends) of size $m$,
one can place $ceil(\frac{m - 2k}{k + 1})$ ones.
Time complexity: $O(n)$
Memory complexity: $O(n)$
Click to show code.
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int ceil(int a, int b) { return (a + b - 1) / b; }
int solve(string s, int k)
{
s = "1" + string(k, '0') + s + string(k, '0') + "1";
int cnt = 0;
vi lengths;
for (auto c : s)
{
if (c == '0')
++cnt;
else
{
lengths.push_back(max(cnt - 2 * k, 0));
cnt = 0;
}
}
return accumulate(begin(lengths), end(lengths), 0LL, [k](int acc, int x) {
return acc + ceil(x, k + 1);
});
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int t;
cin >> t;
while (t--)
{
int n, k;
string s;
cin >> n >> k >> s;
cout << solve(s, k) << endl;
}
return 0;
}
12 Jan 2021
— Tags: greedy,bitmasks,math
— URL
To maximize each term of the summation, we should try to make large numbers
as large as possible (to maximize the contribution of each $a_i^2$).
Note that each operation effectively transfers all $1$’s from a number $a_i$
to another number $a_j$ (in binary).
We can think of a greedy strategy where we redistribute the $1$’s and
concentrate them in a few numbers in order to make them larger.
Time complexity: $O(n \log{a_{max}})$
Memory complexity: $O(n)$
Click to show code.
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
ll solve(vi a)
{
int const BSZ = 20;
vi cnt(BSZ, 0);
for (auto ai : a)
for (int i = 0; i < BSZ; ++i)
cnt[i] += (ai >> i) & 1;
vector<ll> ans(a.size(), 0);
for (auto &ai : ans)
{
for (int i = 0; i < BSZ; ++i)
{
if (cnt[i])
{
ai |= (1 << i);
cnt[i]--;
}
}
}
transform(begin(ans), end(ans), begin(ans), [](ll x) { return x * x; });
return accumulate(begin(ans), end(ans), 0LL);
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int n;
cin >> n;
vi a(n);
for (auto &ai : a)
cin >> ai;
cout << solve(a) << endl;
return 0;
}
12 Jan 2021
— Tags: constructive
— URL
Editorial.
Time complexity: $O(n)$
Memory complexity: $O(1)$
Click to show code.
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int n;
cin >> n;
vector<ii> points = {{1, 0}, {0, 1}, {1, 1}};
cout << (n + 1) * 3 + 1 << endl;
cout << 0 << " " << 0 << endl;
for (int i = 0; i <= n; ++i)
for (auto &[x, y] : points)
cout << x++ << " " << y++ << endl;
return 0;
}
11 Jan 2021
— Tags: greedy,dfs,dp,implementation,sorting,trees
— URL
Let cnt(u, v), be the number of paths that cross edge $(u, v)$. The idea is
to assign the largest primes to the edges with largest cnt.
Implementation details are described in
Editorial. But the key idea is
that if $m < n - 1$, we fill the remaining with $1$s and otherwise we merge
the biggest primes into one.
Time complexity: $O(n \log{n})$
Memory complexity: $O(n)$
Click to show code.
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
using Graph = vector<vi>;
struct DFS
{
const Graph &g;
function<void(int)> fu0, fu1;
function<void(int, int)> fuv0, fuv1;
DFS(const Graph &g) : g(g) { reset(); }
void traverse(int u, int p = -1)
{
fu0(u);
for (auto v : g[u])
{
if (v == p)
continue;
fuv0(u, v);
traverse(v, u);
fuv1(u, v);
}
fu1(u);
}
void operator()(int u, int p = -1) { traverse(u, p); }
void reset()
{
fu0 = fu1 = [](int u) { (void)u; };
fuv0 = fuv1 = [](int u, int v) { (void)u, (void)v; };
}
};
vector<ll> get_edge_counts(const Graph &g)
{
int n = (int)(g).size();
vector<ll> ans(n, 0), sz(n, 1);
DFS dfs(g);
dfs.fuv1 = [&sz](int u, int v) { sz[u] += sz[v]; };
dfs.fu1 = [&sz, &ans, n](int u) { ans[u] = (n - sz[u]) * sz[u]; };
dfs(0);
return ans;
}
int solve(const Graph &g, vector<ll> p)
{
using mint = atcoder::modint1000000007;
int n = g.size(), m = p.size();
auto cnt = get_edge_counts(g);
swap(cnt.front(), cnt.back()), cnt.pop_back();
sort(begin(cnt), end(cnt), greater<ll>());
sort(begin(p), end(p), greater<ll>());
if (m <= n - 1)
p.resize(n - 1, 1);
else
{
auto end = begin(p) + m - n + 1;
p[m - n + 1] *=
accumulate(begin(p), end, mint(1), multiplies<mint>()).val();
p.erase(begin(p), end);
}
mint ans = 0;
for (int i = 0; i < n - 1; ++i)
ans += mint(p[i]) * cnt[i];
return ans.val();
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
Graph g(n);
for (int i = 0; i < n - 1; ++i)
{
int u, v;
cin >> u >> v, u--, v--;
g[u].push_back(v);
g[v].push_back(u);
}
int m;
cin >> m;
vector<ll> p(m);
for (auto &pi : p)
cin >> pi;
cout << solve(g, p) << endl;
}
return 0;
}
11 Jan 2021
— Tags: greedy,dfs,trees
— URL
Editorial.
Time complexity: $O(n + m)$
Memory complexity: $O(n + m)$
Click to show code.
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
using Graph = vector<vector<ii>>;
pair<ll, ll> solve(Graph g)
{
int n = g.size();
vector<ll> sz(n, 1), dp1(n, 0), dp2(n, 0);
function<void(int, int)> dfs;
dfs = [&](int u, int p) {
for (auto [v, w] : g[u])
{
if (v == p)
continue;
dfs(v, u);
sz[u] += sz[v];
dp1[u] += dp1[v] + (sz[v] & 1 ? w : 0);
dp2[v] = min(sz[v], n - sz[v]) * w;
}
};
dfs(0, 0);
return {dp1[0], accumulate(begin(dp2), end(dp2), 0LL)};
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int t;
cin >> t;
while (t--)
{
int k;
cin >> k;
Graph g(2 * k);
for (int i = 0; i < 2 * k - 1; ++i)
{
int u, v, w;
cin >> u >> v >> w, u--, v--;
g[u].emplace_back(v, w);
g[v].emplace_back(u, w);
}
auto [G, B] = solve(g);
cout << G << " " << B << endl;
}
return 0;
}