Codeforces Round 880 Editorial

№	Пользователь	Рейтинг
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	155
8	TheScrasse	154
9	Dominater069	153
10	nor	152

Author: kempusss
Developer: kempusss
First solve: Tima9

Tutorial

Solution

#include <bits/stdc++.h>
using namespace std;
 
const int N = 1e6;
 
int main()
{
    int cases;
    scanf("%d", &cases);
    
    while (cases--) {
    	int n;
    	scanf ("%d", &n);
    	
    	vector <int> cnt(n + 1);
    	for (int i = 0; i < n; i++) {
    		int d;
    		scanf("%d", &d);
    		if (d < n) {
        		cnt[d]++;
    		} else {
    		    cnt[n] = N;
    		}
    	}
    	
    	bool good = true;
    	for (int i = 1; i <= n; i++) if (cnt[i] > cnt[i-1]) {
    	    good = false;
    	    break;
    	}
    	
    	puts(good ? "YES" : "NO");
    }
}

1836B - Astrophysicists

Author: Fly_37
Developer: Okrut
First solve: NTR_Lover

Tutorial

Solution

#include "bits/stdc++.h"
using namespace std;
 
int main()
{
	int t;
	scanf ("%d", &t);
	while (t--) {
		long long n, k, g;
		scanf ("%lld %lld %lld", &n, &k, &g);
 
		long long stolen = min((g - 1) / 2 * n, k * g);
		long long rest = (k * g - stolen) % g;
 
		if (rest > 0) {
		    stolen -= (g - 1) / 2;
		    long long last = ((g - 1) / 2 + rest) % g;
 
		    if (last * 2 < g) {
		        stolen += last;
		    } else {
		        stolen -= g - last;
		    }
		}
 
		printf ("%lld\n", stolen);
	}
}

1836C - k-th equality / 1835A - k-th equality

Author: Okrut
Developer: w0nsh
First solve: NTR_Lover / ksun48

Tutorial

Solution

#include <bits/stdc++.h>

int power(int a, int e) {
    if (e == 0) return 1;
    return e == 1 ? a : a * power(a, e-1);
}

void answer(int a, int b) {
    std::cout << a << " + " << b << " = " << a+b << std::endl;
}

int main() {
    using ll = long long;
    
    int t;
    std::cin >> t;
    while (t--) {

        int a, b, c;
        ll k;
        std::cin >> a >> b >> c >> k;
        
        bool good = false;
    
        for (int i = power(10, a-1); i < power(10, a); ++i) {
            int left = std::max(power(10, b-1), power(10, c-1) - i);
            int right = std::min(power(10, b)-1, power(10, c) - 1 - i);
            if (left > right) continue;
    
            int have = right - left + 1;
            if (k <= have) {
                answer(i, left + k - 1);
                good = true;
                break;
            }
    
            k -= have;
        }
    
        if (!good) std::cout << "-1" << std::endl;
    }

    return 0;
}

1836D - Lottery / 1835B - Lottery

Author: Arti1990
Developer: Arti1990
First solve: Nobody.Emissary / ecnerwala

Tutorial

Solution

#include <bits/stdc++.h>
 
#define forr(i, n) for (int i = 0; i < n; i++)
#define FOREACH(iter, coll) for (auto iter = coll.begin(); iter != coll.end(); ++iter)
#define FOREACHR(iter, coll) for (auto iter = coll.rbegin(); iter != coll.rend(); ++iter)
#define lbound(P, K, FUN) ({auto SSS=P, PPP = P-1, KKK=(K)+1; while(PPP+1!=KKK) {SSS = (PPP+(KKK-PPP)/2); if(FUN(SSS)) KKK = SSS; else PPP = SSS;} PPP; })
#define testy()    \
    int _tests;    \
    cin >> _tests; \
    FOR(_test, 1, _tests)
#define CLEAR(tab) memset(tab, 0, sizeof(tab))
#define CONTAIN(el, coll) (coll.find(el) != coll.end())
#define FOR(i, a, b) for (int i = a; i <= b; i++)
#define FORD(i, a, b) for (int i = a; i >= b; i--)
#define MP make_pair
#define PB push_back
#define ff first
#define ss second
#define deb(X) X;
#define SIZE(coll) ((int)coll.size())
 
#define M 1000000007
#define INF 1000000007LL
 
using namespace std;
 
long long n, m, k;
long long poz_l, poz_p;
vector<long long> v;
 
long long policz_ile(long long strzal)
{
    while (poz_l < n && v[poz_l] < strzal)
        poz_l++;
    while (poz_p < n && v[poz_p] <= strzal)
        poz_p++;
 
    long long pocz = poz_p < k ? 0 : (strzal + v[poz_p - k]) / 2 + 1;
    long long kon = poz_l + k - 1 >= n ? m : (v[poz_l + k - 1] + strzal - 1) / 2;
 
    return max(0ll, kon - pocz + 1);
}
 
int solve()
{
    cin >> n >> m >> k;
    long long a;
    forr(i, n)
    {
        cin >> a;
        v.PB(a);
    }
    sort(v.begin(), v.end());
    v.PB(m + 1);
    long long res = policz_ile(0), best = 0;
    forr(i, n)
    {
        long long pocz = i == 0 ? max(0ll, v[i] - 2) : max(v[i] - 2, v[i - 1] + 3);
        long long kon = min(m, v[i] + 2);
        for (long long s = pocz; s <= kon; s++)
        {
            long long ile = policz_ile(s);
 
            if (ile > res)
            {
                res = ile;
                best = s;
            }
        }
    }
    cout << res << " " << best << '\n';
 
    return 0;
}
 
int main()
{
    std::ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    solve();
 
    return 0;
}

1836E - Twin Clusters / 1835C - Twin Clusters

Author: Anadi, w0nsh
Developer: Fly_37
First solve: GULAL_S_ZHENOY_UMNIKA / Um_nik

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

void solve()
{
    int k, n;
    scanf("%d", &k);

    n = 2 << k;

    vector <long long> input(n + 1);
    vector <int> memHighBits(1 << k, -1);
    vector <pair <int, int> > memLowBits(1 << k, {-1, -1});
    
    auto addInterval = [&memLowBits, &input](int s, int e) {
        const int remXor = input[e] ^ input[s - 1];
        auto &[os, oe] = memLowBits[remXor];

        if (os == -1) {
            os = s, oe = e;
            return false;
        }

        if (oe < s) {
            printf("%d %d %d %d\n", os, oe, s, e);
        } else {
            printf("%d %d %d %d\n", min(s, os), max(s, os) - 1, oe + 1, e);
        }

        return true;
    };

    memHighBits[0] = 0;
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", &input[i]);
        input[i] ^= input[i - 1];
    }

    for (int i = 1; i <= n; ++i) {
        if (memHighBits[input[i] >> k] != -1) {
            if (addInterval(memHighBits[input[i] >> k] + 1, i)) {
                break;
            }
        }

        memHighBits[input[i] >> k] = i;
    }
}

