27ος ΠΔΠ B' Φάση: Άθροισμα τετραγώνων (twosqr) - Λύση

Επεξήγηση εκφώνησης

Σκοπός μας είναι για κάθε \(N_i\) που θα μας δίνεται, να βρούμε το πλήθος όλων των ζευγών φυσικών αριθμών \(a\) και \(b\) με \(a \leq b\), έτσι ώστε \(a^2 + b^2 = N_i\).

Brute force λύση

Παρατήρηση: Για κάθε ζεύγος \(a\) και \(b\) με \(a^2 + b^2 = N_i\) θα πρέπει να ισχύει ότι \(a, b \leq \sqrt{N_i}\), διότι αν ένας τουλάχιστον από τους αριθμούς του ζεύγους είναι μεγαλύτερος από \(\sqrt{N_i}\), τότε το τετράγωνό του θα είναι μεγαλύτερο από το \(N_i\) και συνεπώς θα ισχύει ότι \(a^2 + b^2 > N_i\).

Μία απλή brute force λύση είναι η εξής: Για κάθε \(N_i\), εξετάζουμε κάθε ζεύγος φυσικών αριθμών \(a, b\) με \(a \leq b \leq \sqrt{N_i}\), χρησιμοποιώντας δύο εμφωλευμένα for loops, αν \(a^2 + b^2 = N_i\). Όποτε εντοπίζουμε ένα ζεύγος αριθμών που ικανοποιεί τη συνθήκη αυτή, αυξάνουμε κατά \(1\) μία μεταβλητή που θα λειτουργεί ως μετρητής, έστω \(cnt\), και η οποία θα αρχικοποιείται σε \(0\) για κάθε \(N_i\). Μετά την εκτέλεση των δύο for loops, ο μετρητής έχει την απάντηση για το τρέχον \(N_i\).

Για κάθε \(N_i\), χρειαζόμαστε \(\mathcal{O}(\sqrt{N_i} \cdot \sqrt{N_i}) = \mathcal{O}(N_i)\) για να εκτελέσουμε τα δύο εμφωλευμένα loops. Επομένως, η συνολική χρονική πολυπλοκότητα του αλγορίθμου είναι \(\mathcal{O}(TN)\). Αυτή η χρονική πολυπλοκότητα δεν είναι η βέλτιστη δυνατή για την επίλυση του προβλήματος αυτού και δεδομένων των περιορισμών για τα \(T\) και \(N\) (\(T \leq 10^3\), \(N \leq 10^9\)) και του χρονικού ορίου (\(1\) δευτερόλεπτο) δε περνάει το όλα τα testcases, αν και συγκεντρώνει μερικές μονάδες. Η χωρική πολυπλοκότητα του αλγορίθμου μας είναι \(\mathcal{O}(1)\).

#include <cstdio>

using namespace std;

int main() {
    freopen("twosqr.in", "r", stdin);
    freopen("twosqr.out", "w", stdout);
    long T;
    scanf("%ld", &T);
    for (long tc = 0; tc < T; tc++) {
        long N;
        long cnt = 0;  // Αρχικοποίηση μετρητή
        scanf("%ld", &N);
        for (long b = 0; b * b <= N; b++) {
            for (long a = 0; a <= b; a++) {
                if (a * a + b * b == N)  // Έλεγχος συνθήκης
                    cnt++;
            }
        }
        printf("%ld\n", cnt);
    }
    return(0);
}

Λύση με δυαδική αναζήτηση

Σημείωση: Αυτή η λύση είναι πιο πολύπλοκη από την βέλτιστη λύση.

Μπορούμε να βελτιώσουμε την πολυπλοκότητα του αλγορίθμου μας κάνοντας μία απλή παρατήρηση.

Παρατήρηση: Εάν για κάποιο \(N_i\) θεωρήσουμε ένα σταθερό \(b\) (εξωτερικό for loop) δε χρειάζεται να δοκιμάσουμε όλα τα \(a \leq b\) (εσωτερικό for loop) για να δούμε για πόσα από αυτά ισχύει ότι \(a^2 + b^2 = N_i\). Αυτό, διότι η παραπάνω συνθήκη, δεδομένου του \(b\), μπορεί να ισχύει το πολύ για ένα επιτρεπτό \(a\), το οποίο θα έχει συγκεκριμένη μορφή. Πράγματι, γνωρίζοντας ότι το \(a\) είναι μη αρνητικό, η παραπάνω συνθήκη δεδομένου του \(b\) ικανοποιείται για το \(a = \sqrt{N_i - b^2}\) εάν αυτό είναι φυσικός αριθμός (μικρότερος ή ίσος του \(b\)).

