2022-2023 Southern And Volga Russian Regional

#	User	Rating
1	Radewoosh	3759
2	orzdevinwang	3697
3	jiangly	3662
4	Benq	3644
5	-0.5	3545
6	ecnerwala	3505
7	tourist	3486
8	inaFSTream	3478
9	maroonrk	3454
10	Rebelz	3415

#	User	Contrib.
1	adamant	173
2	awoo	167
3	nor	164
4	SecondThread	162
5	BledDest	161
5	maroonrk	161
5	Um_nik	161
8	-is-this-fft-	149
9	Geothermal	146
10	ko_osaga	142

Idea: BledDest, preparation: awoo

Tutorial

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;
}

1765B - Broken Keyboard

Idea: vovuh, preparation: vovuh

Tutorial

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')

1765C - Card Guessing

Idea: DStepanenko, preparation: BledDest

Tutorial

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;
}

1765D - Watch the Videos

Idea: BledDest, preparation: DmitryKlenov

Tutorial

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;
}

1765E - Exchange

Idea: BledDest, preparation: BledDest

Tutorial

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();
}

1765F - Chemistry Lab

Idea: awoo, preparation: awoo

Tutorial

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;
}

1765G - Guess the String

Idea: BledDest, preparation: BledDest

Tutorial

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);
    }
}

1765H - Hospital Queue

Idea: Neon, preparation: Neon

Tutorial

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 << ' ';
}

1765I - Infinite Chess

Idea: DmitryKlenov, preparation: dmitryme

Tutorial

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;
}

1765J - Hero to Zero

Idea: BledDest, preparation: BledDest

Tutorial

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;
}

1765K - Torus Path

Idea: adedalic, preparation: adedalic

Tutorial

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;
}

1765L - Project Manager

Idea: BledDest, preparation: awoo

Tutorial

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;
}

1765M - Minimum LCM

Idea: BledDest, preparation: Neon

Tutorial

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';
  }
}

1765N - Number Reduction

Idea: Neon, preparation: Neon

Tutorial

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';
  }
}

Comments (28)

Show archived | Write comment?

BledDest

12 months ago, # |

Unfortunately, the editorials for two problems are not ready yet. They will appear here as soon as they're written.

→ Reply

utility

In problem Torus Path wording "Note that you can't visit all vertices on the antidiagonal (vertices .... at the same time." — is quite confusing.

Jackyjuman

can problem N can be solved by using stack data structures ?

Cypher70

12 months ago, # ^ |

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

coding_pigeon

7 months ago, # ^ |

Thanks :)

xioachou

3 months ago, # ^ |

nice solution!

vivekananda1001

5 weeks ago, # ^ |

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?

__Martian

2 weeks ago, # ^ |

https://mirror.codeforces.com/contest/1765/submission/233591731..

The problem K is easily solvable using DP. But the greedy method is quite tricky, at least for me.

2e5

11 months ago, # ^ |

Can you please explain your solution.. And how do you store which cells you have already visited? Thanks in advance

JoshuaYang

10 months ago, # ^ |

I was wondering if DP was possible, but I'm not so experienced with DP, and then I the greedy anyways.

RANJAN888

4 months ago, # ^ |

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??

guess_me_13

Having a problem not understanding the solution to F.

Please, can someone explain it more?

Taha_adeel

11 months ago, # |

The problem D can be done in O(N) using just two pointers.

AC submission: https://mirror.codeforces.com/contest/1765/submission/186659367

KanishkGoel

Sorting does require O(NlogN) operations, you probably meant O(N) operations after sorting.

spkumar9952

Your solution seems ease to understand. Thank you for sharing!. But TC is O(Nlog(N)) because of sorting.

abhayptsr

My implementation for N 187904357 using priorityqueue

computer_jock

can we do N. Neon by using monotonic stack ??

DebugMe

Yes we can. Check out my solution 190315580. I am using string itself to simulate stack.

jatindulani31

10 months ago, # |

Neon Can u plss explain why the limit of for loop in problem M is g * g <= n??

mady07

6 months ago, # ^ |

It is for finding divisor of the number which you will get within root n

berrkannt_

Is there anyone to fail my code ? imo my logic is true and working every test cases that i used. Any help appreciated. 191443868

mixed_juice717

Try:

1
906
2

thanks ^^

Fuddu

How to approach problem K that at max n-1 anti-diagonal elements can be visited editorial proof is understandable but how to approach such a mathematical problem???

hkrai1372

8 months ago, # ^ |

can you explain how at max n-1 anti diagonal elements can be visited. I was unable to understand this part of editorial

ivan100sic

4 months ago, # |

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.

BledDest's blog