int main()
{
    int cases;
    scanf("%d", &cases);

    while (cases--) {
        solve();
    }

    return 0;
}

1836F - Doctor's Brown Hypothesis / 1835D - Doctor's Brown Hypothesis

Author: Okrut
Developer: Okrut
First solve: None / ksun48

Tutorial

Solution

#include<bits/stdc++.h>
using namespace std;
 
#define sz(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define pb push_back
#define FOR(i, n) for(int i = 0; i < n; i++)
 
using vi = vector<int>;
using vvi = vector<vi>;
 
struct SCC {
    int cnt = 0;
    vi vis, scc_nr;
    vvi scc_list, DAG;
 
    SCC(){}
 
    SCC(vvi & G){
        // G is 0 indexed!
        int n = sz(G);
        vvi G_rev(n);
        vis = scc_nr = vi(n);
 
        vi postorder;
        for(int i = 0; i < n; i++)
            if(!vis[i])
                dfs_post(i, G, G_rev, postorder);
        
        vis = vi(n);
        while(sz(postorder)){
            auto akt = postorder.back();
            postorder.pop_back();
            if(!vis[akt]){
                DAG.emplace_back();
                scc_list.emplace_back();
                dfs_rev(akt, G_rev);
                cnt++;
            }
        }
 
        // optional
        for(int i = 0; i < sz(DAG); i++){
            sort(all(DAG[i]));
            DAG[i].resize(unique(all(DAG[i])) - DAG[i].begin());
        }
    }
 
    void dfs_post(int start, vvi & G, vvi & G_rev, vi & postorder){
        vis[start] = 1;
        for(auto & u : G[start]){
            G_rev[u].pb(start);
            if(!vis[u])
                dfs_post(u, G, G_rev, postorder);
        }
        
        postorder.pb(start);
    }
 
    void dfs_rev(int start, vvi & G_rev){
        vis[start] = true;
        scc_list.back().pb(start);
        scc_nr[start] = cnt;
 
        for(auto & u : G_rev[start])
            if(!vis[u])
                dfs_rev(u, G_rev);
            else if(scc_nr[u] != cnt)
                DAG[scc_nr[u]].pb(cnt);
    }
};
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    long long n, m, k;
    cin >> n >> m >> k;
 
    vvi G(n);
 
    set<pair<int, int>> edges;
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        a--, b--;
        G[a].pb(b);
        edges.insert({a, b});
    }
 
    SCC scc(G);
    vi coloring(n, -1);
 
    auto try_coloring = [&](int num_col, const vi& group)
    {
        vi visited;
        function<bool(int)> dfs = [&](int start){
            visited.pb(start);
            
            bool good_coloring = true;
            for (auto & u : G[start])
            {
                if (scc.scc_nr[u] != scc.scc_nr[start])
                {
                    continue;
                }
                if (coloring[u] == -1)
                {
                    coloring[u] = (coloring[start] + 1) % num_col;
                    good_coloring &= dfs(u);
                }
                else
                {
                    good_coloring &= coloring[u] == (coloring[start] + 1) % num_col;
                }
 
                if (not good_coloring)
                {
                    break;    
                }
            }
 
            return good_coloring;
        };
 
        coloring[group[0]] = 0;
        if (not dfs(group[0]))
        {
            for (auto & u : visited)
            {
                coloring[u] = -1;
            }
            return vvi();
        }
        else
        {
            vvi ret(num_col);
            for (auto & u : visited)
            {
                ret[coloring[u]].push_back(u);
            }
            return ret;
        }
    };
 
    long long ans = 0;
    vi depths(n, -1);
 
    for (vi& group : scc.scc_list)
    {
        n = sz(group);
 
        if (n == 1 and edges.count({group[0], group[0]}) == 0)
        {
            continue;
        }
        int gcd = -1;
        function<void(int)> dfs_depths = [&](int start)
        {
            for (auto & u : G[start])
            {
                if (scc.scc_nr[u] != scc.scc_nr[start])
                {
                    continue;
                }
 
                if (depths[u] == -1)
                {
                    depths[u] = depths[start] + 1;
                    dfs_depths(u);
                }
                else {
                    int diff = abs(depths[u] - (depths[start] + 1));
                    if (diff)
                    {
                        if (gcd == -1)
                        {
                            gcd = diff;
                        }
                        else
                        {
                            gcd = __gcd(gcd, diff);
                        }
                    }
                }
            }
        };
 
        depths[group[0]] = 0;
        dfs_depths(group[0]);
        assert(gcd != -1);
 
        vvi by_color = try_coloring(gcd, group);
 
        assert(sz(by_color) != 0);
        if (k % gcd == 0)
        {
            FOR (i, gcd)
            {
                ans += sz(by_color[i]) + 1ll * sz(by_color[i]) * (sz(by_color[i]) - 1) / 2;
            }
        }
        else if (k % gcd * 2 == gcd)
        {
            FOR (i, gcd / 2)
            {
                ans += 1ll * sz(by_color[i]) * sz(by_color[i + gcd / 2]);
            }
        }
    }
    cout << ans << '\n';
}

1835E - Old Mobile

Author: Fly_37
Developer: maras
First solve: tourist

Tutorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
 
constexpr int MAX_M = 1000 + 7;
constexpr int PRECISION = 9;
constexpr long long MOD = 1e9 + 7;
 
long long mod_inv[MAX_M];
long long DP[MAX_M][MAX_M][2][2];
long long DPprob[MAX_M][MAX_M][2][2];
bool updated[MAX_M][MAX_M][2][2];
// DP[correct][incorrect][backspace][bad suffix]
 
long long calc_mod_inv(long long n)
{
    long long res = 1;
    long long exp = MOD - 2;
 
    while (exp)
    {
        if (exp & 1)
        {
            res = (res * n) % MOD;
        }
 
        exp >>= 1;
        n = (n * n) % MOD;
    }
 
    return res;
}
 
