# GUZAC-AUGUST COOKOFF 2018

i made a code for GUZAC. i first got an array of exactly known elements. got it sorted. found if the max diff b/w known elements is less than given max diff. if yes then made a temp variable which stored (max_diff+arr[0]-since array is sorted arr[0] is smallest). then started decreasing temp and simultaneously checked whether it was already present in known arr or not. similar logic for the other case. however this gives me a TLE error. what changes can i make into my code(i thought only sorting would take time else everything is done in almost constant time. since the c++ stlâ€™s sort is having time complexity O(nlog(n)) it should have been well within the time limits.

the link to my code can be found here. Thanks in advance.

Refer to editorial. If the array is sorted, the numbers lying between A[i] and A[i+1] can all be chosen. Find formula to add these numbers in O(1) time, instead of adding one element at a time.

1 Like

Sorting has to be doneâ€¦ What my suggestion is suppose given array is
1,101 ,201, 1001 (after sorting) and x=2000

#### then append (1+2000)+1=2002 to this array

So it will be
1, 101, 201, 1001, 2002
Now in your algo I guess you will start from 2001 and go till 1 or till you get sum linearlyâ€¦
#what you can actually optimize is break sum into parts till you get n elements as followsâ€¦
sum(1002,2001)+sum(202,1000)+sum(102,200)+sum(100,2)
where sum(x,y) denotes sum of x + (x+1) + (x+2) + (x+3) + .... + y
sum(x,y) can be computed in O(1) using formula of summation of 1 to n
##HERE is a refernce link if you donâ€™t know how to compute thatâ€¦
Obviously you need to stop sum before n exceeds as you need only n numbersâ€¦
which is easy to implementâ€¦ just keep subtracting (y-x+1) from n each time you add sumâ€¦

1 Like

#HERE is my accepted solution