LOJ 1021 - Painful Bases, Shouldn't the tutorial Solution get TLE?

[ASADUZZAMAN-HEROK]

For Test case T=100, Each case has Base B=16, K=20, String 0123456789ABCDEF, The tutorial code should have 100 x 20 x 16 x 2¹⁵ which is over 10⁹. I checked the code with codeforces custom set. It took 4867 ms time.

Or am I missing something in the statement???

[rebornplusplus]

Yup, you are right. Dunno how I missed that back then. :man_facepalming: It takes 18.50s on my machine with the following input. Pre-calculating the values should fit in time. Let me know if you wanna update the tutorial.

@faiyaz26 @jan876 I think the dataset for 1021 is weak. The tutorial code runs in 596ms on LightOJ. (submission via vjudge)

Input data

``` 100 16 20 ABCDEF0123456789 16 19 0134728AEB965CDF 16 20 ABCDEF0123456789 16 19 0134728AEB965CDF 16 20 ABCDEF0123456789 16 19 0134728AEB965CDF 16 20 ABCDEF0123456789 16 19 0134728AEB965CDF 16 20 ABCDEF0123456789 16 19 0134728AEB965CDF 16 20 ABCDEF0123456789 16 19 0134728AEB965CDF 16 20 ABCDEF0123456789 16 19 0134728AEB965CDF 16 20 ABCDEF0123456789 16 19 0134728AEB965CDF 16 20 ABCDEF0123456789 16 19 0134728AEB965CDF 16 20 ABCDEF0123456789 16 19 0134728AEB965CDF 16 20 ABCDEF0123456789 16 19 0134728AEB965CDF 16 20 ABCDEF0123456789 16 19 0134728AEB965CDF 16 20 ABCDEF0123456789 16 19 0134728AEB965CDF 16 20 ABCDEF0123456789 16 19 0134728AEB965CDF 16 20 ABCDEF0123456789 16 19 0134728AEB965CDF 16 20 ABCDEF0123456789 16 19 0134728AEB965CDF 16 20 ABCDEF0123456789 16 19 0134728AEB965CDF 16 20 ABCDEF0123456789 16 19 0134728AEB965CDF 16 20 ABCDEF0123456789 16 19 0134728AEB965CDF 16 20 ABCDEF0123456789 16 19 0134728AEB965CDF 16 20 ABCDEF0123456789 16 19 0134728AEB965CDF 16 20 ABCDEF0123456789 16 19 0134728AEB965CDF 16 20 ABCDEF0123456789 16 19 0134728AEB965CDF 16 20 ABCDEF0123456789 16 19 0134728AEB965CDF 16 20 ABCDEF0123456789 16 19 0134728AEB965CDF 16 20 ABCDEF0123456789 16 19 0134728AEB965CDF 16 20 ABCDEF0123456789 16 19 0134728AEB965CDF 16 20 ABCDEF0123456789 16 19 0134728AEB965CDF 16 20 ABCDEF0123456789 16 19 0134728AEB965CDF 16 20 ABCDEF0123456789 16 19 0134728AEB965CDF 16 20 ABCDEF0123456789 16 19 0134728AEB965CDF 16 20 ABCDEF0123456789 16 19 0134728AEB965CDF 16 20 ABCDEF0123456789 16 19 0134728AEB965CDF 16 20 ABCDEF0123456789 16 19 0134728AEB965CDF 16 20 ABCDEF0123456789 16 19 0134728AEB965CDF 16 20 ABCDEF0123456789 16 19 0134728AEB965CDF 16 20 ABCDEF0123456789 16 19 0134728AEB965CDF 16 20 ABCDEF0123456789 16 19 0134728AEB965CDF 16 20 ABCDEF0123456789 16 19 0134728AEB965CDF 16 20 ABCDEF0123456789 16 19 0134728AEB965CDF 16 20 ABCDEF0123456789 16 19 0134728AEB965CDF 16 20 ABCDEF0123456789 16 19 0134728AEB965CDF 16 20 ABCDEF0123456789 16 19 0134728AEB965CDF 16 20 ABCDEF0123456789 16 19 0134728AEB965CDF 16 20 ABCDEF0123456789 16 19 0134728AEB965CDF 16 20 ABCDEF0123456789 16 19 0134728AEB965CDF 16 20 ABCDEF0123456789 16 19 0134728AEB965CDF 16 20 ABCDEF0123456789 16 19 0134728AEB965CDF 16 20 ABCDEF0123456789 16 19 0134728AEB965CDF 16 20 ABCDEF0123456789 16 19 0134728AEB965CDF ```

[jan876]

Since the problem is old, I am adding a limit to the length of the number which is 12.

My solution was around the fact that for each (base, mod) you can run a single dp, since the characters are distinct, your mask is just what characters you are using. This solution works for worst case scenarios really well.