Biteration #3 Contest Discussion

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.


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.

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

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

did it worked?

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

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


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

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

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

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.

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

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.

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

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

1 Like

Can anyone please tell the approach to solve C question?

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.

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

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

1 Like

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

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