Codeforces Round #754 (Div. 2) Editorial

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	166
2	maomao90	163
2	Um_nik	163
4	atcoder_official	161
5	adamant	160
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

Thank you for participating! We hope you enjoyed the contest.

Authored and prepared by JeevanJyot

Hint 1

Hint 2

Hint 3

Solution

Solution [c++] (JeevanJyot)

#include <bits/stdc++.h>
using namespace std;
 
int32_t main()
{
    ios_base::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);
    int T; cin >> T;
    while(T--)
    {
        int a, b, c; cin >> a >> b >> c;
        cout << ((a + c - 2 * b) % 3 == 0 ? 0 : 1) << "\n"; 
    }        
    return 0;
}

Solution [Kotlin] (ExplodingFreeze)

fun main(args: Array<String>) {
    repeat(readLine()!!.toInt()) {
        println(Math.min(readLine()!!.split(" ").map { it.toInt() }.sum() % 3, 1))
    }
}

Solution [Python] (AshishGup)

t=int(input())
for i in range(t):
    a,b,c=[int(x) for x in input().split()]
    print(0 if ((a+b+c)%3 == 0) else 1)

1605B - Reverse Sort

Authored by Ashishgup and prepared by JeevanJyot.

Hint 1

Hint 2

Solution

Solution [c++] (JeevanJyot)

#include <bits/stdc++.h>
using namespace std;
 
int32_t main()
{
    ios_base::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);
    int T; cin >> T;
    while(T--)
    {
        int n; cin >> n;
        string s; cin >> s;
        if(is_sorted(s.begin(), s.end()))
        {
            cout << 0 << "\n";
            continue;
        }
        
        string t = s;
        sort(t.begin(), t.end());
        cout << 1 << "\n";
        vector<int> ans;
        for(int i = 0; i < n; i++)
        {
            if(s[i] != t[i])
                ans.push_back(i+1);
        }
        cout << ans.size() << " ";
        for(int i = 0; i < ans.size(); i++)
            cout << ans[i] << " \n"[i+1 == ans.size()];
    }        
    return 0;
}

Solution [Kotlin] (ExplodingFreeze)

fun main(args: Array<String>) {
    repeat(readLine()!!.toInt()) {
        val n = readLine()!!.toInt()
        val s = readLine()!!
        if("10" in s) {
            println(1);
            val res = s.toCharArray().sorted().withIndex().filter { it.value != s[it.index] }.map { it.index + 1 }
            println("$$${res.size} $$${res.joinToString(" ")}");
        } else {
            println(0);
        }
        
    }
}

Solution [Python] (AshishGup)

q = int(input())
for tc in range(q):
    n = int(input())
    s = input()
    t = ''.join(sorted(s))
    ans = []
    for i in range(len(s)):
        if s[i] != t[i]: 
            ans.append(i)
    val = 1 if len(ans) > 0 else 0
    print(val)
    if val > 0:
        print(len(ans), end = " ")
    for elem in range(len(ans)):
        print(ans[elem] + 1, end = " ")
    print()

1605C - Dominant Character

Authored by Ashishgup and prepared by JeevanJyot.

Hint 1

Hint 2

Hint 3

Solution

Solution [c++] (AshishGup)

#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long
 
const int N = 1e6 + 5;
 
int n;
string s;
 
int32_t main()
{
	IOS;
	int t;
	cin >> t;
	while(t--)
	{
		cin >> n >> s;
		int ans = 1e9;
		for(int i = 0; i < n; i++)
		{
			vector<int> f(3, 0);
			f[s[i] - 'a']++;
			for(int j = i + 1; j < min(n, i + 7); j++)
			{
				f[s[j] - 'a']++;
				if(f[0] > f[1] && f[0] > f[2])
					ans = min(ans, j - i + 1);
			}
		}
		if(ans == 1e9)
			ans = -1;
		cout << ans << endl;
	}
	return 0;
}

Solution [Kotlin] (ExplodingFreeze)

fun main(args: Array<String>) {
    repeat(readLine()!!.toInt()) {
        val n = readLine()!!.toInt()
        val s = readLine()!!
        var ans = 8;
        for(i in 0..n-1) {
            val cnt = IntArray(3) {0}
            for(j in i..Math.min(i + 6, n - 1)) {
                cnt[s[j] - 'a']++;
                if(j > i && cnt[0] > Math.max(cnt[1], cnt[2]))
                    ans = Math.min(ans, j - i + 1);
            }
        }
        if(ans > 7)
            ans = -1;
        println(ans)
    }
}

1605D - Treelabeling

Authored and prepared by the_hyp0cr1t3.

Hint 1

Hint 2

Hint 3

Hint 4

Hint 5

Solution

Solution [c++] (the_hyp0cr1t3)

/**
 * the_hyp0cr1t3
 * 24.09.2021 01:19:28
**/
#ifdef W
    #include <k_II.h>
#else
    #include <bits/stdc++.h>
    using namespace std;
#endif
 
template<class T> class Y {
    T f;
public:
    template<class U> explicit Y(U&& f): f(forward<U>(f)) {}
    template<class... Args> decltype(auto) operator()(Args&&... args) {
        return f(ref(*this), forward<Args>(args)...);
    }
}; template<class T> Y(T) -> Y<T>;
 
