1631A - Min Max Swap
Author: humbertoyusta
Think about how $$$max(a_1, a_2, ..., a_n, b_1, b_2, ..., b_n)$$$ will contribute to the answer.
The maximum of one array is always $$$max(a_1, a_2, ..., a_n, b_1, b_2, ..., b_n)$$$. How should you minimize then?
Let $$$m_1 = \max(a_1, a_2, ..., a_n, b_1, b_2, ..., b_n)$$$. The answer will always be $$$m_1 \cdot m_2$$$ where $$$m_2$$$ is the maximum of the array that does not contain $$$m_1$$$.
Since $$$m_1$$$ is fixed, the problem can be reduced to minimize $$$m_2$$$, that is, minimize the maximum of the array that does not contain the global maximum.
WLOG assume that the global maximum will be in the array $$$b$$$, we can swap elements at each index $$$x$$$ such that $$$a_x > b_x$$$, ending with $$$a_i \leq b_i$$$ for all $$$i$$$. It can be shown that the maximum of array $$$a$$$ is minimized in this way.
Time complexity: $$$O(n)$$$
#include<bits/stdc++.h>
using namespace std;
int calc_max(vector<int> a){
int res = 0;
for( auto i : a )
res = max( res , i );
return res;
}
int main(){
int tc;
cin >> tc;
while( tc-- ){
int n;
cin >> n;
vector<int> a(n), b(n);
for( auto &i : a )
cin >> i;
for( auto &i : b )
cin >> i;
for(int i=0; i<n; i++)
if( a[i] > b[i] )
swap( a[i] , b[i] );
cout << calc_max(a) * calc_max(b) << '\n';
}
}
1631B - Fun with Even Subarrays
Author: humbertoyusta
It is not possible to modify $$$a_n$$$ using the given operation.
Think about the leftmost $$$x$$$ such that $$$a_x \neq a_n$$$.
For simplicity, let $$$b_1, b_2, ..., b_n = a_n, a_{n-1}, ..., a_1$$$ (let $$$b$$$ be $$$a$$$ reversed). The operation transforms to select a subarray $$$[l, r]$$$ of length $$$2\cdot{k}$$$, so $$$k = \frac{r-l+1}{2}$$$, then for all $$$i$$$ such that $$$0 \leq i < k$$$, set $$$b_{l+k+i} = b_{l+i}$$$.
$$$b_1$$$ can not be changed with the given operation. That reduces the problem to make all elements equal to $$$b_1$$$.
Let $$$x$$$ be the rightmost index such that for all $$$1 \leq i \leq x$$$, $$$b_i = b_1$$$ holds.
The problem will be solved when $$$x = n$$$.
If an operation is applied with $$$l + k > x + 1$$$, $$$b_{x+1}$$$ will not change and $$$x$$$ will remain the same.
The largest range with $$$l + k \leq x + 1$$$ is $$$[1, 2\cdot{x}]$$$, applying an operation to it will lead to $$$b_{x+1}, b_{x+2}, ..., b_{2\cdot{x}} = b_1, b_2, ..., b_x$$$, so $$$x$$$ will become at least $$$2\cdot{x}$$$ and there is not any other range that will lead to a bigger value of $$$x$$$.
If $$$2\cdot{x} > n$$$, it is possible to apply the operation on $$$[x-(n-x)+1,n]$$$, after applying it $$$b_{x+1}, ..., b_n = b_{x-(n-x)+1}, ..., b_x$$$ and all elements will become equal.
The problem can now be solved by repeatedly finding $$$x$$$ and applying the operation on $$$[1, 2\cdot{x}]$$$ or on $$$[x-(n-x)+1,n]$$$ if $$$2\cdot{x} > n$$$.
Since $$$x$$$ will become at least $$$2\cdot{x}$$$ in each operation but the last one, the naive implementation will take $$$O(n\log{n})$$$, however, it is easy to implement it in $$$O(n)$$$.
#include<bits/stdc++.h>
using namespace std;
int find_rightmost_x(vector<int> &b){
int n = (int)b.size() - 1;
int x = 1;
while( x + 1 <= n && b[x+1] == b[1] )
x ++;
return x;
}
void apply(vector<int> &b,int l,int r){
int k = ( r - l + 1 ) / 2;
for(int i=0; i<k; i++)
b[l+k+i] = b[l+i];
}
int main(){
int tc;
cin >> tc;
while( tc-- ){
int n;
cin >> n;
vector<int> a(n+1);
for(int i=1; i<=n; i++)
cin >> a[i];
vector<int> b = a;
reverse(b.begin()+1,b.end());
int ans = 0;
while( find_rightmost_x(b) != n ){
int x = find_rightmost_x(b);
if( 2 * x > n ){
apply(b,x-(n-x)+1,n);
ans ++;
}
else{
apply(b,1,2*x);
ans ++;
}
}
cout << ans << '\n';
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int main()
{
int tc;
cin >> tc;
while(tc--)
{
int n;
cin >> n;
vector<int> a(n+1);
for(int i=1; i<=n; i++)
cin >> a[i];
vector<int> b = a;
reverse(b.begin()+1,b.end());
int ans = 0, x = 1;
while( x < n )
{
if( b[x+1] == b[1] ){
x ++;
continue;
}
ans ++;
x *= 2;
}
cout << ans << '\n';
}
return 0;
}
1630A - And Matching
Author: humbertoyusta
Try to find a pairing such that $$$\sum\limits_1^{n/2}{a_i\&{b_i}}=0$$$
Try to find a pairing for $$$k>0$$$ by changing only a few elements from the previous pairing.
Let's define $$$c(x)$$$, the compliment of $$$x$$$, as the number $$$x$$$ after changing all bits 0 to 1 and vice versa, for example $$$c(110010_2) = 001101_2$$$.
It can be shown that $$$c(x) = x\oplus{(n-1)}$$$. Remember that $$$n-1 = 11...11_2$$$ since $$$n$$$ is a power of $$$2$$$.
We will separate the problem into three cases.
Case $$$k = 0$$$:
In this case it is possible to pair $$$x$$$ with $$$c(x)$$$ for $$$0\leq{x}<{\frac{n}{2}}$$$, getting $$$\sum\limits_{x=0}^{\frac{n}{2}-1} {x\&{c(x)}} = 0$$$.
Case $$$0 < k < n-1$$$:
In this case it is possible to pair each element with its compliment except $$$0$$$, $$$k$$$, $$$c(k)$$$ and $$$n-1$$$, and then pair $$$0$$$ with $$$c(k)$$$ and $$$k$$$ with $$$n-1$$$, $$$0\& c(k) = 0$$$ and $$$k\& (n-1) = k$$$.
Case $$$k = n-1$$$:
There are many constructions that work in this case, if $$$n=4$$$ there is no solution, if $$$n \geq8$$$ it is possible to construct the answer in the following way:
It is possible to pair $$$n-1$$$ with $$$n-2$$$, $$$n-3$$$ with $$$1$$$, $$$0$$$ with $$$2$$$ and all other elements with their compliments.
- $$$(n-1)\&{(n-2)}=n-2$$$, for example $$$1111_2\&{1110_2}=1110_2$$$
- $$$(n-3)\&{1}=1$$$, for example $$$1101_2\&{0001_2}=0001_2$$$
- $$$0\&{2}=0$$$, for example $$$0000_2\&{0010_2}=0000_2$$$
- All other elements can be paired with their complements and $$$x\&{c(x)}=0$$$
Note that $$$(n-2)+1+0+0+ ... +0=n-1$$$.
Each case can be implemented in $$$O(n)$$$.
#include<bits/stdc++.h>
using namespace std;
int c(int x,int n){
return ( x ^ ( n - 1 ) );
}
int main(){
int tc;
cin >> tc;
while( tc-- ){
int n, k;
cin >> n >> k;
vector<int> a(n/2), b(n/2);
if( k == 0 ){
for(int i=0; i<n/2; i++){
a[i] = i;
b[i] = c(i,n);
}
}
if( k > 0 && k < n - 1 ){
int small_k = min( k , c(k,n) );
for(int i=0; i<n/2; i++){
if( i != 0 && i != small_k ){
a[i] = i;
b[i] = c(i,n);
}
}
a[0] = 0;
b[0] = c(k,n);
a[small_k] = k;
b[small_k] = n - 1;
}
if( k == n - 1 ){
if( n == 4 ){
cout << -1 << '\n';
continue;
}
a[0] = n - 2;
b[0] = n - 1;
a[1] = 1;
b[1] = n - 3;
a[2] = 0;
b[2] = 2;
for(int i=3; i<n/2; i++){
a[i] = i;
b[i] = c(i,n);
}
}
for(int i=0; i<n/2; i++){
cout << a[i] << ' ' << b[i] << '\n';
}
}
return 0;
}
Let's define $$$a$$$ such that $$$a_i = i-1$$$ for $$$1\le i \le \frac{n}{2}$$$ and $$$b$$$ such that $$$b_i = c(a_i)$$$ for $$$1\le i \le \frac{n}{2}$$$.
For example, for $$$n = 16$$$ they are:
1st element to swap | 2nd element to swap | $$$\sum\limits_{i=1}^{n/2}{ a_i\&{b_i}}$$$ after swap |
---|---|---|
none | none | $$$0$$$ |
$$$b_1$$$ | $$$b_2$$$ | $$$1$$$ |
$$$b_2$$$ | $$$b_3$$$ | $$$3$$$ |
$$$b_3$$$ | $$$b_4$$$ | $$$1$$$ |
$$$b_4$$$ | $$$b_5$$$ | $$$7$$$ |
$$$b_5$$$ | $$$b_6$$$ | $$$1$$$ |
$$$b_6$$$ | $$$b_7$$$ | $$$3$$$ |
$$$b_7$$$ | $$$b_8$$$ | $$$1$$$ |
All swaps are independent and are applied to the original $$$a$$$ and $$$b$$$.
After swapping two adjacent elements of $$$b$$$ (that have not been swapped) the sum will change in $$$2^x-1$$$ for some positive integer $$$x$$$.
Then it is possible to solve the problem by repeatedly swapping the pair that maximizes $$$\sum\limits_{i=1}^{n/2}{ a_i\&{b_i}}$$$ after the swap such that $$$\sum\limits_{i=1}^{n/2}{ a_i\&{b_i}} \leq k$$$ is held and none of its elements have been swapped yet.
However, this only works for all values of $$$k$$$ if $$$n \geq 32$$$, the case $$$n \leq 16$$$ can be handled with brute force.
Please read the previous solution. Arrays $$$a$$$ and $$$b$$$ from it will also be used here.
It is possible to start with $$$a$$$ and $$$b$$$ and repeatedly select and index $$$x$$$ randomly and swap $$$b_x$$$ with $$$b_{x+1}$$$ if $$$\sum\limits_{i=1}^{n/2}{a_i\&b_i} \leq k$$$ holds until $$$\sum\limits_{i=1}^{n/2}{a_i\&b_i} = k$$$.
We have no proof of this solution but it was stressed against each possible input to the problem and it worked quickly for $$$n \geq 16$$$, the case $$$n \leq 8$$$ can be handled with brute force.
1630B - Range and Partition
Author: humbertoyusta
Focus on how to solve the problem for a fixed interval $$$[x,y]$$$
Think about the numbers inside the interval as $$$+1$$$, and the other numbers as $$$-1$$$
Try to relate a partition into valid subarrays with an increasing sequence of the prefix sums array
Note that if some value $$$x$$$ ($$$x>0$$$) appears on the prefix sums array, $$$x-1$$$ appears before since the absolute value of the elements is $$$1$$$ (+1 and -1)
Focus on how to solve the problem for a fixed interval $$$[x,y]$$$:
Let us define an array $$$b$$$ such that $$$b_i = 1$$$ if $$$x \le a_i \le y$$$ or $$$b_i = -1$$$ otherwise, for all $$$1\le i\le n$$$.
Let's define $$$psum_i$$$ as $$$b_1 + b_2 + ... + b_i$$$.
We need to find a partition on $$$k$$$ subarrays with positive sum of $$$b_i$$$.
The sum of a subarray $$$[l,r]$$$ is $$$b_l+b_{l+1}+...+b_r = psum_r-psum_{l-1}$$$. Then a subarray is valid if $$$psum_r > psum_{l-1}$$$.
We need to find an increasing sequence of $$$psum$$$ of length $$$k+1$$$ starting at $$$0$$$ and ending at $$$n$$$.
Let's define $$$firstocc_x$$$ to be the first occurrence of the integer $$$x$$$ in $$$psum$$$.
If $$$psum_n < k$$$ there will be no valid sequence, otherwise the sequence $$$0, firstocc_1, firstocc_2, ..., firstocc_{k-1}, n$$$ will satisfy all constraints.
Note that, since $$$|psum_i-psum_{i-1}| = 1$$$, for $$$i>0$$$, then $$$firstocc_v$$$ exists and $$$firstocc_v < firstocc_{v+1}$$$ for $$$0\leq v \leq psum_n$$$.
This solves the problem for a fixed interval.
It remains to find the smallest interval $$$[x,y]$$$ such that $$$psum_n \geq k$$$.
For a given interval $$$[x,y]$$$, since $$$psum_n = b_1 + b_2 + ... + b_n$$$, $$$psum_n$$$ will be equal to the number of elements of $$$a$$$ inside the interval minus the number of elements outside.
Then for each $$$x$$$, it is possible to find the smallest $$$y$$$ such that $$$psum_n \geq k$$$ using binary search or two pointers.
It is also possible to note that:
We need to find the smallest interval with at least $$$\lceil{\frac{k+n}{2}}\rceil$$$ inside, let $$$A$$$ be the array $$$a$$$ sorted, the answer is the minimum interval among all intervals $$$[A_i, A_{i+\lceil{\frac{k+n}{2}}\rceil-1}]$$$ for $$$1 \leq i \leq n - \lceil{\frac{k+n}{2}}\rceil+1$$$.
Complexity: $$$O(n\log{n})$$$ if solved with the previous formula or binary search, or $$$O(n)$$$ is solved with two pointers.
#include<bits/stdc++.h>
using namespace std;
int main() {
int tc;
cin >> tc;
while( tc-- ){
int n, k;
cin >> n >> k;
vector<int> a(n), sorted_a(n);
for(int i=0; i<n; i++){
cin >> a[i];
sorted_a[i] = a[i];
}
sort(sorted_a.begin(),sorted_a.end());
int req_sum = ( n + k + 1 ) / 2;
pair<int,pair<int,int>> ans = { n + 1 , { -1 , -1 } };
for(int i=0; i+req_sum-1<n; i++)
ans = min( ans , { sorted_a[i+req_sum-1] - sorted_a[i] , { sorted_a[i] , sorted_a[i+req_sum-1] } } );
cout << ans.second.first << ' ' << ans.second.second << '\n';
int subarrays_found = 0, curr_sum = 0;
int last_uncovered = 1;
for(int i=0; i<n; i++){
if( a[i] >= ans.second.first && a[i] <= ans.second.second ) curr_sum ++;
else curr_sum --;
if( curr_sum > 0 && subarrays_found + 1 < k ){
cout << last_uncovered << ' ' << ( i + 1 ) << '\n';
last_uncovered = i + 2;
subarrays_found ++;
curr_sum = 0;
}
}
subarrays_found ++;
cout << last_uncovered << ' ' << n << '\n';
}
return 0;
}
1630C - Paint the Middle
Author: humbertoyusta
Think about all occurrences of some element, what occurrences are important?
Think about the first and last occurrence of each element as a segment.
Think about the segments that at least one of its endpoints will end up with $$$c_i = 0$$$.
For each $$$x$$$ such that all the elements $$$a_1, a_2, ..., a_x$$$ are different from $$$a_{x+1}, a_{x+2}, ..., a_n$$$ it is impossible to apply an operation with some indices from the first part, and some other from the second one.
Then it is possible to split the array in subarrays for each $$$x$$$ such that the previous condition holds, and sum the answers from all of them.
Let's solve the problem independently for one of those subarrays, let's denote its length as $$$m$$$, the values of its elements as $$$a_1, ..., a_m$$$ and their colors as $$$c_1, ..., c_m$$$:
For every tuple $$$(x, y, z)$$$ such that $$$1 \le x < y < z \le m$$$ and $$$a_x = a_y = a_z$$$ it is possible to apply an operation with indices $$$x, y$$$ and $$$z$$$. Then only the first and last occurrences of each element are important.
For all pairs $$$(x, y)$$$ such that $$$1 \le x < y \le m$$$, $$$a_x = a_y$$$, $$$a_x$$$ is the first occurrence and $$$a_y$$$ the last occurrence of that value, a segment $$$[x, y]$$$ will be created.
Let's denote the left border of a segment $$$i$$$ as $$$l_i$$$ and the right border as $$$r_i$$$.
Let's say that a set of segments $$$S$$$ is connected if the union of its segments is the segment $$$[\min(l_i, \forall i\in{S}), \max(r_i, \forall i\in{S})]$$$.
Instead of maximizing $$$\sum\limits_{i=1}^m{c_i}$$$, it is possible to focus on minimizing $$$\sum\limits_{i=1}^m{[c_i=0]}$$$.
Lemma 1: If we have a connected set $$$S$$$, it is possible to apply some operations to its induced array to end up with at most $$$|S|+1$$$ elements with $$$c_i = 0$$$.
For each segment $$$x$$$ in $$$S$$$ if there exists a segment $$$y$$$ such that $$$l_y < l_x < r_x < r_y$$$, it is possible to apply the operation with indices $$$l_y, l_x, r_y$$$ and with $$$l_y, r_x, r_y$$$. Otherwise, add this segment to a set $$$T$$$.
Then is possible to repeatedly select the leftmost segment of $$$T$$$ that have not been selected yet, and set the color of its right border to $$$1$$$, this will be always possible until we select the rightmost segment since $$$T$$$ is connected.
In the end, all the left borders of the segments of $$$T$$$ will have $$$c_i = 0$$$, the same holds for the right border of the rightmost segment of $$$T$$$, which leads to a total of $$$|T|+1$$$ elements with $$$c_i = 0$$$, and $$$|T| \le |S|$$$.
Let $$$X$$$ be a subarray that can be obtained by applying the given operation to the initial subarray any number of times.
Let $$$S(X)$$$ be the set of segments that includes all segments $$$i$$$ such that $$$c[l_i] = 0$$$ or $$$c[r_i] = 0$$$ (or both), where $$$c[i]$$$ is the color of the $$$i$$$-th segment of the subarray $$$X$$$.
Lemma 2: There is always an optimal solution in which $$$S(X)$$$ is connected.
Suppose $$$S(X)$$$ is not connected, if there are only two components of segments $$$A$$$ and $$$B$$$, there will always be a segment from $$$A$$$ to $$$B$$$ due to the way the subarray was formed.
If $$$A$$$ or $$$B$$$ have some segment $$$x$$$ such that there exists a segment $$$y$$$ such that $$$l_y < l_x < r_x < r_y$$$ you can erase it by applying the operation with indices $$$l_y, l_x, r_y$$$ and with $$$l_y, r_x, r_y$$$. Then we can assume that $$$\sum\limits_{i\in A}{([c[l_i]=0]+[c[r_i]=0])} = |A|+1$$$ and similarly for $$$B$$$.
The solution to $$$A$$$ before merging is $$$|A|+1$$$, the solution to $$$B$$$ is $$$|B|+1$$$, if we merge $$$A$$$ and $$$B$$$ with a segment we get a component $$$C$$$ of size $$$|A|+|B|+1$$$, and its answer will be $$$|A|+|B|+1+1$$$ (using \bf{lemma 1}), the case with more than two components is similar, then we can always merge the components without making the answer worse.
Finally, the problem in each subarray can be reduced to find the smallest set (in number of segments), such that the union of its segments is the whole subarray. This can be computed with dp or sweep line.
Let $$$dp[x]$$$ be the minimum size of a set such that the union of its segments is the segment $$$[1,x]$$$.
To compute $$$dp$$$, process all the segments in increasing order of $$$r_i$$$, and compute the value of $$$dp[r_i] = \min(dp[l_i+1], dp[l_i+2], ..., dp[r_i-1]) + 1$$$.
Then the solution to the subarray is $$$dp[m] + 1$$$, this $$$dp$$$ can be computed in $$$O(m\log{m})$$$ with segment tree.
It is possible to compute a similar $$$dp$$$ to solve the problem for the whole array without splitting the array, the time complexity is $$$O(n\log{n})$$$.
#include<bits/stdc++.h>
using namespace std;
template <typename Tnode,typename Tup>
struct ST{
vector<Tnode> st;
int sz;
ST(int n){
sz = n;
st.resize(4*n);
}
Tnode merge_(Tnode a, Tnode b){
Tnode c;
/// Merge a and b into c
c = min( a , b );
return c;
}
void update_node(int nod,Tup v){
/// how v affects to st[nod]
st[nod] = v;
}
void build(vector<Tnode> &arr){ build(1,0,sz-1,arr); }
void build(int nod,int l,int r,vector<Tnode> &arr){
if( l == r ){
st[nod] = arr[l];
return;
}
int mi = ( l + r ) >> 1;
build((nod<<1),l,mi,arr);
build((nod<<1)+1,mi+1,r,arr);
st[nod] = merge_( st[(nod<<1)] , st[(nod<<1)+1] );
}
void update(int id,Tup v){ update(1,0,sz-1,id,v); }
void update(int nod,int l,int r,int id,Tup v){
if( l == r ){
update_node(nod,v);
return;
}
int mi = ( l + r ) >> 1;
if( id <= mi ) update((nod<<1),l,mi,id,v);
else update((nod<<1)+1,mi+1,r,id,v);
st[nod] = merge_( st[(nod<<1)] , st[(nod<<1)+1] );
}
Tnode query(int l,int r){ return query(1,0,sz-1,l,r); }
Tnode query(int nod,int l,int r,int x,int y){
if( l >= x && r <= y ) return st[nod];
int mi = ( l + r ) >> 1;
if( y <= mi ) return query((nod<<1),l,mi,x,y);
if( x > mi ) return query((nod<<1)+1,mi+1,r,x,y);
return merge_( query((nod<<1),l,mi,x,y), query((nod<<1)+1,mi+1,r,x,y) );
}
};
int main(){
int n;
cin >> n;
vector<int> a(n), fst(n,-1), lst(n,-1);
for(int i=0; i<n; i++){
cin >> a[i];
a[i] --;
if( fst[a[i]] == -1 )
fst[a[i]] = i;
lst[a[i]] = i;
}
vector<pair<int,int>> segments;
for(int i=0; i<n; i++)
if( fst[i] != -1 )
segments.push_back({lst[i]+1,fst[i]+1});
sort(segments.begin(),segments.end());
vector<int> dp(n+1,1000000007);
dp[0] = 0;
ST<int,int> st(n+1);
st.build(dp);
for( auto i : segments ){
dp[i.first] = min( dp[i.first] , dp[i.second-1] + 1 + ( i.first != i.second ) );
if( i.second + 1 <= i.first - 1 )
dp[i.first] = min( dp[i.first] , st.query(i.second+1,i.first-1) + 1 );
st.update(i.first,dp[i.first]);
}
cout << n - dp[n] << '\n';
return 0;
}
It is possible to create an event where a segment starts and an event where a segment ends.
Then process the events in order and each time a segment ends, if it is the rightmost segment added, add to the solution the segment with maximum $$$r_i$$$ among the segments that $$$l_i$$$ is already processed.
It is possible to modify the sweep line to solve the problem for the whole array without splitting the array, the time complexity is $$$O(n)$$$ or $$$O(n\log{n})$$$ depending on the implementation.
1630D - Flipping Range
Author: humbertoyusta
What is the size of the smallest subarray that it is possible to multiply by $$$-1$$$ using some operations?
Let $$$s$$$ be a string such that $$$s_i=0$$$ if that element is multiplied by $$$-1$$$ or $$$s_i=1$$$ otherwise, what such $$$s$$$ are reachable?
Think about the parity of the sum of all $$$s_i$$$ such that $$$i\mod{g}=constant$$$, where $$$g$$$ is the size of the smallest subarray that it is possible to multiply by $$$-1$$$ using some operations
If we have $$$x, y \in B$$$ (assume $$$x > y$$$), since all elements of $$$B$$$ are at most $$$\lfloor\frac{n}{2}\rfloor$$$, it is possible to multiply all intervals of size $$$x-y$$$ by either multiplying an interval of size $$$x$$$ that starts at the position of the interval of size $$$x-y$$$, and an interval of size $$$y$$$ that ends at the same position as the interval $$$x$$$, or multiply an interval of size $$$x$$$ that ends at the same position as the interval of size $$$x-y$$$ and another interval of size $$$y$$$ that starts at the same position as the interval of size $$$x$$$.
For two elements $$$x, y \in B$$$ ($$$x > y$$$), it is possible to add $$$x-y$$$ to $$$B$$$, repeatedly doing this it is possible to get $$$\gcd(x, y)$$$.
Let $$$g = \gcd(b_1, b_2, ..., b_m : b_i \in B)$$$, by applying the previous reduction $$$g$$$ is the smallest element that can be obtained, and all other elements will be its multiples, then the problem is reduced to, multiplying intervals of size $$$g$$$ by $$$-1$$$ any number of times, maximize $$$\sum\limits_{i=1}^n{a_i}$$$.
Let's define the string $$$s = 000...00$$$ of size $$$n$$$ (0-indexed) such that $$$s_i = 0$$$ if the $$$i$$$-th element is not multiplied by $$$-1$$$ or $$$s_i = 1$$$ otherwise. The operation flips all values of $$$s$$$ in a substring of size $$$g$$$.
Let's define $$$f_x$$$ as the xor over all values $$$s_i$$$ such that $$$i\mod g = x$$$, note that $$$f_x$$$ is defined for the values $$$0 \le x \le g-1$$$.
In any operation, all values of $$$f$$$ change simultaneously, since they are all $$$0$$$ at the beginning only the states of $$$s$$$ such that all $$$f_i$$$ are equal are reachable.
To prove that all states of $$$s$$$ with all $$$f_i$$$ equal are reachable, let's start with any state of $$$s$$$ such that $$$f = 000...00$$$ and repeatedly select the rightmost $$$i$$$ such that $$$s_i=1$$$ and $$$i\geq g-1$$$ and flip the substring that ends in that position, after doing that as many times as possible, $$$s_i = 0$$$ for $$$g-1\leq i\leq n-1$$$. If $$$s_i=1$$$ for any $$$0\leq i < g$$$, then $$$f_i = 1$$$ which is a contradiction since $$$f_{g-1} = 0$$$ and all $$$f_i$$$ change simultaneously, then $$$s = 000...00$$$. The case with all values of $$$f$$$ equal to $$$1$$$ is similar.
After this, it is possible to solve the problem with $$$dp$$$.
Let $$$dp_{i,0}$$$ be the maximum sum of $$$a_i, a_{i-g}, a_{i-2\cdot{g}}, ..., a_{i-k\cdot{g}}$$$ such that $$$i-k\cdot{g}\equiv{i}(\mod{g})$$$ and $$$\bigoplus\limits_{k\geq 0, i-k\cdot g\geq 0} f_{i-k \cdot g}=0$$$ and $$$dp_{i,1}$$$ be the same such that $$$\bigoplus\limits_{k\geq 0, i-k\cdot g\geq 0} f_{i-k \cdot g}=1$$$.
The answer to the problem is $$$\max(\sum\limits_{i=n-g}^{n-1}{dp_{i,0}}, \sum\limits_{i=n-g}^{n-1}{dp_{i,1}} )$$$ (0-indexed).
This $$$dp$$$ can be computed in $$$O(n)$$$.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int T;
cin >> T;
while(T--)
{
int n,m;
cin >> n >> m;
vector<int> a(n),b(m);
for(int i=0;i<n;i++)
cin >> a[i];
int g=0;
for(int i=0;i<m;i++)
{
cin >> b[i];
g=__gcd(g,b[i]);
}
vector<vector<ll>> dp(g,vector<ll>(2));
for(int i=0;i<g;i++)
dp[i][1]=-2e9;
for(int i=0;i<n;i++)
{
int rem=i%g;
ll v0=max(dp[rem][0]+a[i],dp[rem][1]-a[i]);
ll v1=max(dp[rem][0]-a[i],dp[rem][1]+a[i]);
dp[rem][0]=v0;
dp[rem][1]=v1;
}
ll sum0=0,sum1=0;
for(int i=0;i<g;i++)
{
sum0+=dp[i][0];
sum1+=dp[i][1];
}
cout << max(sum0,sum1) << '\n';
}
return 0;
}
1630E - Expected Components
Author: BrayanD
Think about an easy way to count the number of components in a cyclic array.
The number of components in a cyclic array is equal to the number of adjacent positions with different values.
The problem can be solved by applying Burnside's lemma.
The number of different permutations of the cyclic array $$$a$$$ is equal to the sum of number of fixed points for each permutation function divided by the number of permutations functions.
Let's focus on two parts.
First part (find the number of different permutations of $$$a$$$):
Let's define a permutation function $$$F_x(arr)$$$ as the function that cyclically shifts the array $$$arr$$$ by $$$x$$$ positions.
In this problem for an array of size $$$n$$$ we have $$$n$$$ possible permutations functions and we would need to find the sum of the number of fixed points for each permutation function.
To find the number of fixed points for a permutation function $$$F_x()$$$ we have that $$$arr_i$$$ must be equal to $$$arr_{(i+x)\%n}$$$, if we add an edge $$$(i,(i+x)\%n)$$$ for each position $$$i$$$ then by number theory we would obtain that $$$gcd(n,x)$$$ cycles would be formed and each one of size $$$\frac{n}{gcd(n,x)}$$$, then we can note that each position $$$i$$$ will belong to the $$$(i\%gcd(n,x))$$$-th cycle, so we can say that the problem can be transformed into counting the number of permutations with repetition in an array of size $$$gcd(n,x)$$$.
Let us denote $$$cnt[v]$$$ as the number of values equal to $$$v$$$ in array $$$a$$$, when we are processing the function $$$F_x()$$$ and we reduce the problem to an array of size $$$gcd(n,x)$$$ we should also decrease $$$cnt[v]$$$ to $$$\frac{cnt[v]}{n/gcd(n,x)}$$$ since each component is made up of $$$\frac{n}{gcd(n,x)}$$$ values, also we must observe that for solving a problem for an array of size $$$x$$$, then $$$\frac{n}{x}$$$ should be a divisor of $$$gcd(cnt[1],cnt[2],\ldots,cnt[n])$$$.
Let us denote $$$cnt_x[v] = \frac{cnt[v]}{n/gcd(n,x)}$$$
So to count the number of permutations with repetition for $$$F_x()$$$ that can be formed with the frequency array $$$cnt_x$$$ we can use the formula $$$\frac{n!}{x_1! \cdot x_2! \cdot \ldots \cdot x_n!}$$$
Let us denote $$$G_{all} = gcd(cnt[1],cnt[2],\ldots,cnt[n])$$$
Let us denote $$$fdiv(val)$$$ as the number of divisors of $$$val$$$.
Let us denote $$$tot_{sz}$$$ as the number of permutations with repetition for an array of size $$$sz$$$, from what has been said before we have that $$$\frac{n}{sz}$$$ must be divisible by $$$G_{all}$$$ so we only need to calculate the permutations with repetition for $$$fdiv(G_{all})$$$ arrays.
Now suppose that the number of different values of array $$$a$$$ is $$$k$$$ then $$$G_{all}$$$ must be at most $$$\frac{n}{k}$$$ because the gcd of several numbers is always less than or equal to the smallest of them.
Now to calculate the permutations with repetition for a $$$cnt_x$$$ we do it in $$$O(k)$$$, for that we need to precalculate some factorials and modular inverses before, and since we need to calculate them $$$fdiv(G_{all})$$$ times, then we have that in total the complexity would be $$$O(fdiv(G_{all})\cdot k)$$$ but since $$$G_{all}$$$ is at most $$$\frac{n}{k}$$$ and $$$fdiv(\frac{n}{k})$$$ is at most $$$\frac{n}{k}$$$, substituting it would be $$$O(\frac{n}{k}\cdot k)$$$ equal to $$$O(n)$$$
So to find the sum of the number of fixed points we need the sum of $$$tot_{gcd(n,x)}$$$ for $$$1 \le x \le n$$$ and $$$\frac{n}{gcd(n,x)}$$$ divides to $$$G_{all}$$$, at the end of all we divide the sum of the number of fixed points by $$$n$$$ and we would obtain the number of different permutations of $$$a$$$.
To find the $$$gcd(n,x)$$$ for $$$1 \le x \le n$$$ we do it with the Euclid's algorithm in complexity $$$O(n\cdot log)$$$ so in total the complexity is $$$O(n\cdot log)$$$
Second part (find the expected value of components of different permutations of $$$a$$$):
Here we will use the Linear Expectation property and we will focus on calculating the contribution of each component separately, the first thing is to realize that the number of components is equal to the number of different adjacent values, so we only need to focus on two adjacent values, except if it is a single component, this would be a special case. If we have $$$k$$$ different values we can use each different pair of them that in total would be $$$k\cdot(k-1)$$$ pairs, we can realize that when we put a pair its contribution would be equal to the number of ways to permute the remaining values, which if we are in an array of size $$$\frac{n}{x}$$$ and we use the values $$$val_1$$$ and $$$val_2$$$ it would be equal to:
$$$tot_{n/x} \cdot \frac{1}{(n/x)\cdot(n/x-1)} \cdot cnt_x[val_1] \cdot cnt_x[val_2]$$$
because we removing a value $$$val_1$$$ and another value $$$val_2$$$ from the set, so if we have the formula:
$$$\frac{n!}{x_1! \cdot x_2! \cdot \ldots \cdot x_n!}$$$
and $$$val_1$$$ and $$$val_2$$$ are the first two elements then it would be:
$$$\frac{(n-2)!}{(x_1-1)! \cdot (x_2-1)! \cdot \ldots \cdot x_n!}$$$
which would be equivalent to:
$$$\frac{n!}{x_1! \cdot x_2! \cdot \ldots \cdot x_n!} \cdot \frac{1}{n \cdot (n-1)} \cdot x_1 \cdot x_2$$$
Now to calculate the contribution of the $$$k\cdot(k-1)$$$ pairs we can realize that taking common factor $$$tot_{n/x} \cdot \frac{1}{(n/x)\cdot(n/x-1)}$$$ in the previous expression it only remains to find the sum of $$$cnt_x[i]\cdot cnt_x[j]$$$ for all $$$i \neq j$$$, this can be found in $$$O(k)$$$ easily by keeping the prefix sum and doing some multiplication. Then at the end we multiply by $$$n$$$ since there are $$$n$$$ possible pairs of adjacent elements in the general array.
Let us define $$$sum_{sz}$$$ as the contribution of components of the permutations with repetition for an array of size $$$sz$$$, then:
$$$sum_{n/x} = tot_{n/x} \cdot \frac{1}{(n/x)\cdot(n/x-1)} \cdot (sum~of~(cnt_x[i]\cdot cnt_x[j])~for~i \neq j) \cdot n$$$
Now for each possible permutation with repetition we have by the Burnside's lemma that in the end we divide it by $$$n$$$, so we should also divide by $$$n$$$ the contribution of each component.
Let's define $$$tot'_x = \frac{tot_x}{n}$$$ and $$$sum'_x = \frac{sum_x}{n}$$$
Let's define $$$tot_{all}$$$ as the sum of $$$tot'_{gcd(n,x)}$$$ for $$$1 \le x \le n$$$ and $$$\frac{n}{gcd(n,x)}$$$ divide to $$$G_{all}$$$.
Let's define $$$sum_{all}$$$ as the sum of $$$sum'_{gcd(n,x)}$$$ for $$$1 \le x \le n$$$ and $$$\frac{n}{gcd(n,x)}$$$ divide to $$$G_{all}$$$.
The final answer would be:
$$$res = \frac{sum_{all}}{tot_{all}}$$$
The final complexity then is $$$O(n\cdot log)$$$
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 100;
const int MOD = 998244353;
long long fact[MAXN];
long long F[MAXN];
long long qpow(long long a, long long b)
{
long long res = 1;
while(b)
{
if(b&1)res = res*a%MOD;
a = a*a%MOD;
b /= 2;
}
return res;
}
long long inv(long long x)
{
return qpow(x,MOD-2);
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
fact[0] = 1;
for(int i = 1 ; i < MAXN ; i++)
{
fact[i] = fact[i-1]*i%MOD;
}
int T;
cin >> T;
while(T--)
{
int N;
cin >> N;
for(int i = 1 ; i <= N ; i++)
{
F[i] = 0;
}
for(int i = 1 ; i <= N ; i++)
{
int n;
cin >> n;
F[n]++;
}
vector<long long> vvv;
for(int i = 1 ; i <= N ; i++)
{
if(F[i])vvv.push_back(F[i]);
}
int G = 0;
for(auto x : vvv)
{
G = __gcd(G,x);
}
if(G == N)
{
cout << 1 << '\n';
continue;
}
vector<long long> arr(N+1);
vector<long long> arr2(N+1);
for(int i = 1 ; i <= G ; i++)
{
if(G%i == 0)
{
long long tot = inv(fact[N/i-2]), acum = 0, sum = 0;
for(auto x : vvv)
{
tot = tot*fact[x/i]%MOD;
sum = (sum + acum*(x/i)*2)%MOD;
acum = (acum + (x/i))%MOD;
}
tot = inv(tot);
arr2[i] = tot*(N/i-1)%MOD*(N/i)%MOD;
tot = tot*sum%MOD*N%MOD;
arr[i] = tot;
}
}
long long res = 0;
long long cont = 0;
for(int i = 1 ; i <= N ; i++)
{
long long ggg = N/__gcd(N,i);
if(G%ggg == 0)
{
res = (res + arr[ggg])%MOD;
cont = (cont + arr2[ggg])%MOD;
}
}
cout << res*inv(cont)%MOD << '\n';
}
return 0;
}
1630F - Making It Bipartite
Author: BrayanD
Think about the directed graph where there is an directed edge from $$$a$$$ to $$$b$$$ if and only if $$$b|a$$$
Let us define the above graph as $$$G$$$, make a duplicate graph $$$G'$$$ from $$$G$$$, and then add directed edges $$$(x', x)$$$ for each node $$$x'$$$ of the graph $$$G'$$$. What happens in this graph?
Maximum Antichain
First of all, let's analyze what happens when there are $$$3$$$ vertices $$$x$$$, $$$y$$$ and $$$z$$$ such that $$$a_x|a_y$$$, $$$a_x|a_z$$$ and $$$a_y|a_z$$$, if this happens then the graph cannot be bipartite because there would be a cycle of size $$$3$$$, therefore there cannot be such a triple ($$$x$$$, $$$y$$$, $$$z$$$), this condition, besides to being necessary, is sufficient since we can separate the graph into two sets, set $$$A$$$: vertices that have edges towards multiples, set $$$B$$$: vertices that have edges towards divisors, keep in mind that a vertex cannot exist in two sets at the same time if the condition is fulfilled, now note that there are no edges between elements of the same set because if this happens it would mean that they belong to different sets and it would be a contradiction, then the problem is to find the minimum number of vertices to remove such that in the remaining vertices there is no such triple of numbers ($$$x$$$, $$$y$$$, $$$z$$$). Now instead of minimizing the number of vertices to remove, let's try to maximize the number of vertices that will remain in the graph.
Let us define the directed graph $$$G$$$ as the graph formed by $$$n$$$ vertices, and directed edges ($$$u$$$, $$$v$$$) such that $$$a_v|a_u$$$, now the problem is reduced to finding the maximum number of vertices such that in the graph formed among them, no vertex has ingoing edges and outgoing edges at the same time, formally for each vertex $$$x$$$ the following property must be kept $$$indegree_x = 0$$$ or $$$outdegree_x = 0$$$, in this way we guarantee that there is no triple ($$$x$$$, $$$y$$$, $$$z$$$) such that $$$a_x|a_y$$$, $$$a_x|a_z$$$ and $$$a_y|a_z$$$.
Now let's define the graph $$$G'$$$ as a copy of the graph $$$G$$$. Formally for each directed edge ($$$u$$$, $$$v$$$) in the graph $$$G$$$ there is an directed edge ($$$u'$$$, $$$v'$$$) in the graph $$$G'$$$. On the other hand, let's define the graph $$$H = G + G'$$$ and we will also add new directed edges ($$$u'$$$, $$$u$$$), this graph $$$H$$$ is a $$$DAG$$$, it is easy to see that the edges always go from a vertex $$$u$$$ to a vertex $$$v$$$ only if $$$a_u > a_v$$$, except for the edges ($$$u'$$$, $$$u$$$), which in this case $$$a_{u'} = a_u$$$, these edges are the ones that connect $$$G'$$$ to $$$G$$$, but since they always go in one direction pointing towards $$$G$$$, the property of $$$DAG$$$ is still fulfilled.
Now the only thing we have to do is find the largest antichain in the graph $$$H$$$, this can be done using the Dilworth's Theorem, modeling the problem as a bipartite matching, we can use some flow algorithm such as Dinic's Algorithm, or Hopcroft Karp's Algorithm, which is specific to find the maximum bipartite matching.
Proof:
First of all we realize that the graph $$$G$$$ is a special graph since if there is an indirect path from a vertex $$$u$$$ to a vertex $$$v$$$ then there is always a direct edge between them, this is true because if we have $$$3$$$ vertices $$$x$$$, $$$y$$$ and $$$z$$$ such that $$$a_x|a_y$$$ and $$$a_y|a_z$$$ then always $$$a_x|a_z$$$. With this we can say that two elements are not reachable with each other if and only if there are no edges between them. Now let's say that all the vertices in the graph $$$G$$$ are white and all the vertices in the graph $$$G'$$$ are black, let us denote $$$f(x)$$$ a function such that $$$f(u') = u$$$, where the vertex $$$u$$$ from the graph $$$G$$$ is the projection of the vertex $$$u'$$$ from the graph $$$G'$$$. Now let's divide the proof into two parts.
First part:
Lemma 1: Every antichain of $$$H$$$ can be transformed into a valid set of vertices such that they form a bipartite graph.
Proof of Lemma 1: Let's divide the antichain of $$$H$$$ into two sets, white vertices and black vertices, Let us define the set of white vertices as $$$W$$$ and the set of all black vertices as $$$B$$$, now we will create a set $$$S$$$ = {$$$f(x)$$$ | $$$x \in B$$$}. It is easy to see that no element in $$$S$$$ belongs to $$$W$$$ since if this happens it would mean that there is an element $$$x$$$ such that $$$x$$$ belongs to $$$B$$$ and $$$f(x)$$$ belongs to $$$W$$$ and by the concept of antichain that would not be possible. It is also easy to see that the elements of the set $$$S$$$ are an antichain since the set $$$S$$$ is a projection of vertices from the set $$$B$$$ of the graph $$$G'$$$ on $$$G$$$. Now we have that there are no edges between the vertices of the set $$$S$$$ and there are no edges between the vertices of the set $$$W$$$, with this it is proved that the graph is bipartite.
Second part:
Lemma 2: Every valid set of vertices such that they form a bipartite graph can be transformed into an antichain of $$$H$$$.
Proof of Lemma 2: Let us denote $$$f^{-1}(x)$$$ a function such that $$$f^{-1}(u) = u'$$$, where vertex $$$u$$$ from graph $$$G$$$ is the projection of vertex $$$u'$$$ from graph $$$G'$$$. Let us denote the set $$$A$$$ as all vertices that have $$$indegree$$$ greater than $$$0$$$ and $$$B$$$ to all vertices that have $$$outdegree$$$ greater than $$$0$$$, now we will create a set $$$C$$$ = {$$$f^{-1}(x)$$$ | $$$x \in A$$$}, It is easy to see that set $$$B$$$ is an antichain since if one vertex has an edge to another vertex then some of them would have $$$indegree$$$ greater than $$$0$$$ and would contradict the definition of set $$$B$$$, we can also see that the elements in set $$$A$$$ are an antichain since all the elements have $$$outdegree = 0$$$ so no vertex point towards any other vertex, with this we can define that all the elements in $$$C$$$ are an antichain since they are a projection of vertices of the set $$$A$$$ from the graph $$$G$$$ on $$$G'$$$, Now we want to proof that the union of set $$$B$$$ and $$$C$$$ is an antichain, this is very simple to see since the vertices of set $$$B$$$ belong to $$$G$$$ and the vertices of $$$C$$$ belong to $$$G'$$$, therefore there is no edge from any vertex in $$$B$$$ to a vertex in $$$C$$$ since there are no edges from $$$G$$$ to $$$G'$$$. Now it only remains to proof that from set $$$C$$$ no vertex of set $$$B$$$ can be reached, this is proved taking into account that the vertices reachable from the set $$$C$$$ in the graph $$$G$$$ are the same that the vertices reachable from the set $$$A$$$ in the graph $$$G$$$, and as no vertex of $$$A$$$ has edges towards $$$B$$$, this cannot happen. Therefore the union of the sets $$$B$$$ and $$$C$$$ is an antichain of $$$H$$$.
Then we can say that the two problems are equivalent and it is shown that finding the maximum antichain we obtain the largest bipartite graph.
The graph $$$G$$$ contains $$$n$$$ vertices and around $$$n\cdot log(n)$$$ edges (since the numbers $$$a_x$$$ are different and the sum of the divisors from $$$1$$$ to $$$n$$$ is around $$$n\cdot log(n)$$$). The graph $$$G'$$$ is a duplicate of $$$G$$$ then we would have $$$n\cdot log(n)\cdot2 + n$$$ edges and $$$2\cdot n$$$ vertices, if we use the Hopcroft Karp algorithm we would obtain a time complexity of $$$O(n\cdot log(n)\cdot sqrt(n))$$$ and a space complexity of $$$O(n\cdot log(n))$$$.
#include <bits/stdc++.h>
using namespace std;
struct HOPCROFT_KARP
{
int n, m;
vector<vector<int>> adj;
vector<int> mu, mv, level, que;
HOPCROFT_KARP(int n, int m) : n(n), m(m), adj(n), mu(n, -1), mv(m, -1), level(n), que(n) {}
void add_edge(int u, int v)
{
adj[u].push_back(v);
}
void bfs()
{
int qf = 0, qt = 0;
for(int u = 0 ; u < n ; ++u)
{
if(mu[u] == -1)que[qt++] = u, level[u] = 0;
else level[u] = -1;
}
for( ; qf < qt ; ++qf)
{
int u = que[qf];
for(auto w : adj[u])
{
int v = mv[w];
if(v != -1 && level[v] == -1)
que[qt++] = v, level[v] = level[u] + 1;
}
}
}
bool dfs(int u)
{
for(auto w : adj[u])
{
int v = mv[w];
if(v == -1 || (level[v] == level[u] + 1 && dfs(v)))
return mu[u] = w, mv[w] = u, true;
}
return false;
}
int max_matching()
{
int match = 0;
for(int c = 1 ; bfs(), c ; match += c)
for(int u = c = 0 ; u < n ; ++u)
if(mu[u] == -1)
c += dfs(u);
return match;
}
pair<vector<int>, vector<int>> min_vertex_cover()
{
max_matching();
vector<int> L, R, inR(m);
for(int u = 0 ; u < n ; ++u)
{
if(level[u] == -1)L.push_back(u);
else if(mu[u] != -1)inR[mu[u]] = true;
}
for(int v = 0 ; v < m ; ++v)
if(inR[v])R.push_back(v);
return { L, R };
}
};
const int MAXN = 5e4 + 100;
int arr[MAXN];
vector<int> dv[MAXN];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
for(int i = 1 ; i < MAXN ; i++)
{
for(int j = i*2 ; j < MAXN ; j+=i)
{
dv[j].push_back(i);
}
}
for(int i = 0 ; i < MAXN ; i++)
{
arr[i] = -1;
}
int T;
cin >> T;
while(T--)
{
int N;
cin >> N;
vector<int> vect;
for(int i = 0 ; i < N ; i++)
{
int n;
cin >> n;
vect.push_back(n);
arr[n] = i;
}
vector<pair<int,int>> edge;
for(int i = 0 ; i < N ; i++)
{
for(auto x : dv[vect[i]])
{
if(arr[x] != -1)
{
edge.push_back({i, arr[x]});
}
}
}
for(auto x : vect)
{
arr[x] = -1;
}
HOPCROFT_KARP HK(2*N,2*N);
for(auto x : edge)
{
int i = x.first;
int j = x.second;
HK.add_edge(i,j);
HK.add_edge(i+N,j+N);
}
for(int i = 0 ; i < N ; i++)
{
HK.add_edge(i+N,i);
}
cout << HK.max_matching()-N << '\n';
}
return 0;
}
Auto comment: topic has been updated by BrayanD (previous revision, new revision, compare).
Really appreciate writing an editorial with hints. Helps a lot!!
Did you give the proof of
cont
cannot be $$$0$$$ in problem E? What if $$$\mathit{tot}_{\mathit{all}} \equiv 0 \pmod{998244353}$$$?Upd: Thank the authors for replying. It’s just a tiny flaw. I didn’t solve the problem is just because I’m away from training for too long...
Looking forward to a specific case with $$$\mathit{tot}_{\mathit{all}} \equiv 0 \pmod{998244353}$$$, can someone construct such one?
Advertisement: A live recording of me participating this contest (in Chinese, bilibili: BV1kq4y187B4)The statement will be fixed, I added the restriction:
It is guaranteed that the total number of different permutations of $$$a$$$ is not divisible by $$$M$$$
Sorry for that mistake
Yes, there is a case that leads to $$$tot_{all} = 0$$$ (mod 998244353)
30612 ones, 12124 twos, 2 threes
Love this style of editorial! Thanks!!
In case someone is interested, I made video Solutions for A-D(div-2)
Thanks!
I think in 1630C problem it is also easy to calculate 1's, for reference we do everything same , but few ranges are joint , for e.g. (x1, y1) && (x2, y2) such that y1 > x2 and y2 > y1 than we can not paint both y1 and x2 but we can paint 1 of them including every other element in range x1, y2
here is implementation
https://codeforces.net/contest/1631/submission/144258175
My solution for the same 144255745
UPD: The same problem can be done using two pointers with better TC. Solution using two pointers 144364659
This is exactly what two pointers does in O(n) time :)
Yeah got that idea later.
thanks I was getting confused with editorial
Problem D was really cool problem. I have solved it with segment tree. link
This contest was:- Operationoforces :)
How to solve D1A/D2C without the
k<=n-1
constraint ?Notice that $$$a_i \oplus b_i = a_i + b_i - 2 \cdot (a_i \& b_i)$$$, where $$$\oplus$$$ denotes bitwise xor, which is much nicer for pair-wise budgeting than bitwise and. Thus, in any solution, $$$ \sum_{i=1}^{n/2}{a_i \oplus b_i} = \binom{n}{2} - 2 \cdot k$$$. The bitwise xor of each pair is between $$$1$$$ and $$$n-1$$$, so we may reject if this sum is not between $$$n/2$$$ and $$$n/2 \times (n - 1)$$$. Otherwise, a solution always exists.
You can construct one by starting from a pairing that matches every $$$x$$$ to $$$x \oplus C$$$ for some fixed $$$C$$$ and tweaking it at some small number of pairs, similar to what the main editorial does for $$$k < n - 1$$$. The simplest tweak is to mess with exactly two pairs. This can be done by, for example, pairing $$$(0,x)$$$ and $$$(C, x \oplus C)$$$, with a resulting total xor of $$$(n/2 - 2) \cdot C + 2 \cdot x$$$. It's easy enough to see that there always exists at least one working choice of $$$C$$$ and $$$x$$$, but an explicit formula seems a bit messy. My code just brute-forces all possible options: 144268260
I really liked the problem 1631C - And Matching, but I think the constructive solution shown in editorial is a bit overly complicated. My solution is similiar, but I don't really need to handle that many cases (it's only necessary to check if a number hasn't been already used).
Let's look at the binary representation of $$$k$$$ (as an example, let's say that $$$k = 1001101$$$). Let's look at the set of set bits ("set of set bits" sounds funny, doesn't it?) $$$\lbrace b_1, b_2, b_3, \cdots, b_x \rbrace$$$, for our example it's $$$\lbrace 0, 2, 3, 6 \rbrace$$$ (0-indexed and counting from right). Now we will iterate through this set: we are at index $$$i$$$ which corresponds to $$$b_{i}$$$-th bit set. We will match ($$$2^{b_{i}}$$$, $$$(n-1)\oplus{2^{b_{i-1}}}$$$) (for $$$i=0$$$ we will simply match with $$$n-1$$$). After the last iteration we have to match ($$$(n-1)\oplus{2^{b_x}}$$$, $$$0$$$), Each time we do that we have to check if none of the numbers were used before. Up to this point, all the pairs we have made sum to $$$k$$$ so we need to make sure all other pairs we need to make are zero. We can iterate $$$i=1 \cdots n-1$$$ and check if the $$$i$$$ we are currently at hasn't been already paired before, if not let's pair it with $$$(n-1)\oplus{i}$$$. It's easy to show that pairs formed this way will all sum have their bitwise AND equal to $$$0$$$.
The question is, why does this work? Well, we can easily see that if $$$n$$$ is a power of $$$2$$$ then each number from $$$0, 1, 2, \cdots, n-1$$$ will have unique XOR with $$$n-1$$$ (if there are 2 different numbers $$$x, y$$$ then there is atleast 1 bit where they differ, which shows that $$$x\oplus{(n-1)} \neq y\oplus{(n-1)}$$$.
The problem might come with numbers with their representation like $$$111011$$$ becuase in order to $$$0$$$ the pair, we need to use some power of $$$2$$$ which could have already been used. This is easily solved by pairing ($$$2^{b_i}$$$, $$$(n-1)\oplus{2^{b_{i-1}}}$$$), because the number is already paired and the bitwise AND is still equal to $$$2^{b_i}$$$.
Note: If in the first process any number repeats and we need to use it more than once, the answer is $$$-1$$$.
144240803
I solved it the same way. In simpler terms: match $$$i$$$ with $$$n-1-i$$$, and then 'shift' the positions of $$$ 0, b_1, b_2, ... b_x $$$. This will make the sum $$$k$$$, except when two of them are already matched with each other. It can be proven that this only happens when $$$n=4$$$ and $$$k=3$$$.
In the solution of 2D/1B: $$$[x\le a_i\le y]$$$
What is the name of this square bracket expression? It seems to me that $$$[\text{true}] = 1$$$ and $$$[\text{false}] = 0$$$.
Edit: Iverson bracket
..
You misread the problem. You need to assign the value $$$a_{l+k+i}$$$ to $$$a_{l+i}$$$, not the other way around.
What's wrong with: 144271690
Idea 1: If we have two intervals, one of which contains the other, then remove the smaller interval.
Idea 2: If we have three intervals which mutally intersect, then remove the middle one.
Failing test case
Thanks for the help. I've updated the submission now: 144343029, and the stress tester can no longer find a counterexample, unfortunately.
Reminder that multiple (N) gcd calls over the same variable works in O(log(A) + N) where A is the first number greater than 0 set to it.
So div1E's complexity is wrong. Edit: not wrong but there's a lower bound :)
In problem D1E, we need $$$gcd(n,x)$$$ for all $$$x$$$ independently. So we need to call $$$n$$$ times the $$$gcd$$$ function
True, let's fix that: let's say x = p * y for some prime p that divides x. gcd(x, n) is gcd(y * p, n) which is either gcd(y, n) or gcd(y, n) * p. Do dp[x] = gcd(x, n), check those 2 cases separately and preprocess some prime for every number. Is there any other part higher than O(N)?
Well, that's interesting. In fact, I had a O(N) solution using euler phi function, but O(N*log) solution was easier to explain. Anyways, your idea is good, and yes, it is O(N) in total.
In fact, just the editorial is O(N), I just was too sleepy to realize:
sum log(a[i]) <= sum a[i] == N so sum log(a[i]) is O(N) where a[i] is the frequency of i
This is the part of more complexity, are you sure that it is O(N)?
No, that's O(NlogN). I guess I went by too quickly through that part of the editorial (because I didn't want to completely spoil the idea).
With that code it's clear that
for(d divisor of N) if(G % (N / d) == 0 or something like this) res += arr[d] * phi(d), cont += arr2[d] * phi(d)
is equivalent and another way to optimize the complexity.
Yes, that was my idea with euler phi function. You can precalculate all phi numbers until N in complexity O(N), or maybe factorize N and do something
nice round
For Div.2 Problem D, my first intuition is to enumerate x, and for each x use binary search to find the best y.
The problem is that if we naively implement the predicate
ok
by traversing the given array, it will be of O(n) time and the overall time will be O(n^2 log(n)), which is hopeless.One important intuition to optimize it is to sort the given array and implement an
ok
in O(log(n)) time (in other words, for determining the feasibility of a range [x, y], the order of the given array doesn't matter). Then the overall time becomes O(n (log(n))^2), which is good.During the contest I only came up with the O(n) implementation of the predicate
ok
, and I was even thinking about whether there are some kinds of "2D binary search" to eliminate the outmost enumeration ofx
, but I didn't succeed in that direction.Div1 B can be solved using two pointers on $$$x$$$ and $$$y$$$ with a fenwick tree. Replacing all elements in the range $$$[x,y]$$$ with $$$1$$$ and those not in the range with $$$-1$$$, the partition can be made if the sum of all elements is at least $$$k$$$.
Submission — https://codeforces.net/contest/1630/submission/144278138
Even a fenwick ree is not needed since only the sum of all elements is needed
Submission — https://codeforces.net/contest/1630/submission/144278658
I had a different solution to 1630C - Paint the Middle, which I think was very simple and clean (I wrote 5-10 lines of code without any complex expressions, branching, or sorting events/intervals).
The idea is to define a DP array $$$f(i)$$$ = maximum answer for the subarray $$$[0, i]$$$, assuming $$$0$$$-indexing. Therefore, $$$f(0) = 0$$$ and $$$f(n-1) = \textit{ans}$$$. Note that $$$f(i)$$$ never involves coloring $$$a_i$$$, because it's impossible to color either endpoint of your array.
Let's consider our choices for different ways to get candidate values of $$$f(i)$$$, assuming we know the previous values of $$$f$$$.
Option 1: $$$a_i$$$ has a previous occurrence at index $$$j < i$$$. We can perform the optimal solution for $$$[0, j]$$$, then color the $$$(i-j-1)$$$ elements strictly between $$$a_j$$$ and $$$a_i$$$, giving us a score of $$$f(j) + (i-j-1)$$$.
Option 2: If there is an instance of $$$a_i$$$ at some index $$$k$$$ such that $$$k < j < i$$$, so we can perform the optimal solution for $$$[0, j]$$$ except for leaving $$$a_k$$$ untouched, then color the remaining elements between $$$a_j$$$ (inclusive) and $$$a_i$$$ (exclusive), using the fact that $$$a_k = a_i$$$. This gives us a score of $$$(f(j)-1) + (i-j)$$$, which is the same expression as in the previous paragraph.
Option 3: We can always ignore the last element, giving us a score of $$$f(i-1)$$$. This can be creatively re-written as the same expression as before: $$$f(i-1) + (i - (i-1) - 1)$$$.
Therefore, we have the following simple quadratic DP: $$$f(i) = \max_j \left[f(j) + (i - j - 1)\right]$$$, for $$$j$$$ such that either $$$\text{first}(a_i) \le j < i$$$ or $$$j = i-1$$$. Equivalently, $$$\min(\text{first}(a_i), i-1) \le j < i$$$.
In order to optimize this, we make the following rearrangement: $$$f(i) - i = -1 + \max_j \left[f(j) - j\right]$$$.
Setting $$$g(i) = f(i) - i$$$ gives us $$$g(i) = -1 + \max_j [ g(j) ]$$$. This can be very easily implemented using a segment tree to compute $$$\max_j [g(j)]$$$, and our answer is $$$f(n-1) = g(n-1) + (n-1)$$$.
You can read my full submission (including IO and templates) here: 144275521
Thanks!!! Feeling confused when trying to read the official editorial
I am confused about your Option 2: for first(i)<j<i, why can we always assume that the optimal coloring of j always includes coloring first(i)? Or why it won't be the optimal coloring for i if using a j whose optimal coloring don't include coloring first(i)?
This is the best editorial writtern in the history of codeforces , thanks a lot
hello BrayanD in problem And Matching Constructive approach (easier) The code of this approach in Case 2 : ( k > 0 && k < n — 1 ) if condition ( i != 0 || i != small_k ) should be ( i != 0 && i != small_k )
In fact, I think that the condition is not important. It can be removed. Anyways, I fixed the solution code. Thanks for noticing it and telling me.
Can someone explain me B , I couldnt get it
Could anyone explain solution of Div1 C ?
Can anyone hack my code for div1 problem C? I'm failed in test 3 but I don't know what's wrong.
Ah..I see what's wrong with me
There is another easier (as I consider) solution for Div1 D.
Let's look throw elements with position $$$x \pmod g$$$. If there are even number of elements $$$a_i < 0$$$ — we can make all elements $$$\geqslant 0$$$. And if there are odd number — we can make all elements $$$\geqslant 0$$$ except 1, any of them.
Ok, let's the first set will be remainders $$$\pmod g$$$ with even number of negative elements and the second set — remainders with odd number of them.
And it turns out, that the optimal set of negative elements in the final answer — the 1 element with minimum module from every remainders of the first set or from every remainders of the second set.
The solution with very simple code. 144363709
can you please explain intution behind this approach.
Ok, when we invert the segment — we change (parity of negative elements) of each remainder. (If some of these elements are $$$0$$$, let's imagine, that they will be $$$-0$$$ now: it doesn't really matter).
And the second thought — we can invert any two elements at a distance $$$g$$$. Because we can invert $$$[x, x+g-1]$$$ and $$$[x+1, x+g]$$$. And, of course, we can start to repeat it: $$$(x, x+g)$$$ and $$$(x+g, x+2g)$$$ will turn into $$$(x, x+2g)$$$ and so on.
Finally, we can invert any of pair elements with the same remainder $$$\pmod g$$$. And from here my solution quickly follows :)
Div. 1 D is a harder version of https://atcoder.jp/contests/abc125/tasks/abc125_d. I started with the idea in the first official solution for that problem and ended up with exactly the same solution presented here.
For Div2 C, I got the first 2 cases, but the third case was tricky
Can someone help me with my code div2 problem E . I'm stuck at test case 3 (wrong answer). Although I think my algorithm is correct.
include <bits/stdc++.h> using namespace std; define ll long long define lld long double define ff first define ss second define pb push_back define mp make_pair define fl(i,n) for(int i=0;i<n;i++) define rl(i,m,n) for(int i=n;i>=m;i--) define pi 3.141592653589793238 define vr(v) v.begin(),v.end() define rv(v) v.end(),v.begin() define Code ios_base::sync_with_stdio(false); define By cin.tie(NULL); define Asquare cout.tie(NULL);
ll gcd(ll a, ll b){if (b == 0)return a;return gcd(b, a % b);} ll lcm(ll a, ll b){return (a/gcd(a,b)*b);} bool sorta(const pair<int,int> &a,const pair<int,int> &b){return (a.second < b.second);} bool sortd(const pair<int,int> &a,const pair<int,int> &b){return (a.second > b.second);} void printarr(ll arr[], ll n){fl(i,n) cout << arr[i] <<endl;} ll binaryToDecimal(string n){string num = n;ll dec_value = 0;int base = 1;int len = num.length();for(int i = len — 1; i >= 0; i--){if (num[i] == '1')dec_value += base;base = base * 2;}return dec_value;} bool isPrime(ll n){if(n<=1)return false;if(n<=3)return true;if(n%2==0||n%3==0)return false;for(int i=5;i*i<=n;i=i+6)if(n%i==0||n%(i+2)==0)return false;return true;} bool isPowerOfTwo(int n){if(n==0)return false;return (ceil(log2(n)) == floor(log2(n)));} bool isPerfectSquare(ll x){if (x >= 0) {ll sr = sqrt(x);return (sr * sr == x);}return false;} ll moduloMultiplication(ll a,ll b,ll mod){ll res = 0;a %= mod;while (b){if (b & 1)res = (res + a) % mod;b >>= 1;}return res;} ll powermod(ll x, ll y, ll p){ll res = 1;x = x % p;if (x == 0) return 0;while (y > 0){if (y & 1)res = (res*x) % p;y = y>>1;x = (x*x) % p;}return res;}
int main() { ll n; cin>>n; vector v; ll x;
fl(i,n) { cin>>x; v.pb(x); }
unordered_map<ll,ll > m; vector<pair<ll,ll> > vec;
ll u=1;
fl(i,n) { if(m[v[i]]==0) { m[v[i]]=u; vec.pb(mp(i+1,0)); u++; } else { vec[m[v[i]]-1]=mp(vec[m[v[i]]-1].first,i+1); } }
ll le=vec.size();
// fl(i,le) // cout<<vec[i].ff<<" "<<vec[i].ss<<endl; // cout<<"xxx"<<endl;
vector<pair<ll,ll> > l; ll r=0; for(;r<le;r++) { if(vec[r].second!=0) { l.pb(vec[r]);r++;break;} }
// cout<<"r"<<r<<endl; ll j=0; for(ll i=r;i<le;i++) { if(vec[i].second!=0) { if(vec[i].first> l[j].second) { l.pb(vec[i]); j++; } else if(vec[i].second>l[j].second) {
l[j]=mp(l[j].first,vec[i].ss); } } }
ll len=l.size();
// fl(i,len) // cout<<l[i].ff<<" "<<l[i].ss<<endl;
ll count=0;
fl(i,len) { if(v[l[i].first-1]==v[l[i].second-1]) { count+=l[i].second-1-l[i].first; } else { count+=l[i].second-1-l[i].first-1; } } cout<<count;
}
Nice editorial! Appreciate it!!
Nice editorial, If anyone wants video editorial for problem DIV 2D
Link
1630-D is really an impressive problem!!
Here is a solution to D2C/D1A — AND Matching that works for arbitrary $$$k$$$ values in $$$O(n \cdot logn)$$$ without any casework or brute force.
It's easy to prove that we can reach the maximum possible $$$k$$$ value for $$$n$$$ by pairing $$$0$$$ with $$$1$$$, $$$2$$$ with $$$3$$$ and so on. After constructing this case, we can decrease the sum by $$$2^n$$$ (where $$$n \geq 1$$$) by swapping $$$x$$$ with $$$x ⨁ 2^n$$$. Of course, we have to take care not to swap pairs of elements that were already swapped before. If $$$k$$$ is odd, we can finally increase the sum by $$$1$$$ by swapping $$$0$$$ and $$$1$$$.
I made a mistake, I'm sorry.