COVAXIN O(1)

general
, , ,
1

Hi I was wondering for the Covaxin vs. Covishield problem, if it would be possible to get an O(1) solution by using maths.

We know that the price of the ith Covaxin or Covishield price can be represented as a+(i-1)b and c+(i-1)d respectively, so taking the partial sum of this series from 1 to k yields that sum of the prices of Covaxin or Covishield are 1/2(2ak + bk^2 - bk) and 1/2(2ck + dk^2 - dk).

Now taking this generalisation we should in theory be able to map these two functions on a cartesian plane to form an ellipse with the sum of their sum of prices being <= X. More formally we can plot 1/2(2ax + bx^2 - bx + 2cy + dy^2 - dy) <= X. From here we just need to develop an O(1) algorithm to maximise the integer pair x, y where x, y lies on or within the above ellipse.

To do this my thinking was that I could simply mathematically maximise point (x, y) on the ellipse, then floor and ceil the values to check the three values (floor(x), floor(y)), (ceil(x), floor(y)), and (floor(x), ceil(y)). However in practice there were too many edge cases I didn’t consider such as negative values, ellipses such that there existed no integer coordinates inside etc.

However in theory would this approach work if all the edge cases were accounted for?
Since all this would require are certain edge cases and a bunch of if cases for the logic.

2 Likes
2

simpler O(1) solution:

  • Let i+1 be Covaxin and j+1 be covashield
  • This means i * a + i*(i-1) * 0.5 * b + j * c + j * (j-1) * 0.5 * d <= x
    → A * i * i + B * i + C <=0 ( A = f(a,b), B = f(a,b) , C =Polynomial(j) )
    assuming j as constant we get i <= root as solution where root = some P(j)

→ ans = i+j+2 ~ [root] + j (ignore 2 as it’s constant)

All we need to do is find j such that ans = sqrt(P * j * j + Q * j + R) + j is maximum (P, Q, R are constants in terms of a,b which can be calculated in O(1) ).

->PUT derivative(ans) = 0 and we get Quadratic polynomial in j which satisfies derivative(ans) = 0 but this j could be real number. Hence iterate say vicinity of 10-20 of j and get i from first equation and take max of (i + 1 + j + 1);

1 Like