Lunchtime 2013 -> CHGIFT1

greedy
lunchtime

#1

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?


#2

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*, min + v*, min - v*, max * v*, max + v*, max - v*. 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 ).


#3

Check this Editorial.


#4

Why use max also ?


#5

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


#6

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*^a[j], 1 <= i,j <= N && i != j; I searched for a value in the trie which maximize the value the xorsum.