All editorials have been posted Here

how to move from 4 to 10 in 2 steps ?

how to move from 4 to 10 in 2 steps ?? please explain

Ok thanks

Simply do range minimum query with range updates(lazy)

First create a array with values a[i]+i.

then build a segment tree from this array.

Iterate from 0 to N-1

->update seg tree with +1 from 0 to i-1 and -1 from i to N-1,

->then find minimum from 0 to N-1

https://www.codechef.com/viewsolution/39305830

Can someone please explain which testcase is failing the above solution, i tried every possible testcase, unable to find.

could have solved using just two for loops works in O(N) .

yes

Corner case was to calculate Minimum number of steps needed to achieve an even sum (target) , with one positive odd number (a) and one negative even number(b).

We cannot change a and b.

Find such two numbers and print number of steps.

Mathematically, n * odd_number - m * even_number = sum , You have to Minimize value of (n+m) i.e steps

Maximum *3* number of steps will be needed to achive even sum.

How?

Add odd number (a) to x

Add odd number (a) to x again [Now difference between x and y is even]

Subtract even number (b) from x [even number - even number= even number , x becomes y in this step]

Reference:

odd+odd=even

even-even=even

**Approach 1**: so,we will add 'a' 2 times which becomes an even number and then subtract 'b' from it , which will be our answer.

**Approach 2**: Another case would be , if an odd number(largest) divides the target sum , then number of steps = target/oddnumber.

So answer will be Minimum(Approach 1 , Approach 2)

For example,

Test case is to make x to y,

where x=5 ,y=41 , Target = y-x = 41-5 = 36

**By Approach 1:**

Take 'a' >Target , so a = 37 (must be odd)

Add a to x , x = 42----------------------------------------------------------------------(1 step)

Add a to x , x = 79----------------------------------------------------------------------(1 step)

[odd+odd=even]

As we exceeded the target , we have to subtract a number from it which is b.

b= difference = x-y = 79 - 41 = 38

b= 38, which is even.

Subtract b from x , which comes out to be 41 ,i.e y --------------------------------(1 step) [even-even=even]

x=x-b= 41 =y

**Approach 1 took 3 steps.**

**By Approach 2:**

Largest odd number which divides 36 is 9.

How?

Keep on dividing 36 by 2 and stop when the number is odd.

**Total number of steps by approach 2: 36 / 9 = 4**

Answer=Minimum(Approach 1 , Approach 2) = Minimum(3,4) = 3

You are right, I missed it.

how did you get 36 here?

in approach 2

Input -

x=5 , y=41

Difference = 36

So, 36 is maximum number of steps needed to achieve 41 from 5 (just add '1' 36 times)

what would be minimum number of steps?You will obviously minimize 36 to an extent which is possible.

Understood?

Can you please explain, for x<y, if the difference is even and it will be not divisible by 2… how can we moves in 2 steps?

you can’t do that in 2 steps it will take 3 because even +odd(a) -even(b)=odd so never gonna get 10 or would you explain if something Is wrong with my explanation for x=2 and y=10

Sure.

For X = 4 , Y = 10, add 3 twice, So min steps = 2

For X = 2 , Y = 10, add 5 twice. So min steps = 2

we can do this

a=36 ,b=1

x+36=y

1 round only

Read the question again Buddy!

if x=6 and y=10

So the difference is 4 which is divisible by 4 ,accoridng to the solution the answer must be 3 but

10 can be achieved by adding +3 and +1 so no.of steps is 2.

can anyone please explain this?