HackWithInfy 2022

Правка en2, от prithwiraj15, 2022-03-15 21:41:46

This question appeared on HackWithInfy 2022

Problem Statement

You are given an array of length N containing a permutation of the first N natural numbers i.e (1 to N). You are able to apply the following operation at most once.

  • Choose any subarray of size K and reverse it.

Return the minimum inversions in the array after said operations.

Note — Inversion in an array is defined as a pair of indices (i,j) such that Ai > Aj and i < j.

Constraints

1 <= N <= 5 * 10^3

1 <= A[i] <= N

1 <= K <= N

Sample Test Case — 1

Arr = [1, 2, 3, 4], K = 2

Ans — 0

Explanation

Array initially has 0 inversions. Hence no need to apply any operations.

Sample Test Case — 2

Arr = [4, 3, 5, 1, 2], K = 2

Ans — 6

Explanation

If we reverse the subarray [4, 3], we get Arr = [3, 4, 5, 1, 2].

The resultant inversion is 6. It is the minimum that we can get.

Sample Test Case — 3

Arr = [1, 4, 2, 3, 5], K = 3

Ans — 1

Explanation

If we reverse the subarray [4, 2, 3], we get Arr = [1, 3, 2, 4, 5].

The resultant inversion is 1. It is the minimum that we can get.

Can anyone solve this problem ???

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский prithwiraj15 2022-03-15 21:41:46 796 Tiny change: 'st once.\n- Choose' -> 'st once.\n\n- Choose' (published)
en1 Английский prithwiraj15 2022-03-15 21:22:46 461 Initial revision (saved to drafts)