int main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    int Q; cin >> Q;
 
    while(Q--) []() {
        int i, j, k, n;
        cin >> n;
        vector<vector<int>> g(n);
        for(i = 0; i < n - 1; i++) {
            int u, v; cin >> u >> v;
            g[--u].push_back(--v); g[v].push_back(u);
        }
 
        int lg = 32 - __builtin_clz(n);
        vector<vector<int>> vals(lg);
        for(i = 1; i <= n; i++)
            vals[31 - __builtin_clz(i)].push_back(i);
 
        vector<int> col(n);
        Y([&](auto dfs, int v, int p) -> void {
            for(auto& x: g[v]) if(x ^ p) {
                col[x] = col[v] ^ 1;
                dfs(x, v);
            }
        })(0, -1);
 
        int w = accumulate(col.begin(), col.end(), 0);
        if(w > n - w) {
            w = n - w;
            for(auto& x: col) x ^= 1;
        }
 
        vector<int> ans(n);
        for(i = j = k = 0; k < lg; k++) {
            for(auto x: vals[k]) {
                if(w >> k & 1) {
                    while(!col[i]) i++;
                    ans[i++] = x;
                } else {
                    while(col[j]) j++;
                    ans[j++] = x;
                }
            }
        }
 
        for(i = 0; i < n; i++)
            cout << ans[i] << " \n"[i + 1 == n];
    }();
 
} // ~W

Solution [c++] (AshishGup)

#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
 
const int N = 2e5 + 5;
 
int n;
int msb[N], ans[N];
vector<int> nodes[2];
vector<int> g[N];
 
void precompute()
{
	int bit = 1, cnt = 1, nxt = 2;
	for(int i = 1; i < N; i++)
	{
		msb[i] = bit;
		cnt--;
		if(cnt == 0)
			cnt = nxt, bit++, nxt *= 2;
	}
}
 
void dfs(int u, int par, int col)
{
	nodes[col].push_back(u);
	for(auto &v: g[u])
	{
		if(v == par)
			continue;
		dfs(v, u, col ^ 1);
	}
}
 
 
int32_t main()
{
	IOS;
	precompute();
	int t;
	cin >> t;
	while(t--)
	{
		cin >> n;
		for(int i = 1; i <= n; i++)
			g[i].clear();
		for(int i = 1; i <= n - 1; i++)
		{
			int u, v;
			cin >> u >> v;
			g[u].push_back(v);
			g[v].push_back(u);
		}
		dfs(1, 0, 0);
		vector<vector<int> > v(20);
		for(int i = 1; i <= n; i++)
			v[msb[i]].push_back(i);
		for(int i = 19; i >= 0; i--)
		{
			int cur = 0;
			if(nodes[cur ^ 1].size() > nodes[cur].size())
				cur ^= 1;
			for(auto &it:v[i])
			{
				int node = nodes[cur].back();
				nodes[cur].pop_back();
				ans[node] = it;
			}
		}
		for(int i = 1; i <= n; i++)
			cout << ans[i] << " ";
		cout << endl;
	}
	return 0;
}

Solution [Kotlin] (ExplodingFreeze)

fun dfs(x: Int, p: Int, curcol: Int, adj: Array<MutableList<Int>>, col: Array<Int>) {
    col[x] = curcol
    adj[x]
        .filter { it != p }
        .forEach { dfs(it, x, curcol xor 1, adj, col) }
}
 
fun main(args: Array<String>) {
    val t = readLine()!!.toInt()
    repeat(t) {
        val n = readLine()!!.toInt()
        val adj = Array(n) { mutableListOf<Int>() }
        repeat(n - 1) {
            val (u, v) = readLine()!!.split(" ").map { it.toInt() }
            adj[u - 1].add(v - 1);
            adj[v - 1].add(u - 1);
        }
        val col = Array<Int>(n) {0}
        dfs(0, -1, 0, adj, col)
        var s = Array(2) { mutableListOf<Int>() }
        (0..n-1).forEach { s[col[it]].add(it) }
        if(s[0].size < s[1].size)
            s[0] = s[1].also { s[1] = s[0] }
        val highestBit = Array(20) { mutableListOf<Int>() }
        (1..n).forEach { highestBit[it.takeHighestOneBit().countTrailingZeroBits()].add(it - 1) }
        val ans = Array<Int>(n) {-1}
        (19 downTo 0).forEach { currentBit ->
            val largerSet = if(s[0].size >= s[1].size) 0 else 1
            highestBit[currentBit].forEach { it ->
                ans[it] = s[largerSet].last()
                s[largerSet].removeLast()
            }
        }
        val pos = Array<Int>(n) {-1}
        (0..n-1).forEach { pos[ans[it]] = it };
        (0..n-1).forEach { print ("${pos[it] + 1} ") }
        println()
    }
}

1605E - Array Equalizer

Authored and prepared by JeevanJyot.

Hint 1

Hint 2

Hint 3

Solution

Solution [c++] (JeevanJyot)

#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define int long long
#define endl "\n"
#define sz(w) (int)(w.size())
using pii = pair<int, int>;
 
const double EPS = 1e-9;
const long long INF = 1e18;
 
