02 Jan 2021
— Tags: brute_force
— URL
The formula to compute the slope given two points $(x_1, y_1)$ and
$(x_2, y_2)$ is:
\[m = \frac{y_2 - y_1}{x_2 - x_1}\]
The problem tells you that:
\[-1 \leq \frac{y_2 - y_1}{x_2 - x_1} \leq 1\]
Or equivalently:
\[| y_2 - y_1 | \leq x_2 - x_1\]
Try all pairs and check if such condition holds. Don’t forget to enforce an
order to ease implementation (sort points by $x$-coordinate).
Time complexity: $O(n^2)$
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(vector<ii> xy)
{
int n = (int)(xy).size(), ans = 0;
sort(begin(xy), end(xy));
for (int i = 0; i < n - 1; ++i)
{
for (int j = i + 1; j < n; ++j)
{
auto [xi, yi] = xy[i];
auto [xj, yj] = xy[j];
ans += (abs(yj - yi) <= (xj - xi));
}
}
return ans;
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int n;
cin >> n;
vector<ii> xy(n);
for (auto &[x, y] : xy)
cin >> x >> y;
cout << solve(xy) << endl;
return 0;
}
02 Jan 2021
— Tags: easy,implementation
— URL
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 d(char c) { return c - '0'; }
int s(string x) { return d(x[0]) + d(x[1]) + d(x[2]); }
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
string a, b;
cin >> a >> b;
int sa = s(a), sb = s(b);
cout << (sa >= sb ? sa : sb) << endl;
return 0;
}
02 Jan 2021
— Tags: modulo,math,observation
— URL
By the pigeonhole principle, note that if $R - L + 1 \geq 2019$, there must
be an $i$, $L \leq i \leq R$ such that $i \equiv 0 \mod 2019$. In such case,
the answer is $0$.
Otherwise, we may brutforce all ordered pairs $(i, j)$ in that range and keep
the minimum. Since the range has length at most $2019$, the number of
computations is order $O(10^6)$, enough for the time limit.
Time complexity: $O(2019^2)$
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 solve(int l, int r)
{
if (r - l + 1 >= 2019)
return 0;
int ans = 2019;
for (int i = l; i < r; ++i)
for (int j = i + 1; j <= r; ++j)
ans = min(ans, ((i % 2019) * (j % 2019)) % 2019);
return ans;
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int l, r;
cin >> l >> r;
cout << solve(l, r) << endl;
return 0;
}
02 Jan 2021
— Tags: modulo,observation,lcm
— URL
Imagine there exist a value $m$ such that it maximizes the contribution of
each term in the summation of $f$, meaning that $m \equiv a_i - 1 \mod a_i$
for all $i$.
If such a value exists, then $m + 1$ must be divisible by all $a_i$. We know
an number with such properties exists, as the lcm of all $a_i$ behaves as an
$m + 1$. Therefore, the answer is:
\[\sum_{i = 1}^n a_i - 1\]
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(vi a) { return accumulate(begin(a), end(a), 0LL) - (int)(a).size(); }
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;
}
02 Jan 2021
— Tags: implementation
— URL
First of all, if $n$ is even then it is impossible to decompose it
into subsegments of odd sizes.
Otherwise if $n$ is odd then there must be necessarily a subsegment
containing the first element and a subsegment containing the last element,
otherwise it is not possible. If true, we can take the entire array as a
valid subsegment.
Time complexity: $O(1)$
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 n = (int)(a).size();
if ((a[0] % 2 != 1) or (a.back() % 2 != 1))
return false;
return n % 2;
}
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) ? "Yes" : "No") << endl;
return 0;
}
31 Dec 2020
— Tags: math,implementation
— URL
Let’s say that after some number of operations, all numbers become $x$. Note
that $x$ has to be $\min(a_1, a_2,… a_n)$, because it would be suboptimal
otherwise.
So, if all numbers can reach $x$ by decrementing by $k$, then it should be
possible.
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(vi a, int k)
{
int mv = *min_element(begin(a), end(a));
ll ans = 0;
for (auto x : a)
{
if ((x - mv) % k)
return -1;
ans += (x - mv) / k;
}
return ans;
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int n, k;
cin >> n >> k;
vi a(n);
for (auto &x : a)
cin >> x;
cout << solve(a, k) << endl;
return 0;
}
31 Dec 2020
— Tags: math,modulo
— URL
So, we must pair numbers with remainder $x$ with those with remainder $5-x$,
$\mod 5$. Since I’m lazy I just precomputed such counts in $O(\max(n, m))$.
Time complexity: $O(1)$
Memory complexity: $O(\max(n, m))$
Click to show code.
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
ll solve(int n, int m)
{
vi nrem(5, 0), mrem(5, 0);
for (int i = 1; i <= max(n, m); ++i)
{
int rem = i % 5;
if (i <= n)
nrem[rem]++;
if (i <= m)
mrem[rem]++;
}
ll ans = 0;
for (int i = 0; i < 5; ++i)
ans += ll(nrem[i]) * ll(mrem[(5 - i) % 5]);
return ans;
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int n, m;
cin >> n >> m;
cout << solve(n, m) << endl;
return 0;
}
30 Dec 2020
— Tags: math,bitmask
— URL
Editorial is pretty cool.
Time complexity: $O(n \log{x_{max}})$
Memory complexity: $O(n)$
Click to show code.
using namespace std;
using namespace atcoder;
using ll = long long;
using vi = vector<int>;
using mint = modint1000000007;
int const BITSZ = 60;
int solve(vector<ll> a)
{
int n = (int)(a).size();
vi cnt(BITSZ, 0);
mint ans;
for (int i = 0; i < n; ++i)
for (int j = 0; j < BITSZ; ++j)
cnt[j] += (a[i] >> j) & 1;
for (int j = 0; j < n; ++j)
{
mint sum_or = 0, sum_and = 0;
for (int b = 0; b < BITSZ; ++b)
{
if ((a[j] >> b) & 1)
{
sum_or += mint(1LL << b) * n;
sum_and += mint(1LL << b) * cnt[b];
}
else
sum_or += mint(1LL << b) * cnt[b];
}
ans += sum_or * sum_and;
}
return ans.val();
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
vector<ll> a(n);
for (auto &x : a)
cin >> x;
cout << solve(a) << endl;
}
return 0;
}
30 Dec 2020
— Tags: greedy,trees
— URL
Let’s say we have $k$ colors to paint the tree. Note that it is always
optimal that there’s only one connected component for each color painted.
Painting a tree with $k$ colors with the above strategy means that some of
the vertices will be shared by several colored subgraphs, i.e, that $w_i$
(let’s say node $i$ is shared $y$ times) will be counted $y$ times in the
answer.
This suggest a greedy stretegy where we pick those nodes with highest $w$ to
be the intersections of our colored subgraphs, ie, those that will be counted
repeatedly.
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 pll = pair<ll, ll>;
using vi = vector<int>;
vector<ll> solve(vector<vi> &g, vector<ll> &w)
{
int n = (int)(g).size();
vector<ll> sorted, ps;
for (int u = 0; u < n; ++u)
for (int i = 0, m = (int)(g[u]).size() - 1; i < m; ++i)
sorted.push_back(w[u]);
sort(begin(sorted), end(sorted), greater<ll>());
partial_sum(begin(sorted), end(sorted), back_inserter(ps));
ll sum = accumulate(begin(w), end(w), 0LL);
vector<ll> ans(n - 1, sum);
for (int k = 2; k <= n - 1; ++k)
ans[k - 1] += ps[k - 2];
return ans;
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
vector<ll> w(n);
for (auto &x : w)
cin >> x;
vector<vi> 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);
}
auto ans = solve(g, w);
for (auto x : ans)
cout << x << " ";
cout << endl;
}
return 0;
}
30 Dec 2020
— Tags: greedy
— URL
Note that you only have to worry about substrings of the form: xx or xyx.
Strategy: if element in in a substring of one of the previous form, change it
so that it doesn’t (don’t forget to check that it won’t form another
palindrome).
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(string s)
{
int n = (int)(s).size(), ans = 0;
s += "{{";
vector<vector<bool>> prohibited(n + 2, vector<bool>(27, false));
for (int i = 0; i < n; ++i)
{
if (prohibited[i][s[i] - 'a'])
{
for (int ch = 0; ch < 26; ++ch)
{
if (!prohibited[i][ch] and s[i + 1] != (ch + 'a') and
s[i + 2] != (ch + 'a'))
{
s[i] = ch + 'a';
break;
}
}
ans++;
}
prohibited[i + 1][s[i] - 'a'] = prohibited[i + 2][s[i] - 'a'] = true;
}
return ans;
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int t;
cin >> t;
while (t--)
{
string s;
cin >> s;
cout << solve(s) << endl;
}
return 0;
}