Problem - Chef and Digits
Editorial - DGTCNT - Editorial
I tried to solve using the approach mentioned in editorial, i.e use
You can use a simple digit dp for it, the state of the dp will be dp(i, tight, mask) meaning that we are currently processing i-th digit and tight will denote the current prefix of number being generated is equal to the prefix of n or not, mask will denote the digits that have appeared till now. We can process the current index by trying all possible digits at the i-th place and making transitions.
I implemented using the same approach, but I am getting the wrong answer as I am overcounting the number of valid integers.(It fails on sample cases and various small cases I tried)
If anyone can review why my approach fails. It would be really helpful to me.