Last Updated: 18 Feb, 2021

Game In Space

Hard

Asked in company

Problem statement

Ninja is in space with his super spaceship having unlimited fuel. Ninja initially has a health level ‘H’ and his spaceship has an armour ‘A’. He decides to play a game, where at any instant he can be only on one of the 3 planets: VENUS, MARS or SATURN. At every unit of time, he has to change his location and you can assume he can change his location instantly. Each planet has different effects on health and armour which are :

Venus: Decreases health by 4, decreases armour by 8.
Mars: Increases health by 3, increases armour by 2. 
Saturn: Decreases health by 10, increases armour by 5.

Now the game will end if either ‘H’ <= 0 or ‘A’ <= 0.

Your task is to find the maximum time Ninja can survive.

Note :

You can choose any of the 3 planets during your first move.

Input format :

The first line of input contains a single integer T, representing the number of test cases.

Then the T test cases follow.

The first line of every test case contains 2 single space-separated integers representing initial health and initial armour respectively.

Output format :

For every test case, print a single integer representing the maximum time Ninja can survive.

The output of each test case is printed in a separate line.

Note :

You don’t have to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= H, A <= 10^3

Where ‘T’ denotes the number of test cases,  ‘H’ is the initial health and ‘A’ is the initial armour.

Time Limit: 1sec

Solve now

Approaches

01 Approach

The idea is simple, we will check all the possible ways of choosing planets with the help of recursion and find out which combination gives maximum time.

Along with this, we will prefer to move Mars whenever possible as it is always beneficial to make a move to Mars.

So we will make a recursive function named SOLVE which will receive 3 parameters ‘H’, ‘A’ and ‘MOVE_MARS’.
Initialize a bool variable ‘MOVE_MARS’ = 0 ,where ‘MOVE_MARS’ == 0 indicates we can move to Mars .
Base Case :
- When ‘A’ <= 0 or ‘H’ <= 0 then we will return -1 as we can’t move to any other planet now and we have already added 1 in time for this move.
Check the value of the ‘MOVE_MARS’:
- If it is equal to 0, it means we are moving to Mars.
  - Then increase ‘H’ by 3, ‘A’ by 2 and set ‘MOVE_MARS’ = 1. We then make a recursive call.
  - Return 1 + the result received in above call.
- If the ‘MOVE_MARS’ is equal to 1, it means we have to move either to Saturn or Venus.
  - Make two calls, one to Venus and other to Saturn by changing variables according to their effect and setting ‘MOVE_MARS’ = 0.
  - Return 1+ the results received in the above call.
Return the value returned by SOLVE.

Solve now

02 Approach

Our last approach was very simple and easy, but its time complexity was of exponential order. We can improve our solution by taking care of the overlapping subproblems. Thus, we will eliminate the need for solving the same subproblems again and again by storing them in a lookup table. This approach is known as Memoization

So we will make a recursive function named SOLVE which will receive 3 parameters ‘H’, ‘A’ and ‘MOVE_MARS’.
We will initialize a 2-D array, say ‘MEMO[2000][2000]’ with -1. Where MEMO[i][j] equal to -1 means the current state is not explored. Otherwise, it will store the maximum time Ninja can survive with health = ’i’ and armour = ’j’.
Initialize a bool variable ‘MOVE_MARS’ = 0 ,where ‘MOVE_MARS’ == 0 indicates we can move to Mars .
Base Case :
- When ‘A’ <= 0 or ‘H’ <= 0 then we will return -1 as we can’t move to any other planet now and we have already added 1 in time for this move.
We will check the value of ‘MEMO[H][A]’ :
- If it is not equal to -1, then we can say we have already explored the result for the current state, so return ‘MEMO[H][A]’.
Check the value of the ‘MOVE_MARS’:
- If it is equal to 0, it means we are moving to Mars.
  - Then increase ‘H’ by 3, ‘A’ by 2 and set ‘MOVE_MARS’ = 1. We then make a recursive call.
  - Set ‘MEMO[H][A]’ = 1+result received in above call and return ‘MEMO[H][A]’.
- If the ‘MOVE_MARS’ is equal to 1, it means we have to move either to Saturn or Venus.
  - Make two calls, one to Venus and other to Saturn by changing variables according to their effect and setting ‘MOVE_MARS’ = 0.
  - Set ‘MEMO[H][A]’ = 1+maximum of results received in above call and return ‘MEMO[H][A]’.
Return ‘MEMO[H][A]’.

Solve now

03 Approach

In the earlier approach, we tried to find all the possible solutions and select the one with maximum survival time, but we really do not need to find all the possible solutions. Instead, we will use some greedy approach. We can see that it is always beneficial to go to Mars so for every odd second, we will go to Mars. Now for even seconds, we are left with Venus and Saturn. So we will choose Venus if possible else we will choose Saturn, as Venus decreases health less than Saturn.

Initialize an integer variable ‘TURN’ = 0.
Run an infinite while loop:
- If ‘TURN’ is even (we can go to Mars) then do:
  - Increase ‘H’ by 3 and ‘A’ by 2.
  - Increase ‘TURN’ by 1.
- If ‘TURN’ is odd, it means we have to choose between Saturn or Venus. So, do:
  - If ‘H’ > 4 and ‘A’ > 8 (we can go to Venus):
    - Decrease ‘H’ by 4 and ‘A’ by 8.
    - Increase ‘TURN’ by 1.
  - Else if ‘H’ > 10 (we can go to Saturn):
    - Decrease ‘H’ by 10 and increase ‘A’ by 5.
    - Increase ‘TURN’ by 1.
  - If none of the above two conditions is met :
    - We can not make a move, so break the loop.
Return ‘TURN’.

Solve now