CodeForces Round 959 (PARTIAL) Solution

#	User	Rating
1	tourist	3880
2	jiangly	3669
3	ecnerwala	3654
4	Benq	3627
5	orzdevinwang	3612
6	Geothermal	3569
6	cnnfls_csy	3569
8	jqdai0815	3532
9	Radewoosh	3522
10	gyh20	3447

#	User	Contrib.
1	awoo	161
2	maomao90	160
3	adamant	157
4	maroonrk	153
5	-is-this-fft-	148
5	SecondThread	148
7	Petr	147
7	atcoder_official	147
9	TheScrasse	145
10	nor	144

0. Feeling

Welcome to the easiest Div.1 + Div.2 ever.

Got accepted on ABCDE.

And there's also a version in Chinese here.

1. Diverse Game

Given a permutation with a size of $$$nm$$$, construct another permutation with a size of $$$nm$$$ satisfies that it's different to the previous permutation in each position.

$$$a_i=a_i\bmod nm+1$$$. The time complexity is $$$O(nm)$$$.

Code

#include <iostream>
using namespace std;
const int N = 5e4 + 10;
int n, m;
void run()
{
    scanf("%d%d", &n, &m);
    if (n == 1 and m == 1)
    {
        scanf("%*d");
        puts("-1");
        return;
    }
    for (int i = 1, x; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            scanf("%d", &x);
            printf("%d%c", x % (n * m) + 1, " \n"[j == m]);
        }
    }
}
int main()
{
    int T = 1;
    scanf("%d", &T);
    while (T--)
        run();
}

2. Fun Game

Given two binary sequences $$$a$$$ and $$$b$$$，unlimited operation to make from $$$a_l$$$ to $$$a_r$$$ simultaneously xor $$$a_1$$$ to $$$a_{r-l+1}$$$。Determine if it's able to turn $$$a$$$ into $b$。

Because I was watching Zenless Zone Zero videos on Bilibili, I suddenly realized that, it's able to consider the prefix zeros in $$$a$$$ and $$$b$$$ as "hollow". Because, under the constriants of the problem, regardless how many operations you do, the size of their "hollow" won't decrease.

With only one $$$1$$$, we can freely modify the following zeros and ones.

Only one line of code to solve this problem. The time complexity is $$$O(n)$$$.

Code

#include <iostream>
#include <string>
using namespace std;
const int N = 1e5 + 10;
int n;
string s, t;
void run()
{
    cin >> n >> s >> t;
    puts(s.find('1') <= t.find('1') ? "YES" : "NO");
}
int main()
{
    int T = 1;
    scanf("%d", &T);
    while (T--)
        run();
}

3. Hungry Games

Too lazy to write the statement again.

Answer = total number of possible ranges — ranges with final toxicity of $$$0$$$.

Looks like topological sort.

Define $$$d_i$$$ as the number of left borders $$$j$$$ when set $$$i$$$ as the right border satisfying the final toxicity of the range $$$[j,i]$$$ equals zero.

When enumerating $$$i$$$, find the first $$$t$$$ safisfies $$$\sum_{j=i}^t a_j>x$$$, add 将 $$$d_i+1$$$ to $$$d_t$$$. because, $$$d_i$$$ ranges satisfying the final toxicity equals zero, and the range $$$[i,t]$$$ also makes zero, it's able to combine these two ranges together, that the final toxicity is still zero.

The time complexity is $$$O(n)$$$.

Code

#include <iostream>
#include <cstring>
using namespace std;
const int N = 2e5 + 10;
using ll = long long;
int n, k, r;
ll a[N], dp[N], cur, res;
void run()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld", a + i);
    }
    memset(dp + 2, 0, n << 3);
    cur = 0;
    r = 1;
    for (int i = 1; i <= n; i++)
    {
        cur -= a[i - 1];
        while (r <= n and cur <= k)
            cur += a[r], r++;
        if (cur <= k)
            continue;
        dp[r] += dp[i] + 1;
    }
    res = n;
    res *= n + 1;
    res /= 2;
    for (int i = 2; i <= n + 1; i++)
    {
        res -= dp[i];
    }
    printf("%lld\n", res);
}
int main()
{
    int T = 1;
    scanf("%d", &T);
    while (T--)
        run();
}

