There was such a short announcement before. But it became longer as details have been added. Perhaps this announcement will be the case too. Anyway I hope the description of the problem is as simple as this announcement at the upload.

it's illegal

It's Ehab. Please correct. I still remember the Ehab and expected XOR problem. That was my best contest so far.

*pretest passed >= system test passed

Thanks for calling it out!

I'm in California too and I totally agree. The convenient thing is, at the very least, 6am contests are generally before school/work.

It means that the added problem can be solved by the top level in 15 minutes.

I expect the added problem to be C or D. Likely, the middling finishers will do A,B, and possibly C, then looking at the old next problem with over an hour left, they would find it nearly impossible. However, with this added problem, these middling finishers can now attempt to solve the added problem, with the hour they have left.

Trie + dp:

You build a trie bit by bit with the first edges corresponding to the most significant bits. after that, you define dp[node] = minimum-maximum for the numbers in this subtrie(i made this word up) if you don't consider the first bits(up to the one corresponding to our node). The edge cases when you only have one child are easy. After all the subtrie which will have the opposite bit is gonna be the one which determines our answer so all you need to do is "dp[nod] = min(dp[child1], dp[child2]) + our current power of 2" and that is it.

Hint — If I have atleast one number where ith bit is 0 and another number where ith bit is 1, I can't avoid having answer lesser than 2^i.

No dp required. Complexity will be O(NlogN). Let solve(vec,bitpos) indicate the answer , Now if all the numbers in the vector have same bit set/unset recurse solve(vec,bitpos — 1). Else answer is 2^bitpos + min(solve(vec1,bitpos-1),solve(vec2,bitpos-1)). Where vec1 and vec2 are vectors having the current bit set/unset respectively.

Proof?: If X has current bit set answer has to come from the opposite set ( having bit complementary to X). This is because the numbers belong to the set having same bit parity can never contribute higher minimax that the complementary set.

В ней, на мой взгляд, совершенно нет идеи для человека знающего дерево отрезков на количество 0 на отрезке.

Это очень спорное утверждение. Я например решал только с сетами

It was just maximum subarray sum without including [1,n]

think when does removing a segment actually increases the answer. think about difference arrays (of what? think about that too xD). just saying, but in both [1,10] [2,15] [3,17], and [1,10], [2,15], [12, 17], remove the middle segment and see?

Sort all points in increasing order, process them from left to right, keep a set of segments. If a segment starts at a give point, add to the set and vice versa. When number of segments changes from 2 -> 1 -> 2, we update increase[index]++ where index is the index of the segment when the num segments were exactly 1 in the pattern 2 -> 1 -> 2.

Answer is number of union set without removing + max_element of increase.

Hope I explained it fine.

I tested this case:

5

10 13 16 20 26

and I found the answer is 20, which is not the power of 2.

NO, take $$$n=7 ,arr = $$$ $$$1,2,3,4,5,6,7$$$

Not true. Consider the input

4
0 1 2 3

Answer is 3

Try : 8

One way is to use a prefix trie. If you are at a node at the i'th bit, if there is only one valid edge, say a 0, then that means you can take a 1 without increasing the max xor.

If there are two valid children, then that means no matter if you pick a 0 or 1, you will have to increase the max xor by 2^i. So, you can just add 2^i to your answer, recurse on the child nodes and take their minimum.

Note that the answer won't exceed than 30 bits.

Starting from 30th bit, check if the numbers in the array have the same bit on the 30th bit or not. If yes, it is possible to put the same bit in X to make minimum XOR-SUM.

If not, then we can put either 1 or 0 in X at the 30th bit. If the 30th bit is set 1 in X, then all the numbers in the array with 30th bit as 1 will not give max XORSUM. Hence form a new array with the numbers having 0 as the 30th bit, and continue further towards 29th bit. Similarly, for 30th bit as 0 in X can be handled and take the minimum of them.

I handled it recursively. LINK TO MY SOLUTION

P.S. Don't forget to empty the array before starting pushing the array. I wasted 30 minutes to debug that mistake.

Let's use a Binary trie. Insert all N numbers in the trie. If a number has its 30th bit on then it goes to the right of the root, else goes to the left. similarly at the next level we'll make decision for the 29th bit and so on.