const int N = 2e5+5; 
 
int n, m, a[N], b[N], c[N], add[N], mob[N];
 
void mobius() 
{
    mob[1] = 1;
    for(int i = 2; i < N; i++)
    {
        mob[i]--;
        for(int j = i + i; j < N; j += i) 
        {
          mob[j] -= mob[i];
        }
    }
}
 
int32_t main()
{
    IOS;
    mobius();
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    for(int i = 1; i <= n; i++)
        cin >> b[i];
    for(int i = 1; i <= n; i++)
        c[i] = b[i] - a[i];
    c[1] = 0;
    vector<int> z;
    for(int i = 1; i <= n; i++)
    {
        int d = c[i];
        for(int j = i; j <= n; j += i)
        {
            c[j] -= d;
        }
        add[i] = d;
    }
    int ans = 0;
    for(int i = 1; i <= n; i++)
    {
        if(mob[i] == 0)
            ans += abs(add[i]);
        else if(mob[i] == -1)
            z.push_back(-add[i]);
        else 
            z.push_back(add[i]);
    }
    sort(z.begin(), z.end());
    vector<int> pref = z;
    for(int i = 1; i < sz(z); i++)
        pref[i] = pref[i-1] + z[i];
    auto sum = [&pref](int l, int r)
    {
        if(r < 0) return 0LL;
        int res = pref[r];
        if(l-1 >= 0)
            res -= pref[l-1];
        return res;
    };
    int q; cin >> q;
    while(q--)
    {
        int x; cin >> x;
        x -= a[1];
        int lo = 0, hi = sz(z)-1;
        while(lo <= hi)
        {
            int mid = (lo+hi)/2;
            if(z[mid] <= -x)
                lo = mid+1;
            else
                hi = mid-1;
        }
        swap(lo, hi);
        int res = sum(hi, sz(z)-1) + (sz(z)-hi) * x;
        res -= (sum(0, lo) + (lo+1)*x);
        cout << ans+res << endl;
    }
    return 0;
}

1605F - PalindORme

Authored by ExplodingFreeze and antontrygubO_o and prepared by ExplodingFreeze.

Hint 1

Hint 2

Hint 3

Hint 4

Hint 5

Solution

Solution [c++] (ExplodingFreeze)

#include <bits/stdc++.h>
#define int long long
using pii=std::pair<int,int>;
using namespace std;
 
const int maxn = 105;
 
int t, n, k, MOD, modinv[maxn], fact[maxn], invfact[maxn], cnt_distinct_positive[maxn][maxn], cnt_total[maxn][maxn], cnt_bad[maxn][maxn], pow2[maxn * maxn];
// cnt_distinct_positive[i][j] = ways of choosing i distinct positive values with a combined of exactly j bits on.
// cnt_total[i][j] = total number of arrays of length i with exactly j bits on in total
// cnt_bad[i][j] = number of bad arrays of length i with exactly j bits on in total
 
int mod_expo(int x, int p)
{
    if(!p)
        return 1;
    int res = mod_expo(x, p / 2);
    res *= res;
    res %= MOD;
    if(p & 1)
        res *= x;
    return res % MOD;
}
 
int mod_inv(int x)
{
    return mod_expo(x, MOD - 2);
}
 
// O(1) with O(n) precalc needed
int fast_nCr(int x, int r)
{
    assert(x < maxn && r >= 0 && r <= x);
    int num = fact[x];
    int denom = (invfact[r] * invfact[x - r]) % MOD;
    return (num * denom) % MOD;
}
 
