 # EOOPR Infinity 2020 Rated

It should be %4 in your last case where you print 3.

3 moves is okay. 2 moves in x<y case is difficult to find

Is there anyone who used segment tree+lazy in SOLDVAL or just me What did you stored in the segment tree ?

what will a,b ?? when x=2,y=12

1 Like

Take a = 5, use `X = X + a` twice, choose any b, it won’t matter.

1 Like

or just tell how did u use segment tree to solve this problem ?

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

By adding 3 twice. You check out EOOPR - Editorial for better understanding.

1 Like

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) .

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

yes 1 Like

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

6 Likes

You are right, I missed it.