Lunchtime 2013 -> CHGIFT1

I used a greedy algorithm , calculating the min taking two numbers at a time, starting from the left but could pass only one test case…

What algo would have passed all the test cases?

I’ll post my solution. You have two variables min and max first initialized with v[1]. At a moment i you add in a vector min * v[i], min + v[i], min - v[i], max * v[i], max + v[i], max - v[i]. Sort this vector and reinitialize min and max with min = vector[1], max = vector[6]. Using this greedy algorithm you store the minimum value of the expression at any given moment. The complexity is O(T * N * 6log6 ).

1 Like

Why use max also ?

What algo did you use for XORing question?
I tried Brute Force. Gave TLE!

I used max because of tests like this: N = 3 a[]=3,2,-3.
At the XOR question i used a trie in which I stored every value from the vector with full binary representation and after that for every sum a[i]^a[j], 1 <= i,j <= N && i != j; I searched for a value in the trie which maximize the value the xorsum.

Check this Editorial.