// O(x - r)
int slow_nPr(int x, int r)
{
    assert(r >= 0 && r < maxn);
    int res = 1;
    for(int j = 1; j <= r; j++)
    {
        res *= (x - j + 1 + MOD) % MOD;
        res %= MOD;
    }
    return res;
}
 
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k >> MOD;
    fact[0] = invfact[0] = 1;
    for(int i = 1; i < maxn; i++)
    {
        modinv[i] = mod_inv(i);
        fact[i] = (fact[i - 1] * i) % MOD;
        invfact[i] = mod_inv(fact[i]);
    }
    pow2[0] = 1;
    for(int i = 1; i <= n * k; i++)
        pow2[i] = (pow2[i - 1] * 2) % MOD;
    for(int i = 0; i <= n; i++)
    {
        for(int j = 0; j <= k; j++)
        {
            // The number of ways of selecting i distinct positive values with upto j bits set in total
            cnt_distinct_positive[i][j] = slow_nPr((mod_expo(2, j) - 1 + MOD) % MOD, i);
            // The number of ways of selecting i non-negative values with upto j bits set
            cnt_total[i][j] = pow2[i * j];
            // Inclusion exclusion to get the count for exactly j bits for both values.
            for(int l = 0; l < j; l++)
            {
                cnt_distinct_positive[i][j] += (MOD - ((fast_nCr(j, l) * cnt_distinct_positive[i][l])) % MOD);
                cnt_distinct_positive[i][j] %= MOD;
                cnt_total[i][j] += (MOD - ((fast_nCr(j, l) * cnt_total[i][l])) % MOD);
                cnt_total[i][j] %= MOD;
            }
        }
    }
    // An empty array is good.
    cnt_total[0][0] = 1;
    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= k; j++)
        {
            cnt_bad[i][j] = 0;
            // i' <=> a, j' <=> b
            for(int a = 0; a < i; a++)
                for(int b = 0; b < j; b++)
                {
                    // The only case where this incorrect addition of "bad" arrays of size $$$i$$$ occurs is when we consider good 
                    // arrays of size $$$i - 1$$$ for odd $$$i$$$ during this process. So while calculating the answer for $$$n$$$ in the 
                    // problem we just have to skip good arrays of size $$$n - 1$$$ if $$$n$$$ is odd. 
                    if(i == n && (n & 1) && a == i - 1)
                        continue;
                    // f(i, j, i', j')
                    int cur_bad = 1;
                    // The number of ways of good arrays of length $$$i'$$$ distinct positive values with exactly $$$j'$$$ bits set in total:
                    cur_bad *= (cnt_total[a][b] - cnt_bad[a][b] + MOD) % MOD;
                    cur_bad %= MOD;
                    // The number of ways of selecting $$$i - i'$$$ distinct positive values with exactly $$$j - j'$$$ bits set in total. 
                    cur_bad *= cnt_distinct_positive[i - a][j - b];
                    cur_bad %= MOD;
                    // The number of ways of distributing the $$$i - i'$$$ values among the existing good array of length $$$i'$$$:
                    cur_bad *= fast_nCr(i, a);
                    cur_bad %= MOD;
                    // The number of ways of choosing which $$$j'$$$ of the $$$j$$$ bits were from the good array.
                    cur_bad *= fast_nCr(j, b);
                    cur_bad %= MOD;
                    // The number of ways of choosing the remaining $$$j'$$$ bits of each of the $$$i - i'$$$ distinct values.
                    cur_bad *= pow2[(i - a) * b];
                    cur_bad %= MOD;
                    cnt_bad[i][j] += cur_bad;
                    cnt_bad[i][j] %= MOD;
                }
        }
    int ans = 0;
    for(int j = 0; j <= k; j++)
    {
        int cnt_good = (cnt_total[n][j] - cnt_bad[n][j] + MOD) % MOD;
        // The number of ways of choosing the j bits from the k total bits.
        ans += (fast_nCr(k, j) * cnt_good) % MOD;
        ans %= MOD;
    }
    cout << ans << "\n";
    return 0;
}

Solution [c++] (antontrygubO_o)

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
 
using namespace __gnu_pbds;
using namespace std;
 
using ll = long long;
using ld = long double;
 
typedef tree<
        int,
        null_type,
        less<int>,
        rb_tree_tag,
        tree_order_statistics_node_update>
        ordered_set;
 
#define mp make_pair
 
int MOD;
 
int mul(int a, int b) {
    return (1LL * a * b) % MOD;
}
 
int add(int a, int b) {
    int s = (a+b);
    if (s>=MOD) s-=MOD;
    return s;
}
 
int sub(int a, int b) {
    int s = (a+MOD-b);
    if (s>=MOD) s-=MOD;
    return s;
}
 
int po(int a, ll deg)
{
    if (deg==0) return 1;
    if (deg%2==1) return mul(a, po(a, deg-1));
    int t = po(a, deg/2);
    return mul(t, t);
}
 
int inv(int n)
{
    return po(n, MOD-2);
}
 
 
mt19937 rnd(time(0));
 
 
const int LIM = 40000;
 
vector<int> facs(LIM), invfacs(LIM);
 
vector<vector<int>> C(400, vector<int>(400));
vector<int> degs(LIM);
 
void init()
{
    facs[0] = 1;
    for (int i = 1; i<LIM; i++) facs[i] = mul(facs[i-1], i);
    invfacs[LIM-1] = inv(facs[LIM-1]);
    for (int i = LIM-2; i>=0; i--) invfacs[i] = mul(invfacs[i+1], i+1);
 
    for (int i = 0; i<400; i++)
    for (int j = 0; j<=i; j++)
    {
        C[i][j] = mul(facs[i], mul(invfacs[j], invfacs[i-j]));
    }
    degs[0] = 1;
    for (int i = 1; i<LIM; i++) degs[i] = mul(2, degs[i-1]);
}
 
 
 
