de_dust2's blog

By de_dust2, history, 6 weeks ago, In English

Question from today's CodeFusion contest on Codechef.

Link to the problem : https://www.codechef.com/CFUS2020/problems/CFS2003/ Link to my solution : https://www.codechef.com/viewsolution/38007484

Can someone please help me with where I might be going wrong with my approach? Also kindly help me with the correct solution as well.

Explanation :

dp[i] - stores the minimum jumps to reach ith step
cnt[i] - stores the number of ways to reach ith step using minimum jumps (i.e dp[i]) 

And I keep inp[i], where if inp[i] = 1 then there is a portal at that step otherwise not
And I keep prevPor[i], which indicates position of previous portal 

Transition are defined below (while taking given constraints into considerations)
dp[i] = min(dp[i-1] + 1, dp[i-2] + 1, dp[index(prevPortal)] + 1)

 
 
 
 
  • Vote: I like it
  • -8
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Can someone please explain me the reason for downvotes. I'll try to fix the issue with the post.

»
6 weeks ago, # |
  Vote: I like it +25 Vote: I do not like it

The issue here is that codechef is garbage (as expected).

If you look at all the accepted solutions, on the test case

7 2
2 5

Their output will be

1 3

Instead of

2 3

The checker of this problem seems to have assumed that all optimal solutions will never skip a portal, and because this is wrong any correct solution will be rejected.