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!
How will you solve this problem if there are just $$$2$$$ male cosplayers?
Notice the distance between $$$2$$$ consecutive male cosplayers.
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$$$.
#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();
}
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)
1658B - Марин и не взаимно простая перестановка
Let's $$$ g = \gcd (1 \cdot p_1, \, 2 \cdot p_2, \, \dots, \, n \cdot p_n) $$$. What is the maximum value of $$$g$$$?
For each value of $$$g$$$, can you construct a satisfying permutation?
We can prove that $$$g \leq 2$$$.
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$$$.
#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;
}
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)
1658C - Синдзю и потерянная перестановка
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}$$$.
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}$$$.
Notice the difference of $$$c_i$$$ and $$$c_{i + 1}$$$.
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.me/blog/entry/101302?#comment-899523
#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;
}
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")
1658D1 - 388535 (упрощенная версия)
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$$$.
#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;
}
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 (усложненная версия)
If $$$a \oplus b = 1$$$, then $$$(a \oplus x) \oplus (b \oplus x) = 1$$$.
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$$$).
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.
#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;
}
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))
1658E - Годзё и игра на матрице
What if a player is forced to play in a cell where they get fewer points than the previous move?
Rephrase the problem, then solve it with dynamic programming.
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)$$$.
#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;
}
1658F - Дзюдзю и бинарная строка
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)}$$$.
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?
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)}$$$.
We don't need more than 2 parts, or to say $$$k \leq 2$$$ is needed in this problem.
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)$$$.
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.
[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$$$
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$$$
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
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.
#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;
}
}
}
}
}
Whoever named problem D is a legend!
What does it mean?
It's the sauce for our pasta. (Explaining it more than that would ruin it. You can google "sauce numbers" if you want to find out more)(NSFW)
Never thought that i can learn this kind of things on cf!!!
Dammn bro, you have unlocked "Advanced Observation Haki".
I have solved problem D1 using binary search. I think there must be binary search tag in problem D1. :) Total time complexity is
nlog^2(n)
Explain plz
I had seen some examples and noticed that the greater x, the greater the sorted array obtained by The XOR operations on the [ 0, r ] segment. I just used binary search to find such x ( and x is always in the given array as left boundary is always 0) afterward.
Hey can you explain why you did this
if(v==comp){ cout<<comp[m]<<"\n"; return; }else{ if(v<comp) l=m+1;else r=m-1; }
I want to ask the same question.
it's really amazing approach::)
I attempted to prove this, hopefully i make sense Proof: First of all this fact heavily relies on the fact that the elements of the array are from 0 to r. When counting from 0 we know that for a bit i first 2^i bits are 0 and the next 2^i bits are 1 and then the pattern repeats. Hence if n is a multiple of 2*2^i = 2^(i+1), then numbers in which ith bit is set equals numbers in which ith bit is unset, and for all bits < i this will be true. Now if we look at the binary representation of first 2^(i+1) numbers, we find that the only difference between these is ith bit consider the following example for i = 2
000 001 010 011 100 101 110 111
The point being if there is a number x, in this range, then a number y which is exactly same as x just that ith bit is different is also present. Now lets call first 2^(i+1) integers as a group. The next 2^(i+1) integers as another group and so on. That for i = 2, we say first 8 integers as a group (from 0 to 7), then the next group will contain the next 8 integers (8 to 15) and so on. Now lets say we do bitwise xor of these groups with a number x such that only ith bit is set in x. How will this affect our groups. In each group bottom 2^i numbers have ith bit set and and first 2^i have this bit unset, when we xor with x, bottom numbers will shift up and first numbers will move down and net difference in initial set and final set remains same. This means within a group there is no difference, also relative ordering of groups also doesn't change. Now have have a range from 0 to n, and i apply xor on this range with x, then if ith bit is set in x, then if n is a multiple of 2^(i+1) then this will bring no net change in the range. Now if n is not a multiple of 2^(i+1) then it means it has some complete groups and one incomplete group. In this incomplete group there will be more bits with ith bit unset than numbers with ith bit set. After doing xor with x, numbers of bits with this bit set will be more hence in this group net change will be increase in values of this group.
Now consider xor of range from 0 to n with 2 numbers x and y such that x < y. This means that in binary of x and y when iterating from left to right we will have some prefix which is same and then when we find a different bit this bit will be set in y. Lets say this bit is ith bit. It is clear that any change that prefix (bits to left of i) will bring in the range will same for both x and y hence we ignore these bits. If n+1 (since number of integers from 0 to n are n+1) is a multiple of 2^(i+1) then we know XORing with y will bring no net change in the values. Also since n+1 is a multiple of 2^(i+1) it means this is also multiple of 2^i, 2^(i-1), . . .2^1 i.e all bits after this bit will have same number of set and unset bits and hence XORing will not bring any net change in the range. But what if n+1 is not a multiple of 2^(i+1) then it means that the latest group of ith bit will have more unset bit, and XORing with y will bring a change only in this group and cause a net increase in the values. Lets say this last group starts with some integer k and goes upto n i.e from k to n. Now when comparing the two arrays after XORing with x and y we know that values from 0 to k-1 (index wise) will be same and when we compare current group from k to n we find that group in case of y is larger (lexicographically). Any bit j after ith bit which tries to increase group size in favour of x will still not able to make it larger than y, this group size of group of jth bit will be smaller than size of group with i and hence we will find a greater value in array with y first.
PermutationForces
So show it
believe me bro
damn, cant argue with that
One way to build a satisfying permutation: After rotating the array c[], write the numbers 1 to n one-by-one from the position(s) with highest c[i] to lowest c[i]. If there exists multiple positions with the same value, go from the largest index to the smallest.
not vice versa from largest index to the smallest? take a look at c = [1, 2, 2] according to your algorithm we get [3, 1, 2] instead of [3, 2, 1]
Oh, my bad. Edited, thanks.
How will this help?
According to your algorithm, from this sequence c
we construct the following premutation
But I don't think this is correct. The corresponding numbers of this permutation should be 1 2 3 3 2 2 or 1 2 2 3 3 2 depending on whether you do left-shift or right-shift.
Please correct me if I'm wrong.
Note that no matter we do left-shift or right-shift of the permutation, we always construct the prefix maximums array from left to right (clockwise).
Probably not the easiest way to do it, but one of them. Assume we are adding elements from 1 to N — 1 in front of element N. Now, let's make the permutation. From now on, f[i] equals number of different prefix maximums after we add i elements (so, if N is in position k, then f[1] = c[k + 1] etc.). Claim: if we put element N — 1 into position num, then: A) f[num] = 2 — it will be bigger than all elements at the front, and smaller than N. B) if pos1 > num, then f[pos1] > f[num] (otherwise, this element is bigger than N + 1) So, we put N — 1 into position [k + num]. Then, we have divided our sequence into two parts. If the length of the first one is l1, and the second one l2 (l1 + l2 = N — 2), then let the values of the first sequence be one of a permutation[1:l1], and the second [l1 + 1; l2]. Solve for them recursively. So, we have constructed a permutation which satisfies our condition.
Think in a permutation of lenght 5 like {5 4 3 2 1}, whose power is 1, now is there a way so in just one shift the power becomes 3? there isn't since whichever number you choose to put in fisrt place {x 5 ...} the five will make the array b = { x 5 5 5 5}. in other words, you can sum 1 to the power by sifhting the last number x where x < P[0], because this number will be counted in the power but for summing two you need to put at least two numbers in the beginning so that the b of the permutation becomes b = {x, y, 5, 5, 5} where x < y < 5 which is impossible with one shift (you only sifht one number).
This isn`t to mathematical and I only did this with a permutation of lenght 5, but i think it could be intuitive
It's easy to see that it's the necessary condition but not sure how to prove that it's sufficient.
Let 'c' be an array satisfying the necessary conditions. Rotate 'c' such that its first position is 1 without loss of generality. We will explicitly construct a permutation p obeying c. The first element of p is N.
let a = no. of 2s in array c, b = no. of 3s in array c and so on.
s[2] = {N-1,N-2,N-3...N-a} s[3] = {N-a-1, N-a-2, N-a-b} and so on.
Now traverse the array c from 2nd position.
if the element of c is k, place the lowest element of s[k] at the last available position of p and remove that element from s[k].
We're done.
Adding an example:
let c = 1 2 3 3 3 3 2 2 3 4 5 5 6 4
s[2]={13,12,11} s[3]={10,9,8,7,6} s[4]={5,4} s[5]={3,2} s[6]={1}
step 1: 14 _ _ _ _ _ _ _ _ _ _ _ _ _
step 2: 14 _ _ _ _ _ _ _ _ _ _ _ _ 11
step 3: 14 _ _ _ _ _ _ _ _ _ _ _ 6 11
step 4: 14 _ _ _ _ _ _ _ _ _ _ 7 6 11
step 5: 14 _ _ _ _ _ _ _ _ _ 8 7 6 11
step 6: 14 _ _ _ _ _ _ _ _ 9 8 7 6 11
step 7: 14 _ _ _ _ _ _ _ 12 9 8 7 6 11
step 8: 14 _ _ _ _ _ _ 13 12 9 8 7 6 11
step 9: 14 _ _ _ _ _ 10 13 12 9 8 7 6 11
step 10: 14 _ _ _ _ 4 10 13 12 9 8 7 6 11
step 11: 14 _ _ _ 2 4 10 13 12 9 8 7 6 11
step 12: 14 _ _ 3 2 4 10 13 12 9 8 7 6 11
step 13: 14 _ 1 3 2 4 10 13 12 9 8 7 6 11
step 14: 14 5 1 3 2 4 10 13 12 9 8 7 6 11
This works because if i>j then x<y for all x belongs to s[i] and y belongs to s[j].
Great construction! I guess you can also set s[1] = 14 here to put the entire process in a unified way. Also the condition "c[i + 1] — c[i] <= 1" plays an important role here, because then we can guarantee that at each step of the construction, we have already put enough larger numbers in the array to guarantee the corresponding value of c[i].
insane bruh
This is an example of how the construction would go: Suppose n = 8, c array = 1 2 3 4 5 3 4 2
We always start with the largest element:
[8, _, _, _, _, _, _, _] 1
[7, 8, _, _, _, _, _, _] 2
[6, 7, 8, _, _, _, _, _] 3
[5, 6, 7, 8, _, _, _, _] 4
[4, 5, 6, 7, 8, _, _, _] 5
[6, 3, 4, 5, 7, 8, _, _] 3 (rightmost r where c_r = 3, leftmost l where c_l = 5. Decrement l to r by 1. (l,r) = (0, 2). Add original a_r to first position.)
[6, 5, 2, 3, 4, 7, 8, _] 3 ((l, r) = (0, 0))
[7, 5, 4, 1, 2, 3, 6, 8] 2 ((l, r) = (0, 6))
We can check this is correct:
[8, 7, 5, 4, 1, 2, 3, 6] 1
[6, 8, 7, 5, 4, 1, 2, 3] 2
[3, 6, 8, 7, 5, 4, 1, 2] 3
[2, 3, 6, 8, 7, 5, 4, 1] 4
[1, 2, 3, 6, 8, 7, 5, 4] 5
[4, 1, 2, 3, 6, 8, 7, 5] 3
[5, 4, 1, 2, 3, 6, 8, 7] 3
[7, 5, 4, 1, 2, 3, 6, 8] 2
Sketch of Formal Proof: To be added.
problem D2 : "count the number of $$$a_i$$$ that $$$l\leq a_i \oplus x \leq r$$$ " this can be done with checking if $$$\min_{i=0}^{i=n} (a_i \oplus x) = l$$$ and $$$\max_{i=0}^{i=n} (a_i \oplus x) = r$$$ ($$$a$$$ only contains pairwise distinct elements , thus bijection)
example
can you explain more
i'm sorry if my explanation wasn't clear . as it's said in editorial we will iterate over all posibilities of $$$x$$$ and for each $$$x$$$ we will check if it can have correct mapping or not . for $$$x$$$ we will consider only $$$r-l+1$$$ values because $$$a_0$$$ should be mapped at least to one of them .
now how to check if $$$x$$$ can give us correct mapping or not ? i'm saying that if maximum value that $$$x \oplus a_i$$$ can get for every $$$i$$$ is $$$r$$$ and minimum value that $$$x \oplus a_i$$$ can get is $$$l$$$ then there is correct mapping . how can we check minimum and maximum value that $$$x \oplus a_i$$$ can have ? by trie ,which is quite well known technique .
Why take the min of all x and not stop when you find the first one?
i don't understand question
I changed your code to stop at the first value of x and it got ACC 152482164. So I was wondering why ans=min(ans,x); instead of just stopping there.
I did the same thing: 233974285
But I am assuming that $$$a_i = l \oplus x$$$ and checking if $$$x = a_i \oplus l$$$ for each $$$i$$$ like in the editorial.
You seem to be checking if $$$x = a_0 \oplus i$$$ for each $$$i$$$. Why does that work?
Okay while writing this I understood you are just trying to find the $$$i$$$ for which $$$x \oplus i = a_0$$$.
Amazing solution!
That's correct, I am assuming that in the permutation first element was $$$i$$$, then $$$x = a_0 \oplus i$$$.
can you please explain why d1 approach not working for d2. i know how to solve d2 but i can not understand why d1 approach not valid for all l.
If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table to increase/decrease the constraints.
If you are not able to find a counter example even after changing the parameters, reply to this thread, mentioning the contest_id, problem_index and submission_id.
@variety-jones In this ticket the expected and the actual output seem to be the same but still it says they're different. What am I missing?
It's because the exit code of your submission was not 0. (It did print 7, but it also had runtime errors), hence I consider it as a failing testcase. (On some platforms, it might have different exit codes, depending upon how uninitialized value access works).
An even smaller test case might be
Hint: Look at your array size.
Ya just saw it. From user experience perspective, would "runtime error" or something similar be better? (Not trying to turn the blame on you, just a suggestion :P)
Sure, thanks for the feedback. Will try to incorporate it the next time I make major changes to the website.
Could someone give a proper explanation how to use trie in D1/D2?
In this problem, we use trie(or similar structures) to calculate the number of $$$a_i$$$ such that $$$a_i \oplus x\in [l,r]$$$. So it is sufficient to calculate the number of $$$a_i$$$ satisfying $$$a_i \oplus x < r$$$.
In such queries, we can enumerate the longest common prefix of $$$a_i \oplus x$$$ and $$$r$$$ (in binary, of course, starting from the highest bit). Say this common prefix ends at the $$$k$$$-th bit.
Then we know exactly what the highest $$$17-k$$$ bits for $$$a_i$$$ should be, since $$$a_i \oplus x$$$ share the same bits with $$$r$$$. And the $$$k-1$$$-th bit in $$$r$$$ must be equal to $$$1$$$ (for the $$$0$$$ bits, just skip them), while the same bit in $$$a_i \oplus x$$$ should be $$$0$$$. The last several bits (from $$$k-2$$$ to $$$0$$$) no longer matters.
Thus, for each $$$k$$$, all we need to do is to precaculate the number of $$$a_i$$$ with some specific highest $$$18-k$$$ bits. This can be done using trie or simple arrays.
Trie : the number we wanted is equal to the number of leaves in a specific subtree, which can be precalculated during the trie building part. To find the subtree, just go down the trie while decreasing $$$k$$$. See my code for details.
Arrays : you can precalculate the number using arrays of size $$$2^{17-k}$$$ for each $$$k$$$ (or simply
cnt[17][1<<17]
). It's like a counting machine. Each $$$a_i$$$ will only contribute to one position in this array for each $$$k$$$. The time and space complexity should be the same as trie.(Sorry for my poor English. The details in my explanation may not be very clear. Hope you understand the method.)
You can also use trie or arrays to solve "the max and min of $$$a_i \oplus x$$$" problem, which is mentioned in other comments.
BTW, I've been wondering whether $$$x$$$ is fixed when $$$r-l+1$$$ is odd, since $$$\oplus a_i=\oplus_{l\le i\le r} (i\oplus x)$$$. Hope I'm not alone.
Yes, when $$$r - l + 1$$$ is odd, then $$$x$$$ can be uniquely defined. I actually used this in my solution for D1. Surprised that it wasn't mentioned much. But maybe it's not a complete solution as you'd need still to solve for the even cases.
Could someone give a rough proof of why the condition is sufficient in C (how would the permutation be constructed)?
Think in a permutation of lenght 5 like {5 4 3 2 1}, whose power is 1, now is there a way so in just one shift the power becomes 3? there isn't since whichever number you choose to put in fisrt place {x 5 ...} the five will make the array b = { x 5 5 5 5}. in other words, you can sum 1 to the power by sifhting the last number x where x < P[0], because this number will be counted in the power but for summing two you need to put at least two numbers in the beginning so that the b of the permutation becomes b = {x, y, 5, 5, 5} where x < y < 5 which is impossible with one shift (you only sifht one number).
This isn`t to mathematical and I only did this with a permutation of lenght 5, but i think it could be intuitive.
Sharing again!
Let 'c' be an array satisfying the necessary conditions. Rotate 'c' such that its first position is 1 without loss of generality. We will explicitly construct a permutation p obeying c. The first element of p is N.
let a = no. of 2s in array c, b = no. of 3s in array c and so on.
s[2] = {N-1,N-2,N-3...N-a} s[3] = {N-a-1, N-a-2, N-a-b} and so on.
Now traverse the array c from 2nd position.
if the element of c is k, place the lowest element of s[k] at the last available position of p and remove that element from s[k].
We're done.
what does s[2] denote here?
s[k] is a set of elements to be placed in your permutation whenever you encounter k while traversing c.
All elements of s[2] will be bigger than any element of s[i] where i>2.
In general all elements of s[i] will be bigger than any element of s[j] for j>i
Auto comment: topic has been updated by _FireGhost_ (previous revision, new revision, compare).
wow what an editorial for C, just awesome
Can someone explain what does mean "x is inside a" in D1 tutorial?
l<=x<=r
Anime fans before contest: Step on me MARIN
Anime fans after contest: Oh yeah baby, oh yeah (delta < 0)
Nope
Come on, guys. That was just a joke for anime fandom
Editorial for problem F is really confusing. Read twice, didn't understand a thing. Can you please elaborate?
Ok, let me try to rewrite and add some pictures and examples too. Sorry for the inconvenience right now.
Agreed, I haven't seen an editorial so cryptic in a long time, it took me a while to realize what they're getting at. Here's an attempt at explaining the idea.
Note: all variable names will either be the same ones used in the problem statement or explicitly defined.
Part 1: How many zeros and ones are in the answer?
Let the number of ones in $$$s$$$ be $$$ones$$$. The cuteness of the entire string by definition is $$$\frac{ones}{n}$$$. The concatenated string of length $$$m$$$ that we're looking for has the same cuteness, so the number of ones in it is $$$\frac{ones}{n} \cdot m$$$. Therefore, there is no answer if that value is not an integer (i.e. $$$ones \cdot m \not \equiv 0 \bmod n$$$).
Part 2: How do we find the answer with the minimum number of parts?
Let $$$x = \frac{ones}{n} \cdot m$$$.
Let's also assume the string is circular for now. Consider any length $$$m$$$ subarray in this circular string, including subarrays that wrap around. If we can find a subarray with exactly $$$x$$$ ones, then the minimum number of parts we need is either $$$1$$$ or $$$2$$$, depending on whether or not it wraps around. And both can be checked with sliding window/prefix sums.
It turns out such a subarray always exists. Let $$$c_i$$$ be the number of ones in $$$s[i \dots i + m - 1]$$$ if $$$i \leq n - m + 1$$$, or $$$s[1 \dots m - (n - i + 1)] + s[i \dots n]$$$ otherwise (basically, subarrays that wrap around versus subarrays that don't). Note that $$$|c_{i+1} - c_i| \leq 1$$$ for all $$$1 \leq i < n$$$ and $$$|c_1 - c_n| \leq 1$$$. This is because if we slide the subarray we're considering from $$$i$$$ to $$$i + 1$$$, we exclude $$$s_i$$$ and include $$$s_{((i+m-1) \bmod n) + 1}$$$. So the number of ones in our subarray can only increase or decrease by at most $$$1$$$. The implication of this is that there exists some $$$c_i = y$$$ for all $$$\min c_i \leq y \leq \max c_i$$$ because there's no way to go from a small to large $$$c_i$$$ while "skipping" over the values in the middle.
It holds that $$$\max c_i \geq x$$$ and $$$\min c_i \leq x$$$, implying some $$$c_i = x$$$. Assume that $$$\max c_i < x$$$. This means $$$\sum_{i=1}^n c_i < n \cdot x$$$. Furthermore, each index is included in exactly $$$m$$$ different subarrays. So $$$\sum_{i=1}^n c_i = m \cdot ones$$$. Thus, $$$m \cdot ones < n \cdot x$$$, or $$$x > m \cdot \frac{ones}{n}$$$ which is a contradiction by definition of $$$x$$$. Similarly, assume $$$\min c_i > x$$$. $$$\sum_{i=1}^n c_i = m \cdot ones > n \cdot x$$$, or $$$x < m \cdot \frac{ones}{n}$$$ which is a contradiction. Therefore, $$$\max c_i \geq x$$$ and $$$\min c_i \leq x$$$.
Thank you very much for your wonderful proof. I have completely understood it.
Thank you for writing this! Now everything is clear :)
As for the proof — I don't see anything wrong with it. There are a lot of proofs by contradiction)
Thanks! Also I figured out why my previous proof attempts are wrong as well as why they don't undermine the current proof.
Yes, it is was my fault that make it so cryptic, it is a huge basic mistake when I am too familiar with this problem (when trying to solve it in different ways, make strong tests, ...) I skipped most of the not-so-obvious ad-hoc observations.
For direct proof, I think we can do something like this:
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.
[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$$$
There is also a geometric way, you can use Borsuk–Ulam Theorem for problem F generalization of $$$x$$$ colors. In this theorem, AFAIK it claims that when $$$n = 2 * x$$$ and if it is not an impossible case then we don't need more than $$$x$$$ subarrays.
I can't see what property of solution for D1 uses the fact that $$$l = 0$$$ any ideas for this?
It doesn't work on a test $$$l=1$$$, $$$r=2$$$, $$$a = [0, 3]$$$.
Thanks! But still I can't see where the editorial used the fact :) Can you show me the point?
If number of ones equals number of zeroes at some position $$$i$$$ and $$$l=0$$$, then you know for a fact that $$$n = k \cdot 2^{i+1}$$$ for some $$$k$$$ and the proof from the last paragraph of the editorial works. Otherwise it doesn't.
Oh I see It is for the last line of the editorial. Thanks a lot :)
Hello, in the A problem if n==1 and s="0" should be the answer 1, not 0, and because of that i had wrong answer, the judge is wrong, how can i reclaim?
You cannot form any substring of length >= 2 in a string of length 1 as the statement says
In C tutorial should also be a condition, that there must be only one '1' in array
c
. Because '1' means, that the largest number is first, so if there are at least two '1',p
can't be a permutation.correct
Is this round unrated as rating changes are still not visible?
Can someone prove or refute and hack my solution of task B? I have no idea why this works, just noticed the pattern from example. Submission UPD: I guess I've figured that out, it's like a dynamic calculation of (n!)**2
Why does solution for D1 (bit count) not work for D2?
Think about this case
1 4
0 2 3 5
The answer is 1 and with bit count the answer should be 0.
1 4
2 1 0 7
Another case, answer = 3 and with bit count should be 0.
What did you give as test case the original array a or xored with x (a xor x)
According to me, if we solve D2 using bit count (method to solve D1) , there will not be any issue if bit count at any position for actual array and xored-array will be different. But if at any position, bit count will be same, we can't directly take (any of) 0 or 1 as the value of bit at that position for x ( as we did in D1 ).
LET'S CONSIDER THIS TEST CASE:
l=1 r=4
2 3 0 5 ( xored-array )
If we solve it using method used in D1, we will get output 0, but it's answer should be 1.
Please verify if I am correct.
Ok, I think I understand why the D1 algo does not work for D2.
If we got equal bitcount for 0 and 1 at some position, then in D2 only one of the both options is correct, but we cannot decide which one.
But in D1 both options work.
"But in D1 both options work." — could you please explain why ?
Thats difficult ;)
Well, I think it as: If we allways choose 0 if we can choose, then we will get the lowest possible value for l. That fits D1, since l==0.
But we can't say that ( a xor (x-1) < a xor x ). Maybe if we apply the operation (all elemets in a) xor x+1 that will be less than (all elemets in a) xor x. For example, array (2,3) xor 1 = (3,2) but array(2,3) xor 2 = (0,1) We took greater x (2>1) but got an less array (0,1)<(3,2). Maybe we can take a greater x to got a less initial array ? Why exactly when an initial array is (0 to r) array xor (lesser x) = lesser array ?
My solution is split the whole array into two parts so that we can apply the D1 algo for each part. If for any of the two parts, the number of 1 of some position is not correct, the answer is 1 on this position.
I split the array by the highest position which has both 0 and 1.
For example: l=6, r=10, answer=3 a: 4(0100) 5(0101) 9(1001) 10(1010) 11(1011)
So the highest position which has both 0 and 1 is the 4th one. Then array a is split into [4 5] and [9 10 11].
My Code
C would be worth a picture. Problem here is to wrap head arround rotation, permutation, position...things.
I just realized that the "next cyclic shift" is not created by moving the first element to last position, but instead by moving the last element to first position.
The solution for D2 is missing a "few" details, so I wrote one to make sure I fully knew how to solve the problem.
You can read my solution in the comments here: 151187878. Code is in python but hopefully it's readable since it's python.
Thank you so much for your explanation.The tutorial for D2 didn't tell why initialize ans to l or r(Line 23-25 in C++ code), so I was confused. You explain this in your solution(Line 11-12). Now I understant that because the number we can't pair(i.e.a[i]^1 is not in the set) must used to be either l or r(when l%2!=0&&r%2!=1). So that we can initialize ans so.
Another thing, there may a typo in your solution: in Line 12-"similarly, if r = 2*i+1", "2*i+1" should be revice to "2*i"?
Glad you found it helpful! Yes, it should be r = 2*i since 2*i^1 = r+1 which is not in the range.
thanks, you save my day!
can someone please explain why the solution for d1 doesnt work for d2??
This tutorial can be improved... On the surface it seems like you have put so much effort but for some one who was not able to solve a question , then to read these editorials and then understand and solve it is not possible. Most of the important points and proofs the authors have skipped. The problems were good but the editorial could have been improved.
You said what I want to say.
Proof for D1: Left as an exercise for the reader
I upsolved/practiced 1658D2 - 388535 (Hard Version) this way:
(Example: This happens twice for $$$l = \color{blue}{00}\color{red}{0}101_2, r = \color{blue}{00}\color{red}{1}001_2$$$: first two bits are the same, next one differs)
Then:
Example: $$$l = 00\color{red}{0101}_2, r = 00\color{blue}{1001}_2$$$, in first iteration we have range $$$R_l=[00\color{red}{0}000_2; 00\color{red}{0}111_2]$$$ and $$$R_r=[00\color{blue}{1}000_2; 00\color{blue}{1}111_2$$$], next iteration $$$R_l=[00\color{red}{01}00_2; 00\color{red}{01}11_2]$$$ and $$$R_r=[00\color{blue}{10}00_2; 00\color{blue}{10}11_2]$$$; and so on
Submission: 151190666
In problem.E, Why do you maintain the set S of all pairs $$$(i',j')$$$ such that $$$dp[i'][j']=1$$$ instead of $$$dp[i'][j']=0$$$ ?
Oh, I understand. How stupid I am!
In problem E where did $$$|i-i'|+|j-j'| \leq k \Leftrightarrow \max(|(i+j)-(i'+j')|,|(i-j)-(i'-j')|) \leq k$$$ come from? What's the intuition behind this? Is it something well known?
I think maybe it's a normal method to deal with the absolute value.
We can transform from 2d Manhattan distance metric to Chebyshev distance by transforming all the points $$$(x, y)$$$ to $$$(x+y, x-y)$$$. I think its relatively well known
Consider all points at distance at most $$$k$$$. Actually, this points form a diamond shape. It's hard to work with diamond, so we can rotate the plane by 45 degrees ($$$(x,y)$$$ -> $$$(x+y,x-y)$$$), and now all points at distance at most $$$k$$$ form a square shape. So after this we have a different function for distance: $$$|x_1-x_2| + |y_1-y_2|$$$ -> $$$max(|x_1'-x_2'|, |y_1'-y_2'|$$$, where $$$x' = x+y$$$ and $$$y' = x-y$$$.
How it can be used in this problem? After the transformation we need to know is there any winning points outside the rectangle (it's the same as: are all winning points inside the rectangle). This problem can be easily solved with 2D BIT, for example (but there are simpler solutions, as mentioned in the editorial).
Thank you. I saw this ($$$(x, y) \rightarrow (x+y, x-y)$$$) transformation once before, but I don't understand why it works. It's not just a simple "rotation by $$$45$$$ degrees", is it?
For example, if you take $$$2$$$ points $$$(3, 4)$$$ and $$$(3, 5)$$$ (distance $$$1$$$) and do the transformation, it will be $$$(7, -1)$$$ and $$$(8, -2)$$$ (distance $$$\sqrt{2}$$$). Am I missing something?
The Manhattan distance between $$$(3,4)$$$ and $$$(3,5)$$$ is $$$|3-3|+|4-5|=1$$$, which is equal to the Chebyshev distance between $$$(7,-1)$$$ and $$$(8,-2)$$$($$$\max(|7-8|,|(-1)-(-2)|)$$$).
Yes, I understand how it works. Can you please explain why it works?
As far as I know, rotation keeps distance between points unchanged. This is not happening in this case.
Futhermore, I can't even say it's a rotation, it's something more strange.
Here $$$A$$$, $$$B$$$, $$$C$$$ are points before the transformation and $$$A'$$$, $$$B'$$$, $$$C'$$$ are points after the transformation.
Formula for distance works here, definitely. But can you please elaborate why? What's exactly happening here? Why it's called "rotation by $$$45$$$ degrees"?
Let's define the Manhattan distance between $$$a(x_1,y_1)$$$ and $$$b(x_2,y_2)$$$ to be $$$d(a,b)$$$.Then we can find that:
that is, the Manhattan distance between $$$a(x_1,y_1)$$$ and $$$b(x_2,y_2)$$$ is equal to the Chebyshev distance between $$$(x_1+y_1,x_1-y_1)$$$ and $$$(x_2+y_2,x_2-y_2)$$$.
Thank you. Now I almost got it.
The only thing I don't understand is, why it's called a "rotation by $$$45$$$ degrees"? Isn't it just elegant coordinate transformation?
To be precise, transform from 2d Manhattan distance metric to Chebyshev distance involves rotating and zooming, These are two operations.
What does the first solution for D2 mean? I have no idea about it. How does it work?
In c why do we have to rotate it?
n
Why does solution in D1 does not work for D2? Plz explain
Think about xor-ing 1 to 3,4,5,6
You used same variable name k in F. This is not easy for readers to understand .
The contest is great , but the editorial is not so good .
When I choose "Good problem",I add it to liked.When I choose "Bad problem",I add it to liked too?
In feedback I mean.
Well, 'liked' means that you like such options, not the problem itself.
Sorry for my rudeness , I think ConclusionForces is boring, Problem ABCEF is all Conclusion problems.
Sorry but what is conclusion problems?
A problem that you can solve it only by guessing a simple conclusion.
Is it another name for observation problems?
Eh, I don't think my problem F only needs a simple guess conclusion tho.
why? I guessed one so I get accepted during the contest.
Wow, how did you guess it?
When I am setting the problem, I expected at least 3 ad-hoc observations to solve the problem tho :<
"However, if the number of ones is equal to the number of zeros, we can actually assign the i-th bit anything we like." — how can we proof this part ? Can somenone please explain me ?
Have you known the answer now, I have the same question.
I have solved problem D1 using binary search. I think there must be binary search tag in problem D1. :) Total time complexity is
nlog^2(n)
Problem setters please note that avoid writing note once in a separate statement.
In D1, you said find the value of x. I read it and left everything else and started solving. You wrote in the next paragraph that multiple x can exist.
Its better to write in the original statement itself. I wasted hours trying to form and solve equations
Weak tests for Problem E. A trivial edge case (where one of the 'winning' cells is present at a corner of the matrix) was enough to uphack my AC submission.
For D2, I think the final answer is l or r xor the isolated element in array a after the first step. I can't understand why we should check by this sentence "f &= ((cur ^ j) >= l && (cur ^ j) <= r)". Could anybody tell me this? Thanks
In D2 you can not count the number of numbers in the segment, but just check min(a[i] ^ x) == l and max(a[i] ^ x) == r. Because if all the numbers were different, then they will remain different if they are xoring with x => all number belongs segment
For D2 I have another simple solution :
First sort the array given to you, then divide it into several consecutive intervals.It can be proved that the number of these intervals will not exceed log(r-l+1).
Then for each interval [L,R], check whether x={l^L,l^R,r^L,r^R} satisfies the condition。
It means that the XOR of these continuous intervals will also be a continuous interval after our answer x, and l, r must appear in one [L,R].
more details:151127931
[Deleted]
In Problem.F I have a wrong guess: if $$$m\leq \frac{n}{2}$$$, then $$$k=1$$$. And it gave the wrong answer on case 24 in test 156. But I can't prove it wrong officially. Who can help me?
Let me check for this
In test 156 I generated only testcases that give $$$k = 2$$$ as answer
You can try this testcase I just manually make
Actually, when $$$m = \frac{n}{2}$$$ and $$$b, w$$$ are even then your guess is correct and provable.
Let $$$D[x] = $$$ (number of '1' in $$$s[x \dots x + m - 1]$$$)
If $$$D[x] = m$$$ then we are done
Otherwise WLOG $$$D[x] < m < D[x + m]$$$
Since $$$|D[x + 1] - D[x]| \leq 1$$$ then applying IVT you can prove there is $$$y$$$ in $$$[x + 1, x + m - 1]$$$ that $$$D[y] = m$$$
There is another solution without using IVT and an overkill solution for an even more generalized F problem, if you are interested then I will make a blog about it.
after taking an hour of reading the codes, seeming there are 3 guys make that same wrong guess, but I dont know how to prove for $$$m < \frac{n}{2}$$$ can make $$$k = 2$$$ test using math. I will try to brute-forces for some small cases then..
I'm unable to find errors under random data. maybe we can try constructing some special data.
dunno, I failed to prove it wrong using math too
cunzai_zsy0531 SPyofgame
You can consider this counter example.
The cuteness of the original string is $$$\frac{30}{50} = \frac{3}{5}$$$. If you take the last 19 elements, which contain 12 ones, and a single zero from other segment, the cuteness becomes $$$\frac{12}{20} = \frac{3}{5}$$$. You can also dry run your algorithm on this case to see why $$$k = 1$$$ wouldn't suffice.
You can also systematically construct the counter example to disprove the fact. We need to create a string of length 50, containing 30 ones, we create it as
where
Base = 11111111111000000000
(11 times one, followed by 9 zeroes). (This restricts a substring of length 20 from being an answer).and
Remain = 1111111100
(8 times one, followed by 2 zeroes). (Since we need to ensure that the string contains exactly $$$(11 + 11 + 8 = 30)$$$ ones.Now, it's easy to see that no window of length 20 contains 12 ones. Hence, we will need to split it into 2 segments.
Interesting, but can you generalize it?
As you can see from my generator that only generates k = 2 tests, I make it completely random without any specific forms.
I think the method to generate it is that you put more zeros than you need between the one's subsegments.
that's fantastic. Thank you very much.
I think based on variety-jones binary string construction, you can now analyze it using math :>
Perhaps in magical Codeforces,I lost my ability of datastructrue...I wonder why I cannot think of solutionof 01 Trie in D2 qwq
Could someone help me understand why this code is getting TLE? 151271702
I tried the problem F during the contest,but I had failed.
It's really an amazing problem,and I love it.
Thank you. Also, if you find this problem interested you enough, do you wanna try its generalized problem for $$$k$$$ colors and $$$n = 2 \cdot k$$$ ?
Such blasphemy. Marin simps will never forgive you for D.
can someone please explain me how to find all the squares within k manhatten distance in problem e.I have understood the whole approach of editorial just struggling in implementing last part of the editorial.
Thanks in advance.
I found a pretty elegant proof for E: let's call a cell $$$x$$$ winning if the first player wins starting from $$$x$$$, otherwise let's call it losing. Let's induct backwards from $$$n^2$$$ to $$$1$$$, assuming correctness of previously marked cells. Suppose that we're currently deciding whether cell $$$i$$$ is winning or losing.
There is an important observation: for all previously marked losing cells $$$a$$$, there exists a winning cell $$$b$$$ such that $$$b > a$$$ and $$$dist(a, b) > k$$$. Furthermore, for all previously marked winning cells $$$a$$$, all cells $$$b$$$ such that $$$dist(a, b) > k$$$ are either less than $$$a$$$ or marked losing.
If there exists a marked winning cell $$$j$$$ such that $$$dist(i, j) > k$$$, the second player has a winning strategy: pick the cell $$$j$$$, suppose the first player then picks $$$w$$$. From our observation, either $$$w < j$$$, or $$$w$$$ is a losing cell. In the first case, the second player can respond with $$$j$$$ again. In the second case, from our observation, they can respond with a strictly larger winning cell. We can see that by repeatedly following this strategy, the second player will accrue an advantage of at least $$$10^{100}$$$, since on their turn, they will always respond with a cell strictly larger than that of the first player.
If there doesn't exist such a cell $$$j$$$, then the first player has a similar winning strategy. This time, it can be proven that they can accrue an advantage of at least $$$10^{100} - n^2$$$ (we can imagine that their first move is a "sacrifice", and then they can repeatedly choose a larger cell than what the second player got in the preceding turn).
So I believe that if the number of moves of each player was reduced to $$$n^2 + 1$$$, then the solution would remain the same.
I didn't participate in the contest, but I solved problem C just now with a similar approach.
I first realized that there has to be exactly one 1 in the input array c. Find this index, and reset the array starting from that index. Then I realized that if you go from c[i] to c[i + 1], the following two inequalities hold true if a valid permutation exists: 2 <= c[i + 1] <= c[i] + 1 and c[i + 1] <= n. So a simple O(n) solution is to find the index of the element with a 1, reset the array to start with that element, and check consecutive pairs to make sure the inequalities are satisfied.
I used proof by ac. 152800406
Hi all! I need a help to understand problem D2. Test2 has case: 0 0 1 with answer '0'. As i understand the input values, l=0, r=0, so, initial value of 'a' is '0'. Result of 'xor' operation with 'x' is '1'. We have to find 'x'. Why it is '0'? Pls help to understand.
The question is cleared.
161418396
For D2, we can fix the starting bits. If our first few bits in our array doesn't match with the necessary number of bits (according to l...r), then invert the bits. Otherwise, keep as is. Recurse.
In problem D2's tutorial,
Otherwise, we will pair a_i with a_i⊕1, and we will left with at most 2 candidates for x to check
. I do not quite buy it. Why do we pair $$$a_i$$$ and $$$a_i⊕1$$$? And what do you do to check the 'x'?Uhmm... Sorry, I have just understood it, so I am no longer need for explainations.
Regarding C : Blog
Question link : https://codeforces.me/problemset/problem/1658/C
Pre-requisite : Relationship between $$$p$$$ and $$$c$$$
In the question, we are given that:
This means that $$$c_1$$$ is the 0th shift : Which means that is, for that case, the permutation remains as is => $$$p_1, p_2, p_3,...,p_n$$$
$$$c_2$$$ is the 1st shift : $$$p_n, p_1, p_2, ..., p_{n-1}$$$ $$$c_3$$$ is the 2nd shift : $$$p_{n-1}, p_n, p1, p2, ..., p_{n-2}$$$
So as you see items in $$$c$$$ from 1st index to nth index, you start with the first item being at the start, then you suddenly go $$$p_n$$$ and come back until $$$p_2$$$
So: $$$c_1 \rightarrow p_1$$$ $$$c_2 \rightarrow p_n$$$ $$$c_3 \rightarrow p_{n-1}$$$ ... $$$c_n \rightarrow p_2$$$
Where does $$$c_i + 1 \geq c_{i+1}$$$ come from?
Case 1 : $$$p_1 > p_n$$$
Note that $$$p_1$$$ corresponds to $$$c_1$$$ and $$$p_n$$$ corresponds to $$$c_2$$$
In this case, the next item that is coming at the start ($$$p_n$$$) is smaller than the current item. When $$$p_n$$$ was at the last point, it didn't contribute to $$$c_1$$$ as $$$p_n < p_1$$$, therefore it's removal from the last point doesn't affect the $$$c$$$ value of $$$p_1$$$. But now that it has come to the start of the permutation, we can see that the c-value increases by 1. Therefore in this case $$$c_i + 1 =c_{i+1}$$$
Case 2 : $$$p_1 < p_n$$$
Note that $$$p_1$$$ corresponds to $$$c_1$$$ and $$$p_n$$$ corresponds to $$$c_2$$$
Now at the start we are bringing a bigger element.
When $$$p_n$$$ was at the end of the array, it was more than $$$p_1$$$ so it might be contributing to the c-value in that case (this will happen when $$$p_n$$$ is the largest number in $$$p$$$). So removing it from the last position might decrease the c-value.
Also, when $$$p_n$$$ comes at the start of the array, then it will shadow $$$p_1$$$ and other items smaller than $$$p_n$$$. This means, that the c-value could further decrease.
So we can see that in this case $$$c_i \geq c_{i+1}$$$ (There are cases where the c-value remains the same. Example : 1, 3, 2 has c-value of 2, and 2, 1, 3 also has a c-value of 2)
So by combining $$$c_i \geq c_{i+1}$$$ and $$$c_i + 1 = c_{i+1}$$$ we can say that $$$c_i + 1 \geq c_{i+1}$$$
How is this condition enough to check whether a valid permutation can be formed?
Let's first think about what a permutation would look like, when following the condition $$$c_i + 1 \geq c_{i+1}$$$
This, simply, means that we can have drastic reductions, but increments can only be done in 1s.
Case 1 : Maximum value in $$$c$$$ is $$$n$$$
In this case, we will have a simple incremental array from 1 to n in $$$c$$$. That is, it will look like : $$$1, 2, ..., n$$$ because we NEED to have a single one, to represent the biggest element in $$$p_n$$$, and we need to reach $$$n$$$ from this value, and we can only increase by 1.
This would generate the simple permutation : $$$n, 1, 2, ..., n-1$$$
Case 2 : Maximum value in $$$c$$$ is less than $$$n$$$
In this case, we would have repetitions of numbers in $$$c$$$. Note that we can not have more than one 1 in $$$c$$$. Other numbers can repeat.
So we need to reach this max number (let's say $$$m$$$) from 1, and we can increase by one only.
So this can look like : $$$1, 2, 3, 4, ..., m, m - 2, m - 1, ...$$$ Basically an increasing phase, followed by random drops and increases. The increasing phase can also have repetitions, and drops.
In order to construct the array, this construction method : https://codeforces.me/blog/entry/101302?#comment-899615
When the c value increases, then we can simply put a smaller number at the curr position. That will ensure that a correct permutation is being generated.
When the c-value decreases, note that this value would be a repetition — We already would have seen this value atleast once. Why? Because we started from 1, and in order to decrease, we must have reached the current value by increments of 1. That means we have seen all numbers between 1 and the current number. Therefore, all drops / decrements would generate a number, which already has been seen.
Another point to note : Between the previous instance of this number, and the current instance of this number, we either: - Decreased and increased - This would be handled by the "c-value increase" case. - Increased and decreased - This would mean that c-value increased, and decreased to come back at the same point. An "increase" in c-value means a decrease in absolute value in $$$p$$$. Therefore, all numbers between the same instances would be smaller. This simply means that we can indeed have a correct permutation in this case too.
I think these inferences are enough to see that the condition is enough to check whether a valid permutation can be created from the given c-values.
Btw if the n is odd we can easily solve it just take the xor of numbers from 0 to l-r say it comes out to be x1 and then take xor of the array say x2 and now traverse the array and check if x1^v[i]==x2 that is our answer
can anyone explain why approach of d1 not working for d2
my master give me this D1 problem couldn't able to do was thinking for hours but cant think D1 optimal solution feeling bad , :( idk whether i am improving or not not able to solve as going to higher ratings . feels very demotivated.
I solve D2 using tires i think it is much easier then. please look at this code 265873403