For each index $$$i$$$ ($$$k + 1 \le i \le n$$$), there is exactly one element among $$$a_1$$$ to $$$a_k$$$, which can swap with $$$a_i$$$. If $$$a_i$$$ is greater than that element, swap them. This process perform the operation at most $$$n - k$$$ times. After performing operations, select $$$a_1$$$ to $$$a_k$$$. This is the maximum score we can get.

#172743256

After performing all operations, select $$$p$$$ consecutive elements. $$$p$$$ can be different from $$$k$$$. Find the maximum score.

According to hints, $$$\min(x, y) = 0$$$ and $$$\max(x, y) > 0$$$ and $$$(n - 1) \,\bmod\, \max(x, y) = 0$$$ holds in order to generate a valid result. If so, player $$$1$$$ and player $$$2$$$ would play first. Let's consider player $$$2$$$ wins. Then player $$$2$$$ should win $$$\max(x, y)$$$ games, and loses to player $$$\max(x, y) + 2$$$. Likewise, player $$$\max(x, y) + 2$$$ wins $$$\max(x, y)$$$ games and loses to player $$$2 \cdot \max(x, y) + 2$$$. Construct the remaining result in the same way.

#172746518

Expand $$$x$$$, $$$y$$$ to $$$x$$$, $$$y$$$, $$$z$$$?

If $$$n = 1$$$, do nothing.

Otherwise, select indices $$$1$$$ and $$$n$$$ to make $$$a_1$$$ equal to $$$a_n$$$ first. After that, for each element $$$a_i$$$ ($$$2 \le i < n$$$), select indices $$$1$$$ and $$$i$$$ if $$$a_1 + a_i$$$ is odd, and select indices $$$i$$$ and $$$n$$$ otherwise. This process requires $$$n - 1$$$ operations and make all elements equal, which is also non-decreasing.

#172746622

Find the minimum number of operations?

Consider another binary string $$$c$$$, in which $$$c_i = a_i \oplus b_i$$$ ($$$1 \le i \le n$$$). So doing an operation means selecting two indices of $$$c$$$ and flipping them. Also, let's define $$$d$$$ is the number of $$$1$$$ in $$$c$$$. Because the parity of $$$d$$$ never changes, the answer is $$$-1$$$ if $$$d$$$ is odd.

If $$$d$$$ is even, classify the cases:

$$$[1]$$$ If $$$d = 2$$$ and two $$$1$$$-s are adjacent, the answer is $$$\min(x, 2y)$$$. Because $$$n \ge 5$$$ holds, we can always replace one $$$x$$$-cost operation with two $$$y$$$-cost operations.

$$$[2]$$$ If $$$d = 2$$$ and two $$$1$$$-s are not adjacent, the answer is $$$y$$$.

$$$[3]$$$ If $$$d \ne 2$$$, select $$$i$$$-th $$$1$$$ and $$$(i + \frac{d}{2})$$$-th $$$1$$$ each ($$$1 \le i \le \frac{d}{2}$$$). This costs $$$\frac{d}{2} \times y$$$, and we showed the cost cannot be reduced more in hint 3.

#172746684

(Continued from D1 editorial)

If $$$x < y$$$, greedy approach used in D1 doesn't work. Let's use DP. Define $$$z0[i][j]$$$ as the minimal cost when there is $$$j$$$ $$$1$$$s in first $$$i$$$ elements of $$$c$$$ and $$$c_i = 0$$$, and $$$z1[i][j]$$$ as the minimal cost when there is $$$j$$$ $$$1$$$s in first $$$i$$$ elements of $$$c$$$ and $$$c_i = 1$$$. Initially all table values are $$$\infty$$$.

First, check $$$c_1$$$. If $$$c_1 = 0$$$, set $$$z0[1][0]$$$ to $$$0$$$. Otherwise, set $$$z1[1][1]$$$ to $$$0$$$.

Then, check the following elements from $$$c_2$$$ to $$$c_n$$$ in turn.

$$$[4]$$$ If $$$c_i = 0$$$,

$$$[5]$$$ If $$$c_i = 1$$$,

for $$$0 \le j \le i$$$. The answer is $$$z[n][0]$$$.

#172746737

Solve $$$n \le 10^5$$$ version. Some testers found $$$O(n)$$$ solution.

In the conveyor, cells with same $$$(i + j)$$$ value consists a diagonal ($$$i$$$ is row number, $$$j$$$ is column number). Let's call them $$$(i + j)$$$-th diagonal. So there are $$$239$$$ diagonals, from $$$0$$$-th to $$$238$$$-th.

So, we can find every slime ball move to the next diagonal for every second. It means no two slime ball merge forever.

Given $$$t$$$, $$$x$$$, $$$y$$$, cell $$$(x, y)$$$ belongs to $$$(x + y)$$$-th diagonal. If $$$t < x + y$$$, the answer is NO because there is no slime ball in $$$(x + y)$$$-th diagonal yet. If $$$t \ge x + y$$$, $$$(x + y)$$$-th diagonal contains one slime ball, and the ball is placed on cell $$$(0, 0)$$$ after $$$(t - x - y)$$$ seconds from the start. So $$$(t - x - y)$$$ slime balls passed this diagonal before.