void calc_DP(int digits, int needed)
{
    DP[0][0][0][0] = 0;
    DPprob[0][0][0][0] = 1;
 
    struct ID
    {
        int x, y, z, s;
    };
 
    queue <ID> dp_queue;
    dp_queue.push({0, 0, 0, 0});
 
    while(!dp_queue.empty())
    {
        auto [x, y, z, s] = dp_queue.front();
        dp_queue.pop();
 
        if (updated[x][y][z][s])
        {
            continue;
        }
 
        updated[x][y][z][s] = true;
 
        long long left = digits + 1 - x - y - z;
        long long corr = needed - x;
        long long incorr = digits - needed - y;
        long long prob = DPprob[x][y][z][s];
 
        if (corr == 0 and s == 0)
        {
            // done
            continue;
        }
 
        // correct suffix
        if (s == 0)
        {
            if (corr > 0)
            {
                // found the one correct digit (no need to delete)
                long long opt_prob = (prob * mod_inv[left]) % MOD;
                DPprob[x + 1][y][z][0] = (DPprob[x + 1][y][z][0] + opt_prob) % MOD;
                DP[x + 1][y][z][0] = (DP[x + 1][y][z][0] + DP[x][y][z][0] * mod_inv[left]) % MOD;
 
                // found a needed but currently wrong digit (needs to be deleted)
                if (corr > 1)
                {
                    if (z == 0) // if backspace is not known, the suffix is bad
                    {
                        long long opt_prob = ((prob * (corr - 1) % MOD) * mod_inv[left]) % MOD;
                        DPprob[x + 1][y][z][1] = (DPprob[x + 1][y][z][1] + opt_prob) % MOD;
 
                        DP[x + 1][y][z][1] = (DP[x + 1][y][z][1] + ((corr - 1) * mod_inv[left] % MOD) * DP[x][y][z][0] + 2 * opt_prob) % MOD;
                        dp_queue.push({x + 1, y, z, 1});
                    }
                    else // if backspace is known, the suffix can be instantly repaired
                    {
                        long long opt_prob = ((prob * (corr - 1) % MOD) * mod_inv[left]) % MOD;
                        DPprob[x + 1][y][z][0] = (DPprob[x + 1][y][z][0] + opt_prob) % MOD;
                        DP[x + 1][y][z][0] = (DP[x + 1][y][z][0] + ((corr - 1) * mod_inv[left] % MOD) * DP[x][y][z][0] + 2 * opt_prob) % MOD;
                    }
                }
 
                dp_queue.push({x + 1, y, z, 0});
            }
 
            if (incorr > 0)
            {
                // found an incorrect digit
                if (z == 0)
                {
                    long long opt_prob = (prob * incorr % MOD) * mod_inv[left] % MOD;
                    DPprob[x][y + 1][z][1] = (DPprob[x][y + 1][z][1] + opt_prob) % MOD;
                    DP[x][y + 1][z][1] = (DP[x][y + 1][z][1] + (incorr * mod_inv[left] % MOD) * DP[x][y][z][0] + 2 * opt_prob) % MOD;
                    dp_queue.push({x, y + 1, z, 1});
                }
                else // suffix can be repaired
                {
                    long long opt_prob = ((prob * incorr % MOD) * mod_inv[left]) % MOD;
                    DPprob[x][y + 1][z][0] = (DPprob[x][y + 1][z][0] + opt_prob) % MOD;
                    DP[x][y + 1][z][0] = (DP[x][y + 1][z][0] + (incorr * mod_inv[left] % MOD) * DP[x][y][z][0] + 2 * opt_prob) % MOD;
                    dp_queue.push({x, y + 1, z, 0});
                }
            }
 
            if (z == 0)
            {
                if (x > 0) // deleted correct digit
                {
                    long long opt_prob = prob * mod_inv[left] % MOD;
                    DPprob[x][y][1][0] = (DPprob[x][y][1][0] + opt_prob) % MOD;
                    DP[x][y][1][0] = (DP[x][y][1][0] + mod_inv[left] * DP[x][y][0][0] + 2 * opt_prob) % MOD;
                }
                else // deleted nothing
                {
                    long long opt_prob = prob * mod_inv[left] % MOD;
                    DPprob[x][y][1][0] = (DPprob[x][y][1][0] + opt_prob) % MOD;
                    DP[x][y][1][0] = (DP[x][y][1][0] + mod_inv[left] * DP[x][y][0][0] + opt_prob) % MOD;
                }
 
                dp_queue.push({x, y, 1, 0});
            }
        }
 
        if (s == 1)
        {
            if (corr > 0)
            {
                // found a needed but currently wrong digit (needs to be deleted)
                long long opt_prob = (prob * corr % MOD) * mod_inv[left] % MOD;
                DPprob[x + 1][y][z][1] = (DPprob[x + 1][y][z][1] + opt_prob) % MOD;
                DP[x + 1][y][z][1] = (DP[x + 1][y][z][1] + (corr * mod_inv[left] % MOD) * DP[x][y][z][1] + 2 * opt_prob) % MOD;
                dp_queue.push({x + 1, y, z, 1});
            }
 
            if (incorr > 0)
            {
                // found an incorrect digit
                long long opt_prob = (prob * incorr % MOD) * mod_inv[left] % MOD;
                DPprob[x][y + 1][z][1] = (DPprob[x][y + 1][z][1] + opt_prob) % MOD;
                DP[x][y + 1][z][1] = (DP[x][y + 1][z][1] + (incorr * mod_inv[left] % MOD) * DP[x][y][z][1] + 2 * opt_prob) % MOD;
                dp_queue.push({x, y + 1, z, 1});
            }
 
            if (z == 0)
            {
                // deleted bad suffix
                long long opt_prob = prob * mod_inv[left] % MOD;
                DPprob[x][y][1][0] = (DPprob[x][y][1][0] + opt_prob) % MOD;
                DP[x][y][1][0] = (DP[x][y][1][0] + mod_inv[left] * DP[x][y][0][1]) % MOD;
                dp_queue.push({x, y, 1, 0});
            }
        }
    }
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    mod_inv[0] = 1;
    for (int i = 1; i < MAX_M; ++i) {
        mod_inv[i] = calc_mod_inv(i);
        assert (mod_inv[i] * i % MOD == 1);
    }
 
    int n, m;
    cin >> n >> m;
 
    set <int> different_digits;
 
    for (int i = 0; i < n; ++i)
    {
        int p;
        cin >> p;
 
        different_digits.insert(p);
    }
 
    int needed = different_digits.size();
 
    calc_DP(m, needed);
 
    long long result = 0;
 
    for (int i = 0; i <= MAX_M; ++i)
    {
        result = (result + DP[needed][i][0][0]) % MOD;
        result = (result + DP[needed][i][1][0]) % MOD;
    }
 
    cout << (result + n) % MOD << "\n";
 
    return 0;
}

1835F - Good Graph

Author: Anadi
Developer: Arti1990
First solve: rainboy

Tutorial

Solution

#include <bits/stdc++.h>

