08 Jan 2021
— Tags: greedy
— URL
Observations
- $x - y = x + abs(y)$, given $x \geq 0$ and $y \leq 0$.
- So, if we have a bag with a number, $x$, and other bags with negative
numbers, it’s the same as adding the absolute value of all numbers.
- Following this reasoning, we should find a way to separate a positive
number from the negative numbers in different bags.
- Given that all numbers are initially positive, we must force one to become
negative.
- Making $x$ negative, means doing $x - y$ given $x \leq y$. From our ideal
answer (observation 2.), we have a loss of $2x$. Meaning that if that
achieves our ideal state, then the answer is $\text{total sum} - 2x$.
- We ought to find a way to minimize this loss.
There are two cases that when considered achieve an optimal answer:
- Making an entire bag negative.
- Making the minimum of two bags negative.
There should be a lot of edge cases in the implementation, but it just
magically works, idk.
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>;
using vec2 = vector<vector<ll>>;
ll solve(vec2 a)
{
ll tot = 0;
vector<ll> sum(3, 0);
for (int i = 0; i < 3; ++i)
{
sort(begin(a[i]), end(a[i]), greater<ll>());
tot += sum[i] = accumulate(begin(a[i]), end(a[i]), 0LL);
}
ll ans = max({tot - 2 * a[0].back() - 2 * a[1].back(),
tot - 2 * a[0].back() - 2 * a[2].back(),
tot - 2 * a[1].back() - 2 * a[2].back()});
ans = max({ans, tot - 2 * sum[0], tot - 2 * sum[1], tot - 2 * sum[2]});
return ans;
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
vec2 a(3);
for (int i = 0; i < 3; ++i)
{
int n;
cin >> n;
a[i].resize(n);
}
for (auto &a_row : a)
for (auto &aij : a_row)
cin >> aij;
cout << solve(a) << endl;
return 0;
}
08 Jan 2021
— Tags: brute_force,implementation
— URL
Try all positions and keep the one that reduces hills/valleys the most.
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 solve(vi a)
{
int n = (int)(a).size();
auto is_hill = [n, &a](int i) {
return (i <= 0 or i >= n - 1) ? false
: a[i - 1] < a[i] and a[i] > a[i + 1];
};
auto is_valley = [n, &a](int i) {
return (i <= 0 or i >= n - 1) ? false
: a[i - 1] > a[i] and a[i] < a[i + 1];
};
auto is = [is_hill, is_valley](int i) {
return is_hill(i) or is_valley(i);
};
int ans = 0;
for (int i = 0; i < n; ++i)
ans += is(i);
int cnt = 0;
for (int i = 0; i < n; ++i)
{
int temp = a[i], cur = 0;
bool l = is(i - 1), m = is(i), r = is(i + 1);
if (i > 0)
{
a[i] = a[i - 1];
cur = max(cur, l - is(i - 1) + m - is(i) + r - is(i + 1));
}
if (i < n - 1)
{
a[i] = a[i + 1];
cur = max(cur, l - is(i - 1) + m - is(i) + r - is(i + 1));
}
a[i] = temp;
cnt = max(cnt, cur);
}
return ans - cnt;
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
vi a(n);
for (auto &ai : a)
cin >> ai;
cout << solve(a) << endl;
}
return 0;
}
07 Jan 2021
— Tags: greedy,segment_tree,data_structures
— URL
Some key observations are:
- $x$ always increases.
- Because of 1., after performing a swap on $a_i$, we will only be able
to swap $a_j$, such that $a_j > a_i$.
- Because of 2. (and the fact that we want to sort $A$), after performing a
swap on $a_i$, we will only be able to swap $a_j$, such that $j > i$.
Observation 2 and 3 suggests a greedy approach.
For a position $i$, assume the range $1,…i - 1$ is sorted. Let’s split into
cases:
- If $i…n$ is sorted, we finish.
- Otherwise, we have two cases::
- If $x < a_i$, we know that we have to swap, because otherwise we would
leave
a[i....n] unsorted.
- Otherwise, we can’t do anything.
- After considering these cases, it will only be possible to fix
a[i + 1...n] iff no element in a[i + 1, n] is less than $a_i$.
Editorial has other nice
solutions like a $O(n^2)$ dp or a $O(n)$ greedy (which is quite similar to
mine).
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>;
int op(int a, int b) { return min(a, b); }
int e() { return 0x7fffffff; }
int solve(vi a, int x)
{
using RMQ = atcoder::segtree<int, op, e>;
int n = (int)(a).size();
vector<bool> sorted_suffix(n, false);
int last = a[n - 1];
for (int i = n - 1; i >= 0; --i)
{
if (a[i] <= last)
sorted_suffix[i] = true;
else
break;
last = a[i];
}
RMQ rmq(a);
int ans = 0;
for (int i = 0; i < n; ++i)
{
if (sorted_suffix[i])
break;
else
{
if (x < a[i])
{
swap(a[i], x);
ans++;
}
if (rmq.prod(i + 1, n) < a[i])
return -1;
}
}
return ans;
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int t;
cin >> t;
while (t--)
{
int n, x;
cin >> n >> x;
vi a(n);
for (auto &ai : a)
cin >> ai;
cout << solve(a, x) << endl;
}
return 0;
}
07 Jan 2021
— Tags: two_pointers,greedy,segment_tree,implementation
— URL
Editorial.
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>;
int e() { return 0x7fffffff; }
int min(int a, int b) { return std::min(a, b); }
using RMQ = atcoder::segtree<int, min, e>;
vector<int> solve(vi a)
{
int n = (int)(a).size();
vi ans(n, 0), cnt(n, 0);
RMQ rmq(a);
for (auto ai : a)
cnt[ai]++;
ans[0] = all_of(begin(cnt), end(cnt), [](int x) { return x > 0; });
ans[n - 1] = cnt[0] > 0;
if (!ans[n - 1])
return ans;
int i = 0, l = 0, r = n - 1;
for (; i < n - 1; ++i)
{
if (a[l] == i)
l++;
else if (a[r] == i)
r--;
else
break;
if (rmq.prod(l, r + 1) != i + 1)
break;
}
for (int j = n - (i + 1); j < n - 1; ++j)
ans[j] = true;
return ans;
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
vi a(n);
for (auto &ai : a)
cin >> ai, ai--;
auto ans = solve(a);
for (auto x : ans)
cout << x;
cout << endl;
}
return 0;
}
07 Jan 2021
— Tags: binary_search,greedy
— URL
Given a number of desired cheap ice, $x$, pick the $x$ smallest numbers and
alternate them with the larges ones. Binary search to find $x$.
Editorial.
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>;
int bs(int l, int r, function<bool(int)> p)
{
while (l < r)
{
int m = l + (r - l + 1) / 2;
if (p(m))
l = m;
else
r = m - 1;
}
return l;
}
int solve(vi &a)
{
int n = (int)(a).size();
sort(begin(a), end(a));
auto ok = [&a, n](int x) {
for (int i = 0; i < x; i++)
{
int j = x - i - 1, l = n - i - 2, r = n - i - 1;
if (!(a[l] > a[j] and a[j] < a[r]))
return false;
}
return true;
};
int x = bs(0, (n - 1) / 2, ok);
if (x == 0)
return x;
int i = n - 1;
vi left(a.begin(), a.begin() + x), right(a.begin() + x, a.end());
while (left.size())
{
a[i--] = right.back();
right.pop_back();
a[i--] = left.back();
left.pop_back();
}
while (right.size())
{
a[i--] = right.back();
right.pop_back();
}
return x;
}
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;
for (auto ai : a)
cout << ai << " ";
cout << endl;
return 0;
}
05 Jan 2021
— Tags: easy
— URL
\[n - a + b\]
Time complexity: $O(1)$
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, a, b;
cin >> n >> a >> b;
cout << n - a + b << endl;
return 0;
}
05 Jan 2021
— Tags: dfs,graphs,greedy
— URL
Essentially, 2-coloring the graph with a dfs does the job.
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<int>>;
struct DFS
{
Graph & g;
vector<bool> vis;
vector<int> &color, &ans;
DFS(Graph &g, vector<int> &color, vector<int> &ans)
: g(g), vis((int)(g).size(), 0), color(color), ans(ans)
{
}
void traverse(int u)
{
vis[u] = true;
if (none_of(begin(g[u]), end(g[u]), [this](int v) { return vis[v] and color[v]; }))
{
color[u] = 1;
ans.push_back(u);
}
for (auto v : g[u])
if (not vis[v])
traverse(v);
}
void operator()(int u) { traverse(u); }
};
vi solve(Graph g)
{
int n = (int)(g).size();
vector<int> color(n, 0), ans;
color[0] = 1;
DFS dfs(g, color, ans);
dfs(0);
if (any_of(begin(dfs.vis), end(dfs.vis), [](bool vis) { return !vis; }))
return {};
return ans;
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int t;
cin >> t;
while (t--)
{
int n, m;
cin >> n >> m;
Graph g(n);
for (int i = 0; i < m; ++i)
{
int u, v;
cin >> u >> v, u--, v--;
g[u].push_back(v);
g[v].push_back(u);
}
if (auto ans = solve(g); ans.size() > 0)
{
cout << "YES" << endl;
cout << ans.size() << endl;
for (auto x : ans)
cout << x + 1 << " ";
cout << endl;
}
else
cout << "NO" << endl;
}
return 0;
}
05 Jan 2021
— Tags: number_theory,math
— URL
We can do some algebra using the fact that ab = lcm(a, b) * gcd(a, b) to
arrive at the conclusion that $a$ and $b$ are adjacent iff $ab$ is a perfect
power.
This suggests to match elements $a_i$ and $a_j$ such that multiplying their
prime decompositions results in a prime decomposition of even exponents
(=perfect power). Note that for a given prime decomposition of number $a_i$,
we only care about the factors that needs to be matched. Therefore, we can
discard the even exponents of each factor. We will end up with a number
$a_i’ \leq a_i$ that is the multiplication of the factors that need to be
matched.
Count the occurrences of each $a_i’$ in a map, call it cnt. Note that
cnt[ai'] denotes the number of elements that are adjacent to each other by
matching the primes denoted by the number ai'.
If $w=0$ we only need to take the maximum over all entries of cnt.
Otherwise, note that if cnt[ai'] is even, all such elements will be
replaced by a perfectly matched number (so they will become ai'= 1), and
if it is odd, then all such numbers will still need to be matched.
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>;
template <int SIZE>
struct Sieve
{
static_assert(0 <= SIZE and SIZE <= 1e8, "0 <= SIZE <= 1e8");
using byte = unsigned char;
std::bitset<SIZE> is_prime;
std::vector<int> primes;
Sieve()
{
is_prime.set();
is_prime[0] = is_prime[1] = 0;
for (int i = 4; i < SIZE; i += 2)
is_prime[i] = 0;
for (int i = 3; i * i < SIZE; i += 2)
if (is_prime[i])
for (int j = i * i; j < SIZE; j += i * 2)
is_prime[j] = 0;
for (int i = 2; i < SIZE; ++i)
if (is_prime[i])
primes.push_back(i);
}
};
int const AMAX = 1e4;
Sieve<AMAX> sieve;
int matchable_factors(int x)
{
int ans = 1;
for (ll p : sieve.primes)
{
if (p * p > x)
break;
while (x % (p * p) == 0)
x /= (p * p);
if (x % p == 0)
ans *= p, x /= p;
}
if (x > 1)
ans *= x;
return ans;
}
ii solve(vi a)
{
map<int, int> cnt;
for (auto ai : a)
cnt[matchable_factors(ai)]++;
int maxres[2] = {0, 0}, totalres[2] = {0, 0};
for (auto [x, c] : cnt)
{
if (x == 1)
continue;
bool parity = c & 1;
maxres[parity] = max(maxres[parity], c);
totalres[parity] += c;
}
return {max({cnt[1], maxres[0], maxres[1]}),
max(cnt[1] + totalres[0], maxres[1])};
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
vi a(n);
for (auto &ai : a)
cin >> ai;
auto [w0, wotherwise] = solve(a);
int q;
cin >> q;
while (q--)
{
ll w;
cin >> w;
if (w == 0)
cout << w0 << endl;
else
cout << wotherwise << endl;
}
}
return 0;
}
05 Jan 2021
— Tags: sorting,greedy
— URL
Assign people with higher default cost, $k_i$, to the presents with lower
cost.
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>;
ll solve(vi k, vi c)
{
sort(begin(k), end(k), greater<int>());
int cur = 0;
ll ans = 0;
for (auto &ki : k)
{
if (cur < ki)
ki = cur++;
ans += c[ki];
}
return ans;
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int t;
cin >> t;
while (t--)
{
int n, m;
cin >> n >> m;
vi k(n), c(m);
for (auto &ki : k)
cin >> ki, ki--;
for (auto &ci : c)
cin >> ci;
cout << solve(k, c) << endl;
}
return 0;
}
05 Jan 2021
— Tags: math,implementation
— URL
Disclaimer: I actually don’t know how to explain this well kskjsdkjs.
Let cnt[i] be the maximum number of times $x$ divides $a_i$.
Let minix be the first index such that:
\[minix = argmin_i(cnt_{i})\]
Note three things:
- First, that
cnt[i] tells us how many times the robot may perform its
operation on $a_i$ and the elements $a_i$ produce.
- Second, that the elements $a_i$ produce after an operation have a
contribution of $a_i$ to the sum.
- Third, that the operation will be performed to descendents of elements
$a_i$ until $a_{minix}$ is last expanded.
So, we’ll divide the array into those elements at the left of minix and
those at the right of it. We’ll observe that the elements at the left will be
expanded at most min(cnt[i], cnt[minix] + 1] times and those at the right
cnt[minix] times.
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>;
ll fit(ll ai, ll x)
{
ll ans = 0;
while (ai % x == 0)
{
ans++;
ai /= x;
}
return ans;
}
ll solve(vector<ll> a, ll x)
{
int n = (int)(a).size();
vector<ll> cnt(n, 0);
for (int i = 0; i < n; ++i)
cnt[i] = fit(a[i], x);
ll ans = accumulate(begin(a), end(a), 0LL);
int minix = distance(begin(cnt), min_element(begin(cnt), end(cnt)));
for (int i = 0; i < n; ++i)
{
if (i < minix)
cnt[i] = min(cnt[i], cnt[minix] + 1);
if (i > minix)
cnt[i] = cnt[minix];
ans += cnt[i] * a[i];
}
return ans;
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int t;
cin >> t;
while (t--)
{
int n;
ll x;
cin >> n >> x;
vector<ll> a(n);
for (auto &ai : a)
cin >> ai;
cout << solve(a, x) << endl;
}
return 0;
}