07 Dec 2020
— Tags: strings,implementation
— URL
Assume that $s$ is not already a palindrome (if it is, then just remove the
middle character, as it will remain a palindrome).
If $s$ can be turned into a palindrome by the removal of a character at
position $k$, then it has the form:
\[s_1 s_2 ... s_{k - 1} s_k s_{k + 1} ... s_{k + 1} s_{k - 1} ... s_2 s_1\]
We can observe that such string has a matching suffix and prefix up to
position $k$, but it is uncertain if $s_k$ or $s_{n - k}$ should be removed.
However, we know that if we remove one of those characters, then the
remaining characters must necessarily match.
So we just try both options and see if one matches, if not, it’s impossible
because there would necessarily be at least 2 characters to remove in order
to make the string palindromic.
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 test(const string &s, int l, int r)
{
while (l < r)
{
if (s[l] != s[r])
return false;
++l, --r;
}
return true;
}
int solve(string s)
{
int n = (int)(s).size();
int l = 0, r = n - 1;
while (l < r)
{
if (s[l] != s[r])
{
if (test(s, l + 1, r))
return l;
else if (test(s, l, r - 1))
return r;
else
return -1;
}
else
++l, --r;
}
return n / 2;
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
string s;
cin >> s;
if (auto ans = solve(s); ans != -1)
{
cout << "YES" << endl;
cout << ans + 1 << endl;
}
else
{
cout << "NO" << endl;
}
return 0;
}
07 Dec 2020
— Tags: ad-hoc,implementation,brute_force
— URL
- Try to fit sheet 1 on the corner of the bigger sheet.
- Try to fit sheet 2 on the remaining sheet from step 1.
- Rotate sheets if not possible.
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>;
inline bool fits(ii bigger, ii smaller)
{
return bigger.first - smaller.first >= 0 and
bigger.second - smaller.second >= 0;
}
inline ii rotate(ii x) { return {x.second, x.first}; }
vector<ii> cut(ii bigger, ii smaller)
{
if (!fits(bigger, smaller))
return {};
vector<ii> ans;
if (bigger.first - smaller.first != 0)
ans.emplace_back(bigger.first - smaller.first, bigger.second);
if (bigger.second - smaller.second != 0)
ans.emplace_back(bigger.first, bigger.second - smaller.second);
return ans;
}
bool solve(ii x0, ii x1, ii x2)
{
for (auto x : cut(x0, x1))
if (fits(x, x2) or fits(x, rotate(x2)))
return true;
for (auto x : cut(x0, rotate(x1)))
if (fits(x, x2) or fits(x, rotate(x2)))
return true;
return false;
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
ii x0, x1, x2;
cin >> x0.first >> x0.second >> x1.first >> x1.second >> x2.first >>
x2.second;
cout << (solve(x0, x1, x2) ? "YES" : "NO") << endl;
return 0;
}
07 Dec 2020
— Tags: sorting,implementation
— URL
We’ll maintain two sets:
ordx: Elements ordered by their position $x$.ordp: Elements ordered by their population $p$.
First note that to compute the parent of a city, we don’t need information
about any city with less population.
So, we’ll compute the parent for each city (in increasing order of
population) and remove such city from the set of candidates ordx. Since all
cities with less population have been removed from ordx, the immediate
neighbors of the current city in ordx will be our candidates. Pick the
closest and biggest city.
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>;
using iii = tuple<int, int, int>;
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int n;
cin >> n;
vector<ii> a(n);
set<ii> ordx, ordp;
for (int i = 0; i < n; ++i)
{
cin >> a[i].first >> a[i].second;
ordx.emplace(a[i].first, i);
ordp.emplace(a[i].second, i);
}
vi ans(n);
for (auto [p, i] : ordp)
{
int x = a[i].first;
auto it = ordx.lower_bound({x, 0});
iii cur = {1e9, 0, -2};
if (next(it) != end(ordx))
{
int j = next(it)->second;
cur = min(cur, {abs(a[j].first - x), -a[j].second, j});
}
if (it != begin(ordx))
{
int j = prev(it)->second;
cur = min(cur, {abs(a[j].first - x), -a[j].second, j});
}
ans[i] = get<2>(cur) + 1;
ordx.erase(it);
}
for (auto x : ans)
cout << x << " ";
cout << endl;
return 0;
}
06 Dec 2020
— Tags: constructive_algorithm,coloring_argument
— URL
Editorial.
Same logic as previous problem.
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>;
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 InputIterator,
typename T = typename iterator_traits<InputIterator>::value_type>
void write(InputIterator first, InputIterator last, const char *delim = "\n")
{
copy(first, last, ostream_iterator<T>(cout, delim));
}
void solve(vector<string> &board)
{
int n = (int)(board).size(), kx = 0, ko = 0;
array<vector<ii>, 3> cntx, cnto;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
if (board[i][j] == 'X')
{
cntx[(i + j) % 3].emplace_back(i, j);
++kx;
}
if (board[i][j] == 'O')
{
cnto[(i + j) % 3].emplace_back(i, j);
++ko;
}
}
}
for (int i = 0; i < 3; ++i)
{
for (int j = 0; j < 3; ++j)
{
if (i == j)
continue;
if ((int)(cntx[i]).size() + (int)(cnto[j]).size() <= (kx + ko) / 3)
{
for (auto [r, c] : cntx[i])
board[r][c] = 'O';
for (auto [r, c] : cnto[j])
board[r][c] = 'X';
return;
}
}
}
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
vector<string> board(n);
read_n(begin(board), n);
solve(board);
write(begin(board), end(board));
}
return 0;
}
06 Dec 2020
— Tags: constructive_algorithm,coloring_argument
— URL
Editorial.
Hint: Use the Pigeonhole Principle to prove that:
\[\min{x_0, x_1, x_2} \leq floor(\frac{k}{3})\]
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>;
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 InputIterator,
typename T = typename iterator_traits<InputIterator>::value_type>
void write(InputIterator first, InputIterator last, const char *delim = "\n")
{
copy(first, last, ostream_iterator<T>(cout, delim));
}
void solve(vector<string> &board)
{
int n = (int)(board).size(), k = 0;
array<vector<ii>, 3> cnt;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
if (board[i][j] == 'X')
{
cnt[(i + j) % 3].emplace_back(i, j);
++k;
}
}
}
for (auto &v : cnt)
{
if ((int)(v).size() <= k / 3)
{
for (auto [i, j] : v)
board[i][j] = 'O';
return;
}
}
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
vector<string> board(n);
read_n(begin(board), n);
solve(board);
write(begin(board), end(board));
}
return 0;
}
06 Dec 2020
— Tags: brute_force,observation
— URL
Assume that optimally all points will merge into the point $c$ at coordinates
$(x_c, y_c)$.
The key observation is that if such point exists, then all other points must
be at distance $\leq k$ from it, let’s call such points reachable from $c$.
To prove this (informally), assume otherwise: that there’s a point
$d=(x_d,y_d)$ that is not reachable from $c$.
If $d$ is not reachable by any point, then the answer is clearly $-1$.
Let’s say that there’s a point $e$ that is reachable from both $c$ and $d$.
We can do 3 operations:
- Merge with $c$ as center. Answer $ = -1$, because $d$ is not reachable.
- Merge with $d$ as center. The opposite as above.
- Merge with $e$ as center. If all points are reachable from $e$, then we
contradict our initial assumption and $e = c$. If there’s at least a point
unreachable from $e$ then the answer is $-1$ by this same argument.
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>;
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 InputIterator,
typename T = typename iterator_traits<InputIterator>::value_type>
void write(InputIterator first, InputIterator last, const char *delim = "\n")
{
copy(first, last, ostream_iterator<T>(cout, delim));
}
ll dist(ii a, ii b)
{
return abs(a.first - b.first) + abs(a.second - b.second);
}
int solve(vector<ii> &points, int k)
{
for (auto a : points)
{
bool flag = true;
for (auto b : points)
{
if (dist(a, b) > k)
{
flag = false;
break;
}
}
if (flag)
return 1;
}
return -1;
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int t;
cin >> t;
while (t--)
{
int n, k;
cin >> n >> k;
vector<ii> points(n);
for (auto &[x, y] : points)
cin >> x >> y;
cout << solve(points, k) << endl;
}
return 0;
}
06 Dec 2020
— Tags: sortings,observation
— URL
Since the substring “trygub” doesn’t follow a particular order
character-wise, we can sort the characters in our string to force an order.
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>;
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int t;
cin >> t;
while (t--)
{
int n;
string s;
cin >> n >> s;
sort(begin(s), end(s));
cout << s << endl;
}
return 0;
}
05 Dec 2020
— Tags: ad-hoc
— URL
Let’s handle some cases first:
- If $s > a$, the answer is $0$. From now on we assume the opposite.
- If and only if the whole string is composed from ‘a’s, there’s on answer.
We’ll assume otherwise from now on.
Observe that no matter the string, the maximum answer is the distance of the
first non-‘a’ from the start. However, if such character is greater than ‘t’
then we don’t have to move it to the start, only to the second position.
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 main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int t;
cin >> t;
const string a = "atcoder";
while (t--)
{
string s;
cin >> s;
if (a < s)
cout << 0 << endl;
else
{
if (auto it = find_if(begin(s), end(s), [](char c) { return c != 'a'; });
it != s.end())
{
auto dist = distance(begin(s), it);
cout << dist - (*it > 't') << endl;
}
else
cout << -1 << endl;
}
}
return 0;
}
05 Dec 2020
— Tags: two_pointers
— URL
We want to count the ranges $l, r$ inclusive whose sum is $\geq k$.
For a fixed $r$, we need to count how many $l$’s satisfy this previous
condition. We note that as we increase $l$ for any fixed $r$, its sum
decreases and there’s a point where it becomes $\leq k$.
We can find this point using binary search. However, we may also note that we
can take advantage of the answer for a particular $r$, say $l_r$, to reduce
the search space of $r + 1$. Therefore, a two pointers approach can be
applied.
Time complexity: $O(n)$
Memory complexity: $O(n)$
Click to show code.
using namespace std;
using ll = long long;
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);
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int n;
ll k;
cin >> n >> k;
vector<ll> a(n), pa(n);
read_n(begin(a), n);
partial_sum(begin(a), end(a), begin(pa));
function<ll(int, int)> sum = [&pa](int l, int r) {
return pa[r] - (l == 0 ? 0LL : pa[l - 1]);
};
ll ans = 0;
for (int r = 0, l = 0; r < n; ++r)
{
while (sum(l, r) >= k)
++l;
ans += l;
}
cout << ans << endl;
return 0;
}
04 Dec 2020
— Tags: modular_arithmetic,number_theory,counting
— URL
The key observation is that an array is stable if and only if all its
elements are divisible by the minimum element, $a_1$.
Let’s try to prove the forward direction of this assertion.
By contradiction, let’s assume that there’s an array $A$ that contains at
least a non-multiple of $a_1$. Let’s call that element $a_r$.
We have that for $x = a_r$:
\[((x \% a_1) \% a_r) \% ... \neq ((x \% a_r) \% a_1) \% ...\]
We can repeat this argument for all elements of the array, so in conclusion,
all elements must be multiples of $a_1$.
Now, let’s try to prove the backward direction.
Since $a_1$ is necessarily the minimum element we can reduce the initial
expression:
\[((x \% a_1) \% a_2) ... \% a_n = x \% a_1\]
And since all elements are of the form $a_i = d_i a_1$, we would like to know
if the following congruence holds:
\[x - d_{p_i} a_1 - d_{p_{i + 1} } a_1 - ... - d_{p_n} a_1 \equiv x
\pmod{a_1}\]
Which is true, since all the terms aside from $x$ are congruent to $0$.
So, with this in mind, the problem reduces to counting the number of arrays
subject to the problem constraints and that have $a_1$ as a common factor.
Or, equivalently:
\[ans = \sum_{i = 1}^{n} {\frac{n - i}{i} \choose k - 1}\]
We can then use our favorite method for computing binomial coefficients and
we’re done. :)
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>;
template <int M, typename T = long long>
class NumMod
{
static_assert(std::is_integral<T>::value, "Integral required.");
using NM = NumMod<M, T>;
T x;
public:
static const int MOD = M;
NumMod(T x) : x(x) {}
NumMod() : x(0) {}
NumMod(NM const &y) : x(y.v()) {}
explicit operator T() const { return x; }
T v(void) const { return (this->x + M) % M; }
NM & operator=(NM const &y)
{
this->x = y.v();
return *this;
}
NM &operator=(T const &y) { return this->operator=(NM(y)); }
NM &operator+=(NM const &y) { return this->operator=(operator+(y)); }
NM &operator-=(NM const &y) { return this->operator=(operator-(y)); }
NM &operator*=(NM const &y) { return this->operator=(operator*(y)); }
NM operator+(NM const &y) const { return (v() + y.v()) % M; }
NM operator+(T const &y) const { return this->operator+(NM(y)); }
NM operator-(NM const &y) const { return (v() - y.v()) % M; }
NM operator-(T const &y) const { return this->operator-(NM(y)); }
NM operator*(NM const &y) const { return (v() * y.v()) % M; }
NM operator*(T const &y) const { return this->operator*(NM(y)); }
};
int const NMAX = 5e5 + 11;
int const MOD = 998244353;
using NM = NumMod<MOD, ll>;
NM fact[NMAX], inv[NMAX], inv_fact[NMAX];
void precompute_fact(void)
{
inv[1] = fact[0] = inv_fact[0] = 1;
for (int i = 1; i < NMAX; ++i)
{
if (i > 1)
inv[i] = MOD - ll(inv[MOD % i] * (MOD / i));
fact[i] = fact[i - 1] * i;
inv_fact[i] = inv_fact[i - 1] * inv[i];
}
}
ll C(int n, int k)
{
if (k > n)
return 0;
return ll(fact[n] * inv_fact[k] * inv_fact[n - k]);
}
int solve(int n, int k)
{
if (k == 1)
return n;
int i = 1;
NM cur, ans = 0;
while (cur = C((n - i) / i, k - 1), ll(cur))
{
ans += cur;
++i;
}
return ll(ans);
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int n, k;
cin >> n >> k;
precompute_fact();
cout << solve(n, k) << endl;
return 0;
}