Πρόβλημα #2

[feedWARd]

Έχουμε έναν πίνακα Ν χ Ν όπου κάθε στοιχείο του είναι 0 ή 1. Κάθε γραμμή και κάθε στήλη του έχει ένα κουμπί. Πατώντας το κουμπί μιας γραμμής ή μιας στήλης εναλλάσονται όλα τα στοιχεία της (τα 0 γίνονται 1 και τα 1 γίνονται 0). Θέλουμε πατώντας κάποια κουμπιά να αλλάξουμε τον πίνακα ωστέ τελικά να αποτελείται μόνο από μηδενικά. Βρείτε αλγόριθμο που να διαβάζει έναν πίνακα και 1) να ελέγχει αν υπάρχει λύση, 2) να βρίσκει μια λύση που να αποτελείται από τον ελάχιστο αριθμό πατημάτων. Γράψτε time και memory complexıty.

[thetrojan01]

Μού ρχεται στο μυαλό παραλλαγή ενός γνωστού αλγορίθμου...

Spoiler: show

αναζήτησης, φυσικά.

Ο αλγόριθμος για τι «περιβάλλον προορίζεται» ? Μέγιστο Ν?

[feedWARd]

Ο αλγόριθμος για τι «περιβάλλον προορίζεται» ? Μέγιστο Ν?

Το μέγιστο Ν εξαρτάται από την πολυπλοκότητα του αλγορίθμου σου...

[Κηπουρίδης]

Εμένα πάλι γιατί το μόνο που με έρχεται στο μυαλό είναι μια brute force που για Ν > 10 θα αργεί μισό λεπτό ;

[thetrojan01]

Εμένα πάλι γιατί το μόνο που με έρχεται στο μυαλό είναι μια brute force που για Ν > 10 θα αργεί μισό λεπτό ;

Ναι, αλλά πώς ελέγχεις εάν όντως υπάρχει λύση; (χμμμ κάτι μου λέει ότι αυτό είναι το πιο δύσκολο κομμάτι του αλγορίθμου)...

[chris]

@thetrojan01 + Κηπουρίδης: Σκέφτηκα αυτό που σκεφτήκατε, άλλα με την βοήθεια του feedWARd κατέλειξα πως χρειάζεται κάτι πολύ καλύτερο. Για N>5 θα αργεί δραματικά πολύ η bruteforce BFS. Εάν το έπρεπε να το λύσω σε διαγωνιστικό περιβάλλον, θα έκανα αυτήν την χαζή λύση και αν το N είναι μεγαλύτερο από 5 θα θεωρούσα πως δεν υπάρχει δυνατή λύση.

Πιστεύω πως έχω βρεί μια αρχή. Σχεδόν.

Spoiler: show

Για κάθε κελί που δεν είναι 0, πρέπει να πατήσουμε ή το κουμπί της στήλης του, ή το κουμπί της γραμμής του. Το θέμα είναι, ποιό από τα δύο και με ποιά σειρά;

Πιθανώς να δημοσιεύσω την θεωρία μου αργότερα το απόγευμα αν και προς το παρών έχω κολλήσει.

edit: @tt1, αν δεν υπάρχει λύση μια απλή bfs απλά θα τελειώσει χωρίς να έχει βρεί λύση. Βέβαια για N>5 δεν θα τελειώσει

[thetrojan01]

Όντως, μια BFS θα τερματίσει χωρίς να δώσει απάντηση

Αμάν εσείς οι ηλεκτρονικοί και οι πύλες NOT σας!
(πλακίζω, πλιζ δίνε μας προβλήματα feedWARd!)

[Κηπουρίδης]

Εμένα πάλι γιατί το μόνο που με έρχεται στο μυαλό είναι μια brute force που για Ν > 10 θα αργεί μισό λεπτό ;

Ναι, αλλά πώς ελέγχεις εάν όντως υπάρχει λύση; (χμμμ κάτι μου λέει ότι αυτό είναι το πιο δύσκολο κομμάτι του αλγορίθμου)...

Ε , αυτό είναι εύκολο , εγώ το συντομότερο νομίζω δεν μπορώ να βρω ........ θα το δοκιμάσω μεθαύριο και θα σε πω .
Ακριβώς εκεί που κοιτιέται ο chris ψάχνομαι κι εγώ αλλά δεν έχω βρει κάτι ενδιαφέρον . Ρε feedWARd , μήπως να μας πεις αν υπάρχει μη - brute force λύση ( τουλάχιστον αν έχεις βρει εσύ κάποια ) , μη παιδευόμαστε άδικα ;

[pman]