Now, find out which cell contains slime ball among the diagonal. To do this, we use following method: simulate with $$$(t - x - y)$$$ slime balls to check how many slime reach each cell of the diagonal, and repeat this with $$$(t - x - y + 1)$$$ slime balls. Exactly one cell will show different result, and this cell is where $$$(t - x - y + 1)$$$-th slime ball passes through. If this cell is equal to $$$(x, y)$$$, the answer is YES. Otherwise the answer is NO.

Simulation with $$$x$$$ slime balls processes as follows:

• Place $$$x$$$ slime balls on cell $$$(0, 0)$$$.
• Move slime balls to next diagonal. For each cell, if the cell contains $$$k$$$ slime balls, $$$\lceil \frac{k}{2} \rceil$$$ moves to right and $$$\lfloor \frac{k}{2} \rfloor$$$ moves to down.
• Repeat the second step. If slime balls reached aimed diagonal, stop and find the result.

#172746768

Increase the conveyor size to $$$10^4 \times 10^4$$$. Solve this version. Query number is same.

#include<bits/stdc++.h>

#define endl '\n'

using namespace std;

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

    int k, n, t;

    cin >> t;
    for(;t--;)
    {
        cin >> n >> k;

        if(n < k)
            cout << k - n << endl;

        else if(n % 2 == k % 2)
            cout << 0 << endl;

        else
            cout << 1 << endl;
    }

    return 0;
}

After 2 problems got rejected, I made this problem but it has 2D coordinate originally.

#include<bits/stdc++.h>

#define endl '\n'

using namespace std;

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

    int t;

    cin >> t;
    for(;t--;)
    {
	int m, sum = 0, x0, x1, x2, y0, y1, y2;

	cin >> x0 >> x1 >> x2 >> y0 >> y1 >> y2;

	m = min(x0, y2);
	x0 -= m;
	y2 -= m;

	m = min(x1, y0);
	x1 -= m;
	y0 -= m;

	m = min(x2, y1);
	x2 -= m;
	y1 -= m;
	sum += 2 * m;

	sum -= 2 * min(x1, y2);

	cout << sum << endl;
    }
}

One tester suggested to swap $$$A$$$ and $$$B$$$ but I and adedalic thought it is not good idea, so the order didn't changed.

#import<bits/stdc++.h>

#define endl '\n'

using namespace std;

int a[100005], b[100005];
main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    for(;t--;)
    {
	int k = 0, m = 1000000000, n;

	cin >> n;

	for(int i = 0; i < n; i++)
	{
	    cin >> a[i];
            b[i] = a[i];
	    m = min(m, a[i]);
	}

        sort(b, b + n);

	for(int i = 0; i < n; i++)
	    if(a[i] != b[i] && a[i] % m > 0)
		k = 1;

	if(k)
	    cout<<"NO"<<endl;
	else
	    cout<<"YES"<<endl;
    }
}

Most testers especially liked this problem.

#include<bits/stdc++.h>

#define endl '\n'

using namespace std;

typedef long long LL;

struct H{int x, y;};

int ii, n;
const int q = 1e9 + 7;
LL p[100005], pv[100005], vi[100005], w[100005];
H e[200040];

int C(H a, H b){return a.x < b.x;}
int G(LL a, LL b){return a > b;}

LL dfs(int v)
{
    LL d = 1;

    vi[v] = 1;

    for(int i = pv[v]; i < pv[v+1]; i++)
	if(!vi[e[i].y])
	    d += dfs(e[i].y);

    w[ii] = d * (n - d);
    ii++;

    return d;
}

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

    int t;

    cin >> t;

    for(;t--;)
    {
	int k = 0, m;
	LL x = 1;

	cin >> n;

	for(int i = 0; i < n - 1; i++)
	{
	    cin >> e[i].x >> e[i].y;
	    e[i + n - 1].x = e[i].y;
	    e[i + n - 1].y = e[i].x;
	}

	int sz = 2 * n - 2;

	sort(e, e + sz, C);

	for(int i = 1; i < sz; i++)
	{
	    if(e[i].x > e[i - 1].x)
	    {
		for(int j = e[i - 1].x + 1; j <= e[i].x; j++)
		    pv[j] = i;
	    }
	}
	for(int j = e[sz - 1].x + 1; j <= n + 2; j++)
	    pv[j] = sz;

	ii = k = 0;
	dfs(1);

	cin >> m;

	for(int i = 0; i < m; i++)
	    cin >> p[i];

	sort(p, p + m, G);
	sort(w, w + n - 1, G);

	if(m < n)
	    for(int i = m; i < n - 1; i++)
		p[i] = 1;
	else
	{
	    int i;

	    for(i = m - 1; i > m - n; k = i, i--)
		w[i] = w[i - m + n - 1];

	    for(; i; i--)
		w[i] = w[0];
	}

	int l = max(m, n - 1);
	
	int i;
	for(i = 0, x = w[0]; i <= k; i++)
	    x = x * p[i] % q;

	for(;i < l; i++)
	    x = (x + w[i] * p[i]) % q;

	cout << x << endl;

	for(int i = 1; i <= n; i++)
	    vi[i] = 0;
    }
}

