Minimum Gifts
Problem Description
A Company has decided to give some gifts to all of its employees. For that, company has given some rank to each employee. Based on that rank, company has made certain rules to distribute the gifts.
The rules for distributing the gifts are:
Each employee must receive at least one gift.
Employees having higher ranking get a greater number of gifts than their neighbours.
What is the minimum number of gifts required by company?
Constraints
1 < T < 10
1 < N < 100000
1 < Rank < 10^9
Input
First line contains integer T, denoting the number of testcases.
For each testcases:
First line contains integer N, denoting number of employees.
Second line contains N space separated integers, denoting the rank of each employee.
Output
For each testcase print the number of minimum gifts required on new line.
Time Limit
1
Examples
Example 1
Input
2
5
1 2 1 5 2
2
1 2
Output
7
3
Explanation
For testcase 1, adhering to rules mentioned above,
Employee # 1 whose rank is 1 gets one gift
Employee # 2 whose rank is 2 gets two gifts
Employee # 3 whose rank is 1 gets one gift
Employee # 4 whose rank is 5 gets two gifts
Employee # 5 whose rank is 2 gets one gift
Therefore, total gifts required is 1 + 2 + 1 + 2 + 1 = 7
Similarly, for test case 2, adhering to rules mentioned above,
Employee # 1 whose rank is 1 gets one gift
Employee # 2 whose rank is 2 gets two gifts
Therefore, total gifts required is 1 + 2 = 3
Count Pairs
Problem Description
Given an array of integers A, and an integer K find number of happy elements.
Element X is happy if there exists at least 1 element whose difference is less than K i.e. an element X is happy, if there is another element in the range [X-K, X+K] other than X itself.
Constraints
1 <= N <= 10^5
0 <= K <= 10^5
0 <= A[i] <= 10^9
Input
First-line contains two integers N and K where N is size of the array and K is a number as described above
Second-line contains N integers separated by space.
Output
Print a single integer denoting the total number of happy elements.
Time Limit
1
Examples
Example 1
Input
6 3
5 5 7 9 15 2
Output
5
Explanation
Other than number 15, everyone has at least 1 element in the range [X-3, X+3]. Hence they are all happy elements. Since these five are in number, the output is 5.
Example 2
Input
3 2
1 3 5
Output
3
Explanation
All numbers have at least 1 element in the range [X-2, X+2]. Hence they are all happy elements. Since these three are in number, the output is 3.
Code in python3 ans in 3 sec
inp = input().split(" ")
n = int(inp[0])
k = int(inp[1])
arr = [int(i) for i in input().split()][:n]
count = 0
for x in range(n):
add = 0
sub = 0
add = arr[x] + k
sub = arr[x] - k
for j in range(n):
if j == x:
continue
else:
if arr[j] >= sub and arr[j]<= add:
count = count + 1
break
print(count,end="")
Railway Station
Problem Description
Given the schedule of trains and their stoppage time at a Railway Station, find the minimum number of platforms needed.
Note -
If Train A's departure time is x and Train B's arrival time is x, then we can't accommodate Train B on the same platform as Train A.
Constraints
1 <= N <= 10^5
0 <= a <= 86400
0 < b <= 86400
Number of platforms > 0
Input
First-line contains N denoting number of trains.
Next, N line contains 2 integers, a and b, denoting the arrival time and stoppage time of the train.
Output
A single integer denoting the minimum numbers of platforms needed to accommodate every train.
Time Limit
1
Examples
Example 1
Input
3
10 2
5 10
13 5
Output
2
Explanation
The earliest arriving train at time t = 5 will arrive at platform# 1. Since it will stay there till t = 15, train arriving at time t = 10 will arrive at platform# 2. Since it will depart at time t = 12, train arriving at time t = 13 will arrive at platform# 2.
Example 2
Input
2
2 4
6 2
Output
2
Explanation
Platform #1 can accommodate train 1.
Platform #2 can accommodate train 2.
Note that the departure of train 1 is the same as the arrival of train 2, i.e. 6, and thus we need a separate platform to accommodate train 2.
Code in python3 answer in 3 sec
# Program to find the minimum number of platforms required on a railway station
# Returns minimum number of platforms reqquired
def findPlatform(arr, dep, n):
# Sort arrival and
# departure arrays
arr.sort()
dep.sort()
# plat_needed indicates
# number of platforms
# needed at a time
plat_needed = 1
result = 1
i = 1
j = 0
# Similar to merge in merge sort to process all events in sorted order
while (i < n and j < n):
# If next event in sorted order is arrival, increment count of platforms needed
if (arr[i] <= dep[j]):
plat_needed+= 1
i+= 1
# Else decrement count of platforms needed
elif (arr[i] > dep[j]):
plat_needed-= 1
j+= 1
# Update result if needed
if (plat_needed > result):
result = plat_needed
return result
# driver code
arr = [900, 940, 950, 1100, 1500, 1800]
dep = [910, 1200, 1120, 1130, 1900, 2000]
n = len(arr)
print("Minimum Number of Platforms Required = ",
findPlatform(arr, dep, n))
# This code is contributed
# by Shivam goyal
Faulty Keyboard
Problem Description
Mr. Wick has a faulty keyboard. Some of the keys of the keyboard don't work. So he has copied all those characters corresponding to the faulty keys on a clipboard. Whenever those characters need to be typed he pastes it from the clipboard. In typing whatever is required he needs to make use of paste, backspace and cursor traversal operations. Help him in minimize the number of operations he needs to do to complete his typing assignment. Each operation has one unit weightage.
Constraints
1 <= S <= 16
1 <= T<= 10^4
String T and S will only be comprised of letters a-z and digits 0-9
Input
First-line contains text T to be typed the Second line contains string S of all the faulty keys pasted on the clipboard
Output
Print the minimum number of operations required for typing the text T
Time Limit
1
Examples
Example 1
Input
experience was ultimate
ew
Output
14
Explanation
experience =(2+2+2+2) =[ {p+b} + {p+b} +{p+b} +{p+b} ]
was=(4)=[ p+m+b+m]
ultimate=(2)=[ p+b ]
where p=paste, b=backspace ,m= move cursor
Example 2
Input
the supreme court is the highest judicial court
su
Output
17
Explanation
supreme =(1) =[ p]
court=(4)=[ p+m+b+m]
is=(2)=[ p+b ]
the=(0)
highest=(2)=[p+b]
judicial=(4)=[p+m+b+m]
court=(4)=[p+m+b+m]
The Angel vs Devil
Problem Description
In a board game of dimension(12x12) called Angels vs Devils, various Devils try to kill an Angel whose aim is to get across the board. Each Devil has different powers.
The starting point of the Angel can be on any border but not on the corners of the board. The starting point will be provided as input. Angel will walk in a straight line across the board. Starting points of all three types of devils will be provided as input. Their powers are as follows.
LUCIQUARE (L): His starting point can be on any of the four borders of the board. He leaves a poison trail and moves in 'L' shape such that it is possible to create the biggest square along with the borders of the board. Square may or may not be formed in 12 seconds within which the angel crosses from one end of the board to other.
THREE LEGGED EEK (E): She is a large three legged devil. She crushes the angel if he comes into any of those 3 boxes where her legs are placed. She can only walk diagonally and starts moving towards the cell A1. If she reaches the border she returns on the same path and keeps moving to and fro like this.
For example the image below she is where its mentioned E1 in the 1st second, she is at E2 in the 2nd second, E3 in the 3rd second, in the 4th second she is again in the squares where E2 is mentioned, in the 5th second she is again in the squares where E1 is mentioned, in the 6th second she is in the squares where E6 is mentioned, in the 7th second she is in the squares where E7 is mentioned since she has reached border of the board she will move back again in the same path.
MUTO (M): He can be move to other cells without the need to traverse the path. He can be present at vertically, diagonally, horizontally opposite cells at subsequent seconds. He makes these moves in clockwise manner. If angel comes on the same cell as him, he will convert the Angel into a Muto.
Note:- All four entities move at the speed of 1 cell per second.
Constraints
Angel starts from any of the four borders but not from the corners.
Starting points of angel and all the devils will be different.
In case angel moves to a cell where he meets more than one devil, the angel dies.
It is possible that two or more devils are present in the same cell in the same second
Input
First Line provides the cell(row, col) which is the starting point of Angel
Second Line contains types of devils in order denoted by { L, E, M } separated by '|'
Third Line contains starting points of devils in order mentioned in the 2nd line of input separated by '|'
Output
Output depends on events that occur in 12 second window.
· If Angel successfully crosses the board print 'WON'
· If Angel gets converted into muto print 'MUTO'
· If Angel dies then print the cell number in which the Angel died
Time Limit
1
Examples
Example 1
Input
I12
E|M|L
D9|C2|F1
Output
WON
Explanation
Initial Board Position is displayed in the image by Bold Initials (A1, E1, M1, L1) on the board. Their positions in subsequent seconds is displayed by A2,A3, and E2,E3 and so on. At 2nd Second of the game, Angel will be at I11, EEK will be at B9,C8, and D7. Muto will be at J2 and Luciquare will move to F2 leaving the trail behind.
As shown in the image, EEK will be moving to and fro and will not come in the path of the Angel. Muto can only be at points C2,J2,J11, and C11 at any point in the game. These points also don't come in path of the Angel.
Angel will come at box I7 in the 6th second, Luciquare will take 10 seconds to reach there. Hence Angel will not be in the path of any of the devils. So the outcome will be that the angel will cross the board. Hence, the output will be 'WON'.
Example 2
Input
L3
M|L|E
C10|F12|G3
Output
MUTO
Explanation
MUTO and Angel will be in the same box in the third second and Muto will convert the Angel into a Muto. So the output will be 'MUTO'.
Example 3
Input
A5
E|L|M
H4|J1|K3
Output
J5
Explanation
Angel will be killed at position J5 because of Luciquares's poisonous trail.
Travel Cost
Problem Description
Suresh wants to travel from city A to city B. But due to coronavirus pandemic, almost all the cities have levied entry tax into the cities so that the number of people entering the city can be limited. Suresh can skip at the most m cities at a time. Suresh has to declare his itinerary at the time of leaving city A. Thus he will have to pay upfront for entire itinerary and also has to pay a fee to get the slips issued. Upon payment he will be given the slips for intermediate cities where he has to show the slips to pass through, en route to his destination.
Some cities have enforced lockdown, that means those cities have blocked the entry into the cities and you will have to skip the cities in any case, such cities are represented by -1. This information is known to Suresh upfront.
Help Suresh find the minimum amount to be paid to reach from City A to City B
Constraints
No of cities <=10^5
Input
First line contains an integer N, denoting the number of cities
Second line contains N space separated integers, where first integer denotes the cost of issuing itinerary slips and next (N-1) integers denote the entry fee of all cities. The last integer is always the destination city. If city is under lock down then its entry fee will be -1.
Third line contains an integer, M which represents number of cities he can skip from a present city during his travel
Output
Single integer which represents the minimum cost Suresh has to pay to travel from city A to B, but if city B is not reachable then print -1
Time Limit
1
Examples
Example 1
Input
5
1 6 -1 5 7
1
Output
19
Explanation
Since he could skip only 1 city between the cities. He will have to pay 1+6+5+7, where 1 is the fees paid to issue slips and [6,5,7] are the fees paid for the entry to the respective cities. So the total amount he has to pay while leaving A is 19.
Example 2
Input
4
3 4 1 -1
3
Output
-1
Explanation
Since the city B is under lockdown, he cannot go to city B. Hence the output is -1
