You are not logged in. Please login at www.codechef.com to post your questions!

×

MAGA - Editorial

PROBLEM LINK:

Practice
Contest

Author: Sidhant Bansal
Testers: Hasan Jaddouh
Editorialist: Sidhant Bansal

DIFFICULTY:

medium

PREREQUISITES:

dynamic programming

PROBLEM:

Observation - A dp solution would work because let us say that we have computed the best answer for the subarray i + 1 to (n - (i + 1) + 1) then if want to extend this answer for the subarray i to (n - i + 1) (i.e adding a single element on both sides) then we only need the information wether i + 1 was swapper or not and the information that weather i will be a local maxima/minima.

First for notation let us now use rev(i) = n - i + 1 in the following explanation for simplicity.

This leads us to the dp state -

dp(index, isLocalMaxima, isSwapped) = the minimum no. of swaps required to make the subarray from index to rev(index) a valid subarray where isLocalMaxima (a boolean) denotes wether index is a local maxima or not and isSwapped (a boolean) denotes wether index is swapped with rev(index) or not.

So our final answer would be min(dp(1, 0, 0), dp(1, 0, 1), dp(1, 1, 0), dp(1, 1, 1)), i.e all possibilites of dp states which consider the array from 1 to N.

Now the recurrence forming is hard in this question mainly due to the exhaustive casework.

Firstly for N = even and N = odd, then also for the different conditions of booleans (isLocalMaxima, isSwapped).

Let me demonstrate one of these cases and I expect the reader to form the others in a similar way.

Example -

N = 10 (even)

We have to calculate let us say dp(3, 1, 1). Then dp(3, 1, 1) = answer for subarray from 3 to 8 where the current element(i.e 3 and 8) are swapped and currently 3rd element (after swapping) is the local maxima. Since n is even, so 3 is mapped to 8, where 3 is an odd number and 8 is an even number. This implies that if 3rd element (after swap) is a local maxima then 8th element (after swap) is a local minima.

So here this state is dependent upon 2 cases - (In every case 3rd element is swapped and it is the local maxima, since isLocalMaxima = 1, isSwapped = 1, ).

Case 1 - 4th element is SWAPPED, called if A[rev(3)] > A[rev(4)] and A[3] < A[4]

Case 2 - 4th element is NOT SWAPPED, called if A[rev(3)] > A[4] and A[3] < A[rev(4)]

So here the dp(3, 1, 1) = 1 + min(case1, case2), where we trigger these cases only if the satisfy the conditions and add a +1 because we are swapping the 3rd element.

Here the base cases for N = even, will be filling dp[n/2][a][b], for a = 0 and 1, and b = 0 and 1. Incase N = odd, we would be filling dp[(n + 1)/2][a][b], for a = 0 and 1, and b = 0 and 1.

Please refer to the author solution for better clarity regarding the base cases and case work. In author solution isUp is equivalent to isLocalMaxima and the satisfy(a, b, c) function checks if the elements a and b satisfy the inequality when a is placed just one index before b and it is the local maxima if c = 1, and a local minima when c = 0.

SOLUTIONS

Setter's solution.
Tester's solution.

This question is marked "community wiki".

asked 24 Jan '18, 13:28

sidhant007's gravatar image

6★sidhant007
179819
accept rate: 12%

edited 25 Jan '18, 08:12

admin's gravatar image

0★admin ♦♦
19.8k350498541


This link is not directly available in questions editorial please attach editorial to the question.

link

answered 24 Jan '18, 17:51

im_amartya's gravatar image

3★im_amartya
32
accept rate: 0%

done, thanks for notifying.

(25 Jan '18, 08:12) admin ♦♦0★

What's the role of wow in solve()? @sidhant007 I couldn't understand how it has been used to check for different cases!

link

answered 25 Jan '18, 12:08

dushyant7917's gravatar image

5★dushyant7917
716
accept rate: 0%

edited 25 Jan '18, 12:13

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,575
×2,165
×82

question asked: 24 Jan '18, 13:28

question was seen: 759 times

last updated: 25 Jan '18, 12:13