Με βάση την παραπάνω παρατήρηση, αρκεί για κάθε \(N_i\), να διατρέχουμε όλα τα \(b \leq \sqrt{N_i}\), ελέγχοντας για κάθε ένα από αυτά εάν α) η ποσότητα \(\sqrt{N_i - b^2}\) είναι μικρότερη ή ίση του \(b\) και β) είναι φυσικός αριθμός. Τον έλεγχο για το β) μπορούμε να τον κάνουμε ως εξής: υπολογίζουμε με κάποιον τρόπο την ακέραια ποσότητα¹ \(h = \lfloor \sqrt{N_i - b^2} \rfloor\) και να ελέγχουμε εάν \(h^2 = N_i - b^2\). Ο έλεγχος αυτός θα δώσει θετικό αποτέλεσμα ανν \(h^2 = N_i - b^2 \Leftrightarrow\) \(\lfloor \sqrt{N_i - b^2} \rfloor ^2 = (\sqrt{N_i - b^2})^2 \Leftrightarrow\) \(\lfloor \sqrt{N_i - b^2} \rfloor = \sqrt{N_i - b^2} \Leftrightarrow\) \(\sqrt{N_i - b^2} \in \mathbb{N}\). Οπότε, όταν και μόνο όταν αυτός ο έλεγχος δίνει θετικό αποτέλεσμα και \(h \leq b\), θα αυξάνουμε την τιμή του \(cnt\) κατά \(1\).

Οπότε, για κάθε \(N_i\) και για κάθε \(b\) που δοκιμάζουμε, πρέπει να υπολογίσουμε το \(h = \lfloor \sqrt{N_i - b^2} \rfloor\), για να ελέγξουμε εάν \(h^2 = N_i - b^2\). Αυτός ο υπολογισμός μπορεί να γίνει με διάφορους τρόπους. Ένας από αυτούς είναι με δυαδική αναζήτηση. Αν θεωρήσουμε τη συνθήκη \(h^2 \leq N_i - b^2\) θεωρώντας το \(h\) εντός του διαστήματος ακεραίων \([0, N_i - b^2]\) μπορούμε να παρατηρήσουμε ότι η συνθήκη θα ικανοποιείται από \(h = 0\) μέχρι κάποια μέγιστη τιμή, ενώ δε θα ικανοποιείται για καμία μεγαλύτερη τιμή. Αυτή η μορφή της ικανοποιησιμότητας της συνθήκης μας επιτρέπει να εφαρμόσουμε δυαδική αναζήτηση προκειμένου να βρούμε ποια είναι η μέγιστη τιμή στο διάστημα αυτό που την ικανοποιεί. Η μέγιστη αυτή τιμή θα είναι η ζητούμενη ποσότητα \(h = \lfloor \sqrt{N_i - b^2} \rfloor\), αφού θα ισχύει ότι \(h \in \mathbb{N}\) και \((h + 1)^2 > N_i - b^2\). Είδαμε λοιπόν πώς μπορούμε να λύσουμε αυτό το πρόβλημα με δυαδική αναζήτηση.

Η χρονική πολυπλοκότητα υπολογισμού του \(h = \lfloor \sqrt{N_i - b^2} \rfloor\) με δυαδική αναζήτηση στο διάστημα ακεραίων \([0, N_i - b^2]\) είναι \(\mathcal{O}(\log{N})\). Ο υπολογισμός αυτός θα γίνεται για κάθε μία από τις \(\mathcal{O}(\sqrt{N})\) τιμές του \(b\) που θα εξετάζουμε για κάθε ένα από τα \(T\) δοθέντα \(N_i\). Συνεπώς η σνολική χρονική πολυπλοκότητα αυτού του αλγορίθμου είναι \(\mathcal{O}(T \sqrt{N} \log{N})\). Ο αλγόριθμος αυτός υπερβαίνει το χρονικό όριο για κάποια μεγάλα testcases. Ωστόσο, είναι αρκετά καλύτερος από τον προηγούμενο και συγκεντρώνει πιο πολλούς βαθμούς. Η χωρική πολυπλοκότητα είναι και πάλι \(\mathcal{O}(1)\).

#include <cstdio>
using namespace std;

