Nice.

Definitely not intended, but simply storing the answers for all queries you processed worked for E too
(Feel free to hack it)
Submission

Brute force can AC problem E because of the too small $$$|t|$$$. AC Submission.

That's too bad. I think problem E is really a bad problem.

Someone please explain what does tilde "~" mean in C++

Am i the only guy who tried to solve D using Divide and Conquer approach with lengthy code.

Here is problem D solution using trie

169864432

Seeing who came up with the ideas, I came up with this conclusion about this round.

Can anyone please explain the (Ai & mask) ^ (Bi & mask) = mask in problem D ?

My approach to Problem D.

Let’s call an optimal pair the pair ($$$a_i$$$, $$$b_i$$$) after reordering $$$b$$$ to get the answer.

Initially the answer is $$$0$$$. At first we will try to make the highest bit in the answer into $$$1$$$ (I think this doesn’t need a proof). If we want the $$$i-th$$$ bit in the answer to be $$$1$$$, we need for every element of $$$c$$$ the $$$i-th$$$ bit to be $$$1$$$ and for this in every optimal pair we need $$$(a_i$$$ $$$\And$$$ $$$(1$$$ $$$\ll$$$ $$$i))$$$ $$$\oplus$$$ $$$(b_i$$$ $$$\And$$$ $$$(1$$$ $$$\ll$$$ $$$i))$$$ $$$= (1 \ll i)$$$. In other words, $$$($$$the $$$i-th$$$ bit of $$$a_i)$$$ $$$\oplus$$$ $$$($$$the $$$i-th$$$ bit of $$$b_i)$$$ $$$= 1$$$.

We’ll keep a vector $$$va$$$ of pairs of vectors. In each pair of $$$va$$$ there are elements of $$$a$$$ in the first and the elements of $$$b$$$ in the second element, such that the second elements of the optimal pairs, in which first elements are the elements of the first vector, will be the elements of the second vector (i.e. the elements of first and second vectors will construct an optimal pairs). Initially $$$va$$$ will contain only ($$$a$$$, $$$b$$$).

The algorithm is following : for every bit from $$$29-th$$$ to $$$0-th$$$ (let’s say $$$i-th$$$), we will do this: go threw the $$$va$$$, and for every pair of vectors, divide the first into $$$a0$$$ and $$$a1$$$, and the second into $$$b0$$$ and $$$b1$$$. In $$$a0$$$ there are all elements of the first vector, the $$$i-th$$$ bit of which is $$$0$$$, and in $$$a1$$$, the elements, the $$$i-th$$$ bit of which is $$$1$$$. $$$b0$$$ and $$$b1$$$ are constructed with the same way. Now there are two cases:

• If for every pair in $$$va$$$ the size of $$$a0$$$ is equal to the size of $$$b1$$$, and the size of $$$a1$$$ is equal to the size of $$$b0$$$, we will change $$$va$$$ into a new vector, consisting of all ($$$a0$$$, $$$b1$$$) — s and ($$$a1$$$, $$$b0$$$) — s (don't forget to check whether $$$a0$$$ and $$$b1$$$ ($$$a1$$$ and $$$b0$$$) are empty or not). And we’ll make the $$$i-th$$$ bit of the answer $$$1$$$.

• Otherwise, we will not change $$$va$$$ for the next bit.

Time Complexity is $$$O(30 * n)$$$.

My code

My idea is not very different from the idea in the editorial, but my implementation is another.

D can be done with trie as well, however it is much harder to implement.

The partitioning and matching in D can easily be maintained through simple built-in sorting, without requiring any additional maps or data structures.

To check if the most significant bit can be 1 in the answer, we can simply sort $$$a$$$ and reverse-sort $$$b$$$, and then check if this bit position is different between $$$a_i$$$ and $$$b_i$$$ for each index $$$i$$$. If yes, then we set this bit to 1 in the answer, and check the next position. The sorted order already extends naturally to the next bit (values in which the highest bit position are equal will be sorted based on the next highest bit position), so checking this next bit position like this will automatically account for the partitioning of the earlier bit positions.

The only issue is when the check fails for some bit position, i.e., there is some bit position where some $$$a_i$$$ is the same as the corresponding $$$b_i$$$. This means we can't have 1 in this bit position for the answer, and also that we should not allow this bit position to restrict the sorted ordering for later bit positions. To deal with this, we can simply set this bit position to 0 for ALL values in $$$a$$$ and $$$b$$$, and then sort $$$a$$$ and reverse-sort $$$b$$$ again (where the rearrangement will NOT modify the ordering within higher bit positions).

My Submission: 169955540

Here is my approach for solving D. May someone explain why it does not work?

Start with the MSB. Check if the number of elements with that bit set (1) in A is equal to those in B with that bit not set (0). If they aren't, proceed to the next bit. If they are equal, rearrange A and B such that the elements in A with that bit set precede those with that bit not set. Also rearrange B such that the elements in B with that bit unset precede those with that bit set. This way, that bit would look similar to this in A and B:

A: 1 1 1 1 1 0 0 0
B: 0 0 0 0 0 1 1 1

And hence after XORing the corresponding elements the result is n elements having that bit set. Now that A and B are partitioned into two sections, solve each section separately for the next bit.

Probably, problem E 1721E - Prefix Function Queries can be solved with sorting of all queries in lexicographical order and processing of them strongly in this order. We need to revert changes only to largest common prefix of given query and previous one. My AC submission: 170039416

Can someone find out why on earth this code got RE? thks in advance.

#include<bits/stdc++.h>

#define x first
#define y second

#define N 100005

using namespace std;

int t,n,a[N],b[N],ans,ord,cnt;
pair<int,int>e[N];

bool ch(int k){
	// cout<<k<<endl;
	for(int i=0,j=0;i!=-1;i=e[i].y){
		int tot=e[i].x-j;
		// cout<<j<<" "<<e[i].x<<endl;
		for(;j<e[i].x;j++){
			tot-=((a[j]>>k)&1)+((b[j]>>k)&1);
		}
		if(tot!=0) return 0;
	}
	return 1;
}

bool cmp1(int a1,int a2){
	return (a2>>ord)&1;
}

bool cmp2(int a1,int a2){
	return (a1>>ord)&1;
}

signed main(){
	for(cin>>t;t;t--){
		cin>>n;
		ans=0,cnt=1;
		e[0]={n,-1};
		for(int i=0;i<n;i++){
			cin>>a[i];
		}
		for(int i=0;i<n;i++){
			cin>>b[i];
		}
		for(int k=29;k>=0;k--) if(ch(k)){
			ord=k;
			ans|=(1<<k);
			for(int i=0,j=0;i!=-1;i=e[i].y){
				sort(a+j,a+e[i].x,cmp1);//where it got RE
				sort(b+j,b+e[i].x,cmp2);
				for(++j;j<e[i].x;j++)
				if(((a[j]>>ord)&1)!=((a[j-1]>>ord)&1))
					break;
				if(j==e[i].x) continue;
				e[cnt]=e[i];
				e[i]={j,cnt};
				i=cnt,j=e[cnt++].x;
			}
		}
		cout<<ans<<endl;
	}
}

Edit: solved. (found that sort got an infinite loop. :( )

(Copy-pasted):

Here's an interesting solution I found for E, not sure if it's new. Implementation here, featuring enough spaghetti to feed a family of five for a week.

We do some precomputation first. Use a map<int, int> m, where values are hashes of a substring of $$$S$$$, and the corresponding value is the maximal number $$$i$$$ such that the length $$$i$$$ prefix and suffix of $$$S$$$ are the same. To calculate this, we iterate $$$i$$$ independently of the substring, and check if the prefix and suffix have the same hashes in $$$O(1)$$$ time. If so, we add update m on substrings $$$S[i+1..i+1+j]$$$ (technically their hash values). As we'll see later, we only care about $$$j \leq 10$$$, so this takes $$$O(|S|\log |S|)$$$ time which is fast enough (we can use an unordered_map or gp_hash_table as well but time is not an issue). Note that if we double-check our hash equality by directly comparing the substrings, we TLE on TC 36 which is all a's, since comparing strings/generating substrings is linear in the length of the string so our program runs in $$$O(|s|^2)$$$ in that case.

We consider every $$$|S|+i$$$ more or less independently (I will use uppercase letters). Let $$$T_i=T[1..i]$$$ denote the length $$$i$$$ prefix of $$$T$$$. Suppose we have some prefix string $$$x$$$ of $$$S+T_i$$$ that's also a suffix string. There are three possibilities:

(1): Both the prefix and suffix strings lie in both $$$S$$$ and $$$T_i$$$. In this case, we can break $$$x$$$ up into $$$x_1,x_2,x_3$$$ (in that order) defined as follows: $$$x_1$$$ is the portion of the suffix string lying in $$$S$$$, $$$x_3$$$ is the portion of the prefix string lying in $$$T_i$$$, and $$$x_2$$$ is the remainder of $$$x$$$. To check if any $$$x$$$ of this type work, we iterate over $$$|x_3|:=j$$$, checking if the length-$$$j$$$ prefix and suffix of $$$T_i$$$ are the same. If so, then $$$x$$$ works if and only if the rightmost occurrence of $$$x_2$$$ in $$$S$$$ is as far right as it can be (i.e. occupies starting position $$$|S|-|x_2|$$$). In this case, the length-$$$|x_1|$$$ suffix of $$$S$$$ is also $$$x_1$$$, so we can use our precomputed m. There are at most $$$10$$$ values for $$$|x_3|$$$, so iterating over them is fast.

(2): The prefix string lies entirely in $$$S$$$, but the suffix string does not lie entirely in $$$T_i$$$. This is more or less a simpler version of (1). We split $$$x$$$ into $$$x_1,x_2$$$ such that $$$x_2$$$ is the portion of the suffix string lying in $$$T_i$$$, and $$$x_1$$$ is the remainder. Since $$$x_2$$$ must be $$$T_i$$$ by definition, $$$T_i$$$ must appear in $$$S$$$ as a substring. Further, $$$x_1$$$ must also be the suffix string of $$$S$$$ when this happens. We can use m for this as well. Note that there's only one possible value for $$$x_2$$$.

(3): The suffix string lies entirely in $$$T_i$$$. If $$$|S|\geq i$$$, then that means the prefix string lies entirely in $$$S$$$. There's at most $$$10$$$ values for $$$x$$$, so we can iterate $$$j$$$ from $$$1$$$ to $$$i$$$ (inclusive) and check if $$$S[1..j]=T_i[i-j+1...i]$$$. Otherwise, we have to join $$$S$$$ and $$$T_i$$$, since the prefix string could partially lie in $$$T_i$$$ as well, but the actual check is the same. Since this case only occurs when $$$|S|\leq 10$$$, joining $$$S$$$ and $$$T_i$$$ is quick (if you join $$$S$$$ and $$$T_i$$$ no matter what, you should TLE). Either way, you iterate through at most $$$10$$$ possible values for $$$x$$$. Ignore the comment at the top lol

To find the final answer, we iterate through all $$$O(1)$$$ cases and update our maximum value each time. The final time complexity should be $$$O((|s|+q)\log |s|)$$$ which works if you're not being stupid.

Why does F have to be online? I mean, is there any other way to solve it if one can do it offline?

Could someone explain why rank2 tute7627's submission works? The idea is using kmp to optimize mp. I see there are several this kind of submissions so I wonder if the time complexity of this approach is correct and we can use it as a model solution.

Can anyone uphack my solution to D?

I want to share my ultra elegant solution for 1721D - Maximum AND. Look: 169910079

In Solution of D, why (&ans) is used instead of (ans^(x&ans))? I know they are apparently the same, but how can this formula come up in mind? If it is something obvious , please tell me the trick. BledDest

Why does my D TLEed on #15? 169888012

Can someone please have a look at my submission 170673948? The basic idea is that the longest prefix of s+t matching some suffix of s+t will either have length (1) >|t| or (2) <=|t| . For the >|t| part, some (proper)suffix of s will match some suffix of s i.e the z value(wrt the z algorithm) of the index i from which the suffix starts will be n-i (0-indexing assumed). For the <=|t| part we can just brute force to obtain the answer in O(|t|^2) (to obtain prefix function values of s+t for its last |t| characters). So I first precomputed the z values of string s and then wherever z[i] was n-i, I considered all substrings, {(i+1,i+1),(i+1,i+2)...(i+max(|t|),max(n-1,i+10)) and update the 'score' values of each of these substrings. (score value of a string s1 being the prefix function value of s+s1 at the last index, considering only the case when the prefix length is larger than |s1|.) This can be done in O(max(|t|)) per i using a trie structure. Now while processing the queries, I first computed the prefix functions for case (2) as listed above using brute force in O(|t|^2) and for case(1), I just used the score values calculated for all the prefixes of t and updated the prefix function array (by taking max of answers obtained in both cases for each index). This can also in total be done in O(|t|^2) using the trie structure mentioned above. Hence the total complexity of the solution must be O(n.max(|t|)+q.(max(|t|)^2) ~ 2e7 operations which should comfortably pass in 2 seconds, however it TLEs. So can someone find some operation in my algorithm or its implementation which might be the bottleneck time complexitywise?

P.S- n is |s|.

Problem D was very helpful for me to learn bitmasking

can anyone stress test my submission 175562002 of D or tell me where i am wrong?

My approach for E:

First, look up all prefixs of s which equals to the suffix of same length. They can be find by calculating the prefix function of s in O(|s|). Then, for a certain prefix s[0...j-1], we store the result of s[j], s[j...j+1], s[j...j+2], ... , s[j...j+9] into a HashMap (where I used key of type int64, because |t|<=10 and number of smallcase letters is 26, which is smaller than (1<<5)=32, so we could use 5 bits for a letter and 50 bits for encoding a string t, which would not cause any collision, and the process can be done by bit operations otherwise may cause TLE). Also we should not let the value of the same key being smaller in the process.

Then for any query of t, we look the value of t[0...i], if we find the value, it will be outputed directly. Otherwise the value must be <=10, then we can find it by brute force.

The time complexity of preparation is O(|s|*|t|), and for each query is O(|t|^3). Total time complexity is O(|s|*|t|+q*|t|^3), which is at most about 10^8, fits the time limit.