#define forr(i, n) for (int i = 0; i < n; i++)
#define FOREACH(iter, coll) for (auto iter = coll.begin(); iter != coll.end(); ++iter)
#define FOREACHR(iter, coll) for (auto iter = coll.rbegin(); iter != coll.rend(); ++iter)
#define lbound(P, K, FUN) ({auto SSS=P, PPP = P-1, KKK=(K)+1; while(PPP+1!=KKK) {SSS = (PPP+(KKK-PPP)/2); if(FUN(SSS)) KKK = SSS; else PPP = SSS;} PPP; })
#define testy()    \
    int _tests;    \
    cin >> _tests; \
    FOR(_test, 1, _tests)
#define CLEAR(tab) memset(tab, 0, sizeof(tab))
#define CONTAIN(el, coll) (coll.find(el) != coll.end())
#define FOR(i, a, b) for (int i = a; i <= b; i++)
#define FORD(i, a, b) for (int i = a; i >= b; i--)
#define MP make_pair
#define PB push_back
#define ff first
#define ss second
#define deb(X) X;
#define SIZE(coll) ((int)coll.size())

using namespace std;

const int MXN = 1007;
int n, m;
vector<int> G[MXN];
bitset<MXN> bs[MXN], edge[MXN];

// MATCHING

const int MXM = 1007 * 2;
int skojX[MXM], skojY[MXM];
bool vis[MXM];

bool dfs_m(int x)
{
    vis[x] = 1;
    FOREACH(it, G[x])
    if (!skojY[*it] || (!vis[skojY[*it]] && dfs_m(skojY[*it])))
    {
        skojX[x] = *it;
        skojY[*it] = x;
        return 1;
    }
    return 0;
}

bool skoj()
{
    int czy = 1;
    int res = 0;
    while (czy)
    {
        czy = 0;
        CLEAR(vis);
        FOR(i, 1, n)
        if (!vis[i] && !skojX[i] && dfs_m(i))
        {
            czy = 1;
            res++;
        }
    }
    return res == n;
}

// END OF MATCHING

void dfs(int nr, bitset<MXN> &visited, bitset<MXN> &to_visit)
{
    visited[nr] = 1;
    to_visit[nr] = 0;
    to_visit = to_visit | (edge[nr] & (~visited));
    for (int i = to_visit._Find_first(); i < SIZE(to_visit); i = to_visit._Find_next(i))
        dfs(i, visited, to_visit);
}

int solve()
{
    cin >> n >> m;
    forr(i, m)
    {
        int a, b;
        cin >> a >> b;
        G[a].PB(b);
    }

    int rres = skoj();
    if (rres)
    {
        FOR(i, 1, n)
        {
            for (auto j : G[i])
            {
                edge[i][skojY[j]] = 1;
            }
        }
        unordered_map<bitset<MXN>, vector<int>> mapa;
        vector<pair<int, int>> vec, res;
        FOR(i, 1, n)
        {
            bitset<MXN> to_visit;
            dfs(i, bs[i], to_visit);
            mapa[bs[i]].PB(i);
        }

        for (auto p : mapa)
        {
            vector<int> l = p.ss;
            vec.PB({bs[l[0]].count(), l[0]});
            if (l.size() == 1)
            {
                res.PB({l[0], l[0]});
                continue;
            }
            for (int i = 0; i < SIZE(l); i++)
            {
                res.PB({l[i], l[i]});
                res.PB({l[i], l[(i + 1) % SIZE(l)]});
            }
        }
        sort(vec.begin(), vec.end());
        forr(i, SIZE(vec))
        {
            int nr = vec[i].ss;
            bitset<MXN> b;
            for (int j = i - 1; j >= 0; j--)
                if (vec[j].ff < vec[i].ff)
                {
                    int nr2 = vec[j].ss;
                    if (bs[nr][nr2] && !b[nr2])
                    {
                        b |= bs[nr2];
                        res.PB({nr, nr2});
                    }
                }
        }

        cout << "YES" << '\n';
        cout << res.size() << '\n';
        for (auto p : res)
            cout << p.ff << " " << p.ss + n << '\n';
    }
    else
    {
        CLEAR(vis);
        FOR(i, 1, n)
        {
            if (skojX[i] == 0)
            {
                dfs_m(i);
                break;
            }
        }
        vector<int> v;
        FOR(i, 1, n)
        {
            if (vis[i])
                v.PB(i);
        }
        cout << "NO" << '\n';
        cout << v.size() << '\n';
        for (auto el : v)
            cout << el << " ";
        cout << '\n';
    }

    return 0;
}

int main()
{
    std::ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solve();

    return 0;
}

Комментарии (115)

Показать архивные | Написать комментарий?

Khaild_Salman

17 месяцев назад, # |

← Rev. 2 →

-29

UPD: tutorial is empty

→ Ответить

CodeOfSenior

+25

NTR_LOVER should get ntred ;-;

Here_I_Go420

It says tutorial is not available!!

electric_boogaloo

+28

A fast tutorial without the tutorial.

UPD. The tutorial became available as fast!

EnDeRBeaT

i've never participated in atcoder contests. Is this what agc feels like?

20333333333

17 месяцев назад, # ^ |

+57

No.

Igor_Parfenov

I've participated in AGC only several times, and can't speak much about how close are those problems to problems of this contest. But by difficulty, this contest (Div 1) is very close to AGC.

sbhm_prksh

Fast editorial. B was boomer...

The_Boys_Word

it's not an interesting competition at all

nchn27

You guys are mean, I think the contest was great!

kozliklekarsky

+33

As good as the contest might have been (D1C and D1D look acceptable), people had to read D1B and think about it or just jump in a leap of faith to do D1C, and D1B doesn't have the happiest implementation, solution etc., so the quality of the contest bottlenecked at D1B

SuperJ6

The idea is easy, good competitors will impl quick, worse usually only solve 2 or 3 in div1 anyway. Not every problem should have trivial impl. It wasn't an amazing contest, but the quality was no different than majority of contests i've taken, i liked all the problems i've looked at (A-D).

valeriu

good competitors will solve quickly

How good do the competitors have to be to solve D1B* 😂 😂? I have one of the lowest performances of such competitors (solved in 1h10m) and still managed to get ~2350 performance. I find it uncredible that so many people are poor competitors.

Low master usually only solves 2 or 3 in div1 anyway, so taking 1h30min is reasonable for harder contest. GM can surely solve and implement in 45min and still have time for 3-4 total, or strategize to skip if they think it will be faster to solve harder, which we see both on scoreboard. It is unfortunate many on cf are too bad at implementing because they are only used to 10 line solutions (it is only downside with recommending cf for practice).

batmend_kh

I feel like the problems were definitely interesting. It was just sometimes annoying to think about them.

-6

Editorials are very hard to read tho.

Nevermind, editorials are getting better llmao

Zhouershan

+16