int solve1(int n, int k)
{
    vector<vector<int>> ch_diff(n+1, vector<int>(k+1));
 
    //Choose len distinct nonzero numbers from 1 to 2^k-1 such that each bit is present somewhere
 
    for (int len = 1; len<=n; len++)
    {
        for (int bits = 1; bits<=k; bits++)
        {
            int tot = sub(degs[bits], 1);
            ch_diff[len][bits] = 1;
            for (int i = 0; i<len; i++) {
                ch_diff[len][bits] = mul(ch_diff[len][bits], sub(tot, i));
            }
            //ch[len][bits] = mul(ch[len][bits], invfacs[len]);
 
            for (int bits1 = 1; bits1<bits; bits1++)
            {
                ch_diff[len][bits] = sub(ch_diff[len][bits], mul(ch_diff[len][bits1], C[bits][bits1]));
            }
        }
    }
 
    ch_diff[0][0] = 1;
 
    /*cout<<"CH_DIFF:"<<endl;
 
    for (int len = 0; len<=n; len++)
    {
        cout<<len<<": ";
        for (int bits = 0; bits<=k; bits++)
        {
            //cout<<sub(po(po(2, bits), len), dp_part[len][bits])<<' ';
            cout<<ch_diff[len][bits]<<' ';
        }
        cout<<endl;
    }*/
 
 
 
    vector<vector<int>> ch(n+1, vector<int>(k+1));
 
    //Choose len numbers from 0 to 2^k-1 such that each bit is present somewhere
 
    for (int len = 0; len<=n; len++)
    {
        for (int bits = 0; bits<=k; bits++)
        {
            ch[len][bits] = degs[bits*len];
 
            for (int bits1 = 0; bits1<bits; bits1++)
            {
                ch[len][bits] = sub(ch[len][bits], mul(ch[len][bits1], C[bits][bits1]));
            }
        }
    }
 
    /*cout<<"CH:"<<endl;
 
    for (int len = 1; len<=n; len++)
    {
        cout<<len<<": ";
        for (int bits = 0; bits<=k; bits++)
        {
            //cout<<sub(po(po(2, bits), len), dp_part[len][bits])<<' ';
            cout<<ch[len][bits]<<' ';
        }
        cout<<endl;
    }*/
 
 
    vector<vector<int>> dp_part(n+1, vector<int>(k+1));
 
    //Choose len numbers from 0 to 2^k-1 such that each bit is present somewhere and it's impossible to permutate
 
    for (int len = 1; len<=n; len++)
    {
        for (int bits = 0; bits<=k; bits++)
        {
            int ans = 0;
            for (int sz_bad = 1; sz_bad<=len; sz_bad++)
                for (int bits_bad = 1; bits_bad<=bits; bits_bad++)
                {
                    int good_rem = sub(ch[len-sz_bad][bits-bits_bad], dp_part[len-sz_bad][bits-bits_bad]);
                    //good arrays of length len-sz_bad on exactly bits-bits_bad bits
                    int adding = mul(ch_diff[sz_bad][bits_bad], good_rem);
 
                    adding = mul(adding, C[len][sz_bad]);
                    adding = mul(adding, C[bits][bits_bad]);
                    adding = mul(adding, degs[(bits-bits_bad)*sz_bad]);
                    ans = add(ans, adding);
                }
            dp_part[len][bits] = ans;
        }
    }
 
    /*cout<<"DP_PART:"<<endl;
 
    for (int len = 1; len<=n; len++)
    {
        cout<<len<<": ";
        for (int bits = 0; bits<=k; bits++)
        {
            //cout<<sub(po(po(2, bits), len), dp_part[len][bits])<<' ';
            cout<<dp_part[len][bits]<<' ';
        }
        cout<<endl;
    }*/
 
 
    int answer = 0;
 
    int min_sz_bad = 1; if (n%2==1) min_sz_bad = 2;
 
    for (int bits = 0; bits<=k; bits++)
    {
        int subans = 0;
        for (int sz_bad = min_sz_bad; sz_bad<=n; sz_bad++)
            for (int bits_bad = 1; bits_bad<=bits; bits_bad++)
            {
                int good_rem = sub(ch[n-sz_bad][bits-bits_bad], dp_part[n-sz_bad][bits-bits_bad]);
                //good arrays of length len-sz_bad on exactly bits-bits_bad bits
                int adding = mul(ch_diff[sz_bad][bits_bad], good_rem);
 
                adding = mul(adding, C[n][sz_bad]);
                adding = mul(adding, C[bits][bits_bad]);
                adding = mul(adding, degs[(bits-bits_bad)*sz_bad]);
                subans = add(subans, adding);
                //cout<<bits<<' '<<sz_bad<<' '<<bits_bad<<": "<<subans<<endl;
            }
        subans = sub(ch[n][bits], subans);
        subans = mul(subans, C[k][bits]);
        //cout<<ch[n][bits]<<' '<<subans<<endl;
        answer = add(answer, subans);
 
    }
    return answer;
}
 
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
 
    int n, k; cin>>n>>k>>MOD;
    init();
    cout<<solve1(n, k)<<endl;
 
}

Solution [Kotlin] (ExplodingFreeze)

fun mod_expo(base: Int, pow: Int, MOD: Int): Long {
    if(pow == 0) {
        return 1;
    }
    var res = mod_expo(base, pow / 2, MOD)
    res = (res * res) % MOD
    if(pow % 2 == 1) {
        res = (res * base) % MOD;
    }
    return res;
}
 
fun mod_inv(base: Int, MOD: Int): Long {
    return mod_expo(base, MOD - 2, MOD)
}
 
fun fast_nCr(n: Int, r: Int, fact: Array<Long>, invfact: Array<Long>, MOD: Int): Long {
    val num = fact[n];
    val denom = (invfact[r] * invfact[n - r]) % MOD;
    return (num * denom) % MOD;
}
 
fun slow_nPr(n: Int, r: Int, MOD: Int): Long {
    var res = 1L;
    for(i in 1..r) {
        res *= (n - i + 1 + MOD) % MOD;
        res %= MOD;
    }
    return res;
}
 
