Idea: BledDest
#include <bits/stdc++.h>
using namespace std;
const int N = 1000;
int n;
int a[N];
void solve() {
cin >> n;
for (int i = 0; i < n; ++i)
cin >> a[i];
for (int i = 1; i < n - 1; ++i) {
if (a[i] > a[i - 1] && a[i] > a[i + 1]) {
cout << "YES" << endl;
cout << i << ' ' << i + 1 << ' ' << i + 2 << endl;
return;
}
}
cout << "NO" << endl;
}
int main() {
int T;
cin >> T;
while (T--)
solve();
}
Idea: adedalic
fun main() {
val winBy = mapOf('R' to 'P', 'S' to 'R', 'P' to 'S')
repeat(readLine()!!.toInt()) {
val s = readLine()!!
val maxCnt = s.groupingBy { it }.eachCount().maxBy { it.value }!!.key
println("${winBy[maxCnt]}".repeat(s.length))
}
}
Idea: Roms
for _ in range(int(input())):
n, x = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)
res, cur = 0, 1
for s in a:
if s * cur >= x:
res += 1
cur = 0
cur += 1
print(res)
Idea: Roms
#include <bits/stdc++.h>
using namespace std;
const int N = int(2e5) + 9;
int n, m;
long long x, k, y;
int a[N];
int b[N];
bool upd(int l, int r, long long &res) {
if (l > r) return true;
bool canDel = false;
int mx = *max_element(a + l, a + r + 1);
int len = r - l + 1;
if (l - 1 >= 0 && a[l - 1] > mx) canDel = true;
if (r + 1 < n && a[r + 1] > mx) canDel = true;
if (len < k && !canDel) return false;
int need = len % k;
res += need * y;
len -= need;
if (y * k >= x) {
res += len / k * x;
} else if(canDel) {
res += len * y;
} else {
res += (len - k) * y + x;
}
return true;
}
int main(){
scanf("%d %d", &n, &m);
scanf("%lld %lld %lld", &x, &k, &y);
for (int i = 0; i < n; ++i) scanf("%d", a + i);
for (int i = 0; i < m; ++i) scanf("%d", b + i);
long long res = 0;
int lst = -1, posa = 0, posb = 0;
while (posb < m) {
while(posa < n && a[posa] != b[posb]) ++posa;
if (posa == n) {
puts("-1");
return 0;
}
if (!upd(lst + 1, posa - 1, res)) {
puts("-1");
return 0;
}
lst = posa;
++posb;
}
if (!upd(lst + 1, n - 1, res)) {
puts("-1");
return 0;
}
printf("%lld\n", res);
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int N = 200043;
const int L = 20;
vector<int> g[2 * N];
int p[2 * N];
int up[2 * N][L];
int idx[N];
int psum[N];
int cur[N];
int tin[2 * N];
int tout[2 * N];
int T = 0;
void dfs(int x, int y)
{
tin[x] = T++;
p[x] = y;
up[x][0] = y;
for(int i = 1; i < L; i++)
up[x][i] = up[up[x][i - 1]][i - 1];
for(auto z : g[x])
dfs(z, x);
tout[x] = T++;
}
bool is_ancestor(int x, int y)
{
return tin[x] <= tin[y] && tout[x] >= tout[y];
}
int lca(int x, int y)
{
if(is_ancestor(x, y))
return x;
for(int i = L - 1; i >= 0; i--)
if(!is_ancestor(up[x][i], y))
x = up[x][i];
return p[x];
}
int main()
{
int n, m;
scanf("%d %d", &n, &m);
for(int i = 0; i < n; i++)
{
scanf("%d", &idx[i]);
idx[i]--;
}
for(int i = 0; i < m; i++)
cur[i] = i;
for(int i = 0; i < m - 1; i++)
{
int x, y;
scanf("%d %d", &x, &y);
--x;
--y;
int nidx = m + i;
g[nidx].push_back(cur[x]);
g[nidx].push_back(cur[y]);
cur[x] = nidx;
}
int root = m * 2 - 2;
dfs(root, root);
for(int i = 0; i < n - 1; i++)
{
int t = lca(idx[i], idx[i + 1]);
if(t < m)
psum[0]++;
else
psum[t - m + 1]++;
}
for(int i = 0; i < m - 1; i++)
psum[i + 1] += psum[i];
for(int i = 0; i < m; i++)
printf("%d\n", n - 1 - psum[i]);
}
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
int n, m;
vector<int> p;
vector<vector<int>> val;
vector<int> who;
int getp(int a){
return a == p[a] ? a : p[a] = getp(p[a]);
}
int main(){
scanf("%d%d", &n, &m);
p.resize(m);
val.resize(m);
who.resize(n);
int ans = n - 1;
forn(i, m)
p[i] = i;
forn(i, n){
int x;
scanf("%d", &x);
--x;
who[i] = x;
ans -= (i && who[i] == who[i - 1]);
val[who[i]].push_back(i);
}
printf("%d\n", ans);
forn(i, m - 1){
int v, u;
scanf("%d%d", &v, &u);
v = getp(v - 1), u = getp(u - 1);
if (val[v].size() < val[u].size())
swap(v, u);
for (int x : val[u]){
if (x) ans -= who[x - 1] == v;
if (x < n - 1) ans -= who[x + 1] == v;
}
for (int x : val[u]){
val[v].push_back(x);
who[x] = v;
}
p[u] = v;
printf("%d\n", ans);
}
return 0;
}
Idea: Roms
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for(int i = 0; i < int(n); i++)
const int MOD = 998244353;
const int N = 500 * 1000 + 13;
string s;
int add(int a, int b){
a += b;
if (a >= MOD)
a -= MOD;
return a;
}
int mul(int a, int b){
return a * 1ll * b % MOD;
}
struct node{
int val[4], len;
};
node merge(const node &a, const node &b, int l, int r){
node c;
int na = a.len == 1 ? 0 : 1;
int nb = b.len == 1 ? 0 : 2;
c.len = a.len + b.len;
c.val[0] = mul(a.val[na], b.val[nb]);
c.val[1] = mul(a.val[na], b.val[3]);
c.val[2] = mul(a.val[3], b.val[nb]);
c.val[3] = mul(a.val[3], b.val[3]);
if (l == 1){
na = a.len == 1 ? 2 : 0;
nb = b.len == 1 ? 1 : 0;
c.val[na + nb] = add(c.val[na + nb], mul(mul(a.val[0], b.val[0]), 19 - (l * 10 + r)));
c.val[1 + na] = add(c.val[1 + na], mul(mul(a.val[0], b.val[1]), 19 - (l * 10 + r)));
c.val[2 + nb] = add(c.val[2 + nb], mul(mul(a.val[2], b.val[0]), 19 - (l * 10 + r)));
c.val[3] = add(c.val[3], mul(mul(a.val[2], b.val[1]), 19 - (l * 10 + r)));
}
return c;
}
node t[4 * N];
void build(int v, int l, int r){
t[v].len = r - l;
if (l == r - 1){
t[v].val[0] = 1;
t[v].val[3] = s[l] + 1;
return;
}
int m = (l + r) / 2;
build(v * 2, l, m);
build(v * 2 + 1, m, r);
t[v] = merge(t[v * 2], t[v * 2 + 1], s[m - 1], s[m]);
}
void upd(int v, int l, int r, int x, int val){
if (l == r - 1){
s[l] = val;
t[v].val[3] = s[l] + 1;
return;
}
int m = (l + r) / 2;
if (x < m)
upd(v * 2, l, m, x, val);
else
upd(v * 2 + 1, m, r, x, val);
t[v] = merge(t[v * 2], t[v * 2 + 1], s[m - 1], s[m]);
}
int main(){
int n, m;
scanf("%d%d", &n, &m);
static char buf[N];
scanf("%s", buf);
s = buf;
forn(i, n) s[i] -= '0';
memset(t, 0, sizeof(t));
build(1, 0, n);
forn(i, m){
int x, v;
scanf("%d%d", &x, &v);
--x;
upd(1, 0, n, x, v);
printf("%d\n", t[1].val[3]);
}
}
#include <bits/stdc++.h>
using namespace std;
const int N = int(5e5) + 9;
const int MOD = 998244353;
int mul(int a, int b) {
return (a * 1LL * b) % MOD;
}
void add(int &a, int x) {
a += x;
a %= MOD;
}
int bp(int a, int n) {
int res = 1;
for (; n > 0; n >>= 1) {
if (n & 1) res = mul(res, a);
a = mul(a, a);
}
return res;
}
int inv(int a) {
int ia = bp(a, MOD - 2);
assert(mul(a, ia) == 1);
return ia;
}
int n, m;
string s;
int dp[N][10];
int idp[N][10];
set <pair<int, int> > lr;
int res = 1;
void updRes(int l, int r, int c) {
assert(l <= r);
if (c == 1) {
assert(!lr.count(make_pair(l, r)));
lr.insert(make_pair(l, r));
res = mul(res, dp[r - l + (r + 1 != n)][r + 1 == n? 1 : s[r + 1] - '0']);
} else {
assert(lr.count(make_pair(l, r)));
lr.erase(make_pair(l, r));
res = mul(res, inv(dp[r - l + (r + 1 != n)][r + 1 == n? 1 : s[r + 1] - '0']));
}
}
void getLR(int &l, int &r, int pos) {
l = r = -1;
auto it = lr.lower_bound(make_pair(pos, n));
if(it == lr.begin()) return;
--it;
if(!(it->first <= pos && pos <= it->second)) return;
l = it->first, r = it->second;
}
char buf[N];
int main(){
scanf("%d %d\n", &n, &m);
scanf("%s", buf);
s = string(buf);
for (int i = 0; i <= 9; ++i) {
dp[0][i] = i + 1; //idp[0][i] = inv(dp[0][i]);
dp[1][i] = 2 * (i + 1) + (9 - i); //idp[1][i] = inv(dp[1][i]);
}
for (int i = 2; i < N; ++i)
for (int j = 0; j <= 9; ++j) {
dp[i][j] = (2LL * dp[i - 1][j] + 8LL * dp[i - 2][j]) % MOD;
//idp[i][j] = inv(dp[i][j]);
}
for (int i = 0; i < N; ++i) for(int j = 0; j < 10; ++j) assert(dp[i][j] != 0);
for (int l = 0; l < n; ) {
int r = l;
while(r < n && s[r] == '1') ++r;
res = mul(res, dp[r - l - (r == n)][r == n? 1 : s[r] - '0']);
if (l != r) lr.insert(make_pair(l, r - 1));
l = r + 1;
}
for (int i = 0; i < m; ++i) {
int pos;
char x;
scanf("%d %c\n", &pos, &x);
--pos;
if (x == '1') {
if (s[pos] != '1'){
int l1, r1, l2, r2;
getLR(l1, r1, pos - 1);
getLR(l2, r2, pos + 1);
int l = pos, r = pos;
if (l1 != -1) {
assert(r1 == pos - 1);
updRes(l1, r1, -1);
l = l1;
} else {
res = mul(res, inv(dp[0][s[pos] - '0']));
}
if (l2 != -1) {
assert(l2 == pos + 1);
updRes(l2, r2, -1);
r = r2;
} else {
if (pos + 1 != n) res = mul(res, inv(dp[0][s[pos + 1] - '0']));
}
s[pos] = x;
updRes(l, r, 1);
}
} else {
if (s[pos] != '1') {
if (pos - 1 >= 0 && s[pos - 1] == '1') {
int l, r;
getLR(l, r, pos - 1);
updRes(l, r, -1);
s[pos] = x;
updRes(l, r, 1);
} else {
res = mul(res, dp[0][x - '0']);
res = mul(res, inv(dp[0][s[pos] - '0']));
s[pos] = x;
}
} else {
int l, r;
getLR(l, r, pos);
assert(l != -1 && r != -1);
updRes(l, r, -1);
s[pos] = x;
if (l == r) {
res = mul(res, dp[0][s[pos] - '0']);
if (pos + 1 < n) res = mul(res, dp[0][s[pos + 1] - '0']);
} else if (pos == l) {
res = mul(res, dp[0][s[pos] - '0']);
updRes(l + 1, r, 1);
} else if (pos == r) {
if (pos + 1 != n) res = mul(res, dp[0][s[pos + 1] - '0']);
updRes(l, r - 1, 1);
} else {
updRes(l, pos - 1, 1);
updRes(pos + 1, r, 1);
}
}
}
printf("%d\n", res);
}
}
Idea: BledDest
At first, let's say that the expected value is equal to the average of total earnings over all positions and is equal to the sum of earnings over all positions divided by $$$n$$$. So we can trasition to minimizing the sum.
Let's learn how to solve the task for some fixed $$$k$$$. Fix some arrangement and rotate the rooms so that the last room contains a mimic. So now you have $$$cnt_1$$$ regular chests, then a single mimic, $$$cnt_2$$$ regular chests, single mimic, $$$\dots$$$, $$$cnt_k$$$ regular chests, single mimic. All $$$cnt_i \ge 0$$$ and $$$\sum \limits_{i=1}^{k} cnt_i = n - k$$$.
Take a look at some of these intervals of length $$$cnt_i$$$. The last chest in the interval is taken from $$$cnt_i$$$ starting positions, the second-to-last is taken $$$cnt_i - 1$$$ times and so on.
Now let's find the optimal way to choose $$$cnt_i$$$. Fix some values of $$$cnt_i$$$. Take a look at the smallest of these values and the largest of them. Let the values be $$$x$$$ and $$$y$$$. If they differ by at least $$$2$$$ ($$$x \le y - 2$$$), then the smaller result can always be achieved by moving a regular chest from the larger one to the smaller one.
Consider two sequences of coefficients for both intervals: $$$[1, 2, \dots, x - 1, x]$$$ and $$$[1, 2, \dots, y - 1, y]$$$.
However, if you remove one chest, then they will be equal to $$$[1, 2, \dots, x - 1, x, x + 1]$$$ and $$$[1, 2, \dots, y - 1]$$$.
If you only consider the difference between the numbers of both sequences, then you can see that only coefficient $$$y$$$ got removed and coefficient $$$x + 1$$$ was added. So you can rearrange the chests in such a way that all chests are assigned to the same value and only the chest that was assigned to $$$y$$$ becomes assigned to $$$x+1$$$, thus decreasing the total value.
Now we have all $$$cnt_i$$$ set now. The only thing left is to assign chests optimally. Write down the union of all the coefficient sequences from all the intervals $$$\bigcup \limits_{i=1}^{n-k} [1, \dots, cnt_i-1, cnt_i]$$$ and sort them in the non-decreasing order. It's easy to show that the chests should be sorted in the non-increasing order (really classical thing, you can try proving that by showing that any other arrangement can easily be improved once again).
That allows us to write a solution in $$$O(n^2)$$$. Sort all the chests in the beginning, after that for some $$$k$$$ multiply the value of the $$$i$$$-th chest by $$$\lfloor \frac{i}{k} \rfloor$$$ and sum up the results.
Finally, let's speed this up with prefix sums. Notice that the first $$$k$$$ values are multiplied by $$$0$$$, the second $$$k$$$ values — by $$$1$$$ and so on. If $$$n$$$ is not divisible by $$$k$$$, then the last block just has length smaller than $$$k$$$. Thus, we can calculate the answer for some $$$k$$$ in $$$O(\frac{n}{k})$$$. And that's equal to $$$O(\sum \limits_{k=1}^{n} \frac{n}{k})$$$ = $$$O(n \log n)$$$.
Overall complexity: $$$O(n \log n)$$$.
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int MOD = 998244353;
int add(int a, int b){
a += b;
if (a >= MOD)
a -= MOD;
if (a < 0)
a += MOD;
return a;
}
int mul(int a, int b){
return a * 1ll * b % MOD;
}
int binpow(int a, int b){
int res = 1;
while (b){
if (b & 1)
res = mul(res, a);
a = mul(a, a);
b >>= 1;
}
return res;
}
vector<int> pr;
int main() {
int n;
scanf("%d", &n);
vector<int> c(n);
forn(i, n)
scanf("%d", &c[i]);
sort(c.begin(), c.end(), greater<int>());
pr.push_back(0);
forn(i, n)
pr.push_back(add(pr.back(), c[i]));
int invn = binpow(n, MOD - 2);
for (int k = 1; k <= n; ++k){
int ans = 0;
for (int i = 0, j = 0; i < n; i += k, ++j)
ans = add(ans, mul(j, add(pr[min(n, i + k)], -pr[i])));
printf("%d ", mul(ans, invn));
}
puts("");
return 0;
}