Approach for 2nd problem of LTIME71

general
1

Can someone please share their approach for Firdavs and Planet F.

2

You just need to realize that minimum cost is always |v_y−v_x|+y−x
Then you need to realize that maximum path = number of values (after sorting array) b/w v_x and v_y (inclusive both)
I did binary search for finding maximum path…
https://www.codechef.com/viewsolution/24108221

3 Likes
3

any hint for the 4th problm?

4

why min cost is that ?
I mean why an indirect shortest path is not possible?

5

idk… what was your approach for 3rd one ?

6

let cost = cost_1+cost_2
cost_2 is always y-x regardless of any path…
cost_1 is at least |v_y-v_x|
and hence its the min cost…

1 Like
7

B = MA/ (A - M) can be rewritten as B = M + M^2/(A - M).

Now just need to find all the factors of M^2 which is less than M and set the value of A to be (that factor + M).

8

ik this part… I did that… what was your approach… I found the prime factorization of M^2 and then recursive algorithm for finding multiplication of each subset…
just saw your solution… our “foo” is same

9

Yes, I did the same. I think you may miss the part where A is multiple of M.
For that I did B = M + M/(A/M - 1) seeing this it is clear that for the second part to be an integer the denominator must be a factor of M. So, also add those values in the answer set.

10

nope… only factors of M^2 which are \le M works for me…

11

Then I think that those values come automatically while computing the factors. My bad LOL

12

If you got the solution for CHEFRAMI then please share.

1 Like