05 Jan 2021
— Tags: greedy
— URL
- Max: Leave the array as it is.
- Min: Merge the array into an element.
Intuitively, by summing the entire array into an element, we reduce the
increasing effect of the ceil function.
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 ceil(ll a, ll b) { return (a + b - 1) / b; }
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int t;
cin >> t;
while (t--)
{
int n, x;
cin >> n >> x;
vector<ll> a(n);
for (auto &ai : a)
cin >> ai;
ll min = ceil(accumulate(begin(a), end(a), 0LL), x);
ll max = 0;
for (auto ai : a)
max += ceil(ai, x);
cout << min << " " << max << endl;
}
return 0;
}
05 Jan 2021
— Tags: constructive,math
— URL
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>;
inline int ceil(int a, int b) { return (a + b - 1) / b; }
int bs(int l, int r, function<bool(int)> p)
{
while (l < r)
{
int m = l + (r - l) / 2;
if (p(m))
r = m;
else
l = m + 1;
}
return l;
}
void solve(int n, vector<ii> &ans)
{
if (n == 2)
return;
int i = bs(1, n - 1, [n](int x) { return x >= ceil(n, x); });
for (int j = i + 1; j < n; ++j)
ans.emplace_back(j, n);
ans.emplace_back(n, i);
ans.emplace_back(n, i);
solve(i, ans);
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
vector<ii> ans;
solve(n, ans);
cout << ans.size() << endl;
for (auto [x, y] : ans)
cout << x << " " << y << endl;
cout << endl;
}
return 0;
}
04 Jan 2021
— Tags: math,geometry
— URL
With a bit of geo, we can define the following two equations for the
$x$-coordinate of the incident point, $A_x$.
\[A_x = S_x + S_y \frac{\cos{\alpha}}{\sin{\alpha}}\]
\[A_x = G_x - G_y \frac{\cos{\alpha}}{\sin{\alpha}}\]
We can solve for $\alpha$ and then replace it on one of those equations to
get the answer.
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 x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
double alpha = atan(double(y1 + y2) / double(x2 - x1));
cout << setprecision(12) << fixed << x1 + y1 * cos(alpha) / sin(alpha)
<< endl;
return 0;
}
04 Jan 2021
— Tags: easy
— 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 main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int x;
cin >> x;
cout << max(0, x) << endl;
return 0;
}
04 Jan 2021
— Tags: dp,graphs,dfs
— URL
Let’s call “back-edges” to those edges $(u, v)$ such that $d(v) \leq d(u)$.
Such edges would require move $2$ to be used. We can easily find the
distances, $d$, and the back edges with a bfs.
Having done that, we can define the following dp:
\[dp(u) = min
\begin{cases}
d(u), \\
d(v), \text{ if } (u, v) \text{ is a back edge} \\
dp(v) \text{ otherwise} \\
\end{cases}\]
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>>;
struct BFS
{
Graph & g;
vector<bool> vis;
vector<int> d;
BFS(Graph &g) : g(g), vis(g.size(), 0), d(g.size(), 0) {}
void traverse(int start)
{
queue<int> q;
q.push(start);
vis[start] = true;
while (not q.empty())
{
auto u = q.front();
q.pop();
for (auto &[v, back] : g[u])
{
if (!vis[v])
{
vis[v] = true;
d[v] = d[u] + 1;
q.push(v);
}
else if (d[v] <= d[u])
back = true;
}
}
}
void operator()(int start) { traverse(start); }
};
struct DFS
{
Graph &g;
vi & dp, d;
vector<bool> vis;
DFS(Graph &g, vi &dp, vi d) : g(g), dp(dp), d(d), vis(g.size(), 0) {}
void traverse(int u)
{
vis[u] = true;
for (auto [v, back] : g[u])
{
if (!back and !vis[v])
traverse(v);
if (back)
dp[u] = min(dp[u], d[v]);
else
dp[u] = min(dp[u], dp[v]);
}
}
void operator()(int u) { traverse(u); }
};
vi solve(Graph &g)
{
BFS bfs(g);
bfs(0);
vi dp(bfs.d);
DFS dfs(g, dp, bfs.d);
for (int u = 1, n = (int)(g).size(); u < n; ++u)
if (!dfs.vis[u])
dfs(u);
return dp;
}
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].emplace_back(v, false);
}
auto ans = solve(g);
for (auto x : ans)
cout << x << " ";
cout << endl;
}
return 0;
}
04 Jan 2021
— Tags: math
— URL
First, if the total sum is not even, then it’s impossible. Assume otherwise.
Second, if we have an even amonut of $2$’s (we’ll necesarily have an even
number of $1$s) we can split it into two equal groups with the same sum.
Otherwise, we need at least a pair of $1$’s to fill the missing $2$.
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>;
bool solve(vi a)
{
int sum = accumulate(begin(a), end(a), 0), n = (int)(a).size();
int ones = count_if(begin(a), end(a), [](int x) { return x == 1; });
int twos = n - ones;
return sum % 2 == 0 and ((twos % 2 == 0) or (ones > 0));
}
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) ? "YES" : "NO") << endl;
}
return 0;
}
04 Jan 2021
— Tags: greedy,math
— URL
First note that the order of operations doesn’t matter, and that if we have
currently $m$ identical pieces and we can make a certain cut $x$ (vertical or
horizontal), then we can make such cut for all $m$ pieces (duplicating its
number).
We only need duplicate our count of sheets the total amount of cuts we can
make.
Time complexity: $O(\log{h} + \log{w})$
Memory complexity: $O(1)$
Click to show code.
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
bool solve(int w, int h, int n)
{
int ptwo = 1, m = 1;
while (w % 2 == 0)
{
m *= 2;
w /= 2;
ptwo *= 2;
}
ptwo = 1;
while (h % 2 == 0)
{
m *= 2;
h /= 2;
ptwo *= 2;
}
return m >= n;
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int t;
cin >> t;
while (t--)
{
int w, h, n;
cin >> w >> h >> n;
cout << (solve(w, h, n) ? "YES" : "NO") << endl;
}
return 0;
}
02 Jan 2021
— Tags: trees,dfs
— URL
Let’s root the tree on $0$ to make our life easier.
Without loss of generality, assume $t = 1$. We have two cases:
- $b$ is parent of $a$: We only have to update with $+x$ to the subtree
rooted at $a$.
- $b$ is parent of $a$: We have to update ($+x$) the entire tree but the
subtree rooted at $a$.
Since we only need to know the answer at the end, we may use an analogue to
difference arrays but on trees to perform updates on $O(1)$.
For ase $1.$ add $x$ to ans[a], for case $2.$ add $x$ to ans[0] and
subtract $x$ from ans[a] to cancel the excess.
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 const NMAX = 2e5 + 11;
int a[NMAX], b[NMAX], depth[NMAX];
ll ans[NMAX];
vi g[NMAX];
void precompute_depth(int u, int p)
{
for (auto v : g[u])
{
if (v == p)
continue;
depth[v] = depth[u] + 1;
precompute_depth(v, u);
}
}
void solve(int u, int p)
{
for (auto v : g[u])
{
if (v == p)
continue;
ans[v] += ans[u];
solve(v, u);
}
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int n;
cin >> n;
vi a(n), b(n);
for (int i = 0; i < n - 1; ++i)
{
cin >> a[i] >> b[i], a[i]--, b[i]--;
g[a[i]].push_back(b[i]);
g[b[i]].push_back(a[i]);
}
precompute_depth(0, 0);
int q;
cin >> q;
while (q--)
{
int t, e, x;
cin >> t >> e >> x, e--;
if (t == 1)
{
if (depth[a[e]] > depth[b[e]])
ans[a[e]] += x;
else
{
ans[0] += x;
ans[b[e]] -= x;
}
}
else
{
if (depth[b[e]] > depth[a[e]])
ans[b[e]] += x;
else
{
ans[0] += x;
ans[a[e]] -= x;
}
}
}
solve(0, 0);
for (int u = 0; u < n; ++u)
cout << ans[u] << endl;
return 0;
}
02 Jan 2021
— Tags: greedy,sorting
— URL
Greedy pick elements ordered by $2a + b$. Intuitively, we want to maximize
both the contribution of a pick to oneself, $a + b$, and the loss from the
other, $a$. Also, check this.
Time complexity: $O(n \log{n})$
Memory complexity: $O(n)$
Click to show code.
using namespace std;
using ll = long long;
using ii = pair<ll, ll>;
using vi = vector<int>;
int solve(vector<ii> ab)
{
auto cmp = [](ii x, ii y) {
auto [a1, b1] = x;
auto [a2, b2] = y;
return 2 * a1 + b1 > 2 * a2 + b2;
};
auto sum_first = [](ll acc, ii x) -> ll { return acc + x.first; };
sort(begin(ab), end(ab), cmp);
ll atot = accumulate(begin(ab), end(ab), 0LL, sum_first), btot = 0;
int ans = 0;
for (auto [a, b] : ab)
{
btot += a + b;
atot -= a;
ans++;
if (btot > atot)
break;
}
return ans;
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int n;
cin >> n;
vector<ii> ab(n);
for (auto &[a, b] : ab)
cin >> a >> b;
cout << solve(ab) << endl;
return 0;
}
02 Jan 2021
— Tags: implementation
— URL
Check for existence of $x$ and $!x$.
Time complexity: $O(n)$
Memory complexity: $O(n \log{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 n;
cin >> n;
string x;
bool satisfiable = true;
map<string, int> is_positive;
for (int i = 0; i < n; ++i)
{
string s;
int sign = +1;
char ch = (std::cin >> std::ws).peek();
if (ch == '!')
{
cin >> ch;
sign = -1;
}
cin >> s;
if (is_positive.find(s) == is_positive.end())
is_positive[s] = sign;
else if (is_positive[s] != sign)
{
satisfiable = false;
x = s;
}
}
cout << (satisfiable ? "satisfiable" : x) << endl;
return 0;
}