30 Dec 2020
— Tags: greedy
— URL
From start to end, increase element if it has already been encountered before
(remember elements are given in non-decreasing order). Then, count unique elements.
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();
vector<bool> vis(a.back() + 5, false);
for (int i = 0; i < n; ++i)
{
if (vis[a[i]])
a[i]++;
vis[a[i]] = true;
}
return distance(begin(a), unique(begin(a), end(a)));
}
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 &x : a)
cin >> x;
cout << solve(a) << endl;
}
return 0;
}
30 Dec 2020
— Tags: math,brute_force
— URL
In the formula $A = \frac{h_b b}{2}$, the only variable that changes is the
base length, $b$. List all pairs, of points on the x axis and count the
unique distances.
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(vi a)
{
int n = (int)(a).size(), ans = 0;
vector<bool> vis(100, 0);
for (int i = 0; i < n - 1; ++i)
{
for (int j = i + 1; j < n; ++j)
{
int b = abs(a[i] - a[j]);
if (vis[b])
continue;
vis[b] = true;
ans++;
}
}
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 &x : a)
cin >> x;
cout << solve(a) << endl;
}
return 0;
}
30 Dec 2020
— Tags: math,implementation
— URL
Without loss of generality, say $a \geq b$. We’ll try to make $b$ into $a$ by
multiplying it by $2$, $4$ and $8$.
Note that this is only possible if $a = b \times 2^k$, for some integer $k$.
We verify that, and then decompose $2^k$ into $8$s, $4$s and $2$s.
Time complexity: $O(\log{\max(a, b)})$
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(ll a, ll b)
{
if (a % b)
return -1;
ll twok = a / b;
int k = 0;
while (twok != 1)
{
if (twok % 2)
return -1;
twok /= 2;
k++;
}
int ans = 0;
ans += k / 3;
k %= 3;
ans += k / 2;
k %= 2;
ans += k / 1;
return ans;
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int t;
cin >> t;
while (t--)
{
ll a, b;
cin >> a >> b;
if (a < b)
swap(a, b);
cout << solve(a, b) << endl;
}
return 0;
}
29 Dec 2020
— Tags: graphs,constructive,implementation
— URL
Editorial.
Time complexity: $O(n^2)$
Memory complexity: $O(n^2)$
Click to show code.
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
pair<bool, vector<vi>> solve(int n, int a, int b)
{
if (min(a, b) != 1 or (a == b and (n == 2 or n == 3)))
return {false, {}};
vector<vi> ans(n, vi(n, 0));
bool rev = false;
if (a < b)
{
rev = true;
swap(a, b);
}
for (int i = 0; i < n - a; ++i)
ans[i][i + 1] = ans[i + 1][i] = 1;
if (rev)
{
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
if (i == j)
continue;
ans[i][j] = 1 - ans[i][j];
}
}
}
return {true, ans};
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int n, a, b;
cin >> n >> a >> b;
if (auto [flag, mat] = solve(n, a, b); flag)
{
cout << "YES" << endl;
for (auto row : mat)
{
for (auto x : row)
cout << x;
cout << endl;
}
}
else
cout << "NO" << endl;
return 0;
}
29 Dec 2020
— Tags: greedy,graphs,constructive
— URL
So, intuitively, we want edges to be uniformly distributed on the vertices,
as to minimize the maximum edges for each subgraph in the hope that it fits
the problem’s constraints.
One way to do so is to add edges in lexicographical order.
Time complexity: $O(n)$
Memory complexity: $O(1)$
Click to show code.
using namespace std;
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int t;
cin >> t;
while (t--)
{
int n, p, m;
cin >> n >> p;
m = 2 * n + p;
for (int u = 1; u < n; ++u)
{
for (int v = u + 1; v <= n; ++v)
{
if (!m)
break;
cout << u << " " << v << endl;
m--;
}
if (!m)
break;
}
}
return 0;
}
29 Dec 2020
— Tags: two_pointers,brute_force
— URL
We need to find a pair of indices [l, r] such that the sum of the book
times in this interval is less than $t$ and is maximal.
We may fix the left border, $l$, and use binary search or a two pointers
approach to find $r$.
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 t)
{
int n = (int)(a).size(), r = 0, ans = 0;
vi pa(n);
partial_sum(begin(a), end(a), begin(pa));
auto sum = [pa](int l, int r) { return pa[r] - (l == 0 ? 0 : pa[l - 1]); };
for (int l = 0; l < n; ++l)
{
while (r < n and sum(l, r) <= t)
++r;
ans = max(ans, r - l);
}
return ans;
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int n, t;
cin >> n >> t;
vi a(n);
for (auto &x : a)
cin >> x;
cout << solve(a, t) << endl;
return 0;
}
28 Dec 2020
— Tags: easy,summation
— URL
Reduce summation to closed form and solve the equation.
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 k, n, w;
cin >> k >> n >> w;
int x = max(k * (w * (w + 1)) / 2 - n, 0);
cout << x << endl;
return 0;
}
28 Dec 2020
— Tags: greedy,sorting
— URL
Intuitively, the position with highest ground level constraints its
neighbors. We build on top of this idea.
We’ll maintain a priority queue or set where each position is ordered based
on their ground level height, decreasingly.
The idea is that, we start from the highest ground level, update its
neighbors heights so that they minimally share a side with it, mark it as
done and continue with the next highest position. If at any step we can’t
perform an update on the neighbors (as it would exceed the $k - 1$
displacement from their ground level), then it’s impossible.
Since we’re updating from top to bottom and updating the neighbor’s height to
minimally share a side, we’ll never place a fence too far down (or if we do,
then it’s fixable. I’m lazy today, so I’ll skip the proof.).
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 h, int k)
{
int n = (int)(h).size();
set<ii, greater<ii>> hordered;
for (int i = 0; i < n; ++i)
hordered.emplace(h[i], i);
vector<bool> visited(n, false);
for (int j = 0; j < n; ++j)
{
auto cur = hordered.begin();
auto [hi, i] = *cur;
if (i - 1 >= 0 and not visited[i - 1])
{
int hmax = h[i - 1] + (i - 1 == 0 ? k - 1 : 2 * k - 2);
if (h[i] > hmax)
return false;
auto it = hordered.find(ii{h[i - 1], i - 1});
h[i - 1] = max(hi - k + 1, h[i - 1]);
hordered.erase(it);
hordered.emplace(h[i - 1], i - 1);
}
if (i + 1 < n and not visited[i + 1])
{
int hmax = h[i + 1] + (i + 1 == n - 1 ? k - 1 : 2 * k - 2);
if (h[i] > hmax)
return false;
auto it = hordered.find(ii{h[i + 1], i + 1});
h[i + 1] = max(h[i] - k + 1, h[i + 1]);
hordered.erase(it);
hordered.emplace(h[i + 1], i + 1);
}
visited[i] = true;
hordered.erase(cur);
}
return true;
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int t;
cin >> t;
while (t--)
{
int n, k;
cin >> n >> k;
vi h(n);
for (auto &x : h)
cin >> x;
cout << (solve(h, k) ? "YES" : "NO") << endl;
}
return 0;
}
28 Dec 2020
— Tags: greedy
— URL
$f(a)$ is maximized when $a$ is of the form:
a = r[0, i] . b[0, j] . r[i + 1, n] . b[j + 1, m]
Where . means concatenation and $i$ and $j$ are the indices that maximize
their respective prefix sums.
The reason behind is that the sum of a[0... i + j] = r[0, i] . b[0, j]
will be a consequently the maximal term of $f(a)$ for all $a$.
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 r, vi b)
{
int n = (int)(r).size(), m = (int)(b).size();
vi pr(n, 0), pb(m, 0);
partial_sum(begin(r), end(r), begin(pr));
partial_sum(begin(b), end(b), begin(pb));
return max(*max_element(begin(pr), end(pr)), 0) + max(*max_element(begin(pb), end(pb)), 0);
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int t;
cin >> t;
while (t--)
{
int n, m;
cin >> n;
vi r(n);
for (auto &x : r)
cin >> x;
cin >> m;
vi b(m);
for (auto &x : b)
cin >> x;
cout << solve(r, b) << endl;
}
return 0;
}
28 Dec 2020
— Tags: greedy,observation
— URL
There are two cases in which it is impossible to construct a valid sequence:
- The length of the sequence is odd.
- A parenthesis is unmatchable:
).... or ....(.
To understand why is it otherwise always possible, let $t$ be the string that
results from greedy-matching the existing parenthesis (matching a parenthesis
with the closest interrogation symbol). Such a string will be empty or be an
even-length sequence of ?, which is trivially regular (first half ( and
second half )).
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(string s)
{
if (s[0] == ')' or s.back() == '(')
return false;
return ((int)(s).size() - 2) % 2 == 0;
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int t;
cin >> t;
while (t--)
{
string s;
cin >> s;
cout << (solve(s) ? "YES" : "NO") << endl;
}
return 0;
}