fun main(args: Array<String>) {
    val (n, k, MOD) = readLine()!!.split(" ").map { it.toInt() }
    val fact = Array<Long>(Math.max(n, k) + 1) { 1L }
    val invfact = Array<Long>(Math.max(n, k) + 1) { 1L }
    for(i in 1..Math.max(n, k)) {
        fact[i] = (fact[i - 1] * i) % MOD
        invfact[i] = mod_inv(fact[i].toInt(), MOD)
    }
    val pow2 = Array<Long>(n * k + 1) { 1 }
    for(i in 1..n*k) {
        pow2[i] = (pow2[i - 1] * 2) % MOD;
    }
    val cntDistinctPositive = Array(n + 1) { Array<Long>(k + 1) { 0L } }
    val cntTotal = Array(n + 1) { Array<Long>(k + 1) { 0L } }
    val cntBad = Array(n + 1) { Array<Long>(k + 1) { 0L } }
    for(i in 0..n) {
        for(j in 0..k) {
            cntDistinctPositive[i][j] = slow_nPr((mod_expo(2, j, MOD).toInt() - 1 + MOD) % MOD, i, MOD)
            cntTotal[i][j] = pow2[i * j]
            for(l in 0..j-1) {
                cntDistinctPositive[i][j] += (MOD - ((fast_nCr(j, l, fact, invfact, MOD) * cntDistinctPositive[i][l])) % MOD)
                cntDistinctPositive[i][j] = cntDistinctPositive[i][j] % MOD
                cntTotal[i][j] += (MOD - ((fast_nCr(j, l, fact, invfact, MOD) * cntTotal[i][l])) % MOD);
                cntTotal[i][j] = cntTotal[i][j] % MOD
            }
        }
    }
    cntTotal[0][0] = 1
    for(i in 1..n) {
        for(j in 0..k) {
            cntBad[i][j] = 0
             for(a in 0..i-1) {
                for(b in 0..j-1) {
                    if(i == n && n % 2 == 1 && a == i - 1) {
                        continue;
                    }
                    var curBad = (cntTotal[a][b] - cntBad[a][b] + MOD) % MOD
                    curBad *= (cntDistinctPositive[i - a][j - b])
                    curBad = curBad % MOD
                    curBad *= fast_nCr(i, a, fact, invfact, MOD)
                    curBad = curBad % MOD
                    curBad *= fast_nCr(j, b, fact, invfact, MOD)
                    curBad = curBad % MOD
                    curBad *= pow2[(i - a) * b]
                    curBad = curBad % MOD
                    cntBad[i][j] += curBad
                    cntBad[i][j] = cntBad[i][j] % MOD
                }
            }
        }
    }
    var ans = 0L
    for(j in 0..k) {
        val cntGood = (cntTotal[n][j] - cntBad[n][j] + MOD) % MOD
        ans += (fast_nCr(k, j, fact, invfact, MOD) * cntGood) % MOD
    }
    println(ans % MOD)
}

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

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

ExplodingFreeze

3 года назад, # |

Auto comment: topic has been updated by ExplodingFreeze (previous revision, new revision, compare).

→ Ответить

Sumeet_Verma_is_my_god

+12

In order to solve problems like this problem C, can anyone suggest me anything ? I have solved a lot of 'C' of div2(from another acc 'The_mysterio') , doesn't feel like it helped in this problem. It is observation I understand but may be something else in also needed????

Bungmint

3 года назад, # ^ |

+11

Just wondering, is there a reason behind having an alt account just for solving problems? Like you could already do that with your main account.

Two accounts just to hide my pain . Any advice for developing the hindsight for such 'C' s?

Drpzet

← Rev. 7 →

no-you-didnt

solving small random test cases and finding out an observation for the problem is a good technique.

shashank5013

+35

Thanks for giving hints before the exact solution . It improves the thinking process .

SouLPegasiuuuS

+18

For me, D was a really great problem.

I was able to find out Starting at any node should guarantee a win for her. And I can solve this by implementing bipartite concept. But could not implement in time :(

And yay, I won't be able to participate in Div 3 anymore. I am a blue now :)

_lowerBound

Congrats & strong performance :)! But: You still can participate in div3 though

Yeah, But it won't be rated for me :) Thanks.

RaghavChaurasia

waah bhaiyya,full commentbaaazi

← Rev. 3 →

+116

Also my apologies for F being too tough for a Div2 round. While I expected it would be tougher than an average Div2F I didn't expect it to go unsolved during the round.

Additionally, congratulations to maspy for managing to solve it (135175668) shortly after system testing concluded, before the editorial was posted.

Eclecticity

-35

Bitterly missed the 'traditional' questions today (DP, Seg-Tree based, Bin-Search, etc.) that would otherwise cushion the fall. Great contest though, ig.

TheScrasse

+64

You could try AtCoder Beginner Contest.

doj

+30

7 length substring!!!!!!!!!!

I will kill ya!!

ParsaS

← Rev. 2 →

-40

i like editorial with hints

but not this one

for E

<<Assume the value of b1 to be some variable, say x>> or << solve for one query>> i think if i could solve for one query, i could solve the main problem

joking? do you think this helps? really fun man

OleschY

+54