4. Funny Game

In a complete graph with $$$n$$$ nodes, each node has a value $$$a_i$$$. The weight of the edge connecting node $$$i$$$ and $$$j$$$ is $$$|a_i-a_j|$$$. Find a spanning tree in this graph satisfying $$$i$$$ divides the weight of the $$$i$$$-th edge.

I didn't realize the pigeonhole here, so I had a different approach.

A smaller $$$i$$$ has an expectational bigger number of edges satisfying $$$i$$$ divides its weight.

So, enumerate $$$i$$$ in decreasing order, then use union-find to handle connected components.

The time complexity is $$$O(n^2)$$$.

Code

#include <iostream>
#include <list>
#include <cstring>
using namespace std;
const int N = 2e3 + 10;
int n, a[N], f[N], v[N], p;
bool fl;
using pii = pair<int, int>;
list<pii> ret;
inline int find(int x)
{
    return x == f[x] ? x : f[x] = find(f[x]);
}
inline void merge(int x, int y)
{
    f[find(y)] = find(x);
}
void run()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        f[i] = i;
        scanf("%d", a + i);
    }
    ret.clear();
    for (int i = n - 1; i; i--)
    {
        memset(v, 0, i << 2);
        fl = false;
        for (int j = 1; j <= n; j++)
        {
            p = a[j] % i;
            if (!v[p])
            {
                v[p] = j;
                continue;
            }
            if (find(j) == find(v[p]))
                continue;
            merge(j, v[p]);
            ret.push_front({j, v[p]});
            fl = true;
            break;
        }
        if (!fl)
            return puts("NO"), void();
    }
    puts("YES");
    for (auto &[tx, ty] : ret)
        printf("%d %d\n", tx, ty);
}
int main()
{
    int T = 1;
    scanf("%d", &T);
    while (T--)
        run();
}

5. Wooden Game

Too lazy to rewrite the statement again.

The contribution of a tree with a size of $$$x$$$ is able to be any integer in range $$$[1,x]$$$, regardless its structure, because we can remove its leaves one by one.

When I realized that, I f**ked up.

The time complexity is $$$O(n)$$$.

Code

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1e6 + 10;
int n, a[N], t, res;
void run()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", a + i);
        for (int j = 1; j < a[i]; j++)
            scanf("%*d");
    }
    sort(a + 1, a + n + 1);
    t = 1;
    for (; t < a[n]; t = t * 2 + 1)
        ;
    res = 0;
    for (int i = n; i; i--)
    {
        while ((t > a[i]) or (t & res))
            t--;
        res |= t;
    }
    printf("%d\n", res);
}
int main()
{
    int T = 1;
    scanf("%d", &T);
    while (T--)
        run();
}

6. After

Man!

What can I say?

74TrAkToR out!

Rev.	By	When	Δ	Comment
en7	shiny_shine	2024-07-19 09:07:49	6
en6	shiny_shine	2024-07-19 06:46:24	217
en5	shiny_shine	2024-07-19 06:40:09	34
en4	shiny_shine	2024-07-19 06:09:00	6	Tiny change: 'ty is $O(n)$.\n\n<s' -> 'ty is $O(n\log n)$.\n\n<s'
en3	shiny_shine	2024-07-19 05:58:50	2	Tiny change: 'j>x$, add 将 $d_i+1$ t' -> 'j>x$, add $d_i+1$ t'
en2	shiny_shine	2024-07-19 05:55:08	38
en1	shiny_shine	2024-07-19 05:54:22	6611	Initial revision (published)

0. Feeling

1. Diverse Game

2. Fun Game

3. Hungry Games

4. Funny Game

5. Wooden Game

6. After

History