It's easy to guess the conclusion of Div1.B but very hard to believe and proof it.

wavelets

+101

not really — lets say you choose position "m"

let l be the vote k away from you on the left, and define r similarly

the interval where you win is (l + m)/2 ... (r + m)/2

therefore, m doesn't really matter, except for parity reasons — so it is optimal to choose 1, 2 to the right from a vote

then theres the case where l doesn't exist, in which it would be optimal to choose 1 left from a vote

alexok2006

too hard div2b for me (for me)

kartikey_wariyal

12 месяцев назад, # ^ |

Me too

polosatic

Div.2 B-D have clear solutions but it was quite hard to implement them for me.

Rinzzler

+10

I believe there is a typo in the editorial for problem Div2C. The upper bound for b should be min(10^C — a, 10^B).

Dan4Life

Div 2 C can be solved by brute forcing all candidates for A, then checking the range that satifies the equality with 2 binary searches 210127806. It's actually mostly the same as the editorial, but using binary search instead of basic math.

tgp07

I did something similar.

Victor_Luis123

I tried to do something like that in the contest but it ended up in TLE, I think that the problem was in the way I implemented it.

Abito

Congrats on becoming CM

Thank you XD

OmarAboutaleb77

Can you explain the basic math. I feel kinda dumb because I don't get it. Congrats on becoming Candidate Master btw

Spoiler

Thank you for the explanation. I think I get it.

b2 is the largest possible number that b can be. The largest value C can be is (10^c) -1. Therefore, the largest value b2 can be is (10^c)-1-a. However, b2 is also bounded by its length as it must be b digits. So it is b2 = min((10^c)-1-a,10^(b-1))

Is this correct?

Slight error. For $$$b1$$$, $$$10^{B-1}$$$ is the smallest B-digit number. But for $$$b2$$$ you'd have to look for the largest B-digit number instead(to maximize $$$b2$$$). Also, to know if you're correct, just check if what you wrote is the same as editorial.

oh yeah i mistyped it. I meant 10^b-1

cazaque

In C tutorial, should it be min{10^C — a, 10^B} instead of max?

parag776

OMG i did not read this line in C

Each input file has at most 5 test cases which do not satisfy A,B,C≤3 .

used binary search and at last could not implement :( today is my worst day.

mohamedeltair

+378

+90

if two people can have the same lottery ticket, yall should've at least put that in the samples

mym0404

← Rev. 3 →

+26

I think the difficulty was reasonable if two people cannot share the same position and $$$N \le 10^5$$$ as Div2D/Div1B.

if two people can't share the same position, its still the same algorithm / difficulty, just minor implementation differences

oh, then I should read solution but it is not available...

NTR_Lover

-8

It is the case if you observed that optimal lottery number can only lies on some $$$[x-2, x+2]$$$ range for some bought lottery x. But for me I tried to maintain a sliding window-like algorithm, in which case having same lottery tickets make case discussion like 10x harder ...

sword060

+38

my solution in Div1C:

if N <= 8 , bruteforce all 4 ranges [L1,R1] [L2,R2].
else lets fix a range L1=R1 , now we find a subarray before or after that index that has the same XOR value as that element, run that for some random elements L1 a few times till you find a solution.

can someone hack this solution ? :)

https://codeforces.me/contest/1835/submission/210164524

Good_WeekDay_

Same , and I didn't even consider about the case that n<=8 , just fixed a range l1=r1 for all cases and it passed. :)

https://codeforces.me/contest/1835/submission/210162332

upd: now it has been uphacked.

physics0523

+56

Hacked!
Unfortunately, at least for $$$k=3$$$ (and maybe for larger $$$k$$$), "There exists an answer which satisfies $$$L_1=R_1$$$" is false.
I bruteforced $$$k \le 2$$$ and there are no counterexample, so $$$k=3$$$ is the smallest.
Here are some tests!

By the way how to find it?
I use randomize bruteforce. Try to add some random elements to the end of the current sequence and if successful the sequence is extended, if unsuccessful erase the last element, and repeat this until we find a sequence with the length >= 16.
Code and another counterexample

UPD: Now I have a counterexample for $$$k=4$$$!

UPD2: counterexample for $$$k=5,6,7$$$!
By the way can we generate them in deterministic way?

mrphyx1312

I still did not get Div2B?? Can somebody help?

give all of them g/2 -1 coins except for the last one.

jchatter123

How about the case when there are some coins left? Why is giving them all to one astrophysicist optimal?

I don’t know how to prove it rigorously but it is pretty intuitive. If you were to give any of the other astrophysicists a coin you would just be wasting silver coins. Try thinking of any way to redistribute them when they are in the above state to make it better and you won’t find anything. Either way, A and B are usually about intuition from my very limited experience.

Osama_Fahim

Why we give g/2-1 coins to others except last one , what is logic and intuition behind g/2 — 1 and why we are focusing distributing g/2 — 1 coins at first, can you please explain this intuitively ?

Kohinoor

g/2 — 1 is the maximum number of coins you can save from one astrophysicist.

kunzaZa183

Why was Div2 D/ Div1 B skipped by many contestants?

EN_SA

Even I solved Div2B, but I still can't understand the statements. Is it because I am bad at English?

XiFaN1999

No i guess : (

i also didnt understand the Div2B statement and cant implement the code : (

SPAR-BH

Given n , k , g you must distribute k * g coins to n people in such way that if you round up all of them to nearest integer that is divisible by g , the sum of them us minimum as possible. after that , you should output k * g — sum of them to save the most amount of coins you can have

Livfo

Why nearest integer can't be zero?

it can ne zero if your coins is less than g / 2

for example if you want to near 4 coins to the nearest integer that is divisible by 9 , it will be zero. however if you want to near the 7 coins to the nearest integer that is divisible by 9 , it will be 9

since 9 — 7 >= 7 — 0

nguyenchicuong

Could you help me check it, I run my code and it correct testcase 930th of test 10 but the log show wrong.

My submission: 210165371

Thank you

Restricted

Your BUFSIZE variable (for FastIO) is too small.

Thank you so much, I changed BUFSIZE=8192 and it accepted.

VLTisME986

bro has been coding for 12 years :O

Yep bro ^^

Insanity_123

Are Div 2 Bs supposed to be this math heavy ? Like the statement is not understandable at all unless you carefully parse it and post that try to find the formula ? I am not sure what this problem can you train you for or be reusable for anything else , open to opinions but didn't like the contest

A_G

The answer to 1835E - Old Mobile depends only on $$$n$$$, $$$m$$$, and the number of distinct digits of the array. My submission runs in $$$O(n+m)$$$ time (where the $$$n$$$ term is just for reading input).

saturnbored

+23

Boink

granadierfc

opposite for me

diskoteka

look at E/C first solver's handles

Sinocchi

SajidAbdullah

For Div2B,I did not understand for the part where we have extra money.Can someone explain it with some test case to me?

Spartanlord

In Div 2C, I tried to binary search the values of b for each a, but got TLE on 210139402 for complexity O(10^a*log(10^b)).

I then found limits for minimum possible a and iteratively updated for all subsequent values in submission 210153651 but still got TLE for O(10^a+log(10^b)) complexity.

I thought this should've passed according to constraints in question but still I submitted by replacing long long to int but still TLE on 210154560, then did some more optimisations to reduce operations on each iteration and got AC on 210155518.

I spent ~40 mins on just optimising for the time limit. Granted, my implementation might be too bad but I do think the constraints were too tight for this problem. I think my first 2 solutions itself would've passed if time were 2 sec. Do point out any specific slow part of the code, would be helpful for future.

balalaika

I guess you already got that all time consuming by main cycle.
I guess you already got that in one cycle iteration you do at most 18 calls of digits macros.

So you should ask yourself questions:

1) Do I really need 18 calls in each iteration (you answered no in AC solution)?
2) How long is single call to digits?

