Batteries

Hard
0/120
Average time to solve is 50m
profile
Contributed by
0 upvote

Problem statement

You have to go to a city at night which is 'M' miles away from you, using your torch and a portable charger. Initially, your torch has 'B' units of battery level. Your torch can't glow while charging, so you can't move forward while charging your torch's battery.

Every hour, you can choose to do either one of the following two things with your torch:

1. Charge: Your torch's battery level will increase by one unit.
2. Glow: You will cover one mile of your journey and if you had not walked in the previous hour, your torch's battery level would remain the same; otherwise, it will decrease by one unit more than it had decreased in the previous hour.

For example, if you walk for the first hour, the battery level will decrease by 0, i.e., remain the same, then again if you walk in the next hour, the battery level will decrease by 1, then in the next hour walk by 2, and so on. Then if you charge for an hour, the battery level will increase by 1, then in the next hour, if you choose to walk, the battery level will decrease by 0, and so on.

Note: The battery level should never go below 0.

You have to reach the city in the minimum possible time. If there are multiple ways in which you can reach the city in minimum time, you'll choose the way in which you can retain the maximum battery level.

For Example : 
Let 'M' = 2, 'B' = 0.
We do the following moves:

"Glow", Battery level decreases by '0', we walk one mile towards the city.
"Charge", Battery level increases by '1'.
"Glow", Battery level decreases by '0', we walk one more mile towards the city.

Thus, we reached the city in '3' hours with a battery level of '1'.
Therefore the answer is '3 1'.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains a single integer 'T', which denotes the number of test cases.
Then 'T' test cases follow. For each test case:

The first line contains two integers, 'M' and 'B', denoting the initial distance from the city and the initial battery level of the torch, respectively.
Output Format : 
For each test case, return the minimum time it will take to reach the city and the maximum possible remaining battery level after reaching the city in that minimum time.
Note : 
You don’t need to print anything. Just implement the given function.
Constraints : 
1 <= 'T' <= 10
1 <= 'M, B' <= 10^9

Time Limit: 1 sec
Sample Input 1 :
2
3 21
18 138
Sample Output 1 :
3 18
19 67
Explanation of sample input 1 :
First test case:-
We can simply do the "Glow" operation 3 times in a row to reach the city in '3' hours.
The first "Glow" changes the battery level from '21' to '21'. ( - 0 )
The second "Glow" changes the battery level from '21' to '20'. ( - 1 )
The third "Glow" changes the battery level from '20' to '18'. ( - 2 )
Thus, the answer is '3 18'.

Second test case:-
We can do 9 "Glow" operations followed by a "Charge" operation followed by another 9 "Glow" operations to reach the city in '19' hours.
Consecutively performing 9 "Glow" operations decreases the battery level by '0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 = 36' units.
The first 9 "Glow" operations change the battery level from '138' to '102'. ( - 36 )
The "Charge" operation changes the battery level from '102' to '103'. ( + 1 )
The last 9 "Glow" operations change the battery level from '103' to '67'. ( - 36 )
Thus, the answer is '19 67'.
Sample Input 2 :
2
217 19
100 131
Sample Output 2 :
320 0
124 5
Hint

Binary search on the number of "Charge" operations.

Approaches (1)
Binary Search + Maths

Approach:

  • We need at least 'M' "Glow" operations to reach the city, therefore we need a minimum of 'M' hours to reach the city.
    • However, due to the additional constraint of maintaining a non-negative battery level, we might need to do some "Charge" operations.
  • We can notice that if we can reach the city by using 'X' "Charge" operations then we can also reach the city by using 'X + 1' "Charge" operations.
    • Thus, we can use binary search to find the minimum number of "Charge" operations needed to reach the city.
  • All that remains is to check if the battery level remains non-negative throughout the journey when any 'X' number of "Charge" operations are allowed.
  • If we have 'X' "Charge" operations it is best to distribute them between the "Glow" operations uniformly, to have the maximum remaining battery level.
  • Now let us make the complete algorithm:
    • The initial battery level is 'B'.
    • Define 'part' as 'M / (X + 1)'. Define 'cnt' as 'X + 1 - (M % (X + 1))'.
    • We can split the entire sequence of operations into three sections :
      • Section 1: 'part' times "Glow" operation.
      • Section 2: repeat 'cnt - 1' times: A single "Charge" operation followed by 'part' consecutive "Glow" operations.
      • Section 3: repeat 'X + 1 - cnt' times: A single "Charge" operation followed by 'part + 1' consecutive "Glow" operations.
    • The battery level reduction by 'p' consecutive "Glow" operations is '(p * (p - 1)) / 2'. The battery level increase by a single "Charge" operation is 1.
    • Thus we can process all three sections of the sequence of operations one by one, if the current battery level is negative after any section, it is impossible to reach the city in 'X' "Charge" operations.
    • Otherwise, it is possible to reach the city in 'X' "Charge" operations and the final battery level is the maximum possible battery level.
  • Thus we have solved the problem in O(log(M)).

 

Algorithm:

  • Create a function 'calc( x )' that returns the maximum battery level after reaching the city in 'M + x' hours and '-1' if it is impossible to reach the city in 'M + x' hours. calc( x ) :
    • Initialize a variable 'battery = B'.
    • Initialize variables 'part = m / (x + 1)', cnt = 'x + 1 - (m % (x + 1))'.
    • Decrement 'battery' by '(part  * (part - 1)) / 2'.
    • If ( battery < 0 ) :
      • Return '-1'.
    • Decrement 'battery' by '((part  * (part - 1)) / 2 - 1) * (cnt - 1)'.
    • If ( battery < 0 ) :
      • Return '-1'.
    • Decrement 'battery' by '(((part + 1)  * part) / 2 - 1) * (x + 1 - cnt)'.
    • If ( battery < 0 ) :
      • Return '-1'.
    • Return 'battery'.
  • Initialize variables 'L = 0' and 'R = M - 1'.
  • While ( L < R ) :
    • Initialize variable 'mid = ( L + R ) / 2'.
    • If ( calc(mid) != -1 ) :
      • Set 'R' to 'mid'.
    • Else :
      • Set 'L' to 'mid + 1'.
  • Return '[ M + L, calc(L) ]'.
Time Complexity

O(log(M)), where 'M' is the initial distance from the city.
 

We perform a binary search in the range [0, M - 1], and then perform mathematical operations in the predicate function. Thus, the overall time complexity is of the order O(log(M)).

Space Complexity

O(1).
 

We only use constant extra space. Thus, the space complexity is of the order O(1).

Code Solution
(100% EXP penalty)
Batteries
Full screen
Console