Blog entries - Codeforces

#	User	Rating
1	ecnerwala	3648
2	Benq	3580
3	orzdevinwang	3570
4	cnnfls_csy	3569
5	Geothermal	3568
6	tourist	3565
7	maroonrk	3530
8	Radewoosh	3520
9	Um_nik	3481
10	jiangly	3467

#	User	Contrib.
1	maomao90	174
2	awoo	164
2	adamant	164
4	TheScrasse	159
4	nor	159
6	maroonrk	156
7	-is-this-fft-	150
8	SecondThread	147
9	orz	146
10	pajenegod	145

Thank you for participating in the contest! We hope you enjoy the problems. You can also give feedback on each problem, it will help us much in future problem settings. By the way, feel free to share your solution!

1658A - Marin and Photoshoot

Hint 1

How will you solve this problem if there are just $$$2$$$ male cosplayers?

Hint 2

Notice the distance between $$$2$$$ consecutive male cosplayers.

Tutorial

It is easy to see, in a beautiful picture, there must be at least $$$2$$$ female cosplayers between $$$2$$$ consecutive male cosplayers. It is also the sufficient condition, as if there are $$$x$$$ male cosplayers in a subsegment, there are at least $$$2(x - 1) = 2x - 2 \geq x$$$ for all $$$x \geq 2$$$.

Solution

C++

#include <bits/stdc++.h>
using namespace std;
 
const int N = 2e5 + 5;
 
int n;
string s;
vector<int> v;
 
void solve() {
    v.clear();
    cin >> n >> s;
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        if (s[i] == '0') v.push_back(i);
    }
    for (int i = 0; i < (int)v.size() - 1; ++i) {
        if (v[i + 1] - v[i] <= 2) ans += 2 - (v[i + 1] - v[i]) + 1;
    }
    cout << ans << '\n';
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t; cin >> t;
    while (t--) solve();
}

Python

t = int(input())
for _ in range(t):
    n = input()
    s = input()
    ans = 0
    cnt = 2
    for c in s:
        if c == '1': cnt += 1
        else:
            ans += max(2 - cnt, 0)
            cnt = 0
    print(ans)

Feedback

Didn't solve
Good problem
Average problem
Bad problem

1658B - Marin and Anti-coprime Permutation

Hint 1

Let's $$$ g = \gcd (1 \cdot p_1, \, 2 \cdot p_2, \, \dots, \, n \cdot p_n) $$$. What is the maximum value of $$$g$$$?

Hint 2

For each value of $$$g$$$, can you construct a satisfying permutation?

Tutorial

We can prove that $$$g \leq 2$$$.

Proof

Assuming $$$g > 2$$$:

If there exists a prime number $$$p > 2$$$ that $$$p \mid g$$$, there are $$$\left \lfloor \dfrac{n}{p} \right \rfloor$$$ numbers divisible by $$$p$$$, so we can match at most $$$2 \left \lfloor \dfrac{n}{3} \right \rfloor$$$ numbers into pairs, which is smaller than $$$n$$$.
Otherwise, we can match odd numbers with even positions, and even numbers with odd positions, which leads to $$$2 \mid g$$$. Because $$$p_2$$$ is odd, $$$2 \cdot p_2$$$ is not divisible by $$$2^k$$$ with $$$k > 1$$$.

Therefore, $$$g\leq 2$$$.

Therefore:

If $$$n$$$ is odd, the answer is $$$0$$$ since the number of odd is greater than the number of even.
Otherwise, we will match odd with even and vice versa. For odd number in even position, we have $$$(\dfrac{n}{2})!$$$ ways. According to the multiplicative rule, the answer will be $$$((\dfrac{n}{2})!)^2$$$.

Solution

C++

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

const int MOD = 998244353;

