progintro @ dit

Άσκηση 2: Επεξήγηση & Ανάλυση του flawless.c

Credit για το optimization πάει και στον KostasGeorgako. Είχαμε βρει και οι δύο λύσεις κάτω από 10 δευτερόλεπτα και αποφασίσαμε να το κάνουμε optimize μαζί. Το φτάσαμε σχεδόν 0.3s.

Συμπεριλαμβάνω τις βιβλιοθήκες:

• stdbool.h για να μπορώ να χρησιμοποιήσω boolean data type.
• stdio.h για να μπορώ να χρησιμοποιήσω printf().
• stdlib.h για μα μπορώ να χρησιμοποιήσω strtoll().
• string.h για να μπορώ να χρησιμοποιήσω strlen().

isFlawless()

Αναδρομική συνάρτηση που δέχεται έναν αριθμό και την ρίζα του και επιστρέφει αν είναι ή όχι flawless.

Λειτουργία

Η συνάρτηση επιχειρεί να σπάσει τον αριθμό σε όλα τα δυνατά σημεία και να δει αν υπάρχει συνδιασμός αριθμών (που προκύπτουν από τα ψηφία) που το άθροισμά τους να δίνει την ρίζα του αριθμού.

Αν στο μεσοδιάστημα προκύψουν συνθήκες (αναφέρονται παρακάτω) που καθιστούν την περαιτέρω αναζήτηση ανώφελη η συνάρτηση είτε διακόπτεται επιστρέφοντας αναδρομικά ότι ο αριθμός δεν είναι flawless είτε παρακάμπτει κλήσεις συνάρτησης.

Αν βρεθεί άθροισμα που να ισούται με την ρίζα τότε επιστρέφει αναδρομικά ότι ο αριθμός είναι flawless.

Επειδή η αναδρομή είναι δύσκολο να εξηγηθεί ας δούμε 2 παραδείγματα προκειμένου να είναι πιο εύκολη η κατανόηση της λειτουργίας της. Σημαντικό είναι να κοιτάμε την οπτικοποίηση (πίνακες) μαζί με τα βήματα.

Παράδειγμα με flawless number

Έστω ότι o αριθμός in question είναι το 1296 και η ρίζα του το 36.

Αρχικά καλούμε την συνάρτηση και αρχικοποιούμε τις μεταβλητές.

1. Ξεκινάμε να σπάμε τον αριθμό από δεξιά προς τα αριστερά. 129

   6. Εφόσον το άθροισμα $129 + 6 \neq 36$ συνεχίζουμε.

2. Καλούμε πάλι την συνάρτηση και αυτή την φορά:

• Στον number δίνουμε αυτό που θέλουμε να συνεχίσουμε να σπάμε (το quotient).
• Στην root δίνουμε root - remainder. Με αυτό τον τρόπο λαμβάνουμε υπόψιν το remainder των προηγούμενων καλεσμάτων της συνάρτησης αφού αντί να το προσθέσουμε για να προκύψει το αποτέλεσμα, το αφαιρούμε από αυτό (που είναι το ίδιο πράγμα). Συνεπώς $36-6 = 30$.

if (isFlawless(root - remainder, quotient)) return true;

Σημαντικό: Καλούμε την συνάρτηση μέσα σε if check. Μόνο αν η συνάρτηση επιστρέψει ότι βρήκε flawless αριθμό θα μπορέσει και η ίδια να επιστρέψει πως τον βρήκε. Δημιουργώντας έτσι μια αλυσίδα επιτυχημένων αναδρομικών επιστροφών.

1. Παίρνουμε το number και συνεχίζουμε να το σπάμε. Αυτή την φορά προκύπτει:

• quotient = 12
• remainder = 9

Όμως το root είναι 30 και $12 + 9 = 21 < 30$. Όπως και να σπάσουμε το 12, δεν είναι δυνατόν το άθροισμα αυτό να μας δώσει την ρίζα.

if (quotient + remainder < root) continue;

1. Συνεπώς πρέπει να δοκιμάσουμε να σπάσουμε τον αριθμό μας στο επόμενο δυνατό σημείο. Στο σημείο 1

   29. Κάνουμε continue; έτσι ώστε να ανεβάσουμε την δύναμη του 10 *10. Έτσι όταν πάμε να πάρουμε το div και το mod με το power10 θα πάρουμε quotient = 1 και remainder = 29 αντίστοιχα.

for (int power10 = 10;; power10 *= 10)

1. Τι παρατηρούμε; quotient + remainder = root! 🎉

if (quotient + remainder == root) return true;

Η συνάρτηση θα επιστρέψει στον ευατό της (που την κάλεσε) ότι τον βρήκε η οποία με την σειρά της θα μπει στο if (όπως είπαμε στο βήμα 2) και θα επιστρέψει και αυτή true στην main!

Παράδειγμα με μη flawless number

Έστω ότι o αριθμός in question είναι το 1369 και η ρίζα του το 37.

Αρχικά καλούμε πάλι την συνάρτηση και αρχικοποιούμε τις μεταβλητές.

1. Σπάμε πάλι τον αριθμό από δεξιά προς τα αριστερά. 136

   9. $136 + 9 \neq 37$ συνεχίζουμε.

2. Για να μην τα πολυλογώ καλούμε πάλι και γίνεται

• number = quotient = 136
• root = root - remainder = 28

Όμως όπως και πριν quotient (13) + remainder (6) $= 19 < 28$. Τι νόημα έχει να συνεχίσουμε να σπάμε το quotient; Ο αριθμός αυτός δεν θα γίνει μεγαλύτερος…

if (quotient + remainder < root) continue;

