Algorithme pour trouver des numéros chanceux

Vous devez utiliser DP pour cette tâche. Voici ma solution:

#include <stdio.h>

const int MAX_LENGTH = 18;
const int MAX_SUM = 162;
const int MAX_SQUARE_SUM = 1458;
int primes[1459];
long long dyn_table[19][163][1459];

void gen_primes() {
    for (int i = 0; i <= MAX_SQUARE_SUM; ++i) {
        primes[i] = 1;
    }
    primes[0] = primes[1] = 0;

    for (int i = 2; i * i <= MAX_SQUARE_SUM; ++i) {
        if (!primes[i]) {
            continue;
        }
        for (int j = 2; i * j <= MAX_SQUARE_SUM; ++j) {
            primes[i*j] = 0;
        }
    }
}

void gen_table() {
    for (int i = 0; i <= MAX_LENGTH; ++i) {
        for (int j = 0; j <= MAX_SUM; ++j) {
            for (int k = 0; k <= MAX_SQUARE_SUM; ++k) {
                dyn_table[i][j][k] = 0;
            }
        }
    }
    dyn_table[0][0][0] = 1;

    for (int i = 0; i < MAX_LENGTH; ++i) {
        for (int j = 0; j <= 9 * i; ++j) {
            for (int k = 0; k <= 9 * 9 * i; ++k) {
                for (int l = 0; l < 10; ++l) {
                    dyn_table[i + 1][j + l][k + l*l] += dyn_table[i][j][k];
                }
            }
        }
    }
}

long long count_lucky (long long max) {
            long long result = 0;
    int len = 0;
    int split_max[MAX_LENGTH];
    while (max) {
        split_max[len] = max % 10;
        max /= 10;
        ++len;
    }
    int sum = 0;
    int sq_sum = 0;
    for (int i = len-1; i >= 0; --i) {
        long long step_result = 0;
        for (int l = 0; l < split_max[i]; ++l) {
            for (int j = 0; j <= 9 * i; ++j) {
                for (int k = 0; k <= 9 * 9 * i; ++k) {
                    if (primes[j + l + sum] && primes[k + l*l + sq_sum]) {
                        step_result += dyn_table[i][j][k];
                    }
                }
            }
        }
        result += step_result;

        sum += split_max[i];
        sq_sum += split_max[i] * split_max[i];
    }

    if (primes[sum] && primes[sq_sum]) {
        ++result;
    }

    return result;
}

int main(int argc, char** argv) {
    gen_primes();
    gen_table();

    int cases = 0;
    scanf("%d", &cases);
    for (int i = 0; i < cases; ++i) {
        long long a, b;
        scanf("%lld %lld", &a, &b);
        printf("%lld\n", count_lucky(b) - count_lucky(a-1));
    }
    return 0;
}

Brève explication:

• Je calcule tous les nombres premiers jusqu'à 9 * 9 * MAX_LENGTH en utilisant la méthode Eratosthenes;
• plus Tard, à l'aide de DP, je suis en train de construire le tableau dyn_table où la valeur X dans dyn_table[i][j][k] signifie que nous avons exactement X nombres de longueur , je avec la somme des chiffres égal à j et la somme de ses cases égal à k
• alors nous pouvons facilement compter le nombre de numéros chanceux de 1 à 999..999 (len fois de 9). Pour cela, nous venons de résumer toutes les dyn_table[len][j][k] où les deux j et k sont des nombres premiers.
• pour calculer la quantité de nombre chanceux de 1 au hasard X nous divisons l'intervalle de 1 à X en intervalles de longueur égale à 10^K (voir* count_lucky * function).
• et notre dernière étape est de soustraire count_lucky (a-1) (parce que nous incluons a dans notre intervalle) de count_lucky(b).

C'est tout. Travail de précalcul pour O (log (MAX_NUMBER)^3), chaque étape a aussi cette complexité.

J'ai testé ma solution contre une solution linéaire simple et les résultats étaient égaux

Au lieu d'énumérer l'espace des nombres, énumérez les différentes "signatures" des nombres qui ont de la chance. et puis imprimez toute la combinaison differnet de ceux-ci.