This problem was inspired by 1187E - Покраска дерева and 1281E - Jeremy Bearimy. Originally this was proposed as E, but after some fixing it became more easier than original one. And the modulo was new one originally, but I changed it later by myself.

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

struct H{int k, l, r;};

const int p = 1048576;

LL l[2100000], r[2100000], z[2100000];

H h[100005], v[200040];

int C(H a, H b){return a.k < b.k;}
int D(H a, H b){return a.l < b.l || a.l == b.l && a.r > b.r;}

LL sum(int x, int y, int d) // find the sum of range [x, y]
{
    if(x <= l[d] && r[d] <= y)
	return z[d];

    if(x > r[d] || y < l[d])
	return 0;

    return sum(x, y, d << 1) + sum(x, y, (d << 1) + 1);
}

void REP(int i, LL k) // add k to i-th number
{
    i += p;

    for(z[i] += k; i >>= 1;)
	z[i] = z[i << 1] + z[(i << 1) + 1];
}

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

    LL m, n, s = 1;

    cin >> n >> m;

    for(int i = 0; i < p; i++)
	l[i + p] = r[i + p] = i;

    for(int i = p; --i;)
    {
	l[i] = l[i << 1];
	r[i] = r[(i << 1) + 1];
    }

    for(int i = 0; i < n; i++)
    {
	cin >> h[i].k >> h[i].l >> h[i].r;

	if(h[i].r - h[i].l == 1000000)
	    s++;
    }

    sort(h, h + n, C);

    for(int i = 0; i < m; i++)
    {
	int j = i << 1;

	cin >> v[j].k >> v[j].l >> v[j+1].l;

	v[j + 1].k = v[j].k;
	v[j].r = 1;
	v[j + 1].r = -1;

	if(v[j + 1].l - v[j].l == 1000000)
	    s++;
    }

    sort(v, v + 2 * m, D);

    for(int i = 0, j = 0; i < n && j < 2 * m;)
    {
	if(h[i].k < v[j].l || h[i].k == v[j].l && v[j].r < 0)
	{
	    s += sum(h[i].l, h[i].r, 1);
	    i++;
	}
	else
	{
	    REP(v[j].k, v[j].r);
	    j++;
	}
    }

    cout << s;

    return 0;
}

This problem was inspired by 1075C - Ладья возвращается домой. Originally the restriction of $$$n, m$$$ was small so $$$O(n^2)$$$ solution could pass, but adedalic suggested to increase them up to $$$10^5$$$. In fact, I only knew brute forces solution until he tells me the solution using segment tree. And the size of the square was $$$10^9 \times 10^9$$$ so coordinate compression would be done additionally, but we eliminated it to avoid too many implementation.

#include<bits/stdc++.h>

#define endl '\n'

using namespace std;

typedef long long LL;

LL p, a[528000], ll[528000], rr[528000];

LL SUM(LL l, LL r, LL d)
{
    LL x, y, z;

    x = ll[d];
    y = rr[d];
    z = b & ~(y - x);

    x ^= z;
    y ^= z;

    if(x > r || y < l)
	return 0;

    else if(x < l || y > r)
	return(SUM(l, r, z << 1) + SUM(l, r, (z << 1) + 1));

    else
	return a[z];
}

void REP(LL i,LL k)
{
    i += p;

    for(a[i] = k; i >>= 1;)
	a[i] = (a[i << 1] + a[(i << 1) + 1]);
}

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

    int b = 0, i, n, q;

    cin >> n >> q;
    p = 1 << n;

    for(i = 0; i < p; i++)
    {
	cin >> a[p + i];
	ll[p + i] = rr[p + i] = i;
    }

    for(; i < p; i++)
	ll[p + i] = rr[p + i] = i;

    for(; --i;)
    {
	a[i] = (a[i << 1] + a[(i << 1) + 1]);
	ll[i] = ll[i << 1];
	rr[i] = rr[(i << 1) + 1];
    }

    for(; q--;)
    {
	int m;

	cin >> m;

	if(m == 1)
	{
	    int k, x;

	    cin >> x >> k;

	    REP((x - 1) ^ b, k);
	}

	else if(m == 2)
	{
	    int k;

	    cin >> k;

	    b ^= (1 << k) - 1;
	}

	else if(m == 3)
	{
	    int k;

	    cin >> k;

	    b ^= 1 << k;
	}

	else
	{
	    int l, r;

	    cin >> l >> r;

	    cout << SUM(l - 1, r - 1, 1) << endl;
	}
    }
}

This problem has 6 generators, and I most liked it among 6 problems.