Help with FROGV


The editorial gives a DP solution, but the first thing that came to my mind was a range max query on the distance between frogs. I’ve used a Sparse Table as my RMQ, however it gives a fatal runtime error (SIGABRT) while submitting. Can someone help me find the error in my approach?

( I’ve handled duplicate values with a condition s !- e ).

i tried to solve this problem my way, i did not read the editorial.

but i am getting WA and at this point i hate codechef.

1 Like

I kinda understand your logic, but not sure why WA.
CodeChef says this is easy. Should we jump off a cliff? :sob:

1 Like

@galencolin A little help here? :sweat_smile: I’ve been debugging this for days, and my mind is about to explode. The fatal error occurs in the maximum function of my Sparse Table. -> Latest Submission

Submission without the maximum function, no RE.

indeed :rofl:

In general the best thing to do is to “binary search” on the exact line that causes RE (don’t do this in short contests though)

When I remove the + 1 on line 20, it gets WA instead of RE.

…what exactly have you written

The K is essentially the max jump possible in the table + 1. I’ve initialized it K as floor(log2(n)) + 1, ans used “< K” in loops instead of “<= K”. Not sure why that resolves the RE. Some undefined behavior perhaps?

would you care to explain the maximum function in your code? and even we manage to solve it by sparse table…will it be a better method than simple sorting and precomputing parent for each i

The maximum function is a regular maximum function used for Sparse Tables. (I’m finding the max distance between two adjacent frogs). It has a lot of if conditions and return 0s because I was trying to debug it by submitting different versions to catch out of bounds error or log2 of negative number etc.

And as I have mentioned, this was the first thing that I thought of. It’s not a better solution, I’m just curious about what is causing the RE, so that I don’t repeat it!

I’m not sure what I did here, but this passed. :neutral_face:

i just did this problem with use of sets, and it took only 0.05 sec to run. i am new to DP and i am having a very hard time.

1 Like