Just anecdotal evidence: I solved this task in the contest, and my first attempt solved the problem for 1 query (giving me $$$O(n \cdot q)$$$ complexity, which is not enough). Having implemented that, I was able to find the the optimisation needed afterwards. So I'd say, that one is a valid hint. :)

I guess the problem with hints for E is, that it is a pretty technical task. Like, you use the linearity between input and output to do some linear algebra magic and then you have to work with cases with absolute values. Hard to pinpoint the thing to a "central idea".

Edit: I think a two very good tips would've been:

Solve this by going from left to right and changing each $$$a_i$$$ to $$$b_i$$$. Notice, later operations on $$$i$$$ don't change numbers on positions smaller $$$i$$$.

Look at $$$a=(1,0,0,...)$$$ and $$$b=(0,0,0,...)$$$ and for each position $$$i$$$ count which operations were perfomed. Notice, that at each position either the first operation is performed exactly once, or the second operation is performed exactly once or no operation is performed.

+55

In Problem A you can also get the same result, by noticing, that the sum $$$S=a_1+a_2+a_3$$$ is invariant under the operations. With $$$a_1+a_3=S-a_2$$$ we obtain $$$d(a_1,a_2,a_3)=a_1+a_3-2\cdot a_2=S-3\cdot a_2$$$. So it's enough to check $$$d(a_1,a_2,a_3)\mod3=S\mod3$$$.

electronaota

Thank you for great contest! B and C were amazing :)

E404_Not_Found

really helpful hints for E :|

naeem4265

C:What is the wrong case? https://mirror.codeforces.com/contest/1605/submission/135143742

+14

In this test your code gives 2 expect 3

1
7
abbbaba

Try

1
2
ba

Should give $$$-1$$$, gives $$$2$$$. Your code "finds" and accepts the substring a as a valid string for check(2)

Olympia

+29

I lost 50 rating, but I thought the contest was really cool, and I'm really happy about the hint-based editorial :)

AA_Surely

+24

Super nice and enjoyable problems, I really liked problem D. The cool thing about this problem was how some observations could lead to a neat and easy to code solution, I really loved it.

hope to see more similar problems in the future. And thanks a lot for the round.

sharmaharisam

In case you guys prefer video solutions, here are the solutions to the first 4 problems: Solutions

Akshay162000

can we do problem C using sliding window ?How?

jha_rishi

for reference: https://mirror.codeforces.com/contest/1605/submission/135226082

ticmis

In problem C: I know "the string must look like "a??a??a??a??a" " is correct instinctively. But I could not prove it. Can anyone give me a provement of why the smallest substring should never contain something like "a _ _ _ a"?

ritesh1340

Because you have 3 spaces between the 2 a's

If the 3 spaces does not contain any more $$$a$$$, then "one" of the following 2 conditions are always true -

$$$count(a) = count(b)$$$ $$$or$$$ $$$ count(a) = count(c) $$$

And we don't want that.

And if it does contain at least one more a, then you can always form an answer with at most length=3 (And this will be a better answer)

Thanks a lot!

parthsharma6321

First of all a___a alone is not sufficient to a be a valid string because 3 elements in middle and atleast two would be same. so you need more characters to build a valid string. Now think of something like you could not make up a valid string here, so if a valid string were to exist, then you would have to make up for the fact you left spaces in between, and add some extra a's, then again as you are having two a's at a distance of atleast 4, so adding a's in this way...then the same problem comes. So to have those extra a's you would need to have those a's with dist < 4.Hope this helps. This was my logic behind it. But proving mathematically.. :((

Thanks! It is inspiring to me.

jtrh

$$$x\oplus y\nleq\min(x,y)$$$ for D is a typo right? $$$\nleq$$$ should be $$$\leq$$$

Yup, that's a typo, it will be fixed shortly.

shuv0

I think there is a typo: (Thus, if MSBx=MSBy then x⊕y≰min(x,y).), is not the xor will be always less than min(x,y). correct me if i am wrong.ExplodingFreeze

You are correct, it should be $$$\leq$$$, the typo will be fixed in a bit

wxy2005

I've got a little confusion according to tutorial of problem E.

$$$ |cx + d| $$$ = $$$ cx + d $$$ exist when $$$ cx + d \geq 0 $$$

which is $$$ cx \geq -d $$$.

When $$$ c > 0 $$$, the range of x will be $$$ x \geq -\frac{d}{c} $$$

When $$$ c < 0 $$$, the range of x will be $$$ x \leq -\frac{d}{c} $$$

But in the tutorial, it says $$$ |cx + d| = cx + d $$$ $$$ x \geq -\frac{d}{c}$$$

Could anyone explain it to me?

JeevanJyot I think this might be a mistake in your tutorial. I see that you change $$$ |cx + d| $$$ into $$$ |-cx - d| $$$ if c is negative in your code, you should write it in your tutorial.

JeevanJyot

Apologies for that. I will correct that in a while.

psychobot

C->D(1400->2100) shouldn't there be a problem of 1700 in between(considering div2)

giaogiao_2

Excuse me! But,I think that your solution of E has a mistake. Maybe your theory of sort is not right. Because "c" can be negative.

You can change c into positive because $$$ |cx + d| $$$ = $$$ |-cx - d| $$$. Although he didn't write it in the tutorial, you can see it in his code