void solve() {
    int n; cin >> n;
    if (n & 1) {
        cout << "0\n";
        return;
    }
    long long ans = 1;
    for (int i = 1; i <= n / 2; ++i) {
        ans *= 1LL * i * i % MOD;
        ans %= MOD;
    }
    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

Python

MOD = 998244353
t = int(input())

for _ in range(t):
	n = int(input())
	if n & 1:
	    print(0)
	    continue
	ans = 1
	for i in range(1, n // 2 + 1):
		ans = ans * i % MOD
	ans = ans * ans % MOD
	print(ans)

Feedback

Didn't solve
Good problem
Average problem
Bad problem

1658C - Shinju and the Lost Permutation

Hint 1

There is exactly one $$$1$$$ in array $$$c$$$ (in $$$(i - 1)$$$-th cyclic shift, $$$c_i > 1$$$ if $$$p_1 \neq n$$$, and $$$c_i = 1$$$ if $$$p_1 = n$$$), so if the number of $$$1s$$$ is greater or less than one, the answer is $$$\texttt{NO}$$$.

Hint 2

We can rotate the array such that $$$c_1 = 1$$$ (initial state) because we don't have to construct the permutation, so if there exists a permutation with $$$p_1 = n$$$, the answer is $$$\texttt{YES}$$$.

Hint 3

Notice the difference of $$$c_i$$$ and $$$c_{i + 1}$$$.

Tutorial

In the $$$i$$$-th cyclic shift, if $$$p_1 > p_2$$$ then $$$c_{i + 1} \leq c_i$$$, otherwise $$$c_{i + 1} - c_i = 1$$$, so if there exists a position $$$i$$$ such that $$$c_{i + 1} - c_i > 1$$$, the answer is $$$\texttt{NO}$$$.

This is the sufficient condition. It can be shown that, if $$$c_{i + 1} - c_i \leq 1$$$ for all $$$1 \leq i < n$$$, then there exists a permutation that satisfies.

Here is a sketch of the construction: https://codeforces.com/blog/entry/101302?#comment-899523

Solution

C++

#include <bits/stdc++.h>
using namespace std;
 
void solve() {
    int n; cin >> n;
    vector<int> a(n);
    for (int &v: a) cin >> v;
    if (count(a.begin(), a.end(), 1) != 1) {
        cout << "NO\n";
        return;
    }
    int p = find(a.begin(), a.end(), 1) - a.begin();
    rotate(a.begin(), a.begin() + p, a.end());
    for (int i = 1; i < n; ++i) {
        if (a[i] - a[i - 1] > 1) {
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n";
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

Python

import sys
input = sys.stdin.readline
 
t = int(input())
for _ in range (t):
    n = int(input())
    a = list(map(int, input().split()))
 
    if a.count(1) != 1:
        print("NO")
        continue
 
    a.append(a[0])
    ok = True
    for i in range (0, n):
        if a[i + 1] - a[i] > 1:
            ok = False
            break
    
    if ok: print("YES")
    else: print("NO")

Feedback

Didn't solve
Good problem
Average problem
Bad problem

1658D1 - 388535 (Easy Version)

Tutorial

Let's look at the binary representation of numbers from $$$0$$$ to $$$7$$$:

$$$000$$$
$$$001$$$
$$$010$$$
$$$011$$$
$$$100$$$
$$$101$$$
$$$110$$$
$$$111$$$

Let us look at the $$$i$$$-th bit only (maybe $$$i=2$$$), we will get a sequence like $$$[0,0,1,1,0,0,1,1]$$$. Notice that the number of zeroes equals the number of ones in a prefix only when the length of the prefix is a multiple of $$$2^i$$$. Otherwise, there will be more zeros than ones.

So, we will count the number of flipped and unflipped bits for each bit position.

If the number of ones is greater than the number of zeros, the $$$i$$$-th bit of $$$x$$$ must be $$$1$$$.
If the number of zeros is greater than the number of ones, the $$$i$$$-th bit of $$$x$$$ must be $$$0$$$.
If the number of ones is equal to the number of zeros, that $$$i$$$-th bit of $$$x$$$ can either be $$$0$$$ or $$$1$$$.

However, if the number of ones is equal to the number of zeros, we can assign the $$$i$$$-th bit anything we like. The rough sketch of the proof is that if $$$x$$$ is inside $$$a$$$ then $$$x\oplus2^i$$$ is also inside $$$a$$$.

Solution

C++

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

const int N = 2e5 + 5;
int p[N], cnt[32][2];
 
void solve() {
    memset(cnt, 0, sizeof cnt);
    int l, r; cin >> l >> r;
    for (int i = l; i <= r; ++i) {
    	int x; cin >> x;
    	for (int j = 0; j <= 30; ++j, x >>= 1)
    		cnt[j][x & 1]++;
    }
    int ans = 0;
    for (int i = 0; i <= 30; ++i) {
    	ans |= ((cnt[i][0] < cnt[i][1]) * (1 << i));
    }
    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

Python

import sys
input = sys.stdin.readline
 
t = int(input())
for _ in range (t):
    l, r = map(int, input().split())
    a = list(map(int, input().split()))
    cnt = [[0] * 2 for _ in range (32)]
 
    for x in a:
        for i in range (31):
            cnt[i][x & 1] += 1
            x >>= 1
 
    ans = 0
    for i in range (31):
        if (cnt[i][0] < cnt[i][1]):
            ans |= (1 << i)
    
    print(ans)

1658D2 - 388535 (Hard Version)

Hint 1

If $$$a \oplus b = 1$$$, then $$$(a \oplus x) \oplus (b \oplus x) = 1$$$.

Hint 2

if $$$l$$$ is even and $$$r$$$ is odd, the last bit of $$$x$$$ can be either $$$0$$$ or $$$1$$$ (we can pair $$$a_i$$$ with $$$a_i \oplus 1$$$).

Tutorial

There are two solutions to this problem.

If $$$l$$$ is even and $$$r$$$ is odd, we can skip the last bit and divide the range by two, then recursively solve it. Otherwise, we will pair $$$a_i$$$ with $$$a_i \oplus 1$$$, and we will left with at most $$$2$$$ candidates for $$$x$$$ to check.

There is also another solution: we can iterate all possibilities of $$$x$$$ (by assuming $$$a_i$$$ is $$$l \oplus x$$$ for all $$$1 \leq i \leq n$$$). If $$$x$$$ is the hidden number, $$$l \leq a_i \oplus x \leq r$$$ for all $$$1 \leq i \leq n$$$, so the problem reduce to "count the number of $$$a_i$$$ that $$$l \leq a_i \oplus x \leq r$$$", which can be solved with binary trie.

Solution

C++

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

const int N = 2e5 + 5;
int a[N], l, r; 
set <int> s, s2;
 
void solve() {
    int mul = 1;
    s.clear();
    cin >> l >> r; 
    for (int i = l; i <= r; ++i) {
        cin >> a[i];
        s.insert(a[i]);
    }

    for (; l % 2 == 0 && r % 2 == 1; l >>= 1, r >>= 1, mul <<= 1) {
        s2.clear();
        for (int i: s) s2.insert(i >> 1);
        swap(s, s2);   
    }

    int ans;
    if (l % 2 == 0) ans = r;
    else ans = l;

    for (int i: s) {
        if (s.find(i ^ 1) == s.end()) {
            int cur = i ^ ans;
            bool f = true;
            for (int j : s)
                f &= ((cur ^ j) >= l && (cur ^ j) <= r);
            if (f) {
                ans = cur;
                break;
            }
        }
    }
    cout << ans * mul << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

Python

import sys
input = sys.stdin.readline
 
def solve(l: int, r: int, s: set):
    if l % 2 == 0 and r % 2 == 1:
        t = set()
        for v in s: t.add(v >> 1)
        return solve(l >> 1, r >> 1, t) << 1
    else:
        for v in s:
            if (v ^ 1) not in s:
                ok = True
                ans = v
                if l % 2 == 0: ans ^= r
                else: ans ^= l
                for x in s:
                    if (x ^ ans) < l or (x ^ ans) > r:
                        ok = False
                        break
                if ok: return ans
            
 
t = int(input())
for _ in range (t):
    l, r = map(int, input().split())
    s = set(map(int, input().split()))
    print(solve(l, r, s))

Feedback

Didn't solve
Good problem
Average problem
Bad problem

1658E - Gojou and Matrix Game

Hint 1

What if a player is forced to play in a cell where they get fewer points than the previous move?

Hint 2

Rephrase the problem, then solve it with dynamic programming.

Tutorial

Suppose that Marin places a token at $$$(a,b)$$$. If Gojou places a token at $$$(c,d)$$$ where $$$V_{c,d}<V_{a,b}$$$, then Gojou would not have any advantage as Marin can play at $$$(a,b)$$$ again. After a very huge number of turns, Marin will have more points than Gojou. Generally, if a player is forced to play in a cell where they get fewer points than the previous move, they would instantly lose.

Therefore, we can rephrase the problem as such:

Apart from the first move, the token placed by a player must be more than Manhattan distance k away from the previous token placed on the matrix.
Apart from the first move, the token placed by a player must be on a cell with more points than the cell with the token placed by the previous player.
The player who plays the last token is the winner.

This turns out to be a standard dynamic programming.

Let $$$dp[i][j]$$$ return $$$1$$$ if the player who places a token at $$$(i,j)$$$ wins.

Let $$$V_{a,b}=n^2$$$, then we have $$$dp[a][b]=1$$$ as a base case.

Then we will fill the values of $$$dp$$$ in decreasing values of $$$V_{i,j}$$$. $$$dp[i][j]=1$$$ if for all $$$(i',j')$$$ such that $$$|i-i'|+|j-j'| > k$$$, we have $$$dp[i'][j']=0$$$. Note that by taking the contrapositive, this is equivalent to for all $$$(i',j')$$$ such that $$$dp[i'][j']=1$$$, we have $$$|i-i'|+|j-j'| \leq k$$$.

Let us maintain a set $$$S$$$ that stores the pairs $$$(i',j')$$$ such that $$$dp[i'][j']=1$$$, then our operations are:

adding point $$$(i,j)$$$ to $$$S$$$
given $$$(i,j)$$$, check if for all $$$(i',j')$$$ in $$$S$$$, $$$|i-i'|+|j-j'| \leq k$$$

Notice that $$$|i-i'|+|j-j'| \leq k \Leftrightarrow \max(|(i+j)-(i'+j')|,|(i-j)-(i'-j')|) \leq k$$$.

Checking $$$\max(|(i+j)-(i'+j')|,|(i-j)-(i'-j')|) \leq k$$$ is very simple as we only need to store the minimum and maximum of all $$$(i+j)$$$ and $$$(i-j)$$$.

Solution

C++

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

const int N = 2e3 + 5;
bool f[N][N];
int l, r, u, d, n, k;
vector<array<int, 5>> v;

bool check(int i, int j) {
    return (abs(i - u) <= k && abs(i - d) <= k && abs(j - l) <= k && abs(j - r) <= k);
}

void solve(){
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            f[i][j] = false;
            int x; cin >> x;
            v.push_back({x, i, j, i + j, j - i});
        }
    }

    sort(v.begin(), v.end(), greater<array<int, 5>>());
    l = v[0][4], r = v[0][4], u = v[0][3], d = v[0][3];
    for (array<int, 5> cell: v) {
        if (check(cell[3], cell[4])) {
            f[cell[1]][cell[2]] = true;
            l = min(l, cell[4]);
            r = max(r, cell[4]);
            u = min(u, cell[3]);
            d = max(d, cell[3]);
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (f[i][j]) cout << 'M';
            else cout << 'G';
        }
        cout << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

Feedback

Didn't solve
Good problem
Average problem
Bad problem

1658F - Juju and Binary String

Hint 1

Let $$$b$$$ be the number of black balls and $$$w$$$ be the number of white balls.

The answer will be impossible if $$$m$$$ is not a multiple of $$$\dfrac{b+w}{gcd(b, w)}$$$.

Observation

It is easy to show that the cuteness of $$$s$$$ is $$$\dfrac{b}{n}$$$.

What is the number of $$$\texttt{1}$$$ in the concatenated string needed so that the answer exists?

Proof

The cuteness of $$$s$$$ is $$$\dfrac{b}{n} = \dfrac{b}{b+w}$$$ by definition.

Now consider $$$t = s[l_1, r_1] + [l_2, r_2] + \dots + s[l_k, r_k]$$$, the cuteness of the concatenated string.

The cuteness of $$$t$$$ is $$$\dfrac{b}{b+w}$$$, so the number of $$$\texttt{1}$$$ needed is $$$k = \dfrac{m \cdot w}{b + w}$$$.

If $$$k$$$ is not an integer then there will be no answer, so $$$m$$$ must be a multiple of $$$\dfrac{b+w}{gcd(b, w)}$$$.

Hint 2

We don't need more than 2 parts, or to say $$$k \leq 2$$$ is needed in this problem.

Observation

Let $$$c_i =$$$ (the number of $$$\texttt{1}$$$ in $$$s[i \dots i + m - 1]$$$).

For convenient, from now let assume the array and string is wrapped around: $$$s[i] = s[i + n]$$$ and $$$c_i = c_{i+n}$$$.

We have $$$|c_i-c_{i+1}| \leq 1$$$ and there exists $$$c_i = y$$$ for all $$$y$$$ that $$$min(c_i) \leq y \leq max(c_i)$$$.

Contestant's Proof

GM+ smax provides a simple and clean answer here.

Author's Proof

Let $$$L = min(c_i)$$$, $$$R = max(c_i)$$$ and we are doing with wrap around arrays for convenient.

We want to prove that for any $$$y$$$ that $$$L \leq y \leq R$$$ there will be some $$$c_i = y$$$.

Let $$$d_i = max(c_p, c_{p+1}, \dots, c_i)$$$ for $$$p$$$ is the minimal position that $$$c_p = L$$$.

Let $$$f_x$$$ is the first position $$$i$$$ starting $$$p$$$ that $$$d_i = x$$$, we have $$$d_{f_x} = c_{f_x}$$$

[1] Since $$$L \leq y \leq R$$$ and, we have $$$L = d_p \leq d_{p+1} \leq \dots \leq d_{p+n-1} = R$$$.

[2] Since $$$|c_{i+1} - c_i| \leq 1$$$ we can show that.

$$$\forall p < i < p + n \rightarrow \left[\begin{array}{l} d_i = d_{i-1} \\ d_i = d_{i-1} + 1 \end{array}\right.$$$

[3] Since $$$c_i \in \mathbb{N}$$$, we also have $$$d_i \in \mathbb{N}$$$

From [1], [2], [3], if there is $$$d_i = v > L$$$ then there will be $$$d_j = v - 1$$$ for some $$$j$$$ that $$$p + (v - L) \leq j < i$$$.

$$$\Leftrightarrow \forall v, min(d_i) \leq v \leq max(d_i) \rightarrow \exists d_{f_i} = v$$$

$$$\Leftrightarrow \exists d_{f_i} = y$$$

$$$\Leftrightarrow \exists c_{f_i} = y$$$

Tutorial

The answer will be impossible if $$$m$$$ is not a multiple of $$$\dfrac{b+w}{gcd(b, w)}$$$.

Otherwise, it is proved that $$$k \leq 2$$$ is needed.

Since we need to select a minimum $$$k$$$, let's first check if there is a solution with $$$k = 1$$$

Spoiler

If there exist such position $$$p$$$ that $$$1 \leq p \leq n - m + 1$$$ and $$$s[p, p + m - 1]$$$ have the same cuteness as $$$s[1, n]$$$ then we found an answer.

Otherwise there must be an answer with $$$k = 2$$$, and it is simple too

Spoiler

If there exist such position $$$p$$$ that $$$1 \leq p < m$$$ and $$$s[1, p] \cup s[n - (m - p) + 1, n]$$$ have the same cuteness as $$$s[1, n]$$$ then we found an answer.

Both can be done in linear $$$O(n)$$$ with the sliding window technique or prefixsum.

Solution

C++

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while (t--) {
        int n, k; cin >> n >> k;
        string s; cin >> s;
        int one = count_if(s.begin(), s.end(), [](char c) { return c == '1'; });
        if (1LL * one * k % n != 0) {
            cout << "-1\n";
        } else {
            one = 1LL * one * k / n;
            vector<int> suf(2 * n + 1);
            for (int i = 1; i <= 2 * n; i++) {
                suf[i] = suf[i - 1] + (s[(i - 1) % n] == '1');
                if (i >= k && suf[i] == suf[i - k] + one) {
                    if (i <= n) {
                        cout << "1\n";
                        cout << i - k + 1 << " " << i << '\n';
                    } else {
                        cout << "2\n";
                        cout << 1 << " " << i - n << '\n';
                        cout << i - k + 1 << " " << n << '\n';
                    }
                    break;
                }
            }
        }
    }
}

Feedback

Didn't solve
Good problem
Average problem
Bad problem

Full text and comments »

_FireGhost_'s blog