The constraints partition will if consistent partition the range from 1 to b into several buckets where each bucket contains a certain number of elements.

Within each bucket that number can then get arbitrarily divided up between even and odd numbers.

So basically you keep track of the biggest possible difference between odd and even and even and odd and if they can be zero then it's valid.

I also checked that a partity constraint is satisified.

There is also a nice trick where if you add a fake (b,n) constraint that simplifies conding somewhat.

Once again, good work Errichto, as soon as I read Limak, I thought it will be a good contest.

Knew it was you once I read bears.

Can you please tell why this approach fails?

Initially My state was dp[i][j] which represented is it possible to have j even numbers till i th sorted upto (Note If I know that there are j even numbers I also know the total numbers till i hence I know the number of odd numbers)!

Now I can know the maximum amount of choices of even number and odd numbers by checking the difference of upto[i] and upto[i-1].

It failed for 2 tests!

Then I changed it to simple dp[i][j][k] represents is it possible to form a set of numbers till i th sorted upto such that it contains exactly j even numbers and exactly k odd numbers..

Link

It fails too!

I cannot understand why any of my solution fails(obviously they are incorrect , but why?)

Thanks!!