Blog entries - Codeforces

#	User	Rating
1	Benq	3792
2	VivaciousAubergine	3647
3	Kevin114514	3603
4	jiangly	3583
5	strapple	3515
6	tourist	3470
7	dXqwq	3436
8	Radewoosh	3415
9	Otomachi_Una	3413
10	Um_nik	3376

#	User	Contrib.
1	Qingyu	157
2	adamant	152
3	Proof_by_QED	146
3	Um_nik	146
5	Dominater069	144
6	errorgorn	141
7	cry	139
8	YuukiS	135
9	chromate00	134
9	TheScrasse	134

Thank you everyone for participating!
Here's the Blog Link and Contest Link

E. Ash's Reunion

Idea and Prepared by: ImpersonaTe

Solution

Mathematical Expression:

$$$ \mathrm{ans}_i=\max\!\left\{\,k\ \middle|\space \exists\ \text{distinct }\space j_1,\dots,j_k\ (j_t\neq i\ \forall t)\space\text{ such that }\ \sum_{t=1}^k |x_i-x_{j_t}|\le b_i\,\right\} $$$

First, consider any person $$$a$$$ who lives at position $$$x$$$ on the coordinate line and has a budget $$$y$$$. Our goal is to determine how many people $$$a$$$ can invite such that the total travel cost does not exceed $$$y$$$.

A direct way to solve the equation for every possible $$$X$$$ (meeting point or pivot) takes $$$O(n)$$$ per query, resulting in $$$O(n^2)$$$ overall — which is too slow.

To improve this, we use the following optimized strategy:

We binary search on the answer — i.e., on the maximum number of people (say $$$m$$$) that person $$$a$$$ can invite. For a fixed number $$$m$$$, we must check whether it is feasible.

To check feasibility, we try selecting: $$$r$$$ participants from the left side of $$$x$$$, $$$m - r$$$ participants from the right side of $$$x$$$. For any chosen $$$r$$$, we compute the total travel cost and verify whether it stays within $$$y$$$. Since $$$r$$$ ranges from $$$0$$$ to $$$m$$$, we can again apply binary search on $$$r$$$ to efficiently find the best configuration. Thus, both searches combined significantly reduce the complexity from $$$O(n^2)$$$ to a much faster solution.

$$$\therefore$$$ The complexity of each query is $$$O(\log^2 n)$$$ and the overall complexity of the algorithm is $$$O(n \cdot \log^2 n)$$$ per test case.

Proof: We apply binary search on $$$r$$$ — but why? Because the cost function is unimodal.

The cost function is defined as:

$$$\text{cost}(r) = x \cdot r - \sum_{j=i-r}^{i-1} p_j + \sum_{j=i+1}^{i+(m-r)} p_j - x \cdot (m-r)$$$

Where $$$j$$$ is the index of $$$x$$$ in the position array $$$p$$$.

Define the forward difference:

$$$D(r) = \text{cost}(r+1) - \text{cost}(r)$$$ After simplification: $$$D(r) = 2x - S(r)$$$ Where $$$S(r) = x_{i-(r+1)} + x_{i+m-r-1}$$$ Since the array is sorted, we have: $$$S(r+1) \le S(r)$$$ Thus $$$D(r)$$$ is non-decreasing: $$$D(r+1) \ge D(r)$$$ Therefore, the cost function is unimodal, and binary search on $$$r$$$ is applicable.

Code

#include<bits/stdc++.h>
using namespace std; 
#define fr(i,s,n)      for(ll i=s;i<n;i++)
#define read(a)        for(auto &e:a) cin>>e;
typedef long long            ll;
void solve(){
    ll n; cin>>n;
    vector<ll> x(n),b(n); read(x); read(b);
    vector<ll> pref(n);
    pref[0]=x[0];
    fr(i,1,n) pref[i]=pref[i-1]+x[i];
    auto range_sum=[&](int l,int r)->ll{
        if(l>r) return 0;
        return pref[r]-(l?pref[l-1]:0);
    };
    auto split_cost=[&](int p,int m,int left)->ll{
        if(left<0) return 1e18;
        ll t=x[p];
        int leftL=p-left,leftR=p-1;
        int rightl=p,rightR=p+(m-left)-1;
        if(leftL<0 || rightR>=n) return 1e18;
        ll suml=range_sum(leftL,leftR);
        ll sumr=range_sum(rightl,rightR);
        ll costL=t*left-suml;
        ll costR=sumr-t*(m-left);
        return costL+costR;
    };
    auto min_cost=[&](int p,int m)->ll{// m is the length
        ll l=max(0ll,m-(n-p));
        ll r=min(m,p);
        if(l>r) return 1e18;
        // range for left-side element
        while(l<r){
            int mid=(l+r)>>1;
            ll cost1=split_cost(p,m,mid);
            ll cost2=split_cost(p,m,mid+1);
            if(cost2<cost1) l=mid+1;
            else r=mid;
        }
        return split_cost(p,m,l);
    };
    auto max_count=[&](int p,ll budget)->ll{
        ll low=1,high=n,ans=1;
        ll t=x[p];
        while(low<=high){
            ll mid=(low+high)>>1;
            if(min_cost(p,mid)<=budget){
                ans=mid;
                low=mid+1;
            }
            else high=mid-1;
        }
        return ans;
    };
    fr(i,0,n){
        cout<<max_count(i,b[i])-1<<" ";
    }

}   

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t=1;
    cin>>t;
    fr(i,0,t){
        solve();
        cout<<endl;
    }
    return 0;
}

