PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Neerav
Tester: Felipe Mota, Abhinav Sharma
Editorialist: Pratiyush Mishra
DIFFICULTY:
1888
PREREQUISITES:
None
PROBLEM:
Lav has an array A of size N. He noticed that Chef is initially standing at the first index of the array.
While standing at the i^{th} index (1β€i<N) of the array, Chef can perform the following types of jumps:
- πΉπππ π·: Jump to the immediate next index j such that Ai and Aj have the same parity.
- πΉπππ πΈ: Jump to the immediate next index j such that Ai and Aj have different parity.
Given that Chef can perform πΉπππ πΈ at most once, Lav wants to find the minimum number of jumps required by the Chef to reach the last index of the array.
EXPLANATION:
For each test case, the input consists of an array of size N.
Two cases are possible for this particular problem:
- When the first and last elements have same parity.
- When the first and last elements have different parity.
In the first case, if we perform Jump 2 even once then it is impossible for us to reach the destination(last element). So the number of jumps will be simply total number of elements in the array with same parity as the first element (obviously excluding the first element).
In the second case, we have to perform Jump 2 once which can be done at any element having the same parity as the first element. The total number of jumps in this case will be the jumps required to reach this element plus the number of jumps to reach the last element. This will be equivalent to the number of elements having the same parity as the first element till a particular element plus then the number of elements with different parity till the last element from here on. So, we to have to find the minimum value of this sum for any element in the array having the same parity as the first element. This can be achieved using two extra arrays and pre-computing these values.
TIME COMPLEXITY:
O(N) for each test case.
SOLUTION:
Editorialistβs Solution
Setterβs Solution
Tester-1βs Solution
Tester-2βs Solution