10 Jan 2021
— Tags: graphs,dp,dfs
— URL
Given the $X_i < Y_i$ constraint, we know this is a DAG.
For each node, $u$, with neighbor set $N(u)$, we’ll compute the following two
values:
sell[u] = max(a[u], {sell[v] | v <- N(u)})
ans[u] = max({-a[u] + sell[v] | v <- N(u)})
Where sell[u] denotes the best price to sell for all nodes reachable by $u$
and itself and ans[u] is the best return value if we buy at node $u$ and
sell at some node reachable by $u$.
The final answer is the maximum of $ans$ over all nodes.
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 vll = vector<ll>;
using Graph = vector<vi>;
struct DFS
{
Graph &g;
vll & a, &ans, &sell;
vector<bool> vis;
DFS(Graph &g, vll &a, vll &ans, vll &sell)
: g(g), a(a), ans(ans), sell(sell), vis((int)(g).size(), 0){};
void traverse(int u)
{
vis[u] = true;
for (auto v : g[u])
{
if (!vis[v])
traverse(v);
sell[u] = max(sell[u], sell[v]);
ans[u] = max(ans[u], -a[u] + sell[v]);
}
}
void operator()(int u) { traverse(u); }
};
ll solve(Graph g, vll a)
{
const ll INF = 1e17;
int n = (int)(g).size();
vll ans(n, -INF), sell(a);
DFS dfs(g, a, ans, sell);
for (int u = 0; u < n; ++u)
if (not dfs.vis[u])
dfs(u);
return *max_element(begin(ans), end(ans));
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int n, m;
cin >> n >> m;
vll a(n);
for (auto &ai : a)
cin >> ai;
Graph g(n);
for (int i = 0; i < m; ++i)
{
int u, v;
cin >> u >> v, u--, v--;
g[u].push_back(v);
}
cout << solve(g, a) << endl;
return 0;
}
10 Jan 2021
— Tags: greedy,sweep_line
— URL
Greedily pay for Snuke Prime or not if the accumulated cost of the interval
exceeds the price of a subscription.
To ease implementation, for each interval [l, r], you can merge all l’s
with the same value and all r’s with the same value. Then apply standard
sweep line to compute the answer.
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, ll>;
using vi = vector<int>;
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int n;
ll C;
cin >> n >> C;
vector<iii> events;
map<int, ll> A, B;
for (int i = 0; i < n; ++i)
{
int a, b, c;
cin >> a >> b >> c;
A[a] += c;
B[b] += c;
}
for (auto [k, v] : A)
events.emplace_back(k, -1, v);
for (auto [k, v] : B)
events.emplace_back(k, +1, v);
sort(begin(events), end(events));
ll unit_cost = 0, paying_cost = 0, ans = 0;
int ct = 0;
for (auto [t, sign, c] : events)
{
sign *= -1;
if (sign == +1)
ans += (t - ct) * paying_cost;
else
ans += (t - ct + 1) * paying_cost;
unit_cost += sign * c;
paying_cost = (unit_cost > C ? C : unit_cost);
ct = (sign == 1 ? t : t + 1);
}
cout << ans << endl;
return 0;
}
10 Jan 2021
— Tags: implementation,observation,greedy
— URL
The two finalist will be the ones that have maximum rating in both halves of
the tournament.
Time complexity: $O(2^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;
n = (1LL << n);
ii ansl = {0, 0}, ansr = {0, 0};
for (int i = 0; i < n / 2; ++i)
{
int ai;
cin >> ai;
ansl = max(ansl, {ai, i});
}
for (int i = n / 2; i < n; ++i)
{
int ai;
cin >> ai;
ansr = max(ansr, {ai, i});
}
ii ans = min(ansl, ansr);
cout << ans.second + 1 << endl;
return 0;
}
10 Jan 2021
— Tags: implementation,easy
— URL
Straightforward implementation of dot product.
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<ll>;
bool solve(vi a, vi b)
{
vi ans(a.size());
transform(begin(a), end(a), begin(b), begin(ans), multiplies<ll>());
return accumulate(begin(ans), end(ans), 0LL) == 0;
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int n;
cin >> n;
vi a(n), b(n);
for (auto &ai : a)
cin >> ai;
for (auto &bi : b)
cin >> bi;
cout << (solve(a, b) ? "Yes" : "No") << endl;
return 0;
}
10 Jan 2021
— Tags: easy
— URL
\[|x - y| < 3\]
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 x, y;
cin >> x >> y;
string ans[2] = {"No", "Yes"};
cout << (abs(x - y) < 3 ? "Yes" : "No") << endl;
return 0;
}
10 Jan 2021
— Tags: observation,implementation,greedy
— URL
Editorial is pretty nice.
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 x)
{
if (all_of(begin(a), end(a), [x](int ai) { return ai == x; }))
return 0;
if (accumulate(begin(a), end(a), 0LL) - (int)(a).size() * x == 0 or find(begin(a), end(a), x) != a.end())
return 1;
return 2;
}
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;
}
10 Jan 2021
— Tags: greedy,implementation
— URL
Fix blocks of consecutive characters greedily.
Editorial.
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>;
char mex(string alpha, vector<char> prohibited)
{
for (auto c : alpha)
if (find(begin(prohibited), end(prohibited), c) == prohibited.end())
return c;
return 0;
}
int solve(string &s)
{
int i = 0, n = (int)(s).size(), ans = 0;
s += " ";
while (i < n)
{
int j = i + 1;
while (j < n and s[i] == s[j])
++j;
if (j - i > 1)
{
for (int k = i + 1; k < j - 1; k += 2)
s[k] = mex("RGB", {s[i]}), ans++;
if ((j - i) % 2 == 0)
s[j - 1] = mex("RGB", {s[i], s[j]}), ans++;
}
i = j;
}
s.pop_back();
return ans;
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int n;
string s;
cin >> n >> s;
cout << solve(s) << endl;
cout << s << endl;
return 0;
}
08 Jan 2021
— Tags: divisibility,factors,number_theory,implementation
— URL
Get factors up to $\sqrt{n}$ (with their co-factors) and print them.
Time complexity: $O(\sqrt{n} \log{\sqrt{n}})$
Memory complexity: $O(2 \sqrt{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);
ll n;
cin >> n;
set<ll> factors;
for (ll x = 1, sq = sqrt(n); x <= sq; ++x)
{
if (n % x == 0)
{
factors.insert(x);
factors.insert(n / x);
}
}
for (auto x : factors)
cout << x << endl;
return 0;
}
08 Jan 2021
— Tags: implementation
— URL
Implementation.
Time complexity: $O(n)$
Memory complexity: $O(n)$
Click to show code.
using namespace std;
using ll = long long;
using vi = vector<int>;
tuple<ll, double, ll> solve(vi x)
{
vector<ll> ans(3, 0);
for (auto xi : x)
{
ans[0] += abs(xi);
ans[1] += ll(xi) * xi;
ans[2] = max(ans[2], ll(abs(xi)));
}
return {ans[0], sqrt(ans[1]), ans[2]};
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int n;
cin >> n;
vi x(n);
for (auto &xi : x)
cin >> xi;
auto [ans0, ans1, ans2] = solve(x);
cout << ans0 << endl;
cout << setprecision(12) << fixed << ans1 << endl;
cout << ans2 << endl;
return 0;
}
08 Jan 2021
— Tags: math,implementation
— URL
Test for $a_i \leq \frac{10^{18}}{\text{ans}}$.
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>;
ll solve(vector<ll> a)
{
if (auto it = find(begin(a), end(a), 0LL); it != a.end())
return 0LL;
ll ans = 1, maxv = 1e18;
for (auto ai : a)
{
if (ai <= maxv / ans)
ans *= ai;
else
return -1;
}
return ans;
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int n;
cin >> n;
vector<ll> a(n);
for (auto &ai : a)
cin >> ai;
cout << solve(a) << endl;
return 0;
}