Rate the Problem

F. Mankey vs Primeape

Idea and Prepared by: karock

Solution

Code

#include <bits/stdc++.h>
 
using namespace std;
 
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
 
#define ll long long

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll uid(ll l, ll r) {return uniform_int_distribution<ll>(l, r)(rng);} 

const int N = 2, MX = 1e5 + 1;
using Hash = array<int, N>;
const Hash M = {1000000007, 998244353};
const Hash B = {uid(1000001, M[0] - 1), uid(1000001, M[1] - 1)};
Hash pwr[MX];
 
Hash shift(Hash a, int p) {
    for (int i = 0; i < N; i++) {
        a[i] = (1ll * a[i] * pwr[p][i]) % M[i];
    }
    return a;
}
Hash add(Hash a, Hash b) {
    Hash res;
    for (int i = 0; i < N; i++) {
        res[i] = a[i] + b[i];
        if (res[i] > M[i]) res[i] -= M[i];
    }
    return res;
}
Hash sub(Hash a, Hash b) {
    Hash res;
    for (int i = 0; i < N; i++) {
        res[i] = a[i] - b[i];
        if (res[i] < 0) res[i] += M[i];
    }
    return res;
}
 
 
void solve() {
    int n; cin >> n;
    vector<vector<pair<int, int>>> adj(n);
    for (int i = 1; i < n; i++) {
        int u, v, w; cin >> u >> v >> w;
        --u, --v;
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }
    int timer = 0;
    vector<int> tin(n), tout(n);
    int LG = ceil(log2(n));
    vector<vector<int>> UP(n, vector<int>(LG + 1));
    vector<Hash> dp(n), up(n);
    auto dfs = [&] (auto dfs, int v, int p) -> void {
        tin[v] = timer++;
        UP[v][0] = p;
        for (int i = 1; i <= LG; i++) 
            UP[v][i] = UP[UP[v][i - 1]][i - 1];

        for (int i = 0; i < N; i++) dp[v][i] = 1;
        for (auto &[u, w] : adj[v]) if (u ^ p) {
            dfs(dfs, u, v);
            dp[v] = add(dp[v], shift(dp[u], w));
        }
        tout[v] = timer++;
    }; dfs(dfs, 0, 0);
    
    up[0] = dp[0];
    auto dfs_ = [&] (auto dfs, int v, int p, int w) -> void {
        if (v ^ p) {
            Hash t = sub(up[p], shift(dp[v], w));
            up[v] = add(dp[v], shift(t, w));
        } 
        for (auto &[u, w] : adj[v]) if (u ^ p) dfs(dfs, u, v, w);
    }; dfs_(dfs_, 0, 0, 0);
 
    auto is_ancestor = [&](int u, int v) {
        return tin[u] <= tin[v] && tout[u] >= tout[v];
    };
    auto lca = [&](int u, int v) {
        if (is_ancestor(u, v))
            return u;
        if (is_ancestor(v, u))
            return v;
        for (int i = LG; i >= 0; i--) {
            if (!is_ancestor(UP[u][i], v))
                u = UP[u][i];
        }
        return UP[u][0];
    };
    vector<int> order(n);
    iota(order.begin(), order.end(), 0ll);
    sort(order.begin(), order.end(), [&] (const int &i, const int &j) {
        return up[i] < up[j];
    });
    vector<int> a(n), pre(n);
    for (int i = 0; i < n; i++) {
        int j = i;
        while (j < n && up[order[i]] == up[order[j]]) j++;
        for (int k = i; k < j; k++) a[order[k]] = j - i;
        i = j - 1;
    }
    auto dfs_last = [&] (auto dfs, int v, int p) -> void {
        pre[v] = pre[p] ^ a[v];
        for (auto &[u, w] : adj[v]) if (u != p) {
            dfs(dfs, u, v);
        }
    }; dfs_last(dfs_last, 0, 0);
    auto query = [&] (int v, int u) {
        int _lca = lca(u, v);
        return pre[v] ^ pre[u] ^ a[_lca];
    };
    int q; cin >> q;
    while (q--) {
        int x, y; cin >> x >> y;
        --x, --y;
        cout << query(x, y) << "\n";
    }
}
 
 
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int _TEST = 1;
    cin>>_TEST;
    for (int i = 0; i < N; i++) pwr[0][i] = 1;
    for (int i = 1; i < MX; i++) 
        for (int j = 0; j < N; j++)
            pwr[i][j] = 1ll * pwr[i - 1][j] * B[j] % M[j];
    
    for(int _ = 1; _ <= _TEST; _++) {
        solve();
    }
        
}

