It is a name of a technique. It is also called node-ordering.

LOJ - 1068

Let's generalize the problem. Given a number (1 <=) N (<= INT_MAX). Find how many numbers in the interval [0, N] are divisible by (1 <) K (< 1e4).

So you've to make all the numbers from 0 to N, how to do it? In each state, suppose you have made a number. Now try to place digits (0 — 9) after it and check if the new number is smaller or equal to N. Say, N = 1652 and current number = 165. So the valid numbers are :

        165 * 10 + 0 = 1650
        165 * 10 + 1 = 1651
        165 * 10 + 2 = 1652

These are the new numbers we can make. But handling integers will cause MLE. So you've to treat them as string. Again passing whole string would be stupid too. So let's optimize it. In current state, what you really need to know is how to make a valid new number? That is, which digits you can place (or till which digit you can place starting from 0). Now, in any previous state, if you have placed a smaller digit corresponding to N's digit, then current number is absolutely smaller then N and whatever you place after this number will be smaller then N.

        N = 1652
        current number = 155
        So you can place any digit after 155 to make a valid number

Now, if you haven't placed any smaller digit corresponding to N's digit, then you can from 0 to N's corresponding digit.

        N = 1652
        current number = 165
        So you can place 0, 1 and 2 after 155 to make a valid number

And of course this process would continue till length length (intToString (N)). So one DP state is [pos], another is [preSmall]. One more state is left (divisibility).

Now, checking for divisibility. Following code-segment would do the work :

DP (int pos, int moded, bool preSmall) {
        moded *= 10;
        for (....) DP (pos + 1, (moded + digit) % K, ...);
}

After making a number, if moded is 0, then the number is divisible by K.

The value of moded will be [0,K). So the total complexity will be len * K * 2. And maximum value of len will be at most 10.

This is the solution of the generalized problem. To get the expected result, simply do solve (B) - solve (A - 1).

Thanks

Wish your blog would come in English version..~~~

Ok sorry, I got you now :)

I've never been such situation (actually you are a better coder then me), I got AC with karpRobin (a hashing-based algorithm) for large strings. There are some hashing algorithms for avoiding (minimizing) collision (of course I know none of them :D) that you can use (and I think they ar impractical for contest). And if you get WA for a particular prime number and pretty confident that your algorithm is correct, why not try with a different prime (I would surly do that)? :p

Well it will be ok as long as you are using hashBase > 26 for this problem. Here string size will be at most 10 characters. So the hashValue will be distinct until you take a hashBase enough large so that hashValue crosses the limit of the data type (here unsigned long long).

Let, lim = ULLONG_MAX
A = ULLONG_MAX + 7
B = 2 * ULLONG_MAx + 7
7 = A % lim = B % lim

(When a value crosses the size of the data type i.e. overflows, it is moded by the size of data type, so it increases the probability of two different strings having same hashValue)

And a prime number is always required as hashBase to increase the probability of having all distinct hashValues. Sorry can't give an example of this :(

This problem & code is too tough for me to think and understand :( But if you think you have problem in hashFunction, then try this :

typedef unsigned long long int64u;
// always use a prime number :)
const int64u hashBase = 31;

int64u hashFunction (char *str) {
    int64u hashValue = 0;
    for (int i = 0; str [i]; ++i)
        hashValue = hashValue * hashBase + int64u (str [i] - 'a' + 1);
    return hashValue;
}

Thanks :D Mission successful :D

Nice editorial and clear explanation!! One thing that I want to know that what the following code segment do? And how can I have my own "whatever it is called :p"? Thanks :)

#ifdef Fcdkbear
    freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    double beg=clock();
#endif

There exists a better version of sieve whose runtime is linear, here's the tutorial (translated to English using google translator). You can make it faster and cache friendly using some bitwise tricks (check the following link).

There is also another variant of sieve which is known as segmented sieve.

Thanks :)

I liked the line "The BEST is not always the best". Its so true but yet.. :p I've watched that movie and yea, it's one of my favorite too.

One thing I must say that you talk like my brother who is from Iraq :D :D :D His name is Radwan.

Thanks man, wish you good luck too in life and have fun!! ^_^

Thanks Mario, really feeling a lot more better now. You have been through worser condition than me but still you did it! Its really inspiring.

Thanks mate, thanks for the wish :) I am from Bangladesh.

ThankU ^_^

Thanks a lot!!!!

I need help too!! Anyone? Also need help on game theory.

Nice and fast editorial, pretty cool explanation too, thanks for that :)

Well, I am having problems with probability (+ expected value problems) and game theory. Can't find any good article on them, so I hope you can suggest me and help me, from where did you learn and how did you improve your skills and how to approach to these kind of problems. I know solving problems and analyzing highly ranked coders coeds is the way, but I am newbie, so I need to know from where and how to start, I wanna be at the top too!! Thanks again :) :)