I hope you all liked the round. Please share your feedback in the comments section.
1747A — Two Groups
How about putting all positive numbers in one group and negative in second group
Let $$$S$$$ denotes sum of element of array $$$a$$$.
Claim: Answer is $$$|S|$$$.
Proof: Let sum of all positive elements is $$$S_{pos}$$$ and sum of all negative elements $$$S_{neg}$$$. Put all positive numbers in first group and negative numbers in second group. We get $$$||S_{pos}| - |S_{neg}|| = |S|$$$.
Let's prove that we can not do better than that. Let $$$S_1$$$ denotes sum of elements of first group and $$$S_2$$$ denotes sum of elements of second group. We have $$$|S_1| - |S_2| \leq |S_1 + S_2| = |S|$$$. Hence $$$|S|$$$ is the upperbound for the answer.
// Jai Shree Ram
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define ll long long
#define int long long
#define pb push_back
#define all(v) v.begin(),v.end()
#define endl "\n"
#define x first
#define y second
#define gcd(a,b) __gcd(a,b)
#define mem1(a) memset(a,-1,sizeof(a))
#define mem0(a) memset(a,0,sizeof(a))
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define hell 1000000007
#define elasped_time 1.0 * clock() / CLOCKS_PER_SEC
template<typename T1,typename T2>istream& operator>>(istream& in,pair<T1,T2> &a){in>>a.x>>a.y;return in;}
template<typename T1,typename T2>ostream& operator<<(ostream& out,pair<T1,T2> a){out<<a.x<<" "<<a.y;return out;}
template<typename T,typename T1>T maxs(T &a,T1 b){if(b>a)a=b;return a;}
template<typename T,typename T1>T mins(T &a,T1 b){if(b<a)a=b;return a;}
int solve(){
int n; cin >> n;
int s = 0;
for(int i = 0; i < n; i++){
int x; cin >> x;
s += x;
}
cout << abs(s) << endl;
return 0;
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#ifdef SIEVE
sieve();
#endif
#ifdef NCR
init();
#endif
int t=1;cin>>t;
while(t--){
solve();
}
return 0;
}
1747B — BAN BAN
Instead of subsequences solve for substrings. That is there should not be any substring $$$\texttt{BAN}$$$ after performing operations.
In one operation you can destroy atmost $$$2$$$ substrings. Find minimum operations to destroy $$$n$$$ substrings.
$$$\left \lceil\frac{n}{2}\right \rceil $$$
Congrats, you have solved for subsequences also!
No subsequences of string $$$\texttt{BAN}$$$ would also mean no substrings of $$$\texttt{BAN}$$$ in original string. Let minimum number of operations to have no substrings of $$$\texttt{BAN}$$$ be $$$x$$$, it would be also be the lower bound for having no subsequences of string $$$\texttt{BAN}$$$.
Claim: $$$x = \left \lceil\frac{n}{2}\right \rceil$$$.
Proof: Swap $$$i$$$-th $$$\texttt{B}$$$ from start with $$$i$$$-th $$$\texttt{N}$$$ from end for $$$1 \leq i \leq \left \lceil\frac{n}{2}\right \rceil$$$. We can see that, no substrings of $$$\texttt{BAN}$$$ exists after performing $$$ \left \lceil\frac{n}{2}\right \rceil$$$ operations. Since we can only destroy atmost $$$2$$$ substrings in one operations, $$$\left \lceil\frac{n}{2}\right \rceil$$$ is minimum possible.
Now if you see clearly, after performing above operations, there does not exist any subsequence of string $$$\texttt{BAN}$$$ in original string. Hence $$$\left \lceil\frac{n}{2}\right \rceil$$$ is also the answer for the original problem.
// Jai Shree Ram
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define ll long long
#define int long long
#define pb push_back
#define all(v) v.begin(),v.end()
#define endl "\n"
#define x first
#define y second
#define gcd(a,b) __gcd(a,b)
#define mem1(a) memset(a,-1,sizeof(a))
#define mem0(a) memset(a,0,sizeof(a))
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define hell 1000000007
#define elasped_time 1.0 * clock() / CLOCKS_PER_SEC
template<typename T1,typename T2>istream& operator>>(istream& in,pair<T1,T2> &a){in>>a.x>>a.y;return in;}
template<typename T1,typename T2>ostream& operator<<(ostream& out,pair<T1,T2> a){out<<a.x<<" "<<a.y;return out;}
template<typename T,typename T1>T maxs(T &a,T1 b){if(b>a)a=b;return a;}
template<typename T,typename T1>T mins(T &a,T1 b){if(b<a)a=b;return a;}
int solve(){
int n; cin >> n;
cout << n/2 + n % 2 << endl;
int l = 1, r = 3*n;
while(l < r){
cout << l << " " << r << endl;
l += 3;
r -= 3;
}
return 0;
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#ifdef SIEVE
sieve();
#endif
#ifdef NCR
init();
#endif
int t=1;cin>>t;
while(t--){
solve();
}
return 0;
}
1747C — Swap Game
Divide problem into two different cases. When $$$a_1 \gt \min(a)$$$ and when $$$a_1 = \min(a)$$$.
You do not need more hints to solve the problem.
Case 1: $$$a_1 \gt \min(a)$$$
$$$\texttt{Alice}$$$ can force the $$$\texttt{Bob}$$$ to always decrease the minimum element by always choosing minimum element of $$$a$$$ in her turn. Where as $$$\texttt{Bob}$$$ can not do much, all other elements he would swap with would be greater than or equal to $$$\min(a)$$$. Even if there exists multiple minimums in $$$a$$$, In first move $$$\texttt{Alice}$$$ would decrease from $$$a_1$$$, hence in this case $$$\texttt{Alice}$$$ would always win.
Case 2: $$$a_1 = \min(a)$$$
In this case optimal startegy for $$$\texttt{Bob}$$$ would be to always chhose minimum element of the array, which is $$$a_1$$$. $$$\texttt{Alice}$$$ would always be swapping the element greater than $$$a_1$$$ in her turn, hence in the case $$$\texttt{Bob}$$$ would always win
// Jai Shree Ram
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define ll long long
#define int long long
#define pb push_back
#define all(v) v.begin(),v.end()
#define endl "\n"
#define x first
#define y second
#define gcd(a,b) __gcd(a,b)
#define mem1(a) memset(a,-1,sizeof(a))
#define mem0(a) memset(a,0,sizeof(a))
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define hell 1000000007
#define elasped_time 1.0 * clock() / CLOCKS_PER_SEC
template<typename T1,typename T2>istream& operator>>(istream& in,pair<T1,T2> &a){in>>a.x>>a.y;return in;}
template<typename T1,typename T2>ostream& operator<<(ostream& out,pair<T1,T2> a){out<<a.x<<" "<<a.y;return out;}
template<typename T,typename T1>T maxs(T &a,T1 b){if(b>a)a=b;return a;}
template<typename T,typename T1>T mins(T &a,T1 b){if(b<a)a=b;return a;}
int solve(){
int n; cin >> n;
vector<int> a(n);
for(auto &i:a)cin >> i;
sort(a.begin() + 1,a.end());
cout << (a[0] > a[1] ? "Alice" : "Bob") << endl;
return 0;
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#ifdef SIEVE
sieve();
#endif
#ifdef NCR
init();
#endif
int t=1;cin>>t;
while(t--){
solve();
}
return 0;
}
1747D — Yet another Problem
Forget queries, they are just here to make problem look complicated. Solve for $$$q = 1$$$.
XOR of array does not change after operations. Hence if initially XOR is not equal to $$$0$$$, answer is $$$-1$$$. Is this condition sufficient?
No, We need one more condition
There must exist some prefix of odd size, such that xor of elements of that prefix is $$$0$$$.
First forget queries, solve for single array $$$a$$$.
Let's make some observations.
Xor of array does not change after each operation
Look at the set of prefix XORs while doing operations. Its size always decreases or remains same after each operation. Infact we can further reduce it to parities. Let $$$S_{0}$$$, $$$S_{1}$$$ be sets of prefix XOR's of parities $$$0$$$ and $$$1$$$ respectively. After each operation new sets $$$S'_{0}$$$, $$$S'_{1}$$$ will be subsets of $$$S_{0}$$$ and $$$S_1$$$ respectively.
So necessary conditions for answer to exist is that xor of array should be $$$0$$$ and $$$S_{1}$$$ should contains $$$0$$$.
Now comes to minimum operations.
Claim: If above conditions are satisfied, its always possible to make all elements $$$0$$$ in less than or equal to $$$2$$$ operations
Proof: Let length of array be $$$n$$$.
Case 1: $$$n$$$ is odd
Just apply the operation on whole array.
Case 2: $$$n$$$ is even
There will exists some odd size prefix $$$j$$$ such that xor of its elements is $$$0$$$. Apply operation on $$$[1,j]$$$ and $$$[j + 1,n]$$$. It can happen that $$$j = 1$$$ or $$$j = n - 1$$$, in that case we only need one operation, because other remaining element would already be equal to $$$0$$$.
To solve for queries, you just need to check for odd prefix, which can be done using some data structure like $$$\texttt{std::map}$$$ or $$$\texttt{std::set}$$$ in C++. Do not forget to check the case when all elements are already $$$0$$$.
#include<bits/stdc++.h>
using namespace std ;
#define ll long long
#define pb push_back
#define all(v) v.begin(),v.end()
#define sz(a) (ll)a.size()
#define F first
#define S second
#define INF 2000000000000000000
#define popcount(x) __builtin_popcountll(x)
#define pll pair<ll,ll>
#define pii pair<int,int>
#define ld long double
template<typename T, typename U> static inline void amin(T &x, U y){ if(y < x) x = y; }
template<typename T, typename U> static inline void amax(T &x, U y){ if(x < y) x = y; }
#ifdef LOCAL
#define debug(...) debug_out(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) 3000
#endif
int _runtimeTerror_()
{
int n, Q;
cin >> n >> Q;
map<int, int> odd, even;
vector<int> last_nz(n + 1, 0), last(n + 1, -1), pxor(n + 1, 0);
vector<int> a(n + 1);
even[0] = 0;
int cur = 0;
for(int i=1;i<=n;++i) {
cin >> a[i];
cur ^= a[i];
pxor[i] = cur;
if(a[i] == 0) {
last_nz[i] = last_nz[i - 1];
}
else {
last_nz[i] = i;
}
if(i & 1) {
if(even.count(cur)) {
last[i] = even[cur];
}
odd[cur] = i;
}
else {
if(odd.count(cur)) {
last[i] = odd[cur];
}
even[cur] = i;
}
}
while(Q--) {
int l, r;
cin >> l >> r;
if(pxor[l - 1] != pxor[r]) {
cout << "-1\n";
}
else if(last_nz[r] < l) {
cout << "0\n";
}
else if(r % 2 == l % 2) {
cout << "1\n";
}
else if(a[l] == 0 or a[r] == 0) {
cout << "1\n";
}
else if(last[r] >= l) {
cout << "2\n";
}
else {
cout << "-1\n";
}
}
return 0;
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifdef runSieve
sieve();
#endif
#ifdef NCR
initncr();
#endif
int TESTS = 1;
//cin >> TESTS;
while(TESTS--) {
_runtimeTerror_();
}
return 0;
}
1747E — List Generation
Change your point of view from array to grid. Think of pair of arrays as paths in grid of size $$$(n + 1) \times (m + 1)$$$.
First try counting number of good pair of arrays.
Number of good pairs of arrays comes out to be $$$\sum\limits_{k = 0}{k = \min(n,m} \binom{n}{k} \cdot \binom{m}{k} \cdot 2^{n + m - k - 1}$$$
Given problem is equivalent to:
You are currently at cell $$$(0,0)$$$. From any cell $$$(x,y)$$$ you can jump to cell $$$(x',y')$$$ such that $$$x \leq x' \leq n$$$ , $$$y \leq y' \leq m$$$ and $$$(x,y) \neq (x',y')$$$. Find sum of number of visited cells over all paths starting from $$$(0,0)$$$ and ending at $$$(n,m)$$$. Denote the required value by $$$f(n,m)$$$.
Directly thinking in $$$2$$$ dimensions is difficult, lets first solve for case when $$$n = 0$$$ or $$$m = 0$$$. WLOG, assuming $$$m = 0$$$. We can solve this case using some binomials.
$$$f(n,0) = 2^{n - 1} \cdot \frac{n + 3}{2}$$$, $$$n \gt 0$$$.
Now, we can divide all possible paths from $$$(0,0)$$$ to $$$(n,m)$$$ into several classes of one dimensional paths.
These classes are defined by what I call breakpoints. When we passes the breakpoint we turns right. Hence we can group paths by fixing the number of breakpoints.
WLOG, Assuming $$$n \geq m$$$. For $$$k$$$ breakpoints there are $$$\binom{n}{k} \cdot \binom{m}{k}$$$ ways to select for $$$0 \leq k \leq m $$$. For a path with $$$k$$$ breakpoints, $$$n + m - k$$$ points are optional, that is there will exist $$$2^{n + m - k}$$$ paths with $$$k$$$ breakpoints. It is not difficult to see that sum of number of visited cells over paths with $$$k$$$ breakpoints turned out to be $$$f(n + m - k,0) + 2^{n + m - k - 1}\cdot k$$$. Hence we can write $$$f(n,m) = \sum\limits_{k = 0}^{m} \binom{n}{k} \cdot \binom{m}{k} \cdot (f(n + m - k,0) + 2^{n + m - k - 1}\cdot k)$$$
Time complexity of the solution would be $$$\mathcal{O}(\min(n,m))$$$
// Jai Shree Ram
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define ll long long
#define int long long
#define pb push_back
#define all(v) v.begin(),v.end()
#define endl "\n"
#define x first
#define y second
#define gcd(a,b) __gcd(a,b)
#define mem1(a) memset(a,-1,sizeof(a))
#define mem0(a) memset(a,0,sizeof(a))
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define hell 1000000007
#define elasped_time 1.0 * clock() / CLOCKS_PER_SEC
template<typename T1,typename T2>istream& operator>>(istream& in,pair<T1,T2> &a){in>>a.x>>a.y;return in;}
template<typename T1,typename T2>ostream& operator<<(ostream& out,pair<T1,T2> a){out<<a.x<<" "<<a.y;return out;}
template<typename T,typename T1>T maxs(T &a,T1 b){if(b>a)a=b;return a;}
template<typename T,typename T1>T mins(T &a,T1 b){if(b<a)a=b;return a;}
const int MOD = hell;
struct mod_int {
int val;
mod_int(long long v = 0) {
if (v < 0)
v = v % MOD + MOD;
if (v >= MOD)
v %= MOD;
val = v;
}
static int mod_inv(int a, int m = MOD) {
int g = m, r = a, x = 0, y = 1;
while (r != 0) {
int q = g / r;
g %= r; swap(g, r);
x -= q * y; swap(x, y);
}
return x < 0 ? x + m : x;
}
explicit operator int() const {
return val;
}
mod_int& operator+=(const mod_int &other) {
val += other.val;
if (val >= MOD) val -= MOD;
return *this;
}
mod_int& operator-=(const mod_int &other) {
val -= other.val;
if (val < 0) val += MOD;
return *this;
}
static unsigned fast_mod(uint64_t x, unsigned m = MOD) {
#if !defined(_WIN32) || defined(_WIN64)
return x % m;
#endif
unsigned x_high = x >> 32, x_low = (unsigned) x;
unsigned quot, rem;
asm("divl %4\n"
: "=a" (quot), "=d" (rem)
: "d" (x_high), "a" (x_low), "r" (m));
return rem;
}
mod_int& operator*=(const mod_int &other) {
val = fast_mod((uint64_t) val * other.val);
return *this;
}
mod_int& operator/=(const mod_int &other) {
return *this *= other.inv();
}
friend mod_int operator+(const mod_int &a, const mod_int &b) { return mod_int(a) += b; }
friend mod_int operator-(const mod_int &a, const mod_int &b) { return mod_int(a) -= b; }
friend mod_int operator*(const mod_int &a, const mod_int &b) { return mod_int(a) *= b; }
friend mod_int operator/(const mod_int &a, const mod_int &b) { return mod_int(a) /= b; }
mod_int& operator++() {
val = val == MOD - 1 ? 0 : val + 1;
return *this;
}
mod_int& operator--() {
val = val == 0 ? MOD - 1 : val - 1;
return *this;
}
mod_int operator++(int32_t) { mod_int before = *this; ++*this; return before; }
mod_int operator--(int32_t) { mod_int before = *this; --*this; return before; }
mod_int operator-() const {
return val == 0 ? 0 : MOD - val;
}
bool operator==(const mod_int &other) const { return val == other.val; }
bool operator!=(const mod_int &other) const { return val != other.val; }
mod_int inv() const {
return mod_inv(val);
}
mod_int pow(long long p) const {
assert(p >= 0);
mod_int a = *this, result = 1;
while (p > 0) {
if (p & 1)
result *= a;
a *= a;
p >>= 1;
}
return result;
}
friend ostream& operator<<(ostream &stream, const mod_int &m) {
return stream << m.val;
}
friend istream& operator >> (istream &stream, mod_int &m) {
return stream>>m.val;
}
};
#define NCR
const int N = 5e6 + 5;
mod_int fact[N],inv[N],invv[N];
void init(int n=N){
fact[0]=inv[0]=inv[1]=1;
invv[0] = invv[1] = 1;
rep(i,1,N)fact[i]=i*fact[i-1];
rep(i,2,N){
invv[i] = (MOD - MOD/i)*invv[MOD % i];
inv[i] = invv[i]*inv[i - 1];
}
}
mod_int C(int n,int r){
if(r>n || r<0)return 0;
return fact[n]*inv[n-r]*inv[r];
}
int solve(){
int n,m; cin >> n >> m;
if(m > n)swap(n,m);
auto brute = [&](){
vector<vector<mod_int>>dp(n + 1,vector<mod_int>(m + 1));
vector<vector<mod_int>>exp(n + 1,vector<mod_int>(m + 1));
dp[0][0] = 1;
exp[0][0] = 0;
for(int i = 0; i <= n; i++){
for(int j = 0; j <= m; j++){
if(i + j == 0)continue;
for(int x = 0; x <= i; x++){
for(int y = 0; y <= j; y++){
if(x + y == i + j)continue;
dp[i][j] += dp[x][y];
exp[i][j] += (exp[x][y] + dp[x][y]);
}
}
}
}
return exp[n][m] + dp[n][m];
};
auto correct = [&](){
mod_int in = mod_int(2).inv();
auto d = [&](int x){
mod_int val = x + 1;
return val * in;
};
mod_int ans = 0;
mod_int pw = mod_int(2).pow(n + m);
for(int i = 0; i <= m; i++){
pw *= in;
ans += C(n,i)*C(m,i)*pw*(i + d(n + m - i) + 1);
}
return ans;
};
cout << correct() << endl;
return 0;
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#ifdef SIEVE
sieve();
#endif
#ifdef NCR
init();
#endif
int t=1;cin>>t;
while(t--){
solve();
}
return 0;
}
problem A— Good problem cause it pretty easy as a normal A problem — in some contests problem A is too hard and this's bad cause people leave the competition without any submission and don't affect the distribution of seats although they could do it.problem B— a standard constructive problemproblem C— I really liked it, some people said that it was an ad-hoc problem maybe it was really so but I found a small pretty proof at the contest so this problem wasn't ad-hoc for me.problem D— Nice Div2D, not too easy, not too hard, I liked solving it at the contest.problem E— Very hard problem, didn't solve it. But when there are only five problems in a contest a hard E is a normal and even necessary thingGenerally— A very good contest without any explicit mistakes, I liked it, thanks !Problem C is easier than i expected :))
For D, I think this part is wrong: "So necessary conditions for answer to exist is that xor of array should be 0 and S1 should contains 0"
It should be "S0 should contain 0", because S1 can only contain odd XORs right?
Edit: Nevermind, I understand now. S1 doesn't mean the set of odd prefix XORs, S1 rather means the set of prefix XORs at the odd indices of the array.
How do we know this part is true for D?
"There will exists some odd size prefix j such that xor of its elements is 0."
Edit: Nevermind, I understand now.
Could you tell me how?
Edit: Nevermind, I understand now too.
Could you explain how?
This case happens only in the even subarrays.
That means it will not matter if we begin from the right or the left because if we have an odd prefix whose xor equals 0, the remaining suffix is odd and its xor equals 0 as well. So it is the same thing if we find an odd prefix or an odd suffix.
We will work on suffixes here
Now suppose you have a subarray $$$X$$$ that consists of the subarrays $$$A$$$ and $$$B$$$ respectively.
here the subarray $$$X$$$ is always a prefix of the whole array
It's clear that $$$xor(X)$$$ equals $$$xor(A) \oplus xor(B)$$$, where $$$xor(y)$$$ equals the xor of all elements in y.
Now suppose again that $$$xor(B)$$$ equals 0.
That's it
we need to find the prefix array $A$ that has a cumulative xor equals to the xor of the whole subarray $$$X$$$
You know that $$$xor(A)$$$ equals the cumulative xor of the last element of $$$A$$$. So this is our test, at every element we will check if there is a relative odd index to it that has the same cumulative xor. and we will get the last one because if it one holds, then all the right element of it holds but not vice versa. Note that we can change the beginning of the subarray at each query.
we can store the last occurrences of all cumulative xors in a map. We will need to store evens and odds separately to check the relative odd distance
That's all
I tried almost the same implementation. Can't understand what went wrong. https://pastebin.ubuntu.com/p/7p59QPh59D/ update: Got it.
"Let S0, S1 be sets of prefix XOR's of parities 0 and 1 respectively. After each operation new sets S′0, S′1 will be subsets of S0 and S1 respectively." Can you explain this part please? If I understood it correctly: suppose you have array $$$[1,2,1]$$$, then prefix xor are $$$[1,3,0]$$$, so the two sets $$$S_0, S_1$$$ are $$$[1,0]$$$ and $$$[3]$$$.
Now operate on the whole array to get $$$[2,2,2]$$$, and now the prefix xor are $$$[2,0,2]$$$, then clearly the $$$S_0',S_1'$$$ are not subset of $$$S_0,S_1$$$. Did I understand it wrongly?
Initial Prefix Xor array is $$$[0,1,3,2]$$$.
why am I getting tle in D for exact same complexity. 179934064
Same did you find a solution to it?
No, even after copying the code given in the tutorial it's giving TLE XD 179938608
use fast input output you phool 179948078
yeah just read about it, didn't know before
tutorial for E pls
upd. thank you!
Sorry for delay!
Solution for 1747E - List Generation:
For a good pair $$$a, b$$$ define the following $$$s$$$ array. For each $$$i$$$ from $$$2$$$ to $$$k$$$ append $$$a_i-a_{i-1}$$$ zero, then $$$b_i-b_{i-1}$$$ one, and a two to the end of $$$s$$$.
For example: $$$a=[0, 3, 4]$$$ and $$$b=[0, 2, 2]$$$, than $$$s=[0, 0, 0, 1, 1, 2, 0, 2]$$$. What do we know about $$$s$$$? It starts with $$$0$$$ or with $$$1$$$, it ends with $$$2$$$ and there is no $$$[1, 0]$$$ and $$$[2, 2]$$$ substring.
Obviously $$$|s|=|a|+n+m-1$$$.
If we fix the relative order of the $$$0$$$ and $$$1$$$ elements in $$$s$$$ ($$$s'$$$ array), than there are some $$$x$$$ positions where we must insert a $$$2$$$. (between the $$$[1, 0]$$$ parts). For the remaining $$$n+m-1-x$$$ positions we may insert a $$$2$$$ anywhere.
For example: $$$s'=[0, 0, 0, 1, 1, 0]$$$. We must insert a $$$2$$$ after the second $$$1$$$. And there are $$$4$$$ optional places.
So there are $$$2^{n+m-1-x}$$$ options, and $$$|s|=2+x+\frac{n+m-1-x}{2}$$$ on average. It is easy to calculate this in constant time.
The remaining part: how can we find the number of $$$s'$$$ arrays for a fixed $$$x$$$? If we fix the the ones, than there are $$$\frac{m!}{x! \cdot (m-x)!}$$$ options for the position of the zeroes, and we can place them in $$$\frac{n!}{x! \cdot (n-x)!}$$$ ways (some standard combinatorial problem).
So the final answer is $$$\sum_{x=0}^{m} binom_{m, x} \cdot binom_{n, x} \cdot (2+x+\frac{n+m-1-x}{2}) \cdot 2^{(n+m-1-x)}$$$
After the precalculation everything is linear.
Here is my solution: 180108716.
Nice!, I never looked at this was, but it is similar to my solution.
Can you solve for multiple dimensions?, such that sum over all dimensions is less than or equal to $$$10^5$$$.
For problem D, if $$$S_1$$$ doesn't contain $$$0$$$ and
a[1] != 0, you can't converta[1]to $$$0$$$.With the condition: $$$S_1$$$ contains $$$0$$$ and the whole xor == $$$0$$$, you can construct a method to convert all elements to $$$0$$$, so the 2 conditions is enough. Am I right?
In the editorial of problem E, if you jump to $$$(x,0)$$$ in your first move, does $$$(0,0)$$$ count as a breakpoint?
I wonder whether the time limit of E is too strict?My friend and I were traped due to it,both writing linear solution.
Solve E with generating functions (maybe without clever ideas?)
How many ways if we jump exactly $$$k$$$ times? $$$[x^ny^m](\frac{1}{(1-x)(1-y)}-1)^k$$$
So the answer is $$$Ans=[x^ny^m]\sum\limits_{k\geq 1} (\frac{1}{(1-x)(1-y)}-1)^k(k+1)$$$
As $$$\sum\limits_{k\geq 1}A^k(k+1)=(\sum\limits_{k\geq 1}A^{k+1})'=(\frac{1}{1-A}-1-A)'=(1-A)^{-2}-1$$$
So $$$Ans=[x^ny^m](2-\frac{1}{(1-x)(1-y)})^{-2}=[x^n y^m] {(1-x)}^2 (1-y)^2(1-2(x+y-xy))^{-2}$$$
Let
We can calculate $$$f(n,m)$$$ in $$$O(n+m)$$$
Then $$$Ans=f(n,m)-2*f(n-1,m)-2*f(n,m-1)+4*f(n-1,m-1)+f(n-2,m-2)+f(n-2,m)+f(n,m-2)-2*f(n-2,m-1)-2*f(n-1,m-2)$$$
My solution shows that in test 3 there are no preXORS in the array with similar value. Is it wrong? My solution is https://mirror.codeforces.com/contest/1747/submission/180203710.
Pls help, if you don't understand my solution, i can explain it to you, i just don't know what's wrong with it.
Take a look at Ticket 16424 from CF Stress for a counter example.
thank you, mate
For problem E hint 2 you haven't closed bracket
In problem D, how to prove that if these conditions are not satisfied then answer doesn't exists
If you admit the claim "S1 will always decrease", then if at the beginning there is no odd prefix with xor 0, then no matter how many operations you do, S1 will never contain 0, which means the entire subarray will never become 0.
Are the constraints for E intended to make solutions with FFT not pass?
For problem D, I don't really understand why "S1 and S2 always decrease" unless I try some quite complicated case analysis. Could someone give a better way to see this?
Can someone explain problem E in greater detail please? The tutorial has skipped so many steps, and poorly explained the most important part — what breakpoints are. "When we passes the breakpoint we turns right." What does this mean and and how are they defined? Why will the paths be grouped after that? Will apprecite any replies :)
Jai Shree Ram — OP