04 Dec 2020
— Tags: segment_tree,data_structures
— URL
Without loss of generality, assume there are at least three distinct numbers
on a given range. We can abstract this range into three section:
- A prefix of number $x_1$.
- A middle section with different blocks of numbers $x_2, x_3, …$.
- A suffix of number $x_k$.
Where $k \geq 3$.
The key observation is that for the purpose of computing the most frequent
number in a range, we only need a pair of the form $(cnt_x, x)$ for each of
the three sections in our range, where $x$ is the most frequent number on
that section and $cnt_x$ is its respective count.
Finding the count of the most frequent number on a range would be the same as
taking the maximum of the three pairs.
We can maintain this information on a Segment Tree, where nodes store these
three pairs. Merging nodes $u$ and $v%$ is straightforward:
- Prefix: prefix of $u$.
- Middle: the maximum of the middles in both nodes and the sum of the suffix
of $u$ and prefix of $v$ if both are of the same number (otherwise, they are
treated as separate blocks).
- Suffix: suffix of $v$.
Caution when merging two nodes that have less than 3 unique numbers.
Time complexity: $O(q \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>;
template <typename InputIterator,
typename T = typename iterator_traits<InputIterator>::value_type>
void read_n(InputIterator it, int n)
{
copy_n(istream_iterator<T>(cin), n, it);
}
template <typename T, typename Container = vector<T>>
struct SegmentTree
{
int n;
vector<T> t;
SegmentTree(Container &a) : n(a.size())
{
t.resize(4 * n);
build(a, 1, 0, n - 1);
}
void build(Container &a, int v, int tl, int tr)
{
if (tl == tr)
t[v] = T(a[tl]);
else
{
int tm = (tl + tr) / 2;
build(a, v * 2, tl, tm);
build(a, v * 2 + 1, tm + 1, tr);
t[v] = merge(t[v * 2], t[v * 2 + 1]);
}
}
inline T merge(T a, T b) { return a + b; }
T query(int v, int tl, int tr, int l, int r)
{
if (l > r)
return T();
if (l == tl and r == tr)
return t[v];
int tm = (tl + tr) / 2;
return merge(query(v * 2, tl, tm, l, min(r, tm)),
query(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r));
}
};
struct Node
{
ii l, m, r;
Node() : l({0, 0}), m({0, 0}), r({0, 0}) {}
explicit Node(int x) : l({1, x}), m({1, x}), r({1, x}) {}
Node operator+(Node const &other) const
{
Node ans;
ans.l = l;
ans.r = other.r;
ans.m = max(m, other.m);
if (r.second == other.l.second)
ans.m = max(ans.m, {r.first + other.l.first, r.second});
else
ans.m = max({ans.m, ans.l, ans.r});
if (ans.l.second == ans.m.second)
ans.l = ans.m;
if (ans.r.second == ans.m.second)
ans.r = ans.m;
return ans;
}
int get(void) const { return max({l, m, r}).first; }
};
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int n, q;
while (cin >> n, n)
{
cin >> q;
vi a(n);
read_n(begin(a), n);
SegmentTree<Node, vi> st(a);
while (q--)
{
int i, j;
cin >> i >> j, i--, j--;
cout << st.query(1, 0, n - 1, i, j).get() << endl;
}
}
return 0;
}
30 Nov 2020
— Tags: number_theory,divisors
— URL
Brute-force up to $\sqrt{n}$.
Time complexity: $O(\sqrt{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);
ll n;
cin >> n;
int ans = 64;
for (int i = 1, m = sqrt(n); i <= m; ++i)
if (n % i == 0)
ans = min(ans, 1 + (int)log10(n / i));
cout << ans << endl;
return 0;
}
30 Nov 2020
— Tags: greedy
— URL
Keep in mind that the first priority of each player is to maximize their
wins.
Let’s take the perspective of player $2$, Bob. Bob can win at most $y$,
times, by doing nothing and letting player $1$ run out of stamina. Can Bob
minimize Alice’s wins without affecting his score?
One way is to only respond on Alice’s last serve (since she wouldn’t be able
to respond anyway),. But we soon realize that’s the only option.
If Bob responds to any of Alice’s $i \in {1, 2, …, x - 1}$ serve, then
Alice’s best chance is to not respond until Bob’s last serve, $y$ (same
strategy). Alice would then win $(i - 1) + (x - i) = x - 1$ times and Bob
$y-1$ times. This is suboptimal for Bob, since we know he can win $y$ times
by our optimal strategy.
Since Alice is on Bob’s mercy (she can’t stop serving until she runs out of
stamina or Bob wins), Bob will choose the optimal strategy and win $y$ times
while Alice $x - 1$ times.
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 t;
cin >> t;
while (t--)
{
int x, y;
cin >> x >> y;
cout << x - 1 << " " << y << endl;
}
return 0;
}
30 Nov 2020
— Tags: math,binary_search
— URL
Note that we have to make at least $n$ jumps to reach $x$ (always jumping
forward), where $n$ is:
\[n = argmin_n(f(n)- x >= 0)\]
Where $f(n) = \frac{n \times (n + 1)}{2}$. Intuitively, the answer shouldn’t
be much bigger than that.
Furthermore, we know that $0 <= f(n) - x < n$ (because of the $argmin$
constraints). We have to select a subset of our forward steps and turn them
into backward steps, or try increasing $n$.
We can think of reversing a step $k$ as decreasing $f(n)$ by $k + 1$. For our
range of $[1, n]$, we would have options $[2, n + 1]$.
The problem splits in three cases:
- $f(n) - x = 0$: $n$ is the answer.
- $2 <= f(n) - x < n$: We can reverse the step $f(n) - x - 1$. $n$ is the
answer.
- $f(n) - x = 1$: There’s no way to reverse any step from $[1, n]$ to get to
$x$, but we can just take the $n + 1$ step backward. $n + 1$ is the answer.
Time complexity: $O(\log{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>;
using predicate = function<bool(ll)>;
inline ll f(ll n) { return (n * (n + 1)) / 2; }
ll bs(ll l, ll r, predicate p)
{
while (l < r)
{
ll m = l + (r - l) / 2;
if (p(m))
r = m;
else
l = m + 1;
}
return l;
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int t;
cin >> t;
while (t--)
{
ll x;
cin >> x;
auto ok = [x](ll n) { return f(n) >= x; };
int n = bs(1, x, ok);
if (f(n) - x == 1)
cout << n + 1 << endl;
else
cout << n << endl;
}
return 0;
}
30 Nov 2020
— Tags: math
— URL
Observations:
- $f(f(x))$ is the same as stripping $x$ from all it’s trailing zeros.
- $\frac{x}{f(f(x))}$ will always be the biggest power of $10$ that is a
factor of $x$.
- Finding all unique values of the formula is the same as finding all
possible powers of ten less or equal than $x$.
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 t;
cin >> t;
while (t--)
{
string s;
cin >> s;
cout << (int)(s).size() << endl;
}
return 0;
}
29 Nov 2020
— Tags: backtracking
— URL
- For position $i$, try all possible matches and backtrack if one doesn’t
work.
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 n;
string s, opts[4] = {"dream", "dreamer", "erase", "eraser"};
bool solve(int i)
{
if (i == n)
return true;
bool ans = false;
for (auto const &opt : opts)
{
int m = (int)(opt).size();
if (m + i <= n and s.substr(i, m) == opt)
ans = solve(i + m);
if (ans)
break;
}
return ans;
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
cin >> s;
n = (int)(s).size();
cout << (solve(0) ? "YES" : "NO") << endl;
return 0;
}
29 Nov 2020
— Tags: math,greedy
— URL
(Disclaimer: I came with an uglier $O(n^2 \log{n})$ solution, but a good
friend of mine pointed out that I was doing unnecessary computation. Anyway,
this is the improved version.)
First, note that the seats must be composite numbers that share a factor but
are not multiples of themselves.
So, our answer has to be a subset of the multiples of some prime in [1, 4n].
Furthermore, note that one of the best candidates to fulfill this
common-factor role is 2, since there are more multiples of 2 than any other
prime in that range.
Finally, note that it is always better to pick bigger numbers than smaller
numbers, because they are less likely to be multiples of each other.
Our final answer is:
\[2n + 2, 2n + 4, ... , 4n\]
This subset of $n$ numbers have a common factor of 2 and are definitely not
multiples of each other. If you’re not convinced of this last fact, think
that any multiple of one of these numbers will necessarily exceed 4n,
therefore not be in the chosen subset.
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;
cin >> n;
for (int i = 2 * n + 2; i <= 4 * n; i += 2)
cout << i << " ";
cout << endl;
}
return 0;
}
28 Nov 2020
— Tags: dp
— URL
- $dp(k, l)$: winner of tournament that starts at position $l$ in string and
has $2^k$ players.
Time complexity: $O(n^2)$
Memory complexity: $O(n^3)$
Click to show code.
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int const NMAX = 1e2 + 5;
int n, k;
char dp[NMAX][NMAX];
string s;
ll binpow(ll a, ll b)
{
a %= n;
ll res = 1;
while (b > 0)
{
if (b & 1)
res = res * a % n;
a = a * a % n;
b >>= 1;
}
return res;
}
char op(char a, char b)
{
if (a == b)
return a;
if ((a == 'P' and b == 'R') or (a == 'S' and (b == 'R' or b == 'P')))
swap(a, b);
if (a == 'R' and b == 'P')
return b;
else if (a == 'R' and b == 'S')
return 'R';
else
return 'S';
}
char solve(int l, int w)
{
char &ans = dp[w][l];
if (ans)
return ans;
else if (w == 0)
return s[l];
else
{
return ans = op(solve(l, w - 1),
solve((l + binpow(2, w - 1)) % n, w - 1));
}
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
cin >> n >> k >> s;
cout << solve(0, k) << endl;
return 0;
}
28 Nov 2020
— Tags: binary_search
— URL
Pick the log of size n + 1 and maximize the amount of logs from [1 … m]
that can be cut from n + 1.
\[argmax_{m}((n + 1 - \sum_{i = 1}^{m} i) \geq 0)\]
Time complexity: $O(\log{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>;
using predicate = function<bool(ll)>;
ll n;
inline bool ok(ll m) { return (2 * (n + 1)) / m >= m + 1; }
ll bs(ll l, ll r, predicate p)
{
while (l < r)
{
ll m = l + (r - l + 1) / 2;
if (p(m))
l = m;
else
r = m - 1;
}
return l;
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
cin >> n;
auto ans = bs(1, n, ok);
cout << n - ans + 1 << endl;
return 0;
}
28 Nov 2020
— Tags: math,ad-hoc
— URL
Divide problem on cases:
- a == b. You will need to use a at least one corridor, so might as well use
just one.
- a > b and a < b. Two options:
- Only use corridors (zig-zag).
- Use one corridor and then stairs.
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 a, b, x, y;
cin >> a >> b >> x >> y;
if (a == b)
{
cout << x << endl;
}
else if (a > b)
cout << min(x + (a - 1 - b) * y, x * ((a - b) * 2 - 1)) << endl;
else
cout << min(x + (b - a) * y, x * ((b - a) * 2 + 1)) << endl;
return 0;
}