I guess that you interested in second question. What you should do? Measure. Gladly we have Custom Invocation tab where we can do it.

Snippet

#include <iostream>
#include <cmath>

using namespace std;

int digits1(int n) {
    return (int)(log10l(abs(n)) + 1);
}

int digits2(int n) {
    int res = 0;
    while (n > 0) {
        n /= 10;
        ++res;
    }
    return res;
}

int main() {
    int sum = 0;
    for (int i = 100000; i < 1000000; ++i) {
        for (int j = 0; j < 18; ++j) {
            sum += digits2(i * j);
        }
    }
    cout << sum << endl;
    return 0;
}

And you will see, that digits1 version do whole cycle within ~0.5s and digits2 is ~0.08s.

Why? Don't know (I dont have any expertise in how abs and log10l functions implemented), but I dont see it strange since your version is abs + hard floating point operation and mine is just integer division (yeas, floating point operations hard).

Hey, thanks for the insights and comparison! Will avoid floating pt calculations when possible.

Golovanov399

+85

My solution for Div1 C was different from the (deterministic) one in the editorial.

If there are at least two zeroes in the array, pick one of them as the first segment and another as the second. Now assume that there is at most one zero.

Consider all xors of type $$$a_i\oplus a_{i+1}\oplus\ldots\oplus a_{n/2}$$$, including the empty one; call the multiset of these xors left. Similarly, consider all xors of type $$$a_{n/2+1}\oplus\ldots\oplus a_j$$$, call them right. However, if there is a zero, then it will make two adjacent xors equal, in this case we remove one of them from the corresponding multiset (we'll see later why it's important).

Each pair of a left xor and a right xor generates a subsegment containing the middle of the array (by middle I mean the imaginary bar between elements $$$n/2$$$ and $$$n/2+1$$$). There are at least $$$(n/2+1)\cdot n/2 > 4^k$$$ of them, therefore some two of them have the same xor. Let's find one such $$$x$$$ that at least two pairs $$$(i, j)$$$ satisfy the relation left[i] ^ right[j] = x.

We can find such $$$x$$$ bit by bit, from highest to lowest. Indeed, on the first step calculate the number of xors of type 0????? (this can be done with some binary searches). If it is at least $$$2^{2k-1} + 1$$$, we will look for $$$x$$$ of this type, otherwise we assume that $$$x$$$ looks like 1?????. Then we try to set the next bit zero, and so on. After we found such $$$x$$$, we can find two segments $$$A$$$ and $$$B$$$ with this xor.

Now, if they have different beginnings and different ends, we just take $$$A$$$ and $$$B$$$ if they are disjoint, otherwise $$$A\oplus B$$$ is a disjoint union of two segments, which we print. If they have the same beginning then their ends differ by at least two (because otherwise we had two left/right xors that only differ by a position that has zero). Then $$$A\oplus B$$$ is a segment of length at least $$$2$$$ with zero xor, we can split it into two subsegments (which have to have equal xors).

Also, my screencast

Vercingetorix

I did the same bit by bit approach, but didn't split on left and right. Instead I found 3 subsegments from the whole array with the same xor (there always are) and either some 2 of them don't share an end and it's easy, or all three share one of the ends and we get 2 subsegments with xor 0.

lelbaba

+22

Please add a proper editorial for Div1 B. What am I supposed to understand from that shitty macro-filled code?

Soultaker

+60

First, sort the array A. Suppose you pick your lottery number and insert it into the array A; let's call the resulting array B. For now, assume all values of B are distinct. Then your number has some index $$$i$$$. What is the range of numbers that make you win one of the K prizes? Clearly it's some consecutive range around B[i].

Look at the lower bound first. If i < K then the lower bound is 0: since your number is among the first K, any value less than B[i] will definitely win you a prize. Otherwise, if i ≥ K and the lucky number Q < B[i], then you win a prize only if (Q-B[i]) < (B[i-K]-Q) (in other words: the lucky number is closer to your number B[i] than the K-th number to its left, B[i-K]). Written differently: Q > (B[i-K]+B[i])/2.

Similarly, the upper bound is Q ≤ M if i ≥ N-K, and Q < (B[i+K]+A[i])/2 otherwise.

Combining this, we can calculate the count of winning numbers as: (i >= N-K ? M : floor((B[i]+B[i+K])/2)) - (i < K ? 0 : ceil((B[i-K]+B[i])/2)) + 1. (This is just the difference between the upper and lower bounds mentioned above.)

So far we assumed numbers are all distinct. What if there are duplicates? The basic idea remains the same, you just need to make sure that you count numbers A[j] = B[i] as lying to the left of B[i] in your lower bound calculation, and to the right of B[i] in the upperbound calculation, since all previously-bought tickets will beat yours even if you picked the same number.

So now we have a way to calculate the winning probability given a chosen number and in theory we can find the answer by trying all values between 0 and M. Of course, this is way too slow. Fortunately, we only have to try a few candidates: 0, and the values around each possible A[i]. I ended up using {A[i]-2, A[i]-1, A[i], A[i]+1, A[i]+2}.

Why is this sufficient? Look at the formula above. If K ≤ i < N-K then the count of winning numbers is (floor((B[i]+B[i+K])/2) - ceil((B[i-K)+B[i])/2) + 1). If B[i-1]+2 < B[i] < B[i+1] then we can subtract 2 from B[i] without changing the winning number count, and since we're supposed to minimize B[i] anyway, it doesn't make sense to consider higher values.