Rate the Problem

G. Professor Oak's (Poke)balls

Idea: V1_rus and Solution: Determinist

Solution

Trivial case: If $$$n \lt k$$$, then the modulo operation never happens and we can choose $$$b$$$ to be infinitely large, so the answer will be $$$-1$$$.

Now, The problem can be divided into two different sections:

i) Finding the maximum number of balls possible at time $$$n$$$

At every second, we multiply the current number of balls by $$$2$$$, and at every second $$$t$$$ such that $$$k$$$ divides $$$t$$$, the number of balls $$$x$$$ becomes $$$x \bmod c$$$. We know repeated periodic modulo in such operations is equivalent to taking modulo only once at the end. Hence, we can find the final position $$$m$$$ such that $$$m \bmod k = 0$$$ and $$$m \le n$$$ (i.e., $$$m = n - n \bmod k$$$).

Since the operations after $$$m$$$ are constant and are not altered by the modulo operation, we can calculate the maximum number of balls we can achieve at $$$n$$$ by maximizing the number of balls at $$$m$$$. Initially, we start with $$$b$$$ balls $$$(b \ge 0)$$$, and each second, the number of balls doubles. So the expression that we need to maximize is $$$b \cdot 2^{m} \bmod c$$$. Let $$$\gcd(2^{m}, c)$$$ be $$$g$$$. Then we know the results of this expression are multiples of $$$g$$$. So the results are: $$$0, g, 2g, 3g, \ldots$$$

Therefore, the maximum value that we can achieve for the expression would be the last multiple of $$$g$$$ that is less than $$$c$$$. Since $$$g$$$ divides $$$c$$$, this maximum value is $$$c - g$$$. Hence the maximum number of balls that we can achieve at $$$m$$$ is $$$c - g$$$. Now we need to multiply $$$c - g$$$ by $$$2^{n - m}$$$ modulo $$$998244353$$$ to get the maximum balls at $$$n$$$ modulo $$$998244353$$$.

ii) Find the minimum $$$b$$$ that achieves this maximum.

Now that we know the maximum number of balls we can achieve is $$$c - g$$$ at $$$m$$$. So the new equation to find $$$b$$$ is: $$$(b \cdot 2^{m} \equiv c - g) \bmod c$$$ $$$\Rightarrow (b \cdot 2^{m} \equiv -g) \bmod c$$$

Now, since $$$g$$$ divides both sides of the equivalence as well as the modulo, $$$\Rightarrow (b \cdot 2^{m} / g \equiv -g / g) \bmod (c / g)$$$

Let $$$2^{m} / g$$$ and $$$c / g$$$ be $$$x$$$ and $$$y$$$ respectively. (We know $$$g$$$ divides both $$$2^{m}$$$ and $$$c$$$.) $$$\Rightarrow (b \cdot x \equiv -1) \bmod y$$$ $$$\Rightarrow (b \equiv -x^{-1}) \bmod y$$$ (the inverse $$$x^{-1} \bmod y$$$ exists because $$$\gcd(x, y) = 1$$$)

Hence, we can calculate $$$b$$$ by solving $$$(-x^{-1}) \bmod y$$$.

Time complexity: $$$O(\log n)$$$

Code

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ull unsigned long long
#define sz(x) ((int)(x).size())
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll uid(ll l, ll r) {return uniform_int_distribution<ll>(l, r)(rng);} 


#define int long long
const int N = 1e6 + 10;
const int M = 998244353;

int bpow(int x, int p, int mod) {
    int res = 1;
    while(p) {
        if(p & 1) res = (res * x) % mod;
        x = (x * x) % mod;
        p >>= 1;
    }
    return res;
}

int gcd(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int x1, y1;
    int d = gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return d;
}

int inv(int x, int mod) {
    x %= mod;
    int a, b;
    assert(gcd(x, mod, a, b) == 1);
    return (a % mod + mod) % mod;
}

void Determinist() {
    int n, k, c; cin >> n >> k >> c;
    if(n < k) {
        cout << "-1\n";
        return;
    }
    int pw = bpow(2, n - n % k, c);
    int g = __gcd(pw, c);
    int ans = c - g;
    int npw = pw / g;
    int nc = c / g;
    int b = (nc - inv(npw, nc)) % nc;
    cout << (ans * bpow(2, n % k, M)) % M << ' ' << b << '\n';
}
int32_t main() {
    ios_base ::sync_with_stdio(0); 
    cin.tie(0);               
    cout.tie(0);

    int t = 1;
    cin >> t;
    while(t--) {
        Determinist();
    }
}

