Bon résultat en local mais pas sur HackerRank

Bonjour,

J’ai décidé de me mettre à HackerRank dernièrement en C++14. J’en suis au défi Mini-Max Sum qui consiste à afficher la plus petite et la plus grande somme de 4 entiers dans un tableau de 5 entiers. Voici la solution que j’ai proposé :

void miniMaxSum(vector<int> arr) {
   vector<unsigned long> sums;

   sums.push_back(arr[0] + arr[1] + arr[2] + arr[3]);
   sums.push_back(arr[0] + arr[1] + arr[2] + arr[4]);
   sums.push_back(arr[0] + arr[1] + arr[3] + arr[4]);
   sums.push_back(arr[0] + arr[2] + arr[3] + arr[4]);
   sums.push_back(arr[1] + arr[2] + arr[3] + arr[4]);

   cout << *min_element(sums.begin(), sums.end()) << " " << *max_element(sums.begin(), sums.end()) << endl;
}

Avec la suite 1 2 3 4 5 j’obtiens bien 10 14, de même qu’avec 7 69 2 221 8974, j’obtiens bien 299 9271. Plutôt confiant de mon code je le soumet et… il est refusé. J’ai donc testé mon code en local avec la série 256741038 623958417 467905213 714532089 938071625 et j’obtiens bien la bonne réponse qui est 2063136757 2744467344.

Mon code est donc refusé sur HackerSpace alors qu’en local j’obtiens bien les bonnes réponses. Sauriez-vous pourquoi ?

Merci pour votre aide !

À la fin du problème, il y a le message suivant:

Hints: Beware of integer overflow! Use 64-bit Integer.

Les unsigned int peuvent avoir des tailles différentes suivant l’architecture ciblé par le compilateur: https://en.cppreference.com/w/cpp/language/types. Sur la même page, ils indiquent quels types ont au minimum 64 bits.

Si tu veux être sûr de la taille de tes entiers, tu peux utiliser un type à taille fixe: https://en.cppreference.com/w/cpp/types/integer.

Merci pour ta réponse @Berdes.

J’utilisais les unsigned long justement à cause de ce message. Et unsigned c’est parce que je trouvais des valeurs négatives dans mon tableau (dues à un overflow j’imagine). En utilisant le type int64_t ces valeurs négatives reviennent. Pour la série 256741038 623958417 467905213 714532089 938071625 j’obtiens alors -2008291003 2063136757 et en utilisant le type uint64_t j’obtiens un résultat absolument faux : 2063136757 18446744072159051664.

On est bien d’accord que le type qui doit être changé est le type des valeurs de mon vecteur sums. Les autres vecteurs n’ont pas besoin d’être modifiés, non ?

Les contraintes spécifies qu’il n’y a pas d’entier négatif non ?

Utilises des uint64_t alors non ? Comme ça, c’est parfait ?

Justement comme précisé dans mon dernier message, en utilisant des uint64_t j’obtiens un résultat faux : 2063136757 18446744072159051664 alors que je devrais avoir 2063136757 2744467344.

Je met le code si vous souhaitez essayer :

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdint>

using namespace std;

void miniMaxSum(vector<int> arr) {
    vector<uint64_t> sums;

    sums.push_back(arr[0] + arr[1] + arr[2] + arr[3]);
    sums.push_back(arr[0] + arr[1] + arr[2] + arr[4]);
    sums.push_back(arr[0] + arr[1] + arr[3] + arr[4]);
    sums.push_back(arr[0] + arr[2] + arr[3] + arr[4]);
    sums.push_back(arr[1] + arr[2] + arr[3] + arr[4]);

    cout << *min_element(sums.begin(), sums.end()) << " " << *max_element(sums.begin(), sums.end()) << endl;
}

int main() {
    vector<int> arr{256741038, 623958417, 467905213, 714532089, 938071625};

    miniMaxSum(arr);

    return 0;
}

La sommes d’un milliard d’int sera toujours un int, même si au final dans la stockes dans autre chose.

=> Ne mélange pas et utilise le bon type depuis le début.

En regardant en détail les contraintes, le problème est assez subtile. Chaque nombre vaut au maximum 1e9, ce qui rentre dans un int. En revanche, en les sommant tu peux arriver jusqu’à 4e9, ce qui est trop gros pour un int (mais qui rentre dans un unsigned int).

Pour compléter la réponse de @lmghs, la conversion de int (dans arr) à uint64_t (dans sums) se fait au moment du push_back, donc après que la sommation soit faite.

D’accord donc si je comprend bien en additionnant les int j’obtiens un int qui après seulement est converti au type du vecteur ? Donc j’ai deux solutions, convertir chaque int en unsigned int au moment du calcul ou modifier le code fourni par défaut par HackerRank pour que tout soit des unsigned int dès le début ?

N’y a t-il pas moyen de forcer un calcul dans un type directement ? Histoire d’éviter quelque chose comme :

sums.push_back(unsigned(arr[0]) +unsigned(arr[1]) + unsigned(arr[2]) + unsigned(arr[3]));

Merci pour votre aide !

Si tu ne veux pas modifier le code fourni de base (dont la qualité est débattable quand on voit using namespace std), une solution serait définir une variable entière non-signée et y ajouter chaque valeur. En fait, c’est ce que fait std::accumulate :

auto sum = std::accumulate(arr.cbegin(), arr.cend(), unsigned {});

Avec ça, on obtient la somme totale. Pour les sommes des sous-ensembles, il suffit de soustraire chaque valeur du tableau individuellement.

Pour les sommes des sous-ensembles, il suffit de soustraire chaque valeur du tableau individuellement.

Sinon, tu peux juste soustraire le min et le max de arr pour trouver les valeurs demandées, non ?

Oui mais pour en arriver là, ça demande un effort intellectuel au delà de mes limites.

Utilise juste des uint64_t. Pourquoi utiliser des nombres signés ? Le code de base ne prend juste pas en compte les contraintes apparemment, non ?