Home > matlab, Olympiad > ICPC 2015 World Final Problem A

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 ${\{1,2,...,n\}}$. Then, you need to find the maximum decrease in the function values.

The inputs are parameters ${p,a,b,c,d,n}$, the function is

$\displaystyle \text{price}(k) =p(\sin(ak+b)+\cos(ck+d)+2).$

and the values to be considered are ${p(1),p(2),...,p(n)}$. 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 $n=1000 fg=000000$ but it should be modified to work until $n=10^6 fg=000000$.

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 $n$. 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 $n= 10^6$

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)