22 Jan 2021
— Tags: two_pointers
— URL
Without loss of generality, we want to find the largest substring consisting
of as. To make this task easier, we can fix the right border, $r$ of this
hypothetical subarray.
Note that for a given $r$, to find the longest substring ending at $r$ we
should try to expand the left border as much as possible.
So, following this idea, we can try all $r$’s and find their corresponding
$l$’s using the two pointers technique or binary search.
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 k)
{
int n = (int)(s).size();
vi a(n, 0), b(n, 0);
for (int i = 0; i < n; ++i)
{
a[i] += s[i] == 'a';
b[i] += s[i] == 'b';
if (i > 0)
a[i] += a[i - 1], b[i] += b[i - 1];
}
auto cnt = [](vi &c, int l, int r) {
return c[r] - (l > 0 ? c[l - 1] : 0);
};
int ans = 0;
for (int r = 0, la = 0, lb = 0; r < n; ++r)
{
while (cnt(b, la, r) > k)
++la;
while (cnt(a, lb, r) > k)
++lb;
ans = max({ans, r - la + 1, r - lb + 1});
}
return ans;
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int n, k;
string s;
cin >> n >> k >> s;
cout << solve(s, k) << endl;
return 0;
}
19 Jan 2021
— Tags: implementation
— URL
Define a mapping (array), $id(a)$ that returns the position of the number
$a$ in the array $x$.
The idea will be to use this mapping to know how many rounds we’ll need to
visit all number in an increasing order.
For example, if we start with number $a$ (initially $1$) we can see if $a+1$
would be visited in the same round if $id(a + 1) > id(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 a)
{
int n = a.size();
vi id(n);
for (int i = 0; i < n; ++i)
id[a[i] - 1] = i;
int cur = 0, ans = 0;
while (cur < n)
{
++cur;
while (cur < n and id[cur] > id[cur - 1])
++cur;
++ans;
}
return ans;
}
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;
}
18 Jan 2021
— Tags: greedy,sorting,constructive
— URL
Let’s sort the elements in non-decreasing order and iterate them from
smallest to largest.
While considering element $a_i$, assume that we can create all numbers
$1, 2, …, x$, where $x$ is $\sum_{j = 1}^{i -1}a_j$. Note that by
considering $a_i$, we can construct numbers $a_i, a_i + 1, …, x + a_i$.
Therefore, only if $x + 1 - a_i \leq 1$ would number $x + 1$ be possible to
construct. Otherwise, the smallest impossible coin sum is $x + 1$.
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>;
ll solve(vi a)
{
sort(begin(a), end(a));
ll sum = 0;
for (auto ai : a)
{
if (ai > sum + 1)
return sum + 1;
sum += ai;
}
return sum + 1;
}
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;
}
16 Jan 2021
— Tags: dp
— URL
Observations:
-
- For a given valid path that filled $x$ empty cells, one has $3^{k - x}$
possible configurations (one can freely permute the empty cells that were not
used in a valid path).
-
Let’s define $rowcnt_i(j1, j2)$ to be the amount of empty cells in the range
$(i, j1), (i, j1 + 1), …, (i, j2)$. Similarly, define $colcnt_j(i1, i2)$ as
the amount of empty cells in the range $(i1, j), (i1 + 1, j), …, (i2, j)$.
Define the following dp:
If $(i, j)$ is D:
\[dp(i, j) = dp(i + 1, j) \times 3^{rowcnt_i(j + 1, w)}\]
If $(i, j)$ is R:
\(dp(i, j) = dp(i, j + 1) \times 3^{colcnt_i(i + 1, h)}\)
If $(i, j)$ is X:
\[dp(i, j) = dp(i + 1, j) \times 3^{rowcnt_i(j + 1, w)}
+ dp(i, j + 1) \times 3^{colcnt_i(i + 1, h)}\]
If $(i, j)$ is empty:
\[dp(i, j) = 2 \ times dp(i + 1, j) \times 3^{rowcnt_i(j + 1, w)}
+ 2 \times dp(i, j + 1) \times 3^{colcnt_i(i + 1, h)}\]
The $2$ comes because to turn right one has $|{R, X}| = 2$ options. Similarly
for turning down.
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>;
using mint = atcoder::modint998244353;
ll solve(vector<string> mat)
{
int h = mat.size(), w = mat[0].size();
vector<vector<mint>> dp(h + 1, vector<mint>(w + 1, 0));
mint miss_right(1);
vector<mint> miss_down(w, 1);
for (int i = h - 1; i >= 0; --i)
{
miss_right = 1;
for (int j = w - 1; j >= 0; --j)
{
mint dans = dp[i + 1][j] * miss_right;
mint rans = dp[i][j + 1] * miss_down[j];
int md, mr;
if (auto c = mat[i][j]; c)
{
md = c == 'X' or c == 'D';
mr = c == 'X' or c == 'R';
}
else
{
md = mr = 2;
miss_right *= 3;
miss_down[j] *= 3;
}
dp[i][j] = dans * md + rans * mr;
if (i == h - 1 and j == w - 1)
dp[i][j] = !mat[i][j] ? 3 : 1;
}
}
return dp[0][0].val();
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int h, w, k;
cin >> h >> w >> k;
vector<string> mat(h, string(w, 0));
for (int i = 0; i < k; ++i)
{
int row, col;
char ch;
cin >> row >> col >> ch, row--, col--;
mat[row][col] = ch;
}
cout << solve(mat) << endl;
return 0;
}
16 Jan 2021
— Tags: greedy
— URL
Observations:
- For a given $a_i$, we can only add $a_i + 1$ to the answer if we place all
$0 \leq a_j \leq a_i - 1$ in the same box.
- To maximize the answer, we should try to place the biggest valid $a_i$
possible (following observation 1) on as many boxes as we can.
We can store all numbers ordered in a multiset, and for each box try to place
the biggest valid $a_i$, deleting all the used elements from the multiset in
that attempt. All the remaining elements will be thrown in the last box, as
they don’t contribute to anything.
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 solve(vi a, int k)
{
multiset<int> ms(begin(a), end(a));
int ans = 0;
while (k--)
{
int cur = 0;
auto it = ms.find(cur);
while (it != ms.end())
{
ms.erase(it);
it = ms.find(++cur);
}
ans += cur;
}
return ans;
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int n, k;
cin >> n >> k;
vi a(n);
for (auto &ai : a)
cin >> ai;
cout << solve(a, k) << endl;
return 0;
}
16 Jan 2021
— Tags: data_structures,segment_tree,greedy
— URL
Disclaimer: I was sleepy and segtree was the first thing that came to my
mind, don’t judge me :(.
Observations:
- For each $c_k$ we have two options. Either we pick $1 \leq i \leq j < k$
(which is $c_{i - 1}$) or we pick $b_j$ ($j = k$) and pair it with the
maximum $a_i$, $1 \leq i \leq j$.
We can code a straightforward greedy with 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<int, int>;
using vll = vector<ll>;
using S = ll;
S op(S a, S b) { return max(a, b); }
S e() { return -1; }
vll solve(vll a, vll b)
{
int n = (int)(a).size();
vll c(n);
c[0] = a[0] * b[0];
using RMQ = atcoder::segtree<S, op, e>;
RMQ st(a);
for (int i = 1; i < n; ++i)
c[i] = max(c[i - 1], b[i] * st.prod(0, i + 1));
return c;
}
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int n;
cin >> n;
vll a(n), b(n);
for (auto &ai : a)
cin >> ai;
for (auto &bi : b)
cin >> bi;
auto c = solve(a, b);
for (auto ci : c)
cout << ci << endl;
return 0;
}
15 Jan 2021
— Tags: data_structures,segment_tree,binary_search
— URL
AC-Library
test
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>;
using S = int;
S op(S a, S b) { return max(a, b); }
S e() { return -1; }
bool f(S target, S v) { return v < target; }
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int n, q;
cin >> n >> q;
vi a(n);
for (auto &ai : a)
cin >> ai;
using RangeMax = atcoder::segtree<S, op, e>;
using placeholders::_1;
RangeMax st(a);
while (q--)
{
int type;
cin >> type;
if (type == 1)
{
int x, v;
cin >> x >> v, x--;
st.set(x, v);
}
else if (type == 2)
{
int l, r;
cin >> l >> r, l--;
auto ans = st.prod(l, r);
cout << ans << endl;
}
else
{
int x, v;
cin >> x >> v, x--;
auto ans = st.max_right(x, bind(f, v, _1));
cout << ans + 1 << endl;
}
}
return 0;
}
15 Jan 2021
— Tags: lazy_segment_tree,data_structures,number_theory
— URL
With a sieve precompute a function is_prime(x) in order to know if a number
$x$ is prime in $O(1)$ and trasform our initial array $a$ into an array $b$
such that b[i] = is_prime[a[i]]. We now have an array of $0$s and $1$s.
Note that the queries reduce to:
- Query 1: Range sum of $l, r$.
- Query 2: Change interval $l, r$ to $1$ if $v$ is prime, $0$ otherwise.
We can support these queries using a lazy segment tree.
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 <int SIZE>
struct Sieve
{
static_assert(0 <= SIZE and SIZE <= 1e8, "0 <= SIZE <= 1e8");
using byte = unsigned char;
std::bitset<SIZE> is_prime;
std::vector<int> primes;
Sieve()
{
is_prime.set();
is_prime[0] = is_prime[1] = 0;
for (int i = 4; i < SIZE; i += 2)
is_prime[i] = 0;
for (int i = 3; i * i < SIZE; i += 2)
if (is_prime[i])
for (int j = i * i; j < SIZE; j += i * 2)
is_prime[j] = 0;
for (int i = 2; i < SIZE; ++i)
if (is_prime[i])
primes.push_back(i);
}
};
struct S
{
int n, np;
};
S op(S a, S b) { return {a.n + b.n, a.np + b.np}; }
S e() { return {0, 0}; };
struct F
{
bool lazy, is_prime;
};
S mapping(F f, S x) { return f.lazy ? S{x.n, x.n * f.is_prime} : x; }
F composition(F f, F g) { return f.lazy ? f : g; }
F id() { return {0, 0}; }
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int t;
cin >> t;
int const AMAX = 1e6 + 11;
Sieve<AMAX> sieve;
using SegmentTree =
atcoder::lazy_segtree<S, op, e, F, mapping, composition, id>;
for (int tc = 1; tc <= t; ++tc)
{
cout << "Case " << tc << ":" << endl;
int n, q;
cin >> n >> q;
vector<S> a(n);
for (int i = 0; i < n; ++i)
{
int x;
cin >> x;
a[i] = {1, sieve.is_prime[x]};
}
SegmentTree st(a);
while (q--)
{
int type;
cin >> type;
if (type)
{
int l, r;
cin >> l >> r, l--;
auto ans = st.prod(l, r);
cout << ans.np << endl;
}
else
{
int l, r, v;
cin >> l >> r >> v, l--;
st.apply(l, r, F{true, sieve.is_prime[v]});
}
}
}
return 0;
}
15 Jan 2021
— Tags: greedy,binary_search,implementation
— URL
Editorial.
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 a)
{
ll target = accumulate(begin(a), end(a), 0LL);
if (target & 1)
return false;
target /= 2;
for (int i = 0; i < 2; ++i)
{
ll sum = 0;
set<ll> unique;
for (auto ai : a)
{
sum += ai;
unique.insert(ai);
if (unique.find(sum - target) != unique.end())
return true;
}
reverse(begin(a), end(a));
}
return false;
}
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;
}
15 Jan 2021
— Tags: data_structures,segment_tree
— URL
For each element $a_k$ we can know how many times it contributes to the
weakness of the overall army if we can support the following range query:
inv(l, r): Number of inversions with $a_i > a_j$ such that
$l \leq a_j \leq r$.
To compute such value, we can use this additional function:
freq(l, r): Number of elements $l \leq a_i \leq r$.
For each element from the left to right, we’ll do the following:
- We’ll increase our overall answer by querying for
inv(ai + 1, amax).
- We’ll increase the inverse count of $a_i$ by
freq(ai + 1, amax), i.e.
e number of elements greater than $a_i$ seen so far.
- We’ll increase the occurrence of $a_i$ in
freq by 1.
Any range query data structure should do the job (I’m using AtCoder’s Segment
ee), as long as you compress the numbers.
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>;
template <typename T>
map<T, int> compress(vector<T> values)
{
map<T, int> mp;
int cnt = 0;
for (auto v : values)
mp[v];
for (auto &[k, v] : mp)
v = cnt++;
return mp;
}
using S = ll;
S e() { return 0; }
S op(S a, S b) { return a + b; }
ll solve(vi a)
{
using RangeSumQuery = atcoder::segtree<S, op, e>;
auto id = compress(a);
int n = (int)(id).size() + 1;
ll ans = 0;
RangeSumQuery freq(n), inv(n);
for (auto &ai : a)
{
ai = id[ai];
ll inversions = freq.prod(ai + 1, n);
ans += inv.prod(ai + 1, n);
inv.set(ai, inv.get(ai) + inversions);
freq.set(ai, freq.get(ai) + 1);
}
return ans;
}
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;
}