After you have inserted all numbers in the trie, consider what is the answer for a particular subtree.

if the root of the subtree has only one child that would mean all numbers under consideration have this bit either on or off and hence we may choose a number such that our answer will have this bit off. In this case answer will the same as the childAns.

if the root of subtree has two children then numbers under consideration belong to both bit on and off categories and hence no matter what number we choose this bit will definitely be on in our answer. In this case the answer will be (1<<bitPos) + min(leftChildAns, rightChildAns).

Also for time complexity analysis, the solution can be implemented with a simple DFS. Maximum possible nodes in the trie : 10^5 * 30.

implementation : https://codeforces.me/contest/1285/submission/68543045 (I hope it passes the systest xD).

Alternative soln without trie: Sort all the elements. Let solve(l, r, pos) be the function which gives the answer for the range [l, r] considering only pos least significant bits. Now, observe that most significant bit will be 0 first then 1 in the sorted order. Let f the last position of 0 bit. Now, you can do recursive calls to solve(l, f, pos-1) and solve(f+1, r, pos-1) and then take the answer as (1<<pos) + min(solve(l, f, pos-1), solve(f+1, r, pos-1)). Link to code

I just copy-pasted code from a problem I solved yesterday :Dd

(Simpler solutions exist for sure though)

This is much similar to F see this

Memoization is not needed here.

Yes

Dude, nobody was asking for c solution, why did you put it here?

how you are sure that this will give right answer.. can u explain it more

Solution for B:

Yasser's Score = sum of Ai's

Adel's Score = max sum of subarray of A (Can be found using Kadene's Algorithm, by running from 1 to n-1 and 2 to n.... Since we can't take the whole array sum)

if (Yasser's score > Adel's score) Print("Yes") otherwise Print("No")

If $$$\sum a_{i} \leq 0$$$, Adel can just pick any cupcake with nonnegative tastiness. Answer NO.

If some prefix has sum at most zero, Adel can buy all cupcakes not in that prefix. If some suffix has sum at most zero, Adel can buy all cupcakes not in that suffix. Answer NO.

Otherwise answer YES. Assume Adel buys the interval $$$[l, r]$$$. Then Yasser's tastiness minus Adel's tastiness is $$$sum(1, l-1) + sum(r+1, n) > 0$$$, as all nonempty prefixes and suffixes have positive sum, and either the prefix or suffix is nonempty.

Calculate prefix and suffix sum of array

if any term in prefix or suffix sum array is less than or equal to 0, then the answer is "NO" else the answer is "YES"

He did it smartly say the sum of the array is S, Now if prefix sum is less than or equal to 0 then suffix sum must be greater than or equal to S Hence [Fail] As prefix sum + suffix sum = S, Similarly, we can do it for suffix case.

Now you may think it may not cover all the cases, Consider any [l,r], Say the cases we stated above doesn't happen, Then sum[0,l-1] > 0, So it is safe to consider [0,r] and you can easily visualize that sum[0,r] won't be greater than or equal to S in any case, As sum[r,n] > 0. Hence we prove that for any [l,r] We won't find sum>=S Hence[Pass]

Hope this helps.

The initial value of min is too small. If $$$X$$$ has a divisor that is a power of a prime number and this divisor greater than INT_MAX, the correct min will greater than INT_MAX.

For example: If $$$X=10000600009=100003^2$$$ ($$$100003$$$ is a prime number), your solution outputs 4 2147483647, correct answer is 10000600009 1.

More like: good number in base 10

Yup, C was indeed easier than B

B was infact copy-paste from gfg (kadane's algo),tho C required some brain cells Ps: I got accepted B in 6 attempts lol

You'd think so but surprisingly me and mohammedehab2002 were able to handle most heuristics almost right before the contest.

take [20 30 -10 50 60] 20+30-10+50+60 = 10+5-12+7-10+20+30-10+50+60

Quite strange.The TLE code shown is accepted. I think, you must tag admin in this case.Maybe he can help.

I agree.

my submission in contest time also got WA for same problem 68547513

Initialise mi with 3e18 or any greater value in your code.