1. Σπάμε τον αριθμό στο επόμενο δυνατό σημείο (1

   36). Ναι, αλλά το remainder (36) > root (28). Όχι μόνο δεν έχει νόημα να συνεχίσουμε αφού δεν είναι δυνατόν το remainder να είναι μέρος του αθροίσματος που θα ισούτε το root, αλλά αν πάμε να καλέσουμε πάλι την συνάρτηση με root - remainder θα πάρουμε αρνητικό αριθμό!

Μας σώζει η συνθήκη:

if (root < remainder) return false;

1. Αφού λοιπόν η συνάρτηση μας επιστρέφει false θα ολοκληρωθεί το for loop της προηγούμενης συνάρτησης, θα πάει πάλι πάνω και θα αυξησεί το power10 * 10 = 100. Ως αποτέλεσμα το quotient = 13 και το remainder = 69.

Όμως για άλλη μία (τελευταία φορά) θα χτυπήσει η συνθήκη (root < remainder) αφού $37 < 69$ και θα τερματίσει η συνάρτηση επιστρέφοντας false αφού το 1369 δεν είναι flawless.

Και κάπως έτσι πολύ σύντομα και αποδοτικά έχουμε ελέγξει όλους τους πιθανούς συνδιασμούς.✌

Additional Έλεγχος

Υπάρχει όμως και ένα if check για το οποίο δεν ειπώθηκε τίποτα

if (quotient <= 9)

Η συνθήκη αυτή βγαίνει αληθής πολύ σπάνια (30 φορές σε όλο το εύρος $[1, 10^{12}]$), αφού όπως είδαμε συνήθως ένα από τα 3 προηγούμενα checks θα βγει true εμποδίζοντας τον αλγόριθμο να φτάσει μέχρι εκεί.

Ο πρώτος αριθμός που την ικανοποιεί είναι ο 97298496 ο οποίος παρά είναι μεγάλος για να αναλυθεί σε readme.

Ωστόσο είναι ένα σημαντικό fallback check το οποίο αν αληθές μας δείχνει ότι δεν έχει νόημα να συνεχίσουμε να σπάμε τον αριθμό, αφού έχει μείνει μόνο ένα ψηφίο (Και να θες να τον σπάσεις δεν μπορείς 😛). Οπότε επιστρέφουμε στην προηγούμενη συνάρτηση και προσπαθούμε να σπάσουμε τον αριθμό αλλιώς.

Προφανώς η σειρά των if έχει μεγάλη σημασία για την λειτουργικότητα της συνάρτησης.

main()

Parsing command-line arguments and Input Validation

Ελέγχω αν ο χρήστης έδωσε 2 arguments. Εφόσον το όνομα του προγράμματος είναι πάντα το ένα argument, argc = 3.

Αρχικά αν το μήκος της συμβολοσειράς των input είναι μεγαλύτερο του 13 αυτό σημαίνει ότι ο αριθμός είναι μεγαλύτερος του $10^{13}$ που είναι εκτός ορίων οπότε τερματίζουμε και επιστρέφουμε 1.

Αναθέτουμε τα arguments που δίνει ο χρήστης σε μεταβλητές χρησιμοποιώντας strtoll (που μπορεί να διαχχειριστεί 64-bit ακεραίους) και κάνω τους απαραίτητους ελέγχους που ζητά η εκφώνηση.

Variable Declaration και Initialization

• perfectSquare: Όλα τα τέλεια τετράγωνα στο εύρος του χρήστη που θα ελεγθούν αν είναι flawless.
• sum: Το ζητούμενο της άσκησης. Το άθροισμα όλων των άψογων τετραγώνων στο εύρος που ορίζει ο χρήστης.
• root: Η ρίζα των αριθμών. Την μεταβλητή αυτή υψώνουμε στο τετράγωνο για να φτιάξουμε τέλεια τετράγωνα.

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

Με αυτό τον τρόπο αποφεύγουμε την χρήση sqrt() και ceil(). Έτσι δεν χρειαζόμαστε καθόλου την μαθηματική βιβλιοθήκη.

for()

Χρησιμοποιούμε for() έτσι ώστε όταν το mod 9 if κάνει continue; να αυξάνεται το root.

Modulo 9

if (i % 9 != perfectSquare % 9) continue;

Απόδειξη:

Έστω ένας αριθμός $num$, $k$ ψηφίων. Ο $num$ μπορεί να γραφτεί ως:

οπού $\displaystyle\sum_{i=0}^k a_i$ είναι το άθροισμα των ψηφίων.

Επίσης είναι μαθηματική ιδιότητα ότι αν $a \equiv b \pmod{n}$ και $c \equiv d \pmod{n}$, τότε

Συνεπώς όπως και να σπάσουμε έναν αριθμό το άθροισμα των επιμέρους συνδιασμών (mod 9), θα ισούτε με το άθροισμα των ψηφίων (mod 9).

Άρα από $(1), (2) \Rightarrow$ ότι το άθροισμα των επιμέρους συνδιασμών των ψηφίων ενός αριθμού (mod 9) ισούτε με τον αριθμό (mod 9).

Όμως για να είναι ένας αριθμός flawless θέλουμε το άθροισμα των επιμέρους συνδιασμών των ψηφίων ενός αριθμού να ισούτε με την ρίζα του. Άρα

Άρα αν το $(3)$ δεν ισχύει τότε δεν χρειάζεται να κοιτάξουμε τον αριθμό. Εξού και

if (i % 9 != perfectSquare % 9) continue;

Αν ο αριθμός είναι flawless τότε τον προσθέτουμε στο sum.

The End

• Η printf εκτυπώνει το αποτέλεσμα.
• Επιστρέφουμε success (0).