Oh,I get it. Thanks a lot!

helloworld1102

Hello,wxy2005 I did not understood the concept of the problem E last lines of editorial This opening of |cx+d| thing .Like why we took into consideration the value of c because as it is a variable it can be positive or negative. Why the sign of c matters?Can you explain it fully ?

The sign of c does not matters. The only thing that matters is the sign of $$$(cx + d)$$$ because what we want to know is $$$\sum |c_ix + d_i|$$$.

We know that $$$|c_ix + d_i| = c_ix + d_i$$$ when $$$c_ix + d_i \geq 0$$$ are hold, and $$$|c_ix + d_i| = -c_ix -d_i $$$ when $$$c_ix + d_i < 0$$$ are hold.

If $$$c_i$$$ is positive, the inequality $$$c_ix + d_i \geq 0$$$ holds when $$$x \geq -\frac{d_i}{c_i}$$$, but if $$$c_i$$$ is negative, it will holds when $$$x \leq -\frac{d_i}{c_i}$$$

After doing this, we can sort all $$$c_i, d_i$$$ in the order of $$$\frac{d_i}{c_i}$$$. After doing this, we can used binary search to find a position that for all $$$c_i, d_i$$$ before it $$$c_ix + d_i \geq 0$$$ and for all $$$c_i, d_i$$$ after it $$$c_ix + d_i < 0$$$

Mayur9agt

JeevanJyot can you please explain " \n"[i+1 == ans.size()]?

Basically i+1 == ans.size() will be false (i.e. $$$0$$$) for all values of $$$i$$$ except its last value. So it will print the $$$0$$$-th character of the string " \n" which is ' '.

For the last $$$i$$$, the condition will be true (i.e. $$$1$$$). So it will print the $$$1$$$-st character of that string which is '\n'.

In a nutshell, it's just a one-liner way of printing some space-separated integers with a '\n' in the end.

wWwWw233

Thanks！

Ber

Thanks for the amazing contest! There´s a typo in the editorial of problem E, it says "B4−2" and it should be "B4-b2".

Thanks for pointing it out. Corrected it.

dunjen_master

Time Limit is too strict for C. I used a map to keep a count on the frequency of a, b and c and it resulted in TLE :(

shinghalrishabh

Regarding problem C, I found 13 minimal length substring "abbabbaccacca" which satisfies the properties mentioned in the problem.

But in the tutorial it is said that there can be atmost 7 length substring which can satisfy the property.

If you take characters [3, 9] of this string of length 13 you end up with “abbacca”, which is a string of length 7 satisfying the properties.

Dranoel321

I solved E with complexity $$$O(nlogn+q+2*A_{max})$$$ breaking the sum of $$$|c*x+d|$$$ into the difference between $$$|c*x+d|-|c*(x-1)+d|$$$ and using two prefix arrays but I really liked the editorial approach as it doesn't depend the value of $$$A_{max}$$$. :)

rohit2593

problem c : what is wrong in my code?

https://mirror.codeforces.com/contest/1605/submission/135505427

fallleaves01

I really like the problem F and thank you for the hints! ^ω^

Sprdalo

Is it possible to solve problem D (Treelabeling) via centroid decomposition?

Motivation on why I believe it is possible: when you divide the tree into at least 2 components and label the centroid with number whose MSB is k, then you can label the centroids of the remaining components with some numbers whose MSB is greater than k.

What have I tried: let's call the depth of centroid as the depth of the recursion when we found it (for example first centroid has depth 0, centroids of the remaining components have depth 1, after that decomposition centroids of those remaining components have depth 2, and so on...). Let's keep nodes in lists according to their depth sorted by the number of nodes in their components (when they become centroid). In the k-th list, we will pick first 2^k nodes and label them with numbers with MSB k. If there are more than 2^k such nodes, the rest we shall move to tier (list) k+1. Unfortunately this doesn't work, but I can't find the counter example :(

askd

yayayay I upsolved F with no hints after 3 days, fantastic problem!

thesoulreaper

2 года назад, # |

Under problem D, its written that MSBw < MSBn

But this looks wrong. MSBw can be equal to MSBn (eg MSBw = 4, MSBn = 4 where n = 6 and white nodes are 4). This actually caused problem for me to think where to ideally place fragmented last disjoint set of n. For example if n is 1, 3, 7, or 15, it has perfect disjoint sets of sizes 1, 2, 4, 8 etc. But if n is equal to say 6 then the disjoint sets will be 1, 2, 3 where set of size 3 is not full and will cause problem.

2 года назад, # ^ |

In the line just before $$$MSB_w \lt MSB_n$$$, it is mentioned that "WLOG let $$$w \leq b$$$ (we can swap the colours otherwise)" where WLOG is a common abbreviation of without loss of generality.

We are basically saying that since white and black nodes are just arbitrary labels, lets assume $$$w \leq b$$$ and prove that case. If this does not hold, we can just use the same proof after swapping their labelling (black <---> white).

Thanks man for clearing my doubt..:)

SIR01

5 недель назад, # |

In Problem B, test case 3, the output isn't correct. it has to be 2 3 6 instead of 3 3 5 6. Am i right??

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