(Why do we need A[i]-1 and A[i]-2 too? That's to cover the case where i < K.)

For each candidate, you can easily find the surrounding numbers with binary search in A, for an overall O(1+5N×log N) = O(N log N) solution. I'm pretty sure you can also do the main algorithm in O(N) with a two-pointer solution instead of binary-searching each candidate, and that's probably faster in practice, but since you need to sort the input first, it's technically still O(N log N).

I think my solution is more readable, too: https://codeforces.me/contest/1835/submission/210182613

RobinFromTheHood

Great 'editorial'! Thanks.

I made a 2-pointer implementation here: 210231900

Your formula:

(i >= N-K ? M : floor((B[i]+B[i+K])/2)) - (i < K ? 0 : ceil((B[i-K]+B[i])/2)) + 1

is slightly different from your implementation, I used:

hi= (i >= N-K ? M : ceil((B[i]+B[i+K])/2)-1)

lo= (i < K ? 0 : floor((B[i-K]+B[i])/2) + 1)

hailcpy

Hey, i dont understand why we are choosing A[i]+1, A[i] + 2. I undertstand we choose A[i] so that he is between A[i] and A[i+1] and it is the smallest optimal. but why are we checking A[i]+1, A[i]+2. Wouldnt they give the same winning range.

Considering only A[i] isn't sufficient, because if you tie with a previously-picked number, you lose. For example, if K=1 and you pick any A[i], you can never win. That's why for K=1 you need to pick A[i]+1 or A[0]-1.

You need A[i]+2 too due to the rounding after dividing by 2: sometimes when you move one space to the right, you gain 1 winning number on one side without losing it on the other side. For example, when K=2 and A={1,2,10,11}, then 4 is better than 3.

(Maybe you don't need A[0]-2.)

+32

What a cute determistic approach for D1C! How evil I always think about birthday-attack like approach for this kind of problems...

ChaosAngel

Might be biased, and sorry if it sounds harsh, but problem div 2C, from the problem itself, to the statement, to the constraints, to the format of the output, is the worst problem I have seen on codeforces in my 4 years here.

I think it's fair to criticize if you also support your criticism with arguments, which you haven't really done.

Problem itself: What's bad about it?

Statement: It seemed clear and concise to me; maybe the lexicographical comparison could have been explained a bit more rigorously, but I think in this case it was pretty easy to understand what it meant for equations to appear in sorted order, since the numbers all had equal size (so you didn't have to wonder whether e.g. a space comes before or after a digit).

Constraints: okay, the “at most 5 test cases do not satisfy A, B, C ≤ 3” part is a little awkward, but it's clearly intended to allow O(A) solutions to pass while also making it possible to create some input files with many test cases. Maybe I would have phrased this as:

For at most 5 test cases: A, B, C ≤ 6.
For all other test cases: A, B, C ≤ 3.

Output format: what gives you trouble here? You can just do printf("%d + %d = %d\n", a, b, c); or std::cout << a << " + " << b << " = " << c << '\n'; in C++, or print(a, '+', b, '=', c); in Python. I could see how printing only the three numbers would be slightly simpler but adding a '+' and '=' character in between it's really not that hard, is it?

How would you improve the problem?

bigSchrodinger

You literally just listed all the problems, and you're still asking what the problem is

The point was, the problems I could identify weren't all that bad; just minor complaints. I don't think that justifies the label of “worst problem in four years”.

Maybe it was intended as a compliment? If this was the worst problem in the past four years, then CodeForces is doing great!

I would improve the problem by implementing the changes you gracefully pointed out.

Presence of larger inputs, even if limited, suggests a faster than roughly brute force is needed, and while possible, it is very ugly. Sure, contestants can spend time figuring out what will pass and what won't based on input distribution, but I have never seen this in a cf contest and I don't see a reason to start now.

The output format is easy sure, but I have never seen this in a cf contest and I don't see a reason to start now.

All in all, it breaks with several precedents, and I add my opinion that the problem itself is uninteresting, but that is subjective so to be taken with a grain of salt.

Periaraperi

In div2-C shouldn't b be less than MIN(10^C−a,10^B) instead of MAX?

YouKn0wWho

What is the proof that $$$n^3$$$ is a large enough bound in Div1.D?

peltorator

Consider a strongly connected component. Consider the gcd of all cycles in this SCC to be $$$g$$$. Say $$$v$$$ and $$$u$$$ are a suitable pair. It means that there is a path between them (of length $$$\le n$$$) such that after going through it we are left to go divisible by $$$g$$$ number of steps. Now look at any simple cycle through $$$u$$$. Its length is divisible by $$$g$$$. Say this cycle length is $$$gx$$$. But the gcd of all cycles is $$$g$$$. Notice that if we start calculating this gcd with $$$gx$$$ and take new cycles one by one into the gcd (there is an infinite number of cycles, but you get what I mean), every time the current gcd either does not change or is divided by smth. We can look at only the cycles that decreased the gcd. Every time the gcd decreased by a factor of at least $$$2$$$, so we need only $$$\log n$$$ other cycles for their gcd to be equal to $$$g$$$. Now we can combine all these other cycles into one that has length $$$yg$$$ where $$$gcd(y, x) = 1$$$. The length of this cycle is $$$O(n \log n)$$$. Now we go through this cycle some number of times until the remaining distance we need to cover is not divisible by $$$xg$$$. This can be done due to the Chinese remainder theorem (it is easy to see that in this case there exists a positive solution to the linear gcd representation, and it uses $$$O(n)$$$ passes through the cycle because if you have one solution to $$$ax+by=1$$$, you can get a different one by adding $$$y$$$ to $$$a$$$ and subtracting $$$x$$$ from $$$b$$$). When the remaining distance is divisible by $$$xg$$$, we just go through the cycle of length $$$xg$$$ the needed number of times. This way we proved that we need at most $$$O(n^2 \log n)$$$ steps. In this argument, I didn't try to be precise, so we have the $$$O$$$ notation, so it does not prove the desired inequality for small values of $$$n$$$, but I hope I gave you an idea of how it works, and now you can figure out how to do in more precisely.

rqi

15 месяцев назад, # ^ |

How do you combine the $$$\log{n}$$$ cycles into one with length $$$yg$$$ where $$$gcd(y, x) = 1$$$, such that the combined cycle is length $$$O(n \log{n})$$$?

You can't just add the cycle lengths together: for example, if you have $$$g=1$$$, $$$x=30$$$, and other cycles of length $$$5, 3$$$, if you add these other cycle lengths together, you get a cycle of length $$$y = 8$$$, and $$$gcd(x, y) \neq 1$$$.

Also, what if some of these $$$\log{n}$$$ cycles that are added to the list to make the $$$gcd(x, y) = 1$$$ do not share a common vertex, so they cannot be combined easily into one big cycle?

Lastly, how would one prove the exact $$$n^3$$$ bound (as big O notation doesn't show the exact bound for smaller $$$n$$$)?

AlternatingCurrent

Hello, my submission to div. 1 C 210190393 returned "wrong answer Segments have different xors (test case 8)", but my answer to test case 8 seems right. Is there anything wrong with the checker?

input:
1
2 1 2 3

output:
2 2 3 4

GoldyBhai

+13

I think the test cases are numbered starting with 0. And answer for next test case is wrong. Input : 1 0 3 2 3

Output : 1 1 3 3

Anadi

That wasn't very clear. Test cases are numbered starting with $$$1$$$ now.

none_c

I don‘t understand why d2C t* o(10^a+10^b) = 1e9 not TLE.And I write 2hours binary search.

jiangbowen

+46

aasill

Correction: [ 1836C — k-th equality ]

Section — Tutorial

We can easily find this range. We get that max{10C−1−a,10B−1}≤b<_max{10C−a,10B}_

The upper bound should be min {10^C-a,10^B}

You're right, fixed

ArhN

← Rev. 4 →

+42

can't solve problem Div.1 B, because can't analyzed the details of the code.

lost rating, its very sad.

How improve?

yeminghan

Why the tutorial of D1B is unavailable? Or it's my problem?

-44

It's not written. We'll add it today or tomorrow.

Ice_teapoy

Why problem D's tutorial is not available?

Mirali777

Сan it be proved that gcd of all cycles in SCC is lcm of good values for coloring (I tried to pass with this implementation and somehow failed)?

kehuydiet800cf

I need the tutorial of Div.2 D / Div.1 B

1835C — Twin Clusters

Interesting pair of "First solve")

Can someone explain how for div2C we get that the range is max{10C−1−a,10B−1}≤b<min{10C−a,10B}

nhanhoang510

In the tutorial (Deterministic solution) of problem 1836E — Twin Clusters / 1835C — Twin Clusters, we can prove that there are always two segment have the same XOR. But what if that two segment do not disjoint, how can we prove that we will always have two disjoint segment with the same XOR value.

MarioYC

If they're not disjoint, you can still remove the common part and obtain two disjoint intervals with equal XOR.

Ah yes yes, I have realized it yesterday. But in the situation that one of these intervals only have 1 length (like a = b and c = a, d > a), I just don't know to solve it.

Limitations for div1E are kinda confusing. Why $$$m \le 1000$$$ if the intended time complexity is $$$O(m^2)$$$ time? I first wrote an $$$O(m^3)$$$ solution that worked in twice the time limit and I was beating my head around trying to understand how to optimize it until I figured out that I just need to make it quadratic. I feel like $$$m \le 3000$$$ for example would be more suitable for this problem.

I have the same solution for div1F but I thought about it in a different way. I also first tried to use submodularity, but it seems like a too complicated concept for this problem. We can do it in classical CP terms!

As in the intended solution, we first handle the NO-case. If we are in the YES-case, it means that there exists a perfect matching. Let's rename the vertices in the right part such that in this matching vertex $$$i$$$ on the left side is connected to the vertex $$$i$$$ on the right side ($$$n+i$$$ in the problem definitions, but let's number both parts from $$$1$$$ to $$$n$$$). Now for every subset of vertices on the left side $$$S$$$ it is connected to at least the same set $$$S$$$ on the right side. So a set is tight if edges from this set go only into this set on the right side. Let's replace this bipartite graph on $$$2n$$$ vertices with a directed graph with $$$n$$$ vertices: if we have an edge between vertices $$$u$$$ in the left part and $$$v$$$ in the right part, we add a directed edge from $$$u$$$ to $$$v$$$ in the new graph. Now our condition can be translated as "A set $$$S$$$ of vertices is tight if and only if there are no outgoing edges from this set into the remaining vertices". If we now look at the strongly connected components of the resulting graph, it is easy to see that a set is tight if and only if it is downward closed in the DAG of strongly connected components (so it consists of multiple strongly connected components, and if it consists one of them, it also contains all reachable ones).

Ok. We want to create a new graph. The new graph is also good, so it also has a perfect matching. Let it again connect vertices $$$i$$$ with the same vertices on the right side. Now we want to minimize the number of remaining edges to add such that the set of downward closed sets in the corresponding directed graph is the same as in the directed graph for $$$G$$$. It is equivalent to making sure that the reachability is preserved ($$$u$$$ is reachable from $$$v$$$ in $$$G'$$$ if and only if it is reachable in $$$G$$$). Every strongly connected component should remain strongly connected, so if its size is larger than one, we should connect its vertices into a cycle. Now we need to preserve the reachability inside the DAG of strongly connected components. We should add an edge $$$v \to u$$$ only if it already existed, and also if we can not reach $$$u$$$ from $$$v$$$ via a detour. It all can be checked by going through SCCs in the reversed topological order and storing in bitsets all the reachable vertices from the current vertex. Code: 210678931.

Essentially this solution is exactly the same as the one presented in the editorial, however, I think that it is easier to grasp, and it is more natural. It also shows that the editorial actually talks about things like this directed graph, and its strongly connected components, but without saying these words, which could make things a bit harder to understand.

P.S. Maybe it was done on purpose so that people don't notice that both div1D and div1F are actually problems about strongly connected components :)

BIg-P

Sorry,I have a question. 1836B — Astrophysicists'Tutorial at the end of this part "and by decreasing the bonus of one astrophysicist, we can get at most 1 from another one" why is it at most not at least?

Eeezoe

Indeed, based on the analysis we've discussed so far, it should be clear why allocating only one silver coin to each person is not an optimal decision. Firstly, by giving each person only one silver coin, we can only save one coin per person. Secondly, in cases where the number of people is insufficient, the last person to receive coins would end up needing to be compensated with a larger amount of silver coins. This prevents us from saving the maximum number of coins. Therefore, allocating one silver coin to each person is not the most optimal decision.

8 месяцев назад, # ^ |

TTthanks just noticed your reply 0.0 I will review problem B

Attiesal

16 месяцев назад, # |

For Div2D, how to prove this : 'It will either have a length of ⌊(b−a)/2−1⌋ or ⌊(b−a)/2−2⌋'

Rafi

11 месяцев назад, # |

In Prb C (https://codeforces.me/problemset/problem/1835/A) tutorial says we can iterate over all a (1e6). but tc is 1e3. so in worst case it can be O(1e6*1e3). and there is no information about sum of all a in all tc will be 1e6. What's the problem here?

beyondpluto

4 месяца назад, # |

I think Div2B statement is poorly written. It took me some good amount of time to understand the question.

Блог пользователя Anadi