Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int x, y;
cin >> x >> y;
int d = x * x + y * y;
int r = 0;
while (r * r < d) ++r;
int ans = 2;
if (r * r == d) ans = 1;
if (x == 0 && y == 0) ans = 0;
cout << ans << '\n';
}
}
Idea: adedalic
Tutorial
Tutorial is loading...
Solution (adedalic)
fun main() {
repeat(readLine()!!.toInt()) {
val (n, B, x, y) = readLine()!!.split(' ').map { it.toInt() }
var cur = 0L
var ans = 0L
for (i in 1..n) {
cur += if (cur + x <= B) x else -y
ans += cur
}
println(ans)
}
}
1657C - Bracket Sequence Deletion
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (vovuh)
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int t;
cin >> t;
while (t--) {
int n;
string s;
cin >> n >> s;
int l = 0;
int cnt = 0;
while (l + 1 < n) {
if (s[l] == '(' || (s[l] == ')' && s[l + 1] == ')')) {
l += 2;
} else {
int r = l + 1;
while (r < n && s[r] != ')') {
++r;
}
if (r == n) {
break;
}
l = r + 1;
}
++cnt;
}
cout << cnt << ' ' << n - l << '\n';
}
return 0;
}
1657D - For Gamers. By Gamers.
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); ++i)
int main(){
int n, C;
scanf("%d%d", &n, &C);
vector<long long> bst(C + 1);
forn(i, n){
int c, d, h;
scanf("%d%d%d", &c, &d, &h);
bst[c] = max(bst[c], d * 1ll * h);
}
for (int c = 1; c <= C; ++c) for (int xc = c; xc <= C; xc += c)
bst[xc] = max(bst[xc], bst[c] * (xc / c));
forn(c, C)
bst[c + 1] = max(bst[c + 1], bst[c]);
int m;
scanf("%d", &m);
forn(j, m){
int D;
long long H;
scanf("%d%lld", &D, &H);
int mn = upper_bound(bst.begin(), bst.end(), D * H) - bst.begin();
if (mn > C) mn = -1;
printf("%d ", mn);
}
puts("");
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); ++i)
const int MOD = 998244353;
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;
}
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;
}
int main(){
int n, k;
scanf("%d%d", &n, &k);
--n;
vector<vector<int>> dp(k + 1, vector<int>(n + 1, 0));
vector<vector<int>> C(n + 1);
forn(i, n + 1){
C[i].resize(i + 1);
C[i][0] = C[i][i] = 1;
for (int j = 1; j < i; ++j)
C[i][j] = add(C[i - 1][j], C[i - 1][j - 1]);
}
dp[0][0] = 1;
forn(i, k) forn(t, n + 1) {
int pw = binpow(k - i, t * (t - 1) / 2);
int step = binpow(k - i, t);
forn(j, n - t + 1){
dp[i + 1][j + t] = add(dp[i + 1][j + t], mul(dp[i][j], mul(C[n - j][t], pw)));
pw = mul(pw, step);
}
}
printf("%d\n", dp[k][n]);
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); ++i)
vector<vector<int>> t;
vector<int> p, h;
void init(int v){
for (int u : t[v]) if (u != p[v]){
p[u] = v;
h[u] = h[v] + 1;
init(u);
}
}
vector<int> get_path(int v, int u){
vector<int> l, r;
while (v != u){
if (h[v] > h[u]){
l.push_back(v);
v = p[v];
}
else{
r.push_back(u);
u = p[u];
}
}
l.push_back(v);
while (!r.empty()){
l.push_back(r.back());
r.pop_back();
}
return l;
}
vector<vector<int>> g, tg;
void add_edge(int v, bool vx, int u, bool vy){
// (val[v] == vx) -> (val[u] == vy)
g[v * 2 + vx].push_back(u * 2 + vy);
tg[u * 2 + vy].push_back(v * 2 + vx);
g[u * 2 + !vy].push_back(v * 2 + !vx);
tg[v * 2 + !vx].push_back(u * 2 + !vy);
}
vector<int> ord;
vector<char> used;
void ts(int v){
used[v] = true;
for (int u : g[v]) if (!used[u])
ts(u);
ord.push_back(v);
}
vector<int> clr;
int k;
void dfs(int v){
clr[v] = k;
for (int u : tg[v]) if (clr[u] == -1)
dfs(u);
}
int main(){
cin.tie(0);
iostream::sync_with_stdio(false);
int n, m;
cin >> n >> m;
t.resize(n);
p.resize(n);
h.resize(n);
p[0] = -1;
forn(i, n - 1){
int v, u;
cin >> v >> u;
--v, --u;
t[v].push_back(u);
t[u].push_back(v);
}
init(0);
vector<vector<int>> paths(m);
vector<string> s(m);
vector<pair<char, char>> opts(n, make_pair(-1, -1));
forn(i, m){
int v, u;
cin >> v >> u >> s[i];
--v, --u;
paths[i] = get_path(v, u);
int k = s[i].size();
assert(int(paths[i].size()) == k);
forn(j, k) opts[paths[i][j]] = {s[i][j], s[i][k - j - 1]};
}
int nm = (n + m) * 2;
g.resize(nm);
tg.resize(nm);
forn(i, m){
int k = s[i].size();
forn(j, k){
int v = paths[i][j];
char c = s[i][j], rc = s[i][k - j - 1];
char d = opts[v].first, rd = opts[v].second;
if (d != c) add_edge(v, false, n + i, true);
if (d != rc) add_edge(v, false, n + i, false);
if (rd != c) add_edge(v, true, n + i, true);
if (rd != rc) add_edge(v, true, n + i, false);
}
}
used.resize(nm);
forn(i, nm) if (!used[i]) ts(i);
clr.resize(nm, -1);
reverse(ord.begin(), ord.end());
for (int v : ord) if (clr[v] == -1){
dfs(v);
++k;
}
forn(i, nm) if (clr[i] == clr[i ^ 1]){
cout << "NO\n";
return 0;
}
cout << "YES\n";
for (int i = 0; i < 2 * n; i += 2){
if (opts[i / 2].first == -1)
cout << 'a';
else if (clr[i] > clr[i ^ 1])
cout << opts[i / 2].first;
else
cout << opts[i / 2].second;
}
cout << "\n";
}
If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table to increase/decrease the constraints.
If you are not able to find a counter example even after changing the parameters, reply to this thread, mentioning the contest_id, problem_index and submission_id.
Ignore
video solution in Hindi -problem A Integer moves
video solution in Hindi-problem B XY sequence
BledDest thank you for such an interesting and good task D. I hope there will be more similar tasks
Update:-I got it from the editorial thank u authors.
can someone please explain me the problem e i m unable to get it from the editorial.
Thanks in advance.
There are two different $$$k$$$ in the editorial of E.
I can't understand this line from the D's tutorial. Can anyone help? You can see that for each cost c we can only leave one unit type of that price that has the largest value of d⋅h. Let's call it bstc. Thank you, in advance.
suppose we have warriors h1,d1,c and h2, d2, c. They have the same cost. In this case we can pick one which have greater h * d and discard another from consideration. In other words for each 1 <= c <= C we can keep max 1 warrior with highest d * h
Thank you @Alexey.
E is very beautiful! Thank you.
In problem C if I give the input as ())( then the expected output should be 1 0 as the given input is a palindrome, but the solution provided in the editorial gives 1 2 as the output when run, which means that we have to leave the last 2 characters in the string, I don't understand how 1 2 is considered correct, can someone please explain. Thanks in advance.
you've probably figured but () is a good substring and it is shorter than ())(
In problem C, if we give the input : 5 ((((( the expected answer ACC to editorial is 2 1. However, I feel it should be 1 0 because it is already a palindrome and it will take only 1 operation to delete it. Can someone kindly point out where's the flaw in my thinking process?
Because You have to always take the shortest prefix meaning (( and (( and (.
in case of problem A if I choose point 20,23 how can i reach their in 2 moves?
maybe? 0,0 -> 20,0 -> 20,23
Greedy algo for F (that might just be a special case of 2sat in the end? idk):
Dumb greedy: Place a string, then dfs to its intersecting string neighbors and try to fix those, and so on.
But this isn't correct: if you look at the cases where for a string $$$S$$$, flipping its neighbor $$$T$$$ both ways both work, then the algorithm can't decide which way to fix $$$T$$$.
But if flipping $$$T$$$ both ways works, that must necessarily mean that the nodes at $$$T \cap S$$$ are fixed letters. So just don't consider nodes with fixed letters as intersecting anymore; two strings are only intersecting if they share a node s.t. two letters are possible.
Now you can actually make the binary choice at each intersection, so greedy string fixing dfs works.
Time complexity is still $$$\widetilde{\mathcal{O}}(n + q + \sum_i^q|s_j|)$$$
The idea is similar to this problem
Implementation here, could be a lot cleaner.