PROBLEM LINK:
Author: Kaushik N Doddamani
Tester: Kaushik N Doddamani
Editorialist: Kaushik N Doddamani
DIFFICULTY:
HARD
PREREQUISITES:
Basic Math, Logic, Arrays, Lists, Sorting.
PROBLEM:
There are M different types of toy cars. Each type of toy car has N number cars. There are M number of machines which produce cars of its corresponding type. For example, a “Type 1” machine would produce “Type 1” car only. There is only one machine for each type. Each machine has a special button that reverses the logic of the circuit used in the toy car. For example, if the logic circuit of the car is designed to move forward when turned ON then by pressing this special button on this machine, the car produced would move backward instead of moving forward similarly, if the logic circuit of the car is designed to move backward when turned ON then by pressing this special button on this machine, the car produced would move forward instead of moving backward thus revering the logic. K is the number of machines in which this special button is turned ON.
A car is said to have correct logic if and only if it moves forward when turned ON.
A car is said to have incorrect logic if it moves backward when turned ON.
The factory has produced M*N number of toy cars. Out of which there are some faulty cars produced with incorrect logic. In order to correct the logic, all the cars are put back into corresponding types of machine. If K is the number of machines in which the special button is turned ON (pressed), what is the maximum number of cars could be produced with correct logic.
QUICK EXPLANATION:
The special button of the machine corresponding to the ith type should be pressed. Such that ith type has a maximum number of cars with incorrect logic. This process should be followed K times. The result should be the sum of all the cars with correct logic.
EXPLANATION:
Let us define 3 functions namely, parser(), get_word(), get_number()
def parser():
while 1:
data = list(input().split(' '))
for number in data:
if len(number) > 0:
yield(number)
input_parser = parser()
def get_word():
global input_parser
return next(input_parser)
def get_number():
data = get_word()
try:
return int(data)
except ValueError:
return float(data)
In the above code when we invoke get_number() the function get_word() is invoked which in turn invokes the parser function. The parser() function is used to split the input values with “ “ (space) as a delimiter and convert the whole elements into a list. The elements of the list are returned element by element to the get_number() function through get_word() function. It returns an integer number if the number is in integer else a floating number.
T = get_number()
In the above code, we get the number of test cases as an input.
for i in range(0,T):
M = get_number()
N = get_number()
K = get_number()
Total = M * N
Correct = []
Final = []
for j in range(0,M):
Correct.append(get_number())
Correct.sort()
for k in range(0,K):
Final.append(N - Correct[k])
Final.extend(Correct[K::])
Ans = sum(Final)
print(Ans)
For each test case we perform some operations. Now, let’s look at these operations one by one.
M = get_number()
N = get_number()
K = get_number()
Here, we get the values of M, N and K (in integer or floating format)
Total = M * N
Correct = []
Final = []
for j in range(0,M):
Correct.append(get_number())
Correct.sort()
In the above code snippet we calculate the total number of cars, i.e. Given M types of cars and each type having N cars. Then the total number of cars would be M*N
Correct list is created to hold total number of cars of each type with correct logic.
Final list is created to hold the maximum number of cars with correct logic of each type.
With the help of for loop we get the total number of cars with correct logic for all the “M” types of cars. This list is then sorted in ascending order so that the lesser number cars belonging to a particular type with correct logic appears first. Thus, the lowest number of cars belonging to a particular type will appear as a first element in the list and the highest number of cars belonging to a type will appear as a last element in the list.
for k in range(0,K):
Final.append(N - Correct[k])
It is given that K number of machines have their special button pressed. So in order to maximise the total number of cars with correct logic, only those machines which belong to a type having the highest number of cars with incorrect logic has to be pressed. So that the result would be the maximum total number of cars with correct logic. We know that the list named “Correct” holds the total number of cars with correct logic, and as it is sorted in ascending order the types having lesser numbers of cars with correct logic would appear first. Therefore, the special button of the machine should be pressed for K types of elements.
We know that by pressing the special button on the machine the logic of the cars get reversed, therefore cars with correct logic would be incorrect and vice versa. Hence, given N number of cars out of we have X number of cars with correct logic. Then by pressing the special button of the machine we would get N-X number of cars with correct logic. Hence, we used N – Correct[k] in the for loop.
Final.extend(Correct[K::])
Ans = sum(Final)
print(Ans)
Out M types of machines we have K types of Machines with special button pressed remaining M-K machines are left as it. Therefore, the cars with correct logic will remain as correct and those with incorrect logic will remain as incorrect. Hence, we append the elements from Kth index position to the last into the “Final” list.
As we are expected to print the total number of cars with correct logic, we add all the elements of the list “Final” and assign it to variable Ans which is then printed.
ALTERNATE EXPLANATION:
One could make use of arrays instead of lists or any other similar data type. Here we used the complement method and sorting method to implement the given logic. One could also think of using a comparison approach or algorithms which could perform the same logic in a faster way.
SOLUTIONS:
Setter's Solution
def parser():
while 1:
data = list(input().split(' '))
for number in data:
if len(number) > 0:
yield(number)
input_parser = parser()
def get_word():
global input_parser
return next(input_parser)
def get_number():
data = get_word()
try:
return int(data)
except ValueError:
return float(data)
T = get_number()
for i in range(0,T):
M = get_number()
N = get_number()
K = get_number()
Total = M * N
Correct = []
Final = []
for j in range(0,M):
Correct.append(get_number())
Correct.sort()
for k in range(0,K):
Final.append(N - Correct[k])
Final.extend(Correct[K::])
Ans = sum(Final)
print(Ans)