Idea: BledDest, preparation: awoo
Tutorial
Tutorial is loading...
Solution (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
int n, m, m2;
vector<vector<char>> g;
int T;
vector<int> mt;
vector<int> used;
bool try_kuhn(int v){
if (used[v] == T)
return false;
used[v] = T;
forn(u, m2) if (g[v][u] && (mt[u] == -1 || try_kuhn(mt[u]))){
mt[u] = v;
return true;
}
return false;
}
int main() {
cin >> n >> m;
vector<string> b(m, string(n, '0'));
forn(i, n){
string t;
cin >> t;
forn(j, m) b[j][i] = t[j];
}
vector<string> nw = b;
sort(nw.begin(), nw.end());
nw.resize(unique(nw.begin(), nw.end()) - nw.begin());
m2 = nw.size();
g.assign(m2, vector<char>(m2, 0));
forn(i, m2) forn(j, m2) if (i != j){
bool in = true;
forn(k, n) in &= nw[i][k] >= nw[j][k];
if (in) g[i][j] = 1;
}
mt.assign(m2, -1);
used.assign(m2, -1);
T = 0;
int k = m2;
forn(i, m2) if (try_kuhn(i)){
++T;
--k;
}
vector<int> nxt(m2, -1);
vector<char> st(m2, true);
forn(i, m2) if (mt[i] != -1){
nxt[mt[i]] = i;
st[i] = false;
}
vector<int> gr(m2), req(m2);
int t = 0;
forn(i, m2) if (st[i]){
int v = i;
int pos = 2;
while (v != -1){
gr[v] = t;
req[v] = pos;
++pos;
v = nxt[v];
}
++t;
}
assert(t == k);
vector<int> num(m);
forn(i, m) num[i] = lower_bound(nw.begin(), nw.end(), b[i]) - nw.begin();
printf("%d\n", k);
forn(i, m) printf("%d ", gr[num[i]] + 1);
puts("");
forn(i, m) printf("%d ", req[num[i]]);
puts("");
forn(i, n){
vector<int> l(k, 1);
forn(j, m2) if (nw[j][i] == '1')
l[gr[j]] = max(l[gr[j]], req[j]);
forn(j, k)
printf("%d ", l[j]);
puts("");
}
return 0;
}
Idea: vovuh, preparation: vovuh
Tutorial
Tutorial is loading...
Solution (vovuh)
for _ in range(int(input())):
n = int(input())
s = input()
print('YES' if n % 3 != 2 and not False in [s[i * 3 + 1] == s[i * 3 + 2] for i in range(n // 3)] else 'NO')
Idea: DStepanenko, preparation: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define fore(i, l, r) for (int i = int(l); i < int(r); i++)
using namespace std;
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);
vector<int> fact(4 * n + 1);
fact[0] = 1;
fore(i, 1, fact.size()) fact[i] = mul(fact[i - 1], i);
vector<int> rfact(4 * n + 1);
rfact.back() = binpow(fact.back(), MOD - 2);
for (int i = int(fact.size()) - 2; i >= 0; --i)
rfact[i] = mul(rfact[i + 1], i + 1);
auto cnk = [&](int n, int k){
return mul(fact[n], mul(rfact[k], rfact[n - k]));
};
vector<vector<int>> sv(n + 1, vector<int>(5));
forn(i, n + 1) forn(t, 5) sv[i][t] = mul(binpow(cnk(n, i), t), rfact[t]);
vector<vector<vector<int>>> dp(2, vector<vector<int>>(4 * n + 1, vector<int>(5)));
forn(ii, n + 1){
int i = ii & 1;
int ni = i ^ 1;
dp[ni] = vector<vector<int>>(4 * n + 1, vector<int>(5));
for (int t = 1; t <= 4; ++t)
dp[ni][ii * t][t] = mul(n - ii, sv[ii][t]);
forn(j, k + 1) for (int p = 1; p <= 4; ++p) if (dp[i][j][p]){
dp[ni][j][p] = add(dp[ni][j][p], dp[i][j][p]);
for (int t = 1; p + t <= 4; ++t)
dp[ni][j + ii * t][p + t] = add(dp[ni][j + ii * t][p + t], mul(dp[i][j][p], sv[ii][t]));
}
}
int ans = 0;
forn(sum, k + 1){
ans = add(ans, mul(mul(mul(
sum < k ? 1 : 4 * n - k,
dp[(n & 1) ^ 1][sum][4]),
mul(binpow(4 * n - sum, MOD - 2), mul(rfact[4 * n], fact[4 * n - sum]))),
mul(fact[4], fact[sum]))
);
}
printf("%d\n", ans);
return 0;
}
Idea: BledDest, preparation: DmitryKlenov
Tutorial
Tutorial is loading...
Solution (DmitryKlenov)
#include <iostream>
#include <algorithm>
using namespace std;
#define N 200000
int a[N], n, s;
bool can(int x) {
int l = x - 1, r = n - 1;
while (l < r) {
if (a[r] > s - a[l]) return false;
++l;
if (l < r) {
if (a[l] > s - a[r]) return false;
--r;
}
}
return true;
}
int main() {
long long sum = 0;
scanf("%d %d\n", &n, &s);
for(int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
sum += a[i];
}
sort(a, a + n, greater<int>());
int l = 1, r = n;
while (l < r) {
int m = (l + r) >> 1;
if (can(m)) r = m;
else l = m + 1;
}
long long ans = sum + r;
cout << ans << endl;
return 0;
}
Idea: BledDest, preparation: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include <bits/stdc++.h>
using namespace std;
void solve()
{
int n, a, b;
cin >> n >> a >> b;
int x = (n + a - 1) / a;
if(a > b) x = 1;
cout << x << endl;
}
int main()
{
int t;
cin >> t;
for(int i = 0; i < t; i++)
solve();
}
Tutorial
Tutorial is loading...
Solution (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
typedef long long li;
const li INF64 = 1e18;
struct base{
int x, w, c;
};
li area(const base &a, const base &b){
return (a.c + b.c) * li(abs(a.x - b.x));
}
int main() {
int n, k;
scanf("%d%d", &n, &k);
vector<base> a(n);
forn(i, n) scanf("%d%d%d", &a[i].x, &a[i].w, &a[i].c);
sort(a.begin(), a.end(), [](const base &a, const base &b){ return a.x > b.x; });
vector<li> dp(n, -INF64);
li ans = 0;
forn(i, n){
dp[i] = max(dp[i], -a[i].w * 200ll);
for (int j = i + 1; j < n; ++j)
dp[j] = max(dp[j], dp[i] + area(a[i], a[j]) * k - a[j].w * 200ll);
ans = max(ans, dp[i]);
}
printf("%.15Lf\n", ans / (long double)(200));
return 0;
}
Idea: BledDest, preparation: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(42);
uniform_int_distribution<int> d(1, 2);
int ask(int t, int i)
{
cout << t << " " << i + 1 << endl;
int x;
cin >> x;
return x;
}
void giveAnswer(const string& s)
{
cout << 0 << " " << s << endl;
int x;
cin >> x;
assert(x == 1);
}
void guessOne(string& s, int i)
{
int res = ask(1, i);
if(res == 0)
s[i] = '1';
else
s[i] = s[res - 1];
}
char inv(char c)
{
if(c == '0') return '1';
return '0';
}
void guessTwo(string& s, int i)
{
if(s[1] == '0')
{
if(d(rnd) == 1)
{
int res = ask(1, i);
if(res >= 2)
{
s[i] = s[res - 1];
s[i - 1] = s[res - 2];
}
else if(res == 1)
{
s[i] = '0';
s[i - 1] = '1';
}
else
{
s[i] = '1';
guessOne(s, i - 1);
}
}
else
{
int res = ask(2, i);
if(res >= 2)
{
s[i] = inv(s[res - 1]);
s[i - 1] = inv(s[res - 2]);
}
else if(res == 1)
{
s[i] = '1';
s[i - 1] = '0';
}
else
{
s[i] = '0';
guessOne(s, i - 1);
}
}
}
else
{
if(d(rnd) == 1)
{
int res = ask(1, i);
if(res >= 2)
{
s[i] = s[res - 1];
s[i - 1] = s[res - 2];
}
else if(res == 1)
{
s[i] = '0';
guessOne(s, i - 1);
}
else
{
s[i] = '1';
s[i - 1] = '1';
}
}
else
{
int res = ask(2, i);
if(res >= 2)
{
s[i] = inv(s[res - 1]);
s[i - 1] = inv(s[res - 2]);
}
else if(res == 1)
{
s[i] = '1';
guessOne(s, i - 1);
}
else
{
s[i] = '0';
s[i - 1] = '0';
}
}
}
}
int main()
{
int t;
cin >> t;
for(int i = 0; i < t; i++)
{
int n;
cin >> n;
string s(n, '0');
for(int j = 1; j < n; j += 2)
{
if(j == 1) guessOne(s, j);
else guessTwo(s, j);
}
if(n % 2 == 1) guessOne(s, n - 1);
giveAnswer(s);
}
}
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int n, m;
cin >> n >> m;
vector<int> a(n);
for (auto &x : a) cin >> x;
vector<vector<int>> g(n);
for (int i = 0; i < m; ++i) {
int x, y;
cin >> x >> y;
g[y - 1].push_back(x - 1);
}
vector<int> ans(n, -1);
for (int s = 0; s < n; ++s) {
vector<int> deg(n);
for (int i = 0; i < n; ++i)
for (int j : g[i]) ++deg[j];
priority_queue<pair<int, int>> q;
for (int v = 0; v < n; ++v)
if (deg[v] == 0 && v != s)
q.push({a[v], v});
for (int i = n; i > 0; --i) {
if (q.empty() || q.top().first < i) {
if (deg[s] == 0 && i <= a[s])
ans[s] = i;
break;
}
int v = q.top().second;
q.pop();
for (int u : g[v]) {
--deg[u];
if (deg[u] == 0 && u != s)
q.push({a[u], u});
}
}
}
for (int &x : ans) cout << x << ' ';
}
Idea: DmitryKlenov, preparation: dmitryme
Tutorial
Tutorial is loading...
Solution (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const string al = "KQRBN";
const int INF = 1e9;
struct mv{ int dx, dy; };
struct piece{ int x, y, t; };
struct seg{ int l, r; };
struct pos{ int x, y; };
bool operator <(const pos &a, const pos &b){
if (a.x != b.x) return a.x < b.x;
return a.y < b.y;
}
vector<vector<mv>> mvs({
{{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}},
{{-1, 0}, {0, 1}, {1, 0}, {0, -1}, {-1, -1}, {1, -1}, {1, 1}, {-1, 1}},
{{-1, 0}, {0, 1}, {1, 0}, {0, -1}},
{{-1, -1}, {1, -1}, {1, 1}, {-1, 1}},
{{-2, -1}, {-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}}
});
int main() {
int sx, sy, fx, fy;
cin >> sx >> sy >> fx >> fy;
swap(sx, sy), swap(fx, fy);
--sx, --fx;
int k;
cin >> k;
vector<piece> a(k);
forn(i, k){
string t;
cin >> t >> a[i].x >> a[i].y;
swap(a[i].x, a[i].y);
--a[i].x;
a[i].t = al.find(t[0]);
}
sort(a.begin(), a.end(), [](const piece &a, const piece &b){
if (a.x != b.x) return a.x < b.x;
return a.y < b.y;
});
vector<int> base({sy, fy});
forn(i, k) base.push_back(a[i].y);
vector<int> ys;
for (int y : base) for (int i = y - 16; i <= y + 16; ++i)
ys.push_back(i);
sort(ys.begin(), ys.end());
ys.resize(unique(ys.begin(), ys.end()) - ys.begin());
vector<vector<char>> tk(8, vector<char>(ys.size()));
forn(i, k){
a[i].y = lower_bound(ys.begin(), ys.end(), a[i].y) - ys.begin();
tk[a[i].x][a[i].y] = true;
}
sy = lower_bound(ys.begin(), ys.end(), sy) - ys.begin();
fy = lower_bound(ys.begin(), ys.end(), fy) - ys.begin();
vector<vector<char>> bad = tk;
forn(i, k){
int x = a[i].x, y = a[i].y;
if (a[i].t == 0 || a[i].t == 4){
for (auto it : mvs[a[i].t]){
int nx = x + it.dx;
int ny = y + it.dy;
if (0 <= nx && nx < 8)
bad[nx][ny] = true;
}
}
else{
for (auto it : mvs[a[i].t]){
for (int nx = x + it.dx, ny = y + it.dy; ; nx += it.dx, ny += it.dy){
if (nx < 0 || nx >= 8) break;
if (ny < 0 || ny >= int(ys.size())) break;
if (tk[nx][ny]) break;
bad[nx][ny] = true;
}
}
}
}
vector<vector<int>> d(8, vector<int>(ys.size(), INF));
vector<vector<pos>> p(8, vector<pos>(ys.size()));
set<pair<int, pos>> q;
d[sx][sy] = 0;
q.insert({0, {sx, sy}});
while (!q.empty()){
int x = q.begin()->second.x;
int y = q.begin()->second.y;
q.erase(q.begin());
if (x == fx && y == fy){
cout << d[x][y] << endl;
return 0;
}
for (int ny : {y - 1, y, y + 1}){
if (ny < 0 || ny >= int(ys.size())) continue;
int dy = max(1, abs(ys[y] - ys[ny]));
for (int nx = max(0, x - 1); nx <= min(7, x + 1); ++nx) if (!bad[nx][ny]){
int nd = d[x][y] + dy;
if (d[nx][ny] > nd){
q.erase({d[nx][ny], {nx, ny}});
d[nx][ny] = nd;
p[nx][ny] = {x, y};
q.insert({d[nx][ny], {nx, ny}});
}
}
}
}
cout << -1 << endl;
return 0;
}
Idea: BledDest, preparation: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
scanf("%d", &n);
vector<int> a(n), b(n);
for(int i = 0; i < n; i++) scanf("%d", &a[i]);
for(int i = 0; i < n; i++) scanf("%d", &b[i]);
sort(a.begin(), a.end());
sort(b.begin(), b.end());
long long total = 0;
for(int i = 0; i < n; i++)
{
total += n * 1ll * (a[i] + b[i]);
total -= a[i] * 2ll * (b.end() - lower_bound(b.begin(), b.end(), a[i]));
total -= b[i] * 2ll * (a.end() - upper_bound(a.begin(), a.end(), b[i]));
}
for(int i = 0; i < n; i++)
total -= (n - 1) * 1ll * abs(a[i] - b[i]);
cout << total << endl;
}
Idea: adedalic, preparation: adedalic
Tutorial
Tutorial is loading...
Solution (adedalic)
#include<bits/stdc++.h>
using namespace std;
int n;
vector< vector<int> > a;
bool read() {
if (!(cin >> n))
return false;
a.resize(n, vector<int>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
cin >> a[i][j];
}
return true;
}
void solve() {
long long sum = 0;
for (int i = 0; i < n; i++)
sum += accumulate(a[i].begin(), a[i].end(), 0LL);
int mn = a[0][n - 1];
for (int i = 0; i < n; i++)
mn = min(mn, a[i][n - 1 - i]);
cout << sum - mn << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
Idea: BledDest, preparation: awoo
Tutorial
Tutorial is loading...
Solution (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const string days[] = {"Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"};
int main() {
cin.tie(0);
iostream::sync_with_stdio(false);
int n, m, k;
cin >> n >> m >> k;
vector<vector<char>> ds(n, vector<char>(7));
forn(i, n){
int t;
cin >> t;
forn(_, t){
string s;
cin >> s;
ds[i][find(days, days + 7, s) - days] = true;
}
}
vector<int> h(m);
forn(i, m) cin >> h[i];
vector<vector<int>> a(k);
forn(i, k){
int p;
cin >> p;
a[i].resize(p);
forn(j, p){
cin >> a[i][j];
--a[i][j];
}
}
int j = 0;
vector<int> ans(k, -1), lst(k);
int done = 0;
vector<map<int, int>> cur(7);
vector<set<int>> wk(n);
forn(i, k) forn(j, 7) if (ds[a[i][0]][j])
++cur[j][a[i][0]];
forn(i, k)
wk[a[i][0]].insert(i);
for (int d = 1;; ++d){
if (j < m && h[j] == d){
++j;
continue;
}
int wd = (d - 1) % 7;
vector<int> now, sv;
for (auto it : cur[wd]) now.push_back(it.first);
for (int x : now){
forn(i, 7){
auto it = cur[i].find(x);
if (it != cur[i].end()){
if (it->second == 1)
cur[i].erase(it);
else
--it->second;
}
}
int y = *wk[x].begin();
sv.push_back(y);
wk[x].erase(wk[x].begin());
}
forn(i, now.size()){
int y = sv[i];
++lst[y];
if (lst[y] == int(a[y].size())){
ans[y] = d;
++done;
continue;
}
wk[a[y][lst[y]]].insert(y);
forn(j, 7) if (ds[a[y][lst[y]]][j])
++cur[j][a[y][lst[y]]];
}
if (done == k) break;
}
forn(i, k) cout << ans[i] << " ";
cout << endl;
}
Idea: BledDest, preparation: Neon
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int a = 1;
for (int g = 2; g * g <= n; ++g) {
if (n % g == 0) {
a = n / g;
break;
}
}
cout << a << ' ' << n - a << '\n';
}
}
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--) {
string x;
cin >> x;
int k;
cin >> k;
int n = x.size();
vector<vector<int>> pos(10);
for (int i = 0; i < n; ++i)
pos[x[i] - '0'].push_back(i);
for (int i = 0; i < 10; ++i)
reverse(pos[i].begin(), pos[i].end());
string ans;
int lst = 0, len = n - k;
for (int i = 0; i < len; ++i) {
for (int d = (i == 0); d <= 9; ++d) {
while (!pos[d].empty() && pos[d].back() < lst)
pos[d].pop_back();
if (!pos[d].empty() && pos[d].back() - lst <= k) {
ans += d + '0';
k -= pos[d].back() - lst;
lst = pos[d].back() + 1;
break;
}
}
}
cout << ans << '\n';
}
}
Unfortunately, the editorials for two problems are not ready yet. They will appear here as soon as they're written.
it's been more than a year and the editorials are still not ready yet
it's been more than 2 years but the editorials are still not ready yet
Still no editorial for Problem 1765M
In problem Torus Path wording "Note that you can't visit all vertices on the antidiagonal (vertices .... at the same time." — is quite confusing.
can problem N can be solved by using stack data structures ?
Yes indeed! You need to check for all 1 <= i <= n-1, if s[i] > s[i+1] then we can delete s[i] to obtain a smaller number. You will continue doing this till k is 0. One special case, when stack's first element is greater than 0 and all the remaining values are 0, when placing a value x > 0 and x < stack.top, if k >= stack size, delete all the elements from the stack and push the current one . P.S — You need vector to do this stack operation. Check my submission
nice solution!
I liked your implementation! This code indeed requires a good sense of implementation! How did you come up with this?
Have you done similar problems before?
https://codeforces.net/contest/1765/submission/233591731..
The problem K is easily solvable using DP. But the greedy method is quite tricky, at least for me.
Can you please explain your solution.. And how do you store which cells you have already visited? Thanks in advance
In your code,using 'for loop', you have have handled the case of going from last to first within a row.But you have not done anything in case of going from last column to first column,whenever lvl==n if prev!=n-1 , you are just returning INT_MIN.why have you ignored that case??
Do you have some kind of proof why the answer would be moving y-axis wise and not x-axis wise. In ur code, the incrementing lvl parameter is a sifn of u are moving yaxis wise
The for loop iterates over x-axis.The modulo operation handles the case of going from last to first column.
The problem D can be done in O(N) using just two pointers.
AC submission: https://codeforces.net/contest/1765/submission/186659367
Sorting does require O(NlogN) operations, you probably meant O(N) operations after sorting.
Your solution seems ease to understand. Thank you for sharing!. But TC is O(Nlog(N)) because of sorting.
Is there anyone to fail my code ? imo my logic is true and working every test cases that i used. Any help appreciated. 191443868
Try:
Thank you BledDest for one of the most beautiful problems I've recently seen (J).
In problem G, using the exact same idea from the editorial, and going backwards from the end instead of forwards, you end up with $$$1000/1.5 \approx 667$$$ steps on average. Even better, when you get a reply $$$x > 2$$$, you can find $$$x$$$ values in one move.
The only observation I made in problem H is its a "DAG" in entire day.one could go to hospital and stand in queue and come back, even then I am trying to solve this problem lol and I found that N<=2000 after an entire day one more thing to make me laugh
"and at least j values that are not less than aj (let's call them Group B)"
in the editorial for D, I think instead of $$$a_j$$$ it should $$$a_{n-j+1}$$$