Rate the Problem

H. Brock the Builder

Idea and Prepared by: pranav_2005

Solution

Code

#include <bits/stdc++.h>
#include <climits>

#ifndef ONLINE_JUDGE
#include "debug.h"
#else
#define debug(...)
#endif

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <class T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define ll long long
#define ld long double
#define endl '\n'

const ld eps = 1e-12;

ll no_operation = LLONG_MAX;
ll x;
struct Node {
	ll l = -1, r = -1;
	ll sum = 0;
	ll operation = no_operation;
	bool type = false;
	ll maxi = LLONG_MIN;
	Node(ll val, ll idx) {
		// debug(x);
		l = idx, r = idx;
		sum = val;
		maxi = val - l * x;
	}
	Node() {

	}
	void apply(ll op) {
		type = false;
		operation = op;
		sum = (r - l + 1) * op;
		maxi = op - l * x;
	}
	void apply1(ll op) {
		if (operation != no_operation) {
			operation += op;
		} else if (operation == no_operation) {
			operation = op;
			type = true;
		}
		sum += (r - l + 1) * op;

		maxi += op;
	}
};

struct Stree {
	vector<Node> segtree;
	vector<ll> arr;
	void init(ll n, vector<ll> A) {
		arr = A;
		segtree.resize(4 * (n + 1));
	}

	Node merge(const Node &left, const Node &right) {
		if (left.l == -1)return right;
		if (right.l == -1)return left;
		Node cur;
		cur.l = left.l;
		cur.r = right.r;
		cur.maxi = max(left.maxi, right.maxi);
		cur.sum = right.sum + left.sum;
		return cur;
	}

	void propagate(ll tl, ll tr, ll node) {
		if (tl >= tr)return;
		if (segtree[node].operation != no_operation) {
			ll op = segtree[node].operation;
			if (!segtree[node].type) {

				segtree[2 * node].apply(op);
				segtree[2 * node + 1].apply(op);
			} else {
				segtree[2 * node].apply1(op);
				segtree[2 * node + 1].apply1(op);
			}
		}
		segtree[node].operation = no_operation;
	}

	void build(ll l, ll r, ll node) {
		if (l > r) return;
		if (l == r) {
			segtree[node] = Node(arr[l], l);
			return;
		}
		ll mid = (l + r) >> 1;
		build(l, mid, 2 * node);
		build(mid + 1, r, 2 * node + 1);
		segtree[node] = merge(segtree[2 * node], segtree[2 * node + 1]);
	}

	Node query(ll l, ll r, ll tl, ll tr, ll node) {
		propagate(tl, tr, node);
		if (l > r || tl > tr || tl > r || tr < l) return Node();

		if (tl >= l && tr <= r) {
			return segtree[node];
		}

		ll mid = (tl + tr) >> 1;
		return merge(query(l, r, tl, mid, 2 * node) ,
		             query(l, r, mid + 1, tr, 2 * node + 1));
	}


	ll Query(ll idx, ll val, ll tl, ll tr, ll node)
	{
		propagate(tl, tr, node);
		if (tl > tr || segtree[node].maxi < val || tl >= idx)return -1;
		if (tl == tr)return tl;
		ll mid = (tl + tr) >> 1;
		ll right = Query(idx, val, mid + 1, tr, 2 * node + 1);
		if (right != -1)return right;
		return Query(idx, val, tl, mid,	2 * node);
	}


	void update(ll l, ll r, bool type, ll value, ll tl, ll tr, ll node) {
		propagate(tl, tr, node);
		ll mid = (tl + tr) >> 1;
		if (tl > tr || tr < l || tl > r || l > r) return;

		if (tl >= l && tr <= r) {
			// we apply update
			if (!type)
				segtree[node].apply(value);
			else segtree[node].apply1(value);
			return;
		}
		update(l, r, type, value, tl, mid, 2 * node);
		update(l, r, type, value, mid + 1, tr, 2 * node + 1);

		segtree[node] = merge(segtree[2 * node], segtree[2 * node + 1]);
	}


	void update(ll l, ll val, ll tl, ll tr, ll node) {
		propagate(tl, tr, node);
		ll mid = (tl + tr) >> 1;
		if (tl > tr || tr < l || tl > l) return;

		if (tl == l && tr == l) {
			segtree[node] = Node(val, l);
			return;
		}
		update(l, val, tl, mid, 2 * node);
		update(l, val, mid + 1, tr, 2 * node + 1);

		segtree[node] = merge(segtree[2 * node], segtree[2 * node + 1]);
	}
};


