1. Strong Password
It's optimal to make adjacent characters different.
If two adjacent characters are same, then they only add the total time by $$$1$$$ seconds. If we insert a different character between them, the $$$1$$$ will turn into two $$$2$$$ s, which add the total time by $$$2$$$ seconds. Since you can only insert $$$1$$$ character in it, it's the optimal insertion method.
If that same adjacent pair doesn't exist, we can still add a different character between an arbitrary pair, then it will add the total time by $$$2$$$ seconds.
Time complexity: $$$O(n)$$$.
# include <iostream>
# include <string>
using namespace std;
const int N = 1e5 + 10;
string s;
int n, tp;
void run()
{
cin >> s;
n = s.size();
for (int i = 0; i < n - 1; i++)
{
if (s[i] == s[i + 1])
{
tp = 0;
while (s[i] == tp + 'a' or s[i + 1] == tp + 'a')
tp++;
s.insert(s.begin() + i + 1, tp + 'a');
break;
}
}
if (n == s.size())
{
if (s.back() == 'z')
s.push_back('a');
else
s.push_back('z');
}
cout << s << '\n';
}
int main()
{
int T = 1;
scanf("%d", &T);
while (T--)
run();
}
2. Make Three Regions
The given grid contains at most $$$1$$$ connected region.
There are only $$$2$$$ rows in this grid.
Imagine a trap.
Since there are only $$$2$$$ rows in the grid, so all the cell unblocked will have at most $$$3$$$ adjacent unblocked cells.
In order to make $$$3$$$ connected components, we should seperate these $$$3$$$ adjacent unblocked cells into different connected components. So how to do that?
Imagine a "trap" like this:
...
x.x
We can see that if we block the middle cell on the upper row, it will separate into $$$3$$$ connected components like this:
.x.
x.x
It's the only way to separate legally.
Time complexity: $$$O(n)$$$.
# include <iostream>
using namespace std;
const int N = 2e5 + 10;
int n, res;
char ch[2][N];
void run()
{
cin >> n;
cin >> ch[0];
cin >> ch[1];
res = 0;
for (int j = 0; j < 2; j++)
{
for (int i = 1; i < n - 1; i++)
{
if (ch[j][i] == '.')
{
res += (ch[j ^ 1][i - 1] == 'x' and
ch[j ^ 1][i + 1] == 'x' and
ch[j ^ 1][i] == '.' and
ch[j][i - 1] == '.' and
ch[j][i + 1] == '.');
}
}
}
printf("%d\n", res);
}
int main()
{
int T = 1;
scanf("%d", &T);
while (T--)
run();
}
3. Even positions
It's OK to construct it greedily.
For a RBS $$$s$$$, we define its layer value $$$l$$$ as this:
"Layer" stands for "the layer number of brackets pair".
And its prefix value $$$p$$$ is this:
Then, it's required to satisfy $$$p_n=0$$$ and $$$\min(p)=0$$$.
If $$$\min(p)<0$$$, it'll no longer be a RBS.
Then, we define the require value $$$r$$$ as this:
Note that this $$$s$$$ may contains "_".
A legal construction of $$$s$$$ satisfies $$$p_i\ge r_i$$$.
Then, for each position $$$i$$$, if inserting an ")" may make $$$p_i<r_i$$$, then insert an "(" instead.
It can be proved that this is the optimal construction method.
Time complexity: $$$O(n)$$$.
Fun fact: I got $$$2$$$ runtime errors during the contest because I set the array size to $$$10^5$$$ while the problem requires $$$2\times 10^5$$$.
# include <iostream>
# include <string>
# include <stack>
using namespace std;
const int N = 2e5 + 10;
string s;
int n, ts[N];
stack<int> stk;
using ll = long long;
ll res;
void run()
{
cin >> n >> s;
ts[n] = res = 0;
for (int i = n - 1; ~i; i--)
{
if (s[i] != ')')
{
ts[i] = max(0, ts[i + 1] - 1);
}
else
{
ts[i] = ts[i + 1] + 1;
}
}
for (int i = 0, tmp = 0; i < n; i++)
{
if (s[i] == '(')
{
tmp++;
stk.push(i);
continue;
}
if (s[i] == ')')
{
tmp--;
res += i - stk.top();
stk.pop();
continue;
}
if (tmp - 1 < ts[i + 1] or !stk.size())
{
tmp++;
s[i] = '(';
stk.push(i);
continue;
}
s[i] = ')';
tmp--;
res += i - stk.top();
stk.pop();
}
printf("%lld\n", res);
}
int main()
{
int T = 1;
scanf("%d", &T);
while (T--)
run();
}
4. Maximize the root
After each operation, the values on all vertices should be non-negative.
Maximize the minimum.
With the formula in hint $$$3$$$, we can quickly realize that we should make $$$\min_{i=2}^n a_i$$$ as big as possible. So how to do that?
Well, the operation that the problem provides is able to add a vertex by subtracting the rest of its subtree. So, in order to maximize the minimum, we can simply make them closer.
If the value of a vertex is already higher than the minimum value of its subtree, we can't get them closer.
Apply a depth-first search to do that.
Time complexity: $$$O(n)$$$.
# include <iostream>
# include <vector>
using namespace std;
const int N = 2e5 + 10;
int n, a[N], cont[N];
vector<int> road[N];
void dfs(int x, int f)
{
cont[x] = 0x3f3f3f3f;
for (auto &i : road[x])
{
if (i == f)
continue;
dfs(i, x);
cont[x] = min(cont[x], cont[i]);
}
if (x == 1)
return;
if (cont[x] == 0x3f3f3f3f)
cont[x] = a[x];
else if (cont[x] > a[x])
{
cont[x] = (cont[x] + a[x]) / 2;
}
}
void run()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", a + i);
road[i].clear();
}
for (int i = 2, x; i <= n; i++)
{
scanf("%d", &x);
road[x].push_back(i);
}
dfs(1, 0);
printf("%d\n", a[1] + cont[1]);
}
int main()
{
int T = 1;
scanf("%d", &T);
while (T--)
run();
}
5. Level Up
What will happen when we increase $$$k$$$?
The number of the monsters fleeing won't be higher. Why?
Because, a higher $$$k$$$ means the lower expectation level.
Binary search.
With the conclusion in hint $$$2$$$, we can calculate the Firmness requirement $$$f$$$ which satisfies when $$$k\ge f_i$$$, the $$$i$$$-th monster always fights with Monocarp.
If $$$i$$$-th monster fight with Monocarp with a parameter of $$$k$$$, then it must satisfy that
Because when Monocarp already fought $$$a_ik$$$ or more monsters before, then his level will be higher than $$$a_i$$$, and the $$$i$$$-th monster will flee.
The formula above is easy to calculate with a BIT.
After calculating the sequence $$$f$$$, we can answer all the queries in a time complexity of $$$O(1)$$$.
Time complexity: $$$O(n\log n\log (\max a_i)+q)$$$.
Fun fact: I applied an unnecessary sort on the queries. However, it still has a good speed.
# include <iostream>
# include <vector>
# include <tuple>
# include <algorithm>
using namespace std;
const int N = 2e5 + 10;
int a[N], n, q, tr[N], idx = 1, l, r, mid;
vector<int> dst[N];
inline void update(int x, int v)
{
while (x < N)
{
tr[x] += v;
x += (x & -x);
}
}
inline int query(int x)
{
int res = 0;
while (x)
res += tr[x], x -= (x & -x);
return res;
}
inline bool check(int x, int v)
{
return 1ll * a[x] * v <= query(v);
}
using t3i = tuple<int, int, int>;
t3i qry[N];
bool res[N];
int main()
{
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++)
{
scanf("%d", a + i);
}
for (int i = 1; i <= q; i++)
{
auto &[x, k, id] = qry[i];
scanf("%d%d", &x, &k);
id = i;
}
sort(qry + 1, qry + q + 1);
for (int i = 1; i <= q; i++)
{
auto &[x, k, id] = qry[i];
while (idx < x)
{
l = 1, r = n;
while (l < r)
{
mid = (l + r) >> 1;
if (check(idx, mid))
l = mid + 1;
else
r = mid;
}
update(l, 1);
idx++;
}
res[id] = !check(x, k);
}
for (int i = 1; i <= q; i++)
{
puts(res[i] ? "YES" : "NO");
}
}
#include <iostream>
#include <tuple>
using namespace std;
const int N = 2e5 + 10;
int a[N], n, q, tr[N], idx = 1, l, r, mid, req[N];
inline void update(int x, int v)
{
while (x < N)
{
tr[x] += v;
x += (x & -x);
}
}
inline int query(int x)
{
int res = 0;
while (x)
res += tr[x], x -= (x & -x);
return res;
}
inline bool check(int x, int v)
{
return 1ll * a[x] * v <= query(v);
}
int main()
{
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++)
{
scanf("%d", a + i);
}
for (int i = 1; i <= n; i++)
{
l = 1, r = n;
while (l < r)
{
mid = (l + r) >> 1;
if (check(i, mid))
l = mid + 1;
else
r = mid;
}
update(l, 1);
req[i] = l;
}
for (int i = 1, x, k; i <= q; i++)
{
scanf("%d%d", &x, &k);
puts(k < req[x] ? "NO" : "YES");
}
}
thx
By looking at Ur hints one can solve easily. Tx for ur hints specially.
I just read E but yeah this was good shit, nice
Maybe just remove the comments in the code since they are not really necessary...