Πάντα υπάρχει brute-force λύση σε κάποιο πρόβλημα. Όντως BFS θέλει και είσαι έτοιμος. Το πρόβλημα αυτό το έχω ξαναδεί νομίζω κάπου.

[feedWARd]

Ρε feedWARd , μήπως να μας πεις αν υπάρχει μη - brute force λύση ( τουλάχιστον αν έχεις βρει εσύ κάποια ) , μη παιδευόμαστε άδικα ;

Υπάρχει μη - brute force λύση. Δεν το έβαλα το πρόβλημα για να μου πείτε "brute force"

Ήδη με την παρατήρηση του chris μπορούμε να κατασκευάσουμε μια πολύ καλύτερη brute-force λύση από την BFS-brute force.

Btw, αν θυμάμαι καλά με τον chris βρήκαμε οτί το BFS είναι πολυπλοκότητας Ο(N * 2^(N^2) ) και ίσως και χειρότερο (ανάλογα με το πως θα κωδικοποιήσεις το state σου).

[thetrojan01]

BFS με ευριστικούς σκεπτόμουν.
Μα και πάλι, δε μου έρχεται κανένας ευριστικός στο μυαλό.

Θα το παλέψω μόλις βρω λίγη ησυχία στο σπίτι.

[kernelpanic]

Νομίζω γίνεται σε
χρόνο Ν^2
και χώρο Ν^2
(Όχι ακριβώς, αλλά το Ν^2 είναι το σημαντικότερο)

ΕΝΤΙΤ: Έτοιμο!

Θεωρητικά δουλεύει μέχρι Ν=20, μετά πρέπει να αλλάξεις τα μεγέθη των πινάκων.
Μπορεί κάποιος να μου εξηγήσει γιατί δεν παίρνει αρχεία με κατάληξη BAS;

[chris]

Νομίζω γίνεται σε
χρόνο Ν^2
και χώρο Ν^2
(Όχι ακριβώς, αλλά το Ν^2 είναι το σημαντικότερο)

Τώρα το υλοποιώ σε Basic...Θα κάνω έντιτ μόλις τελειώσω.

ΟΟΟΟΟΟΟΟΟΟΟΟΧΧΧΧΧΧΧΧΧΧΧΧΧΧΧΧΧΙΙΙΙΙΙΙΙΙΙΙΙΙΙΙΙΙΙΙΙΙΙΙΙΙΙ BASIC!

Αστειεύομαι

[kernelpanic]

QuickBasic, για να είμαι πιο ακριβής.
Σοβαρά τώρα, τη προτιμώ όταν θέλω να κάνω διάφορα πειράματα, ειδικά όταν αφορούν γραφικά. Κυρίως για την ταχύτητα ανάπτυξης, όμως, όταν θέλω να φτιάξω κάτι απλό.
Και το πιο σημαντικό: γιατί ήταν, είναι και θα μείνει η μοναδική μου αγάπη.

[thetrojan01]

FUCKING BASIC?!?!?!!
WELL,

Spoiler: show

No, Screw you, guys; home.

Spoiler: show

Για όποιον δεν το 'πιασε:

[kernelpanic]

Βασικά έκανα λάθος πριν:
Γίνεται σε χρόνο Ν^2 και χώρο Ν, με λίγες αλλαγές.
Ποστάρω σε λίγο.

[Κηπουρίδης]

Τελικά, πῶς;;;

[userresu]

Spoiler: show

1) Πατάω το κουμπί της πρώτης γραμμής
2) Για κάθε κουμπί στήλης έστω j, το πατάω αν το στοιχείο στη θέση (1,j) είναι 1, αλλιώς δεν το πατάω.
3) Για κάθε κουμπί γραμμής (από τη 2η και μετά), αν όλα τα στοιχεία της γραμμής είναι 0 δεν το πατάω, ενώ αν όλα είναι 1 το πατάω. Σε διαφορετική περίπτωση δεν υπάρχει λύση.
4) Αν ο αριθμός των κουμπιών που πάτησα στα παραπάνω βήματα είναι a, η απάντηση είναι min(a,2N-a) (Σκεφτείτε γιατι)

Time: O(N²)
Memory: O(N) (το προφανές είναι O(N²) αλλα μπορεί να γίνει O(N), το αφήνω σαν άσκηση)

[Κηπουρίδης]

Ἰδιοφυές! Δὲν θὰ τὸ ἔβγαζα οὔτε τοῦ χρόνου. Καὶ πάλι μπράβο:D.

[kernelpanic]

To «σε λίγο» είναι σχετικό. Όπως τα τέρμινα