AORB Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Utkarsh Gupta
Tester: Abhinav Sharma, Utkarsh Gupta
Editorialist: Pratiyush Mishra

DIFFICULTY:

728

PREREQUISITES:

None

PROBLEM:

There are two problems in a contest.

  • Problem A is worth 500 points.
  • Problem B is worth 1000 points.

Once the contest starts, after each minute:

  • Maximum points of Problem A reduce by 2 points .
  • Maximum points of Problem B reduce by 4 points.

It is known that Chef requires X minutes to solve Problem A and Y minutes to solve Problem B.

Find the maximum number of points Chef can score if he optimally decides the order of attempting both the problems.

EXPLANATION:

Let us define a function as f(n,t,d), where n is the points of that problem, t is the time taken to solve the problem and d as the deduction in points per minute for that problem. Then we can define it as:

f(n,t,d) = max(0,n-(t \times d))

Now we have two choices, i.e to either solve problem A first then problem B or vice versa. The score for first case would be:

scoreAB = f(500,X,2) + f(1000, X + Y , 4)

and for the second case would be:

scoreBA = f(1000,Y,4) + f(500, X + Y , 2)

Our answer would be the maximum of the two scores.

answer = max(scoreAB, scoreBA)

TIME COMPLEXITY:

O(1), for each test case

SOLUTION:

Editorialist’s Solution
Setter’s Solution
Tester1’s Solution
Tester2’s Solution