## ICPC 2015 World Final Problem A

This is the solution to Problem A from the International Collegiate Programming Contest. The list of problems can be found here. This first problem consists simply of reading the parameters of the function defined below, and computing its values on the set . Then, you need to find the maximum decrease in the function values.

The inputs are parameters , the function is

and the values to be considered are . Below is a Matlab code which works, at least for the given Sample Inputs. This should be optimized by removing the for loop. It is instant for but it should be modified to work until .

function res = Prob1_2015(p,a,b,c,d,n) dis = 1:n; vals = p*(sin(a*dis+b)+cos(c*dis+d)+2); mat = zeros(n,1); for i = 1:n mat(i) = vals(i)-min(vals(i:end)); end res = max(mat)

The sample outputs are:

>> Prob1_2015(42,1,23,4,8,10) 104.855110477394

>> Prob1_2015(100,7,615,998,801,3) 0

>> Prob1_2015(100,432,406,867,60,1000) 399.303812592112

New version which works for large . It suffices to eliminate the computation of the min at each of the phases of the iteration. This solves the problem in 0.2 seconds for

function res = Prob1_2015(p,a,b,c,d,n) dis = 1:n; vals = p*(sin(a*dis+b)+cos(c*dis+d)+2); mat = zeros(n,1); lastmax = vals(1); for i = 1:n lastmax = max(lastmax,vals(i)); mat(i) = lastmax-vals(i); end res = max(mat)