Lighting Fast Editorial and Thanks for the wonderful problems.

Thanks for the contest and the lightning fast editorial, but on my computer the tutorial doesn't work, it says

[problem:]

Tutorial is not available

it would be great if you could fix

The editorial is currently not working though it's already written, we're trying to find out why.

UPD: I've added ABC by hand

UPD2: It's working now

Can someone tell why my logic is failing in B?? I am getting WA in B. ~~~~~ //My short logic cnt = count of 1; cnt0=count of 0 ; final answer will be - cout<<(cnt*pow(2,cnto))<<"\n"; ~~~~~

AlFlen for D for the case where all elememnts are 10000 and n=100000 then the sum of abs(bi) = 1000010000, which is >10^9 Acc to editorial.

Problem B cpp failed sol | Problem B python passed sol any idea why cpp solution failed while python passed? they were the same pseudo-code :/

Problem — B

#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
using namespace std;

#define fi              first
#define se              second
#define ll             long long
#define pb              push_back
#define mp              make_pair
#define mt              make_tuple
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define all(v)          v.begin(),v.end()
#define ubound(v,val)   std::upper_bound(all(v), val)
#define pqb             priority_queue<int>
#define mnheap          priority_queue<int,vi,greater<int> > //mnheap  use less<int> for mxheap // push(),top(),pop() //
#define setbits(x)      __builtin_popcountll(x)
#define mod             1000000007
#define inf             1e18
#define FastIO             ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

int main()
{
	FastIO;
	// #ifndef ONLINE_JUDGE
	// freopen("inputf.in", "r", stdin);
	// freopen("outputf.out", "w", stdout);
	// #endif
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		vector<int> arr(n);
		ll zc =0;
		ll oc=0;
		for(int i=0;i<n;i++){
			cin>>arr[i];
			// sum+=arr[i];
			if(arr[i]==0)
				zc++;
			if(arr[i]==1)
				oc++;
		}
		ll ans = (1L<<zc)*1LL;
		cout<<oc*ans<<'\n';

	}
	return 0;
}

#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
using namespace std;

#define fi              first
#define se              second
#define ll             long long
#define pb              push_back
#define mp              make_pair
#define mt              make_tuple
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define all(v)          v.begin(),v.end()
#define ubound(v,val)   std::upper_bound(all(v), val)
#define pqb             priority_queue<int>
#define mnheap          priority_queue<int,vi,greater<int> > //mnheap  use less<int> for mxheap // push(),top(),pop() //
#define setbits(x)      __builtin_popcountll(x)
#define mod             1000000007
#define inf             1e18
#define FastIO             ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

	ll power(ll a, ll b)	//a is base, b is exponent
	{
		if(b==0)
			return 1;
		if(b==1)
			return a;
		if(b%2 == 1)
			return (power(a,b-1)*a)%mod;
		ll q = power(a,b/2);
		return (q*q)%mod;
	}
int main()
{
	FastIO;
	// #ifndef ONLINE_JUDGE
	// freopen("inputf.in", "r", stdin);
	// freopen("outputf.out", "w", stdout);
	// #endif
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		vector<int> arr(n);
		ll zc =0;
		ll oc=0;
		for(int i=0;i<n;i++){
			cin>>arr[i];
			// sum+=arr[i];
			if(arr[i]==0)
				zc++;
			if(arr[i]==1)
				oc++;
		}
		ll ans = power(2,zc)*1LL;
		cout<<oc*ans<<'\n';

	}
	return 0;
}

#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
using namespace std;

#define fi              first
#define se              second
#define ll             long long
#define pb              push_back
#define mp              make_pair
#define mt              make_tuple
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define all(v)          v.begin(),v.end()
#define ubound(v,val)   std::upper_bound(all(v), val)
#define pqb             priority_queue<int>
#define mnheap          priority_queue<int,vi,greater<int> > //mnheap  use less<int> for mxheap // push(),top(),pop() //
#define setbits(x)      __builtin_popcountll(x)
#define mod             1000000007
#define inf             1e18
#define FastIO             ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

	ll power(ll a, ll b)	//a is base, b is exponent
	{
		if(b==0)
			return 1;
		if(b==1)
			return a;
		if(b%2 == 1)
			return (power(a,b-1)*a)%mod;
		ll q = power(a,b/2);
		return (q*q)%mod;
	}
int main()
{
	FastIO;
	// #ifndef ONLINE_JUDGE
	// freopen("inputf.in", "r", stdin);
	// freopen("outputf.out", "w", stdout);
	// #endif
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		vector<int> arr(n);
		ll zc =0;
		ll oc=0;
		for(int i=0;i<n;i++){
			cin>>arr[i];
			// sum+=arr[i];
			if(arr[i]==0)
				zc++;
			if(arr[i]==1)
				oc++;
		}
		ll ans = pow(2,zc)*1LL;
		cout<<oc*ans<<'\n';

	}
	return 0;
}

Is'nt left shift and logarithimic power method better than pow??

why did my solution with left shift failed and how it is different from one in the editorial

anyone can explain why??

thanks in advance.

> (действительно, если просто действовать по жадному алгоритму и брать 
> трехминутные треки пока можем, затем двухминутные, затем одноминутные,
> то мы сможем получить любую длительность).
> 
> Тогда ответом на задачу будет являться остаток по модулю 2 числа S

Кто-нибудь, может привести доказательство, что это так? Я не могу понять, почему это так?

For Problem B,

The suggested solution returns an answer of 4 subsequences for the testcase below:

1

3

0 0 1

When I counted I could only get 3 subsequences:

[empty set]

0

0 0

Could somebody tell me if I had misunderstood? Sorry for bad formatting and thanks in advance.

weak pretests!!! rnm tq！

The editorial is working now

problem A was really misleading and harder than most div2 A

In D, if odd n you can make MAXA * (MAXN + 1)

I probably overkilled it, but i tried a fenwick tree solution to F1 but it gives WA on test 7. Could someone help?

https://mirror.codeforces.com/contest/1582/submission/132929945

Why does my code fail on D?

if (a[0]==a[1] && a[1]==a[2])
{
	cout<<"2 -1 -1 ";
}else{	
	cout<<(a[1]-a[2])<<" "<<(a[2]-a[0])<<" "<<(a[0]-a[1])<<" ";
}

Please don't downvote, I might be completely wrong

D is slightly harder if sum of absolute values of $$$b$$$ is restricted to $$$n * max(|a_i|) + 1$$$. I accidentally solved this problem. Anybody interested can try too.

Actually Could someone pls tell me why my approach on D failed ? consider a[1] * x + a[2] * y = a[3] + a[4] + ...

let t be the gcd(a[1], a[2]) let v1 = a[1] / t, v2 = a[2] / t

so t1 * x + t2 * y = sum, where sum = a[3] + a[4] + ...

we can solve for x and y using the extended eucledian method for finding the inverse and handling some corner cases. (when t2 * y = sum, ... )

Then we assign b[3] = b[4] = ... = t and a[1] = -x, a[2] = -y

Let g be gcd(-x, -y, t) divide the whole b array by g and print the answer.

But wrong answer on test 3 submission. Any help would be appreciated.

EDIT : Ignore this. The hypothesis was wrong.

Let's notice that since a,b,c≥1, it is possible to make a concert of any duration from 0 to S

Seems like you are solving a diophantine equation. But can I get more explanation on that statement please?

In problem A, Can someone explain why we can make every value from 0 to S?

My approach to F2 seems a bit different from the editorial's:

Say $$$dp_i$$$ contains all values $$$(ind_j, v_j)$$$, sorted by $$$ind_j$$$, such that it is possible to get an increasing subsequence with an xor of $$$v_j$$$ and last element at index $$$ind_j$$$, using only elements in the array less than or equal to $$$i$$$. If there are multiple possible values for one $$$v_j$$$, only store the one with the minimum $$$ind_j$$$.

To transition from $$$dp_{i - 1}$$$ to $$$dp_{i}$$$, first, add all elements already in $$$dp_{i-1}$$$ to $$$dp_i$$$. Then, for each $$$(ind_j, v_j)$$$ in $$$dp_{i-1}$$$, take the minimum index $$$k$$$ such that $$$a[k] = i$$$ and $$$k > ind_j$$$. Then, add $$$(k, v_j \oplus i)$$$ to $$$dp_i$$$ (if this $$$k$$$ does not exist, don't do anything). This can be done in linear time with two pointers if you store the occurrences of each $$$i$$$.

Two important details:

1. To make sure that each $$$dp_i$$$ remains sorted, while transitioning, you can store the values $$$(k, v_j \oplus i)$$$ and $$$(ind_j, v_j)$$$ in two separate vectors, since each of these separately will be sorted. Then, combine the two in linear time (same method used in mergesort).
2. To make sure you only store the minimum $$$ind_j$$$ for each $$$v_j$$$, you can keep track of the minimum value $$$ind_j$$$ for each $$$v_j$$$ with an array $$$minindex$$$. Then, only add a pair $$$(ind_j, v_j)$$$ to the dp if $$$ind_j = {minindex}_{v_j}$$$.

My code: 132932565

Korney Korneevich sounded like gennady korotkevich to me :-)

132925114, this is my solution for E, i am getting RE on test 7 with exit code 2147483647, can someone please help.

I wonder whether it is possible to solve F2 with python? (python 3.8 or pypy or pypy-64) indeed python is somehow disadvantaged...but indeed it is easier to write-.-

Where is the editorial for F1?

Are there any other solutions for D?

except editorial

Can you somehow solve D with a Diophantine equation? I tried to, but I failed on the third test.

Could someone plz share the tutorial of Problem F1, which seems to have an easier solution. Thx!

Could someone plz share the tutorial of problem F1 which has a relatively easier solution? Thx!

C reference code is written very well！！！It's better than what I wrote.

I have a simmilar solution for C that should have better complexity:

First notice that the center of the palindrome can vary, but the edges don't. Because of this we can check the first with last, second with second to last, ... and stop when we find 2 different chars or we checked all pairs(answer is 0).

When we find some i such that S[i]!=S[N-1-i](with 0 based indexing) there are 2 possibilities:

1. Deleting either one leaves a palindrome in which case the answer is the minimum of the required removals in the case that they produce a palindrome.
2. Removing neither one of them will produce a palindrome so the answer is -1.

The reason why there are only 2 cases is that if we remove some other character then we will still have those 2 characters mismatched. So we need one of them to go away.

The complexity would be O(N) with at most 3 passes through the string. The solution presented in the tutorial does a similar thing but doesn't stop when it finds the different characters and so it loses time. With some tighter time limit(Or if we expand the alphabet, maybe with upper case letters or diggits) it might not fit.

As always, here are the video solutions for the first 6 problems(A to F1) :

solutions

There is an easy solution for F2. Let dp[i] be the first index in which its possible to make an increasing subsequence of xor i. Lets also maintaing a vector of vectors V such that V[i] stores all the occurences of i in the array in order.

We can now iterate through the values x in increasing order, and for we to update dp[i] we do dp[i] = min(dp[i],V[x].upperbound(dp[i^x])).

This works in $$$O(n+maxa^2*log(n))$$$: https://mirror.codeforces.com/contest/1582/submission/132952152

Proof for problem A solution

Can someone explain if this solution to problem G works? I was confident that I had a simple $$$\Theta(n)$$$ solution, but it's failing on test case 18 for some reason so now I'm feeling doubtful. I don't know if the problem is my code or my proof though.

Here is the proof:

We scan the array $$$a$$$ of size $$$n$$$ from left to right. For any integer $$$r$$$, we define $$$S_r$$$ to be the set of possible starting points $$$l$$$ such that the segment $$$[l;r]$$$ is simple. Then it follows from the definition that the solution to the problem is $$$\sum_{r\in [0,n)} |S_r|.$$$ Now, we consider how to compute $$$S_r$$$ from $$$S_{r-1}$$$. If $$$b_r$$$ is '*' or $$$a_r$$$ is 1, then $$$S_{r} = S_{r-1}\cup {r}$$$, since any path that worked before will still work, and the path starting at $$$r$$$ will also work.

Now, if $$$b_r$$$ is '/' and $$$a_r$$$ is not 1, then to get $$$S_r$$$, it suffices to take $$$S_{r-1}$$$ and remove invalid starting positions. (Namely, we remove any element $$$l\in S_{r-1}$$$ such that the segment $$$[l;r-1]$$$ ends with a number that does not divide $$$a_{r}$$$.) Observe that for any two elements $$$l_1 < l_2 \in S_{r-1}$$$, if the segment $$$[l_2;r]$$$ is simple, then the segment $$$[l_1;r]$$$ is also simple. To see this, first note that the segment $$$[l_1, l_2]$$$ must be simple, since otherwise, $$$[l_1, r-1]$$$ would not be simple, contradicting the fact that $$$l_1\in S_{r-1}.$$$ Thus we just need to remove the largest few elements of $$$S_{r-1}$$$ to compute $$$S_r$$$.

For any two consecutive elements $$$l_i, l_{i+1} \in sorted(S_{r-1} \cup r)$$$, we can say that the value of the path $$$[l_i;l_{i+1}]$$$ is the value remaining after traversing this path. To compute $$$S_r$$$, we continuously pop the largest-indexed element from $$$S_{r-1}$$$ and divide $$$a[r]$$$ by that element's value until $$$a[r]$$$ is 1. Some caution is needed to maintain the invariant — you need to update the last value you popped out from being the value of a path $$$[l_i;l_{i+1}]$$$ to the value of the path $$$[l_i, r]$$$.

Here is the code: https://mirror.codeforces.com/contest/1582/submission/132953817

In the code, V is a stack of the value of paths $$$l_i, l_{i+1} \in sorted(S_{r-1} \cup r)$$$.

Maybe maintests of F2 are a bit weak.
My sulotion to F2 has only considered the first and last three times of occurrences for each different elements.
So can somebody hack me or prove that it's correct.
Here it is

Anyway,There is also a sulotion has passed maintests but hacked by me. this one
Perhaps we need stronger maintests

I want to understand F1!

I have another solution for E that works in $$$O(NlogN)$$$. Maybe it is hackable because I am not good at proving.
Here is the submission: 132984246
Reverse the array first. Let $$$dp_{i,j}$$$ be the maximum sum on the segment of length $$$j$$$ considering all elements on the prefix $$$i$$$.
Then the transition should be like:

for(int i = 1; i <= n; i++) {
	for(int j = 1; j <= n; j++) {
		dp[i][j] = max(dp[i][j], dp[i - 1][j]);
	}
	long long sum = 0;
	for(int j = 1; i + j <= n; j++) {
		sum += a[i + j - 1];
		if(sum >= dp[i - 1][j] && sum < dp[i - 1][j - 1])
			dp[i + j - 1][j] = max(dp[i + j - 1][j], sum);
	}
}

I added sum >=dp[i-1][j] to the condition because if sum<dp[i-1][j] then sum>=dp[i+j-1][j] will not holds.
It can be noticed that $$$dp_{i,j} \ge dp_{i,k}$$$ if $$$j \le k$$$ (Like LIS) and sum is increasing, so the condition sum>=dp[i-1][j] holds for monotonicity. Also, sum<dp[i-1][j-1] must hold, too.
Therefore, the if condition will be triggered at most once for every $$$i$$$: when the first $$$j$$$ such that $$$sum(i..(i+j-1))\ge dp_{i-1,j}$$$. And we can use Binary Search to find such $$$j$$$.

I request proof of 1582C - Grandma Capa Knits a Scarf. Why this approach indeed find optimal removal for fixed letter? AlFlen can you explain?

Can anyone Explain point 1 of 1582F2 — Korney Korneevich and XOR Tutorial using an example: like test case: 12 4 2 6 5 2 4 5 6 4 2 5 6??

[user:74TrAkToR][user:AlFlen]

Can Anyone Explain or prove point 1 of 1582F2 — Korney Korneevich and XOR (hard version) Tutorial (using a test case would be very helpful) . example test case is:

12

4 2 6 5 2 4 5 6 4 2 5 6

Hello guys,

So, in problem E I tried implementations with 2D array as well as vector<vector >. However, only vector implementation passes and the array implementation gives runtime error on test 8. Can somebody explain this? Besides, the vector implementation needed 1900 ms to pass which either means that the 2s bound was tight or I have implementation issues. Can anyone suggest improvements in vector implementation?

vector impl: 133108745 array impl: 133108661

Hello guys,

So, in problem E I tried implementations with 2D array as well as vector<vector >. However, only vector implementation passes and the array implementation gives runtime error on test 8. Can somebody explain this? Besides, the vector implementation needed 1900 ms to pass which either means that the 2s bound was tight or I have implementation issues. Can anyone suggest improvements for vector implementation?

vector impl: 133108745 array impl: 133108661

can anyone pls explain the last line of editorial of B cout << (1ll << cnt0) * (ll)cnt1 << '\n';

I am getting TLE for Problem E but I think my solution is O(nk), k = sqrt(n). Not sure why. could anybody please help me with this. Solution link : https://mirror.codeforces.com/contest/1582/submission/133125904.

Although I am looping for j=1 to k and then calling memo(), but according to me, the total dp state calculation time is O(nk) only.

In problem D in the case of n being odd

isn't the sum of the array b going to be 1e9+1e4 which exceeds the required constraints?

Can someone please explain it to me?

In editorial for G, can someone please explain what next_i is really calculating?

For problem C, the answer can probably be obtained by using either the first or the last character in the original string. There is no need to run the algo for all the 26 characters :p

Can anyone explain how is The sum |b1|+|b2|+…+|bn−3| does not exceed MAXA⋅(MAXN−1−3).

F1 can be done using segment tree + bitset optimization

Submission here: 155885705

Extremely simple $$$O(n + (max(a[i])^2 + max(a[i]).\log{max(a[i])})$$$ solution for F-2: link

(Basic idea is to consider all elements in increasing order of value, as then we dont have to care about ensuring subsequence is increasing, we just have to care about indices of consecutive elements in the subsequence.)