JS Editorial

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

1 Like

recursive dynamic programming solution (O(n))
click here

1 Like

i did it with binary search in O(nlogn)
(even though it is not optimal I just wanted to share a different method that can also be accepted…)
here is the solution
https://www.codechef.com/viewsolution/63279818

I wrote the same logic as told in editorial. Except for subtask 1 and subtask 2, all subtask passed. Can anyone look at the code please and tell the reason? Code link (It’s in C++)

Solution link (explained my approach in comments)
Implemented a dp solution, but it is giving errors for first two subtasks.
Can anyone help me in debugging ?


/*
	dp[i][0] = min jumps to reach idx i without using jmp2
	dp[i][1] = min jumps to reach idx i using jmp2

	dp[i][0] = 0, dp[i][1] = 0
	it takes 0 steps to get at first step

	Case 1: if current elem is odd
		we can come from
		a) prev odd (come to prevOdd without using jump2 & used jump1 here)
		b) prev odd (come to prevOdd using jump2 & used jump1 here)
		c) prev even (come to prevOdd without using jump2 & used jump2 here)

		dp[i][0] = dp[prevOdd][0] + 1;
		dp[i][1] = min(dp[prevOdd][1], dp[prevEven][0]) + 1;

	Case 2: if current elem is even
		we can come from
		a) prevEven (come to prevEven without using jump2 & used jump1 here)
		b) prevEven (come to prevEven using jump2 & used jump1 here)
		c) prevOdd (come to prevOdd without using jump2 & used jump2 here)

		dp[i][0] = dp[prevEven][0] + 1;
		dp[i][1] = min(dp[prevOdd][0], dp[prevEven][1]) + 1;
	*/

check your code for array 2 1 1 2 1 1

1 Like

Thanks! your testcase helped to find bug in my code.

can you please explain your approach in brief or comment your code.