int main() {
    freopen("twosqr.in", "r", stdin);
    freopen("twosqr.out", "w", stdout);
    long T;
    scanf("%ld", &T);
    for (long tc = 0; tc < T; tc++) {
        long N, cnt = 0;  // Αρχικοποίηση μετρητή
        scanf("%ld", &N);
        for (long b = 0; b * b <= N; b++) {
            long lo = 0, hi = N - b * b;  // Αρχικοποίηση ορίων δυαδικής αναζήτησης
            while (lo < hi) {
                // Χρειάζεται +1 ώστε να μην εισέλθει σε
                // infinite loop.
                long mid = lo + (hi - lo + 1) / 2;
                if (mid * mid <= N - b * b)
                    lo = mid;
                else
                    hi = mid - 1;
            }
            long h = lo;
            if (h <= b && h * h == N - b * b)  // Έλεγχος συνθήκης
                cnt++;
        }
        printf("%ld\n", cnt);
    }
    return(0);
}

Βέλτιστη λύση με τη συνάρτηση sqrt

Η προηγούμενη λύση μπορεί να βελτιωθεί περαιτέρω εάν για τον υπολογισμό της ποσότητας \(h = \lfloor \sqrt{N_i - b^2} \rfloor\) αντί για δυαδική αναζήτηση χρησιμοποιήσουμε τη συνάρτηση sqrt της C++ που είναι υλοποιημένη στη βιβλιοθήκη cmath. Η συνάρτηση αυτή θα δέχεται ως όρισμα το \(N_i - b^2\) και θα επιστρέφει την τετραγωνική του ρίζα ως double. Αναθέτοντας το double αποτέλεσμα σε μία μεταβλητή ακέραιου τύπου, έστω την \(h\), γίνεται αυτόματα type casting και αφού πρόκειται για μη αρνητικό αριθμό, τελικά αποθηκεύεται στην \(h\) η στρογγυλοποίησή της προς τα κάτω όπως και επιθυμούμε.

Ο λόγος που η χρήση της συνάρτησης αυτής βελτιώνει την πολυπλοκότητα του αλγορίθμου μας, παρόλο που ο υπολογισμός που κάνει είναι μεγαλύτερης ακρίβειας (double αντί για ακέραιο), είναι ότι για τον υπολογισμό της τετραγωνικής ρίζας αντί για δυαδική αναζήτηση χρησιμοποιεί την αριθμητική μέθοδο Newton Raphson η οποία έχει πολύ μεγάλη ταχύτητα σύγκλισης και δίνει το επιθυμητό αποτέλεσμα με κάτω από 10 επαναλήψεις (της αριθμητικής μεθόδου εσωτερικά στη συνάρτηση sqrt) σε αντίθεση με τη δυαδική αναζήτηση που για τους περιορισμούς για τα \(N_i\) μπορεί να χρειαστεί μέχρι και 30 επαναλήψεις. Για πρακτικούς σκοπούς, η συνάρτηση sqrt μπορεί να θεωρηθεί ότι έχει σταθερή πολυπλοκότητα.

Σημείωση: Επειδή \(b \geq a\), η μικρότερη τιμή δυνατή τιμή του \(b\) ώστε \(a^2 + b^2 = N_i\), είναι \(\sqrt{\frac{N_i}{2}} \geq \lfloor \sqrt{\frac{N_i}{2}} \rfloor\). Μπορούμε λοιπόν παραλείψουμε τις μικρότερες τιμές του \(b\). Ωστόσο, λόγω της στρογγυλοποίησης προς τα κάτω, δεν είναι βέβαιο ότι για την υπολογισθείσα ελάχιστη τιμή του \(b\), θα ισχύει ότι \(a \leq b\). Οπότε ο έλεγχος αυτός δεν μπορεί να παραληφθεί.

Η παράλειψη ορισμένων ελέγχων που μπορεί να γίνει λόγω της παραπάνω παρατήρησης δε βελτιώνει ασυμπτωτικά τη χρονική πολυπλοκότητα του αλγορίθμου μας, όμως κάνει το πρόγραμμά μας κάπως πιο γρήγορο.

Πλέον η χρονική πολυπλοκότητα του αλγορίθμου είναι \(\mathcal{O}(T \sqrt{N})\) και η χωρική \(\mathcal{O}(1)\). Όλα τα testcases μπορούν να περαστούν με επιτυχία.

#include <cstdio>
#include <cmath>
using namespace std;

int main() {
    freopen("twosqr.in", "r", stdin);
    freopen("twosqr.out", "w", stdout);
    long T;
    scanf("%ld", &T);
    for (long tc = 0; tc < T; tc++) {
        long N, cnt = 0;  // Αρχικοποίηση μετρητή
        scanf("%ld", &N);
        long mn_b = sqrt(N / 2);  // Υπολογισμός ελάχιστου δυνατού b
        for (long b = mn_b; b * b <= N; b++) {
            long h = sqrt(N - b * b);
            if (h <= b && h * h == N - b * b)  // Έλεγχος συνθήκης
                cnt++;
        }
        printf("%ld\n", cnt);
    }
    return(0);
}