Cela peut être fait avec trivial backtracking:

#define _GNU_SOURCE
#include <assert.h>
#include <limits.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>

#define bitsizeof(e)   (CHAR_BIT * sizeof(e))
#define countof(e)     (sizeof(e) / sizeof((e)[0]))
#define BITMASK_NTH(type_t, n) ( ((type_t)1) << ((n) & (bitsizeof(type_t) - 1)))
#define OP_BIT(bits, n, shift, op) \
    ((bits)[(unsigned)(n) / (shift)] op BITMASK_NTH(typeof(*(bits)), n))
#define TST_BIT(bits, n)    OP_BIT(bits, n, bitsizeof(*(bits)), &  )
#define SET_BIT(bits, n)    (void)OP_BIT(bits, n, bitsizeof(*(bits)), |= )

/* fast is_prime {{{ */

static uint32_t primes_below_1M[(1U << 20) / bitsizeof(uint32_t)];

static void compute_primes_below_1M(void)
{
    SET_BIT(primes_below_1M, 0);
    SET_BIT(primes_below_1M, 1);
    for (uint32_t i = 2; i < bitsizeof(primes_below_1M); i++) {
        if (TST_BIT(primes_below_1M, i))
            continue;
        for (uint32_t j = i * 2; j < bitsizeof(primes_below_1M); j += i) {
            SET_BIT(primes_below_1M, j);
        }
    }
}

static bool is_prime(uint64_t n)
{
    assert (n < bitsizeof(primes_below_1M));
    return !TST_BIT(primes_below_1M, n);
}

/* }}} */

static uint32_t prime_checks, found;

static char     sig[10];
static uint32_t sum, square_sum;

static void backtrack(int startdigit, int ndigits, int maxdigit)
{
    ndigits++;

    for (int i = startdigit; i <= maxdigit; i++) {
        sig[i]++;
        sum        += i;
        square_sum += i * i;
        prime_checks++;
        if (is_prime(sum) && is_prime(square_sum)) {
                found++;
        }
        if (ndigits < 18)
            backtrack(0, ndigits, i);
        sig[i]--;
        sum        -= i;
        square_sum -= i * i;
    }
}

int main(void)
{
    compute_primes_below_1M();
    backtrack(1, 0, 9);

    printf("did %d signature checks, found %d lucky signatures\n",
           prime_checks, found);
    return 0;
}

Quand je l'exécute, il le fait:

$ time ./lucky
did 13123091 signature checks, found 933553 lucky signatures
./lucky  0.20s user 0.00s system 99% cpu 0.201 total

Au Lieu de trouvé++ vous souhaitez générer toutes les permutations distinctes de chiffres que vous pouvez construire avec ce numéro. J'ai aussi précalculé le premier 1M de nombres premiers jamais.

Je n'ai pas vérifié si le code est 100% correct, vous devrez peut-être le déboguer un peu. Mais l'idée rought est ici, et je suis capable de générer toute la permutation chanceuse en dessous de 0.2 s (même sans bugs, elle ne devrait pas être plus de deux fois plus lente).

Et bien sûr, vous voulez générer les permutations qui vérifient A

(Note: le texte de présentation au début est parce que je coupe et colle le code I écrit pour le projet euler, d'où le très rapide is_prime qui fonctionne pour N

Pour ceux qui n'étaient pas déjà au courant, c'est un problème sur le site InterviewStreet.com (et à mon avis, le plus difficile là-bas). Mon approche a commencé similaire à (et a été inspirée par) OleGG ci-dessous. Cependant, après avoir créé la première table[19] [163] [1459] qu'il a faite (que j'appellerai table1), je suis allé dans une direction légèrement différente. J'ai créé une deuxième table de longueur déchiquetée [19] [x] [3] (table2), où x est le nombre de paires de somme uniques pour le nombre correspondant de chiffre. Et pour la troisième dimension de la table, avec la longueur 3, le 1er élément est la quantité de "paires de somme" uniques avec les valeurs sum et squareSum détenues par les 2ème et 3ème éléments.

Par exemple:

//pseudocode

table2[1] = new long[10][3]
table2[1] = {{1, 0, 0}, {1, 1, 1}, {1, 2, 4},
             {1, 3, 9}, {1, 4, 16}, {1, 5, 25},
             {1, 6, 36}, {1, 7, 49}, {1, 8, 64}, {1, 9, 81}}

table2[2] = new long[55][3]
table2[3] = new long[204][3]
table2[4] = new long[518][3]
    .
    .
    .
    .
table2[17] = new long[15552][3]
table2[18] = new long[17547][3]

Les nombres que j'ai pour la deuxième longueur de dimension du tableau (10, 55, 204, 518, ..., 15552, 17547) peut être vérifié en interrogeant table1, et d'une manière similaire table2 peut être rempli. Maintenant, en utilisant table2, nous pouvons résoudre de grandes requêtes "chanceuses" beaucoup plus rapidement que celles D'OleGG méthode affichée, bien qu'employant toujours un processus de "scission" similaire à celui qu'il a fait. Par exemple, si vous avez besoin de trouver lucky (00000-54321) (c'est-à-dire les nombres chanceux entre 0 et 54321), il se décompose à la somme des 5 lignes suivantes:

lucky(00000-54321) = {
    lucky(00000-49999) +
    lucky(50000-53999) +
    lucky(54000-54299) +
    lucky(54300-53319) +
    lucky(54320-54321)
}

Qui se décompose plus loin:

lucky(00000-49999) = {
    lucky(00000-09999) +
    lucky(10000-19999) +
    lucky(20000-29999) +
    lucky(30000-39999) +
    lucky(40000-49999)
}
    .
    .
lucky(54000-54299) = {
    lucky(54000-54099) +
    lucky(54100-54199) +
    lucky(54200-54299)
}
    .
    .
    .
    etc

Chacune de ces valeurs peut être obtenue facilement en interrogeant table2. Par exemple, lucky (40000-49999) est trouvé en ajoutant 4 et 16 aux 2ème et 3ème éléments de la troisième dimension table2:

sum = 0
for (i = 0; i < 518; i++)
    if (isPrime[table2[4][i][1] + 4] && isPrime[table2[4][i][2] + 4*4])
        sum += table2[4][i][0]
return sum

Ou pour les chanceux(54200-54299):

sum = 0
for (i = 0; i < 55; i++)
    if (isPrime[table2[2][i][1] + (5+4+2)]
    && isPrime[table2[2][i][2] + (5*5+4*4+2*2)])
        sum += table2[2][i][0]
return sum

Maintenant, la solution D'OleGG a fonctionné beaucoup plus vite que toute autre chose que j'avais essayé jusqu'alors, mais avec mes modifications décrites ci-dessus, elle fonctionne encore mieux qu'avant (d'un facteur d'environ 100x pour un grand ensemble de tests). Cependant, il n'est pas encore assez rapide pour les cas de test à l'aveugle donnés sur InterviewStreet. Grâce à un hack intelligent, j'ai pu déterminer que je suis actuellement en cours d'exécution à propos de 20x trop lent pour terminer leur test dans le temps imparti. Cependant, je ne trouve pas d'autres optimisations. Le plus grand puits de temps ici est évidemment itérer à travers la deuxième dimension de table2, et la seule façon d'éviter cela serait de tabuler les résultats de ces sommes. Cependant, il y a trop de possibilités pour calculer tous dans le temps (5 secondes) ou de stocker toutes dans l'espace (256 MO). Par exemple, la boucle lucky (54200-54299) ci-dessus pourrait être pré-calculée et stockée comme une seule valeur, mais si c'était le cas, nous pourrions aussi besoin de pré-calculer chanceux (123000200-123000299) et chanceux (99999200-99999299), etc etc. J'ai fait le calcul et c'est beaucoup trop de calculs à pré-calculer.

Je viens de résoudre ce problème.

C'est juste un problème de programmation dynamique. Prenez {[3] } comme fonction DP, et DP[n](sum-square_sum) est le nombre de tous les nombres dont les chiffres sont inférieurs ou égaux à n, avec la somme et square_sum des chiffres du nombre est respectivement représenté par sum et square_sum. Par exemple:

DP[1](1-1) = 1      # only 1 satisfies the condition                        
DP[2](1-1) = 2      # both 1 and 10 satisfies the condition                        
DP[3](1-1） = 3      # 1 10 100
DP[3](2-4） = 3      # 11 110 101

Puisque nous pouvons facilement comprendre le premier état DP DP [1] [..][..], il est:

(0-0) => 1     (1-1) => 1    (2-4) => 1     (3-9) => 1     (4-16) => 1    
(5-25) => 1    (6-36) => 1   (7-49) => 1    (8-64) => 1    (9-81) => 1

Ensuite, nous pouvons déduire DP [1] de DP [1], puis DP [3]... DP [18] la déduction ci-dessus est faite par le fait que chaque fois que n augmente de 1, par exemple de DP[1] à DP[2], nous obtenons un nouveau chiffre (0..9), et l'ensemble de la paire (sum, square_sum) (C'est-à-dire DP[N]) doit être mis à jour.

Enfin, nous pouvons traverser L'ensemble DP[18] et compter les nombres qui ont de la chance.

Eh bien, que diriez - vous de la complexité temporelle et spatiale de l'algorithme ci-dessus? Comme nous le savons somme

ruby lucky_numbers.rb  0.55s user 0.00s system 99% cpu 0.556 total

Et je teste mon programme en écrivant une fonction de test en utilisant l'algorithme de force brute, et c'est juste pour les nombres inférieurs à 10^7 .

Sur la Base des exigences, vous pouvez le faire de différentes manières. Si je le faisais, je calculerais les nombres premiers en utilisant 'tamis D'Eratosthène' dans la plage requise (A à (9*2)*B. length), les mettre en cache (encore une fois, en fonction de votre configuration, vous pouvez utiliser en mémoire ou cache disque) et l'utiliser pour la prochaine exécution.

Je viens de coder une solution rapide (Java), comme ci-dessous (NOTE: le débordement entier n'est pas vérifié. Juste un exemple rapide. En outre, mon code n'est pas optimisé.):

import java.util.ArrayList;
import java.util.Arrays;

public class LuckyNumbers {
    public static void main(String[] args) {
        int a = 0, b = 1000;
        LuckyNumbers luckyNums = new LuckyNumbers();
        ArrayList<Integer> luckyList = luckyNums.findLuckyNums(a, b);
        System.out.println(luckyList);
    }

    private ArrayList<Integer> findLuckyNums(int a, int b) {
        ArrayList<Integer> luckyList = new ArrayList<Integer>();
        int size = ("" + b).length();        
        int maxNum = 81 * 4; //9*2*b.length() - 9 is used, coz it's the max digit
        System.out.println("Size : " + size + " MaxNum : " + maxNum);
        boolean[] primeArray = sieve(maxNum);

        for(int i=a;i<=b;i++) {
            String num = "" + i;
            int sumDigits = 0;
            int sumSquareDigits = 0;

            for(int j=0;j<num.length();j++) {
                int digit = Integer.valueOf("" + num.charAt(j));
                sumDigits += digit;
                sumSquareDigits += Math.pow(digit, 2);
            }

            if(primeArray[sumDigits] && primeArray[sumSquareDigits]) {
                luckyList.add(i);
            }
        }

        return luckyList;
    }

    private boolean[] sieve(int n) {
        boolean[] prime = new boolean[n + 1];
        Arrays.fill(prime, true);
        prime[0] = false;
        prime[1] = false;
        int m = (int) Math.sqrt(n);

        for (int i = 2; i <= m; i++) {
            if (prime[i]) {
                for (int k = i * i; k <= n; k += i) {
                    prime[k] = false;
                }
            }
        }

        return prime;
    }
}

Et le la sortie était:

[11, 12, 14, 16, 21, 23, 25, 32, 38, 41, 49, 52, 56, 58, 61, 65, 83, 85, 94, 101, 102, 104, 106, 110, 111, 113, 119, 120, 131, 133, 137, 140, 146, 160, 164, 166, 173, 179, 191, 197, 199, 201, 203, 205, 210, 223, 229, 230, 232, 250, 289, 292, 298, 302, 308, 311, 313, 317, 320, 322, 331, 335, 337, 344, 346, 353, 355, 364, 368, 371, 373, 377, 379, 380, 386, 388, 397, 401, 409, 410, 416, 434, 436, 443, 449, 461, 463, 467, 476, 490, 494, 502, 506, 508, 520, 533, 535, 553, 559, 560, 566, 580, 595, 601, 605, 610, 614, 616, 634, 638, 641, 643, 647, 650, 656, 661, 665, 674, 683, 689, 698, 713, 719, 731, 733, 737, 739, 746, 764, 773, 779, 791, 793, 797, 803, 805, 829, 830, 836, 838, 850, 863, 869, 883, 892, 896, 904, 911, 917, 919, 922, 928, 937, 940, 944, 955, 968, 971, 973, 977, 982, 986, 991]

Je n'ai pas soigneusement analysé votre solution actuelle mais cela pourrait l'améliorer:

Puisque l'ordre des chiffres n'a pas d'importance, vous devriez passer par toutes les combinaisons possibles de chiffres 0-9 de longueur 1 à 18, en gardant une trace de la somme des chiffres et de leurs carrés et en ajoutant un chiffre à la fois, en utilisant le résultat du calcul précédent.

Donc, si vous savez que pour 12 somme des chiffres est 3 et des carrés est 5, regardez les nombres 120, 121, 122... etc et calculer des sommes pour eux trivialement de la 3 et 5 pour 12.

, Parfois, la solution la plus rapide est incroyablement simple:

uint8_t precomputedBitField[] = {
    ...
};

bool is_lucky(int number) {
    return precomputedBitField[number >> 8] & (1 << (number & 7));
}

Modifiez simplement votre code existant pour générer "precomputedBitField".

Si vous vous inquiétez de la taille, pour couvrir tous les nombres de 0 à 999, cela ne vous coûtera que 125 octets, donc cette méthode sera probablement plus petite (et beaucoup plus rapide) que toute autre alternative.

J'essayais de trouver une solution en utilisant la méthode d'énumération de Pierre, mais je n'ai jamais trouvé un moyen suffisamment rapide de compter les permutations. La méthode de comptage d'OleGG est très intelligente, et les optimisations de pirate sont nécessaires pour le rendre assez rapide. Je suis venu avec une amélioration mineure, et une solution de contournement à un problème sérieux.

Tout d'abord, l'amélioration: vous n'avez pas à parcourir toutes les sommes et squaresums un par un en vérifiant les nombres premiers dans les boucles J et k de pirate. Vous ont (ou peuvent facilement générer une liste de nombres premiers. Si vous utilisez les autres variables pour déterminer quels nombres premiers sont dans la plage, vous pouvez simplement parcourir la liste des nombres premiers appropriés pour sum et squaresum. Un tableau de nombres premiers et une table de recherche pour déterminer rapidement à quel index se trouve le nombre premier >= est utile. Cependant, ce n'est probablement qu'une amélioration assez mineure.

Le gros problème est avec le tableau de cache ans de pirate. Ce N'est pas 45MB comme revendiqué; avec des entrées 64 bits, c'est quelque chose comme 364MB. Ceci est en dehors des limites de mémoire autorisées (actuelles) pour C et Java. Il peut être réduit à 37MB en se débarrassant de la dimension" l", Ce Qui est inutile et nuit aux performances du cache de toute façon. Vous êtes vraiment intéressé par les comptes de mise en cache pour l + sum et l*l + squaresum, pas l, sum et squaresum individuellement.

Tout d'abord, je voudrais ajouter qu'un nombre chanceux peut être calculé par un tamis, l'explication du tamis peut être trouvée ici: http://en.wikipedia.org/wiki/Lucky_number

Vous pouvez donc améliorer la vitesse de votre solution en utilisant un tamis pour déterminer les nombres,