void solve() {
	ll n, q; cin >> n >> q >> x;
	vector<ll> a(n + 1);
	vector<ll> arr(n + 1, 0);
	for (ll i = 1; i <= n; i++)cin >> a[i];
	Stree just;
	just.init(n + 1, a);
	just.build(1, n, 1);
	while (q--) {
		ll type; cin >> type;
		if (type == 1 || type == 2) {
			ll l, r ; cin >> l >> r;
			ll val ; cin >> val;
			just.update(l, r, (type == 2), val, 1, n, 1);
		} else {
			ll i , k; cin >> i >> k;



			ll cur = just.query(i, i, 1, n, 1).sum;
			if (k < cur) {
				cout << -1 << endl;
				continue;
			}
			if (k == cur) {
				cout << 0 << endl;
				continue;
			}



			auto ck1 = [&](ll mid)->ll{
				ll looking = mid - i * x ;
				ll idx = just.Query(i, looking, 1, n, 1);
				if (idx != -1) {

					ll su = just.query(idx + 1, i, 1, n, 1).sum;
					ll len = i - idx;
					ll sum = (2 * mid + (len - 1) * (-x)) * len;
					sum >>= 1;
					return sum - su;
				} return -1;
			};
			cout << ck1(k) << endl;
		}
	}
}




int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
#ifndef ONLINE_JUDGE
	freopen("F:\\cp_sublime\\input.txt", "r", stdin);
	freopen("F:\\cp_sublime\\output.txt", "w", stdout);
	freopen("F:\\cp_sublime\\debug.txt", "w", stderr);
#endif
	int tt = 1;
	cin >> tt;
	while (tt--)
		solve();
}

Rate the Problem

I. Pokedex and Lexicographically Smallest String

Idea and Prepared by: 7rikster

Solution

Code

#include <bits/stdc++.h>
 
using namespace std;

struct FenwickTree {
    int n;
    vector<int> bit;
    FenwickTree(int n) {
        this->n = n;
        bit.assign(n, 0);
    }
    FenwickTree(vector<int> const &a) : FenwickTree(a.size()) {
        for (size_t i = 0; i < a.size(); i++)
            add(i, a[i]);
    }
    int sum(int r) {
        int ret = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1)
            ret += bit[r];
        return ret;
    }
    int sum(int l, int r) {
        return sum(r) - sum(l - 1);
    }
    void add(int idx, int delta) {
        for (; idx < n; idx = idx | (idx + 1))
            bit[idx] += delta;
    }
};
 
void solve() {
    int n, k; cin >> n >> k;
    string s; cin >> s;
 
    vector<set<int>> at(26);
    for (int i = 0; i < n; i++) {
        at[s[i] - 'a'].insert(i);
    }
    vector<int> ans;
    FenwickTree bit(n);
    for (int i = 0; i < n; i++) bit.add(i, 1);
    int rem = k, start = 0;
    for(int q = 0; q<n/k; q++){
        start = -1;
        rem = k;
        vector<int> v;
        for (int j = 0; j < k; j++) {
            for (int i = 0; i < 26; i++) {
                auto it = at[i].upper_bound(start);
                if (it == at[i].end()) continue;
                int sum = bit.sum(n - 1 - *it);
                if (sum>=rem) {
                    ans.push_back(*it);
                    start = *it;
                    v.push_back(i);
                    rem--;
                    break;
                }
            }
        }
        reverse(v.begin(),v.end());
        int p = n+1;
        for(auto i:v){
            auto it = prev(at[i].lower_bound(p));
            p = *it;
            bit.add(n - 1 - *it, -1);
            at[i].erase(it);
        }
    }
    for (int &e : ans) cout << s[e];
    cout << "\n";
}
int32_t main() {
#ifndef ONLINE_JUDGE
    freopen("Error.txt", "w", stderr);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0); 
    int _TEST = 1;
    cin>>_TEST;

    for(int i=1; i<=_TEST; i++) {
        solve();
    }   
}

Rate the Problem

J. Pikachu or Mimikyu?

Idea and Prepared by: karock

Solution

Code

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif

#define int long long

using Matrix = array<array<int, 2>, 2>;
const int MOD = 998244353;
Matrix mul(Matrix a, Matrix b) {
    Matrix res = {{{0, 0}, {0, 0}}};
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 2; k++) {
                res[i][j] += a[i][k] * b[k][j];
                res[i][j] %= MOD;
            }
        }
    }
    return res;
}
void solve() {
    int n; cin >> n;
    Matrix base = {{{1, 0}, {0, 1}}};
    Matrix m = {{{1, 1}, {1, 0}}};
    n += 3;
    for (; n > 0; n /= 2, m = mul(m, m)) {
        if (n & 1) base = mul(base, m);
    }
    int ans = base[0][1] - 1;
    if (ans < 0) ans += MOD;
    cout << ans << "\n";
}
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int _TEST = 1;
    cin>>_TEST;
    for(int _ = 1; _ <= _TEST; _++) {
        solve();
    }
}

Rate the Problem

K. Pokemon Battle?

Idea and Prepared by: karock

Hint 1

Hint 2

Solution

Code

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif

#define int long long

void solve() {
    int n, m; cin >> n >> m;
    vector<vector<int>> a(n, vector<int>(m));
    for (auto &v : a) for (int &e : v) cin >> e;
    int alice = 0;
    int bob = a[0][0] + a[0][m - 1] + a[n - 1][0] + a[n - 1][m - 1];
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) 
        if (i != 0 && i != n - 1 && j != 0 && j != m - 1) 
            alice += a[i][j];

    if (alice > bob) cout << "Ash\n";
    else cout << "Gary\n";
}
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int _TEST = 1;
    cin>>_TEST;
    for(int _ = 1; _ <= _TEST; _++) {
        solve();
    }
}

Rate the Problem

L. Uncreative Pokemon Themed Problem Name

Idea and Prepared by: karock

Solution

Code

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
void solve() {
    int n; cin >> n; 
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
    }
    cout << (n - 1 >> 1) << "\n";
 
}
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int _TEST = 1;
    cin>>_TEST;
    for(int _ = 1; _ <= _TEST; _++) {
        solve();
    }    
}

Rate the Problem

M. Ho-oh's Arrival

Idea and Prepared by: Determinist

Solution

Let’s represent the array $$$a$$$ as a Directed Graph with vertices $$$1 \ldots n$$$ and edges $$$i \rightarrow a_i$$$.

If $$$a_i \le n$$$, the edge points to another vertex in the graph

Else, the edge points to outside of the graph, thus imposing no restrictions.

We can observe that for a good array, the graph has two types of edges $$$(i, a_i)$$$:

i) $$$a_i \ge i$$$: The indegree (number of edges incident on a vertex) of $$$i$$$ can take any non-negative value.

ii) $$$a_i \lt i$$$: The indegree of $$$i$$$ has to be zero.

Proof

So let’s divide the elements $$$i$$$ into two sets :

i) Good ($$$G$$$): $$$a_i \ge i$$$

ii) Bad ($$$B$$$): $$$a_i \lt i$$$ and $$$a_i \in G$$$

Now we can frame the solution as:

We chose a subset of indices $$$G \in {1, 2, \ldots, n}$$$. Let $$$|G| = k$$$.

For $$$i \in G$$$: $$$a_i \ge i$$$ must hold.

For $$$i \in B$$$: $$$a_i \in G$$$ and $$$a_i \lt i$$$.

Let’s pursue a DP approach. Let $$$dp_{i, j}$$$ be the number of ways to assign the first $$$i$$$ elements to the sets $$$G$$$ and $$$B$$$ such that $$$j$$$ elements belong to $$$G$$$.

Add $$$i^{th}$$$ element to $$$G$$$: $$$dp_{i, j} += dp_{i - 1, j - 1}$$$

Add $$$i^{th}$$$ element to $$$B$$$ by choosing one of the $$$j$$$ elements in $$$G$$$ to anchor it: $$$dp_{i, j} += dp_{i - 1, j} \cdot j$$$

So, $$$dp_{i, j} = dp_{i - 1, j - 1} + dp_{i - 1, j} \cdot j$$$.

However, these transitions would only land us with an $$$O(n^2)$$$ transition that would TLE under our problem constraints.

To optimise $$$dp$$$, we can observe that $$$dp_{i, j}$$$ basically calculates the number of ways to partition a set of $$$i$$$ elements into $$$j$$$ non-empty subsets, which is exactly the definition of Stirling Numbers of the Second Kind.

So finally, the number of ways to distribute $$$n$$$ elements to the sets $$$G$$$ and $$$B$$$ such that $$$k$$$ of them belong to the set $$$G$$$:

$$$dp_{n, k} = S(n, k) = \sum_{t = 0}^{k} \frac{(-1)^{k - t}t^n}{t!(k-t)!}$$$

We can calculate the $$$n^{th}$$$ row of Stirling Numbers of the Second Kind using NTT efficiently.

Let the indices in $$$G$$$ the sorted order be: $$$j_1, j_2, \ldots j_k$$$. Now we need to assign values to each of these indices.

Let's consider $$$j_k$$$, it can take any value $$$ \gt n$$$ or $$$a_{j_{k}} = j_k$$$. So there are $$$(max(0, m - n) + 1)$$$ ways.

Now for $$$j_{k -1}$$$, it can either take values $$$ \gt n$$$ or from {$$$j_{k-1}, j_k$$$}, hence there are $$$(max(0, m - n) + 2)$$$ ways.

We can generalize the ways for each $$$j_p$$$ ($$$1 \le p \le k$$$) as: $$$(max(0, m - n) + k - p + 1) $$$

Hence, the total number of ways to assign values to each of the indices is:

$$$ways_k = \prod_{p = 1}^{k} (max(0, m - n) + p)$$$

So the total number of ways to form good arrays is:

Case $$$m \ge n$$$:

$$$Ans = \sum_{k = 0}^{n} S(n, k) \cdot ways_k$$$

Case $$$m \lt n$$$:

All the indices $$$i$$$ such that $$$i \gt m$$$ will have to be part of set $$$B$$$ and will point to one of the $$$k$$$ elements in $$$G$$$. Hence, we can calculate the number of good arrays with size $$$m$$$ and point the rest $$$n-m$$$ elements to one of the $$$k$$$ indices belonging to $$$G$$$. This leads to a multiplier of $$$k^{n-m}$$$.

$$$Ans = \sum_{k = 0}^{m} S(m, k) \cdot ways_k \cdot k^{n - m}$$$

Overall time complexity: $$$O(nlogn)$$$

Code

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ull unsigned long long
#define sz(x) ((int)(x).size())
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll uid(ll l, ll r) {return uniform_int_distribution<ll>(l, r)(rng);} 


const int N = 1e6 + 10;

ll myRand(ll B) {
    return (ull)rng() % B;
}
 
 
ll MOD = 998244353;
struct Mint { // 1000000007  1000000009
    ll x;
 
    Mint() : x(0) {}
    Mint(ll _x) {
        _x %= MOD;
        if (_x < 0) _x += MOD;
        x = _x;
    }
 
    Mint& operator += (const Mint &a) {
        x += a.x;
        if (x >= MOD) x -= MOD;
        return *this;
    }
    Mint& operator -= (const Mint &a) {
        x += MOD - a.x;
        if (x >= MOD) x -= MOD;
        return *this;
    }
    Mint& operator *= (const Mint &a) {
        x = (ull)x * a.x % MOD;
        return *this;
    }
    Mint pow(ll pw) const {
        Mint res = 1;
        Mint cur = *this;
        while(pw) {
            if (pw & 1) res *= cur;
            cur *= cur;
            pw >>= 1;
        }
        return res;
    }
    Mint inv() const {
        assert(x != 0);
        ll t = x;
        ll res = 1;
        while(t != 1) {
            ll z = MOD / t;
            res = (ull)res * (MOD - z) % MOD;
            t = MOD - t * z;
        }
        return res;
    }
    Mint& operator /= (const Mint &a) {
        return *this *= a.inv();
    }
    Mint operator + (const Mint &a) const {
        return Mint(*this) += a;
    }
    Mint operator - (const Mint &a) const {
        return Mint(*this) -= a;
    }
    Mint operator * (const Mint &a) const {
        return Mint(*this) *= a;
    }
    Mint operator / (const Mint &a) const {
        return Mint(*this) /= a;
    }
 
    bool sqrt(Mint &res) const {
        if (MOD == 2 || x == 0) {
            res = *this;
            return true;
        }
        if (pow((MOD - 1) / 2) != 1) return false;
        if (MOD % 4 == 3) {
            res = pow((MOD + 1) / 4);
            return true;
        }
        int pw = (MOD - 1) / 2;
        int K = 30;
        while((1 << K) > pw) K--;
        while(true) {
            Mint t = myRand(MOD);
            Mint a = 0, b = 0, c = 1;
            for (int k = K; k >= 0; k--) {
                a = b * b;
                b = b * c * 2;
                c = c * c + a * *this;
                if (((pw >> k) & 1) == 0) continue;
                a = b;
                b = b * t + c;
                c = c * t + a * *this;
            }
            if (b == 0) continue;
            c -= 1;
            c *= Mint() - b.inv();
            if (c * c == *this) {
                res = c;
                return true;
            }
        }
        assert(false);
    }
 
    bool operator == (const Mint &a) const {
        return x == a.x;
    }
    bool operator != (const Mint &a) const {
        return x != a.x;
    }
    bool operator < (const Mint &a) const {
        return x < a.x;
    }
};
struct Factorials {
    vector<Mint> f, fi;
 
    Factorials() : f(), fi() {}
    Factorials(int n) {
        n += 10;
        f = vector<Mint>(n);
        fi = vector<Mint>(n);
        f[0] = 1;
        for (int i = 1; i < n; i++)
            f[i] = f[i - 1] * i;
        fi[n - 1] = f[n - 1].inv();
        for (int i = n - 1; i > 0; i--)
            fi[i - 1] = fi[i] * i;
    }
 
    Mint C(int n, int k) {
        if (k < 0 || k > n) return 0;
        return f[n] * fi[k] * fi[n - k];
    }
};
struct Powers {
    vector<Mint> p, pi;
 
    Powers() : p(), pi() {}
    Powers(int n, Mint x) {
        n += 10;
        if (x == 0) {
            p = vector<Mint>(n);
            p[0] = 1;
        } else {
            p = vector<Mint>(n);
            pi = vector<Mint>(n);
            p[0] = pi[0] = 1;
            Mint xi = x.inv();
            for (int i = 1; i < n; i++) {
                p[i] = p[i - 1] * x;
                pi[i] = pi[i - 1] * xi;
            }
        }
    }
 
    Mint pow(int n) {
        if (n >= 0)
            return p[n];
        else
            return pi[-n];
    }
};
struct Inverses {
    vector<Mint> ii;
 
    Inverses() : ii() {}
    Inverses(int n) {
        n += 10;
        ii = vector<Mint>(n);
        ii[1] = 1;
        for (int x = 2; x < n; x++)
            ii[x] = Mint() - ii[MOD % x] * (MOD / x);
    }
 
    Mint inv(Mint x) {
        assert(x != 0);
        ll t = x.x;
        ll res = 1;
        while(t >= (int)ii.size()) {
            ll z = MOD / t;
            res = (ull)res * (MOD - z) % MOD;
            t = MOD - t * z;
        }
        return ii[t] * res;
    }
};

#define int long long

const long long mod = (119 << 23) + 1, root = 62; // = 998244353
// For p < 2^30 there is also e.g. 5 << 25, 7 << 26, 479 << 21
// and 483 << 21 (same root). The last two are > 10^9.

long long modpow(long long b, long long e) {
	long long ans = 1;
	for (; e; b = b * b % mod, e /= 2)
		if (e & 1) ans = ans * b % mod;
	return ans;
}
typedef vector<long long> vl;
void ntt(vl &a) {
	int n = sz(a), L = 31 - __builtin_clz(n);
	static vl rt(2, 1);
	for (static int k = 2, s = 2; k < n; k *= 2, s++) {
		rt.resize(n);
		long long z[] = {1, modpow(root, mod >> s)};
		for(int i = k; i < 2 * k; i ++) rt[i] = rt[i / 2] * z[i & 1] % mod;
	}
	vector<int> rev(n);
	for(int i = 0; i < n; i ++) rev[i] = (rev[i / 2] | (i & 1) << L) / 2;
	for(int i = 0; i < n; i ++) if (i < rev[i]) swap(a[i], a[rev[i]]);
	for (int k = 1; k < n; k *= 2)
		for (int i = 0; i < n; i += 2 * k) for(int j = 0; j < k; j ++) {
			long long z = rt[j + k] * a[i + j + k] % mod, &ai = a[i + j];
			a[i + j + k] = ai - z + (z > ai ? mod : 0);
			ai += (ai + z >= mod ? z - mod : z);
		}
}
vl conv(const vl &a, const vl &b) {
	if (a.empty() || b.empty()) return {};
	int s = sz(a) + sz(b) - 1, B = 32 - __builtin_clz(s),
	    n = 1 << B;
	int inv = modpow(n, mod - 2);
	vl L(a), R(b), out(n);
	L.resize(n), R.resize(n);
	ntt(L), ntt(R);
	for(int i = 0; i < n; i ++)
		out[-i & (n - 1)] = (long long)L[i] * R[i] % mod * inv % mod;
	ntt(out);
	return {out.begin(), out.begin() + s};
}

Factorials ft(N);

void Determinist() {
    int n, m; cin >> n >> m;
    int N = min(n, m);

    vl a(N + 1), b(N + 1);
    for(int i = 0; i <= N; i ++) {
        a[i] = (ft.fi[i] * (i & 1? -1: 1)).x;
        b[i] = (Mint(i).pow(N) * ft.fi[i]).x;
    }
    auto c = conv(a, b); //stirling second kind
    
    Mint ans = 0, ways = 1;
    for(int i = 1; i <= N; i ++) {
        ways *= (max(0ll, m - n) + i);
        ans += ways * c[i] * Mint(i).pow(max(0ll, n - m));
    }
    cout << ans.x << '\n';
}   

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

    int t = 1;
    cin >> t;
    while(t--) {
        Determinist();
    }
}

Rate the Problem

Full text and comments »

karock's blog

Please refer to these guidelines to make sure you are prepared to submit the videos after the contest.

UPDATE: Submit your recordings here.

A. AntiDitto Arrays!

B. Alakazam's GCD Riddles

C. Pokeball Engineering

D. Who's that Pokemon?

E. Ash's Reunion

F. Mankey vs Primeape

G. Professor Oak's (Poke)balls

H. Brock the Builder

I. Pokedex and Lexicographically Smallest String

J. Pikachu or Mimikyu?

K. Pokemon Battle?

L. Uncreative Pokemon Themed Problem Name

M. Ho-oh's Arrival