Can anyone make good and understandable editorial on january easy contest Questions “Shubham And Subarray” & “Shubham and Subarray XOR” ? Any help is most appreciated.
Shubham and Subarray :
You need to count the number of distinct subarrays. Two subarrays are distinct if there is at least one number that is present in only one of the two. So, you need to be able to somehow represent the numbers present in a subarray, and compare this representation for different subarrays. This is what I did:
Since the values present in the array must be less than 1000, I used a vector of unsigned long long ints to represent subarrays. Each of those will have 64 bits, so, 16 numbers will be sufficient to represent any subarray. Each bit will correspond to one particular number, and we will set the bit if that number is in the subarray. In this way, I created vectors for all the subarrays, and added them to a set. Finally you just need to print the size of the set.
Shubham and Subarray XOR :
Basically, you need to pick two subarrays, and maximise the XOR of their sums. This is what I did:
First, lets call the two subarrays left and right. For each position i 2<=i<=N I calculated the maximum XOR that I can get if the right subarray starts at position i. Since the right subarray starts at i, the left subarray must be some subarray from 1…i-1. So, if you have the sums for all those subarrays, then you can check which one of them will give you the maximum XOR. You can use a trie to do this quickly.
So, for each position ‘i’, you need to find the sum of subarrays starting at ‘i’ and for each of them, find the maximum XOR with all possible left subarrays. There will be O(N) subarrays starting at ‘i’, and checking for the maximum using trie takes O(Log(val)) time, where ‘val’ is the largest number that you can have in the trie. After this is done, before moving to i+1, you need to add the sums of all subarrays ending at ‘i’ to the trie, because for the next position, these are also valid left subarrays. There will be O(N) of those. Adding to trie also takes O(Log(val)). So, overall the number of operations for one particular position ‘i’ is O(NLog(Val)). Since you will be doing this for every position, overall, the complexity will be O(N^2Log(val))
1 Like