Biteration #3 Contest Discussion

1

Link: Biteraton #3

I can only solve A and B.
How to solve C and D?
If anyone can give hints would be useful. Thank you.

Between the problems were very nice. Appreciate the efforts of team. Loved it.

2 Likes
2

got wrong answer on problem BIT3E (D-Minimum Cost) here is my approach My solution.
Any help with any testcase is highly appreciated.
Thanks in advance.

3

Whats the correct approach for B,(jumping Monkey) My Solution
I tried to do it with recursive dp, with states of current_index and parity? Where I am wrong, what’s wrong in my code.
Kindly help

4

In B I tried to take as maximum steps as I can and if I can’t reach ans is -1 else ans is the smallest possible

5

did it worked?

i did the same only i tried from last region. WA

6

yes! This question can be easily solved by some optimization to greedy

here https://www.codechef.com/viewsolution/34735242

7

but for that you have to go for all index from index + 1 to index + k, somehow you have to do that recursively? Please correct if I am wrong

8

from index + k to index + 1, we want to maximize size of steps.

9

yeah that’ ok I guess that would not make any difference if I am going to explore each step

10

Nope! if you can reach from i + c to n then you can always reach n from i + d where d > c .

And you can also reduce duplicate checking by remembering the last pos you were on.

11

you said from index + 1 to index + k if you literally did this <- you would find that max possible number of steps.

12

Okkk I guess I get What I was doing wrong, it’s possible to solve it using greedy technique instead of forcing DP into it.

13

but I am taking the minimum of all possible paths, Can you please look into my code I provided the soln link above

15

please look into the main function, I stored the no. as 0 or 1

1 Like
17

Can anyone please tell the approach to solve C question?

18

you are going for unoptimized search… you are going for every poosible move… which is too heavy to implement in 1 sec.
try this optimization, in every search call… go for only point which is farthest from current.

19

This might be the culprit
in recursive function you did int ans = INT_MAX;

but in main function you’re checking
if(ans1 == INT_MIN and ans2 == INT_MIN)

1 Like
20

If L = 1 then smallest cyclic shift in any other case it is possible to get sorted string.

1 Like
22

hey can you brief this? I can’t get it why this is the case with l > 1

23

If l>=2 you can swap adjacent elements over a course of n moves so sorting is possible.

3 Likes