Πρόβλημα #2

Συζητήσεις για προετοιμασία για τον διαγωνισμό, online διαγωνισμούς, βιβλία προγραμματισμού και αλγορίθμων, και όλων των σχετικών.
Απάντηση
feedWARd
Δημοσιεύσεις: 72
Εγγραφή: Κυρ Δεκ 21, 2008 3:32 pm

Πρόβλημα #2

Δημοσίευση από feedWARd » Παρ Ιούλ 30, 2010 8:59 pm

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

Άβαταρ μέλους
thetrojan01
Δημοσιεύσεις: 712
Εγγραφή: Κυρ Δεκ 21, 2008 2:45 pm
Τοποθεσία: Ρόδος
Επικοινωνία:

Re: Πρόβλημα #2

Δημοσίευση από thetrojan01 » Κυρ Αύγ 01, 2010 3:01 am

Μού ρχεται στο μυαλό παραλλαγή ενός γνωστού αλγορίθμου...
Spoiler: show
αναζήτησης, φυσικά.
Ο αλγόριθμος για τι «περιβάλλον προορίζεται» ? Μέγιστο Ν?
svyr cercrv an inevrfnv cbyl tvn an gb iyrcrvf nhgb... cvtrar xnzvn ibygn yrj tj.

feedWARd
Δημοσιεύσεις: 72
Εγγραφή: Κυρ Δεκ 21, 2008 3:32 pm

Re: Πρόβλημα #2

Δημοσίευση από feedWARd » Κυρ Αύγ 01, 2010 4:46 am

thetrojan01 έγραψε:Ο αλγόριθμος για τι «περιβάλλον προορίζεται» ? Μέγιστο Ν?
Το μέγιστο Ν εξαρτάται από την πολυπλοκότητα του αλγορίθμου σου... ;)

Άβαταρ μέλους
Κηπουρίδης
Δημοσιεύσεις: 298
Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm

Re: Πρόβλημα #2

Δημοσίευση από Κηπουρίδης » Κυρ Αύγ 01, 2010 9:32 am

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

Άβαταρ μέλους
thetrojan01
Δημοσιεύσεις: 712
Εγγραφή: Κυρ Δεκ 21, 2008 2:45 pm
Τοποθεσία: Ρόδος
Επικοινωνία:

Re: Πρόβλημα #2

Δημοσίευση από thetrojan01 » Κυρ Αύγ 01, 2010 12:58 pm

Κηπουρίδης έγραψε:Εμένα πάλι γιατί το μόνο που με έρχεται στο μυαλό είναι μια brute force που για Ν > 10 θα αργεί μισό λεπτό :D ;
Ναι, αλλά πώς ελέγχεις εάν όντως υπάρχει λύση; (χμμμ κάτι μου λέει ότι αυτό είναι το πιο δύσκολο κομμάτι του αλγορίθμου)...
svyr cercrv an inevrfnv cbyl tvn an gb iyrcrvf nhgb... cvtrar xnzvn ibygn yrj tj.

chris
Δημοσιεύσεις: 528
Εγγραφή: Κυρ Δεκ 28, 2008 9:27 am

Re: Πρόβλημα #2

Δημοσίευση από chris » Κυρ Αύγ 01, 2010 1:00 pm

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

Πιστεύω πως έχω βρεί μια αρχή. Σχεδόν.
Spoiler: show
Για κάθε κελί που δεν είναι 0, πρέπει να πατήσουμε ή το κουμπί της στήλης του, ή το κουμπί της γραμμής του. Το θέμα είναι, ποιό από τα δύο και με ποιά σειρά;
Πιθανώς να δημοσιεύσω την θεωρία μου αργότερα το απόγευμα αν και προς το παρών έχω κολλήσει.

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

Άβαταρ μέλους
thetrojan01
Δημοσιεύσεις: 712
Εγγραφή: Κυρ Δεκ 21, 2008 2:45 pm
Τοποθεσία: Ρόδος
Επικοινωνία:

Re: Πρόβλημα #2

Δημοσίευση από thetrojan01 » Κυρ Αύγ 01, 2010 1:09 pm

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

Αμάν εσείς οι ηλεκτρονικοί και οι πύλες NOT σας!
(πλακίζω, πλιζ δίνε μας προβλήματα feedWARd!)
svyr cercrv an inevrfnv cbyl tvn an gb iyrcrvf nhgb... cvtrar xnzvn ibygn yrj tj.

Άβαταρ μέλους
Κηπουρίδης
Δημοσιεύσεις: 298
Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm

Re: Πρόβλημα #2

Δημοσίευση από Κηπουρίδης » Κυρ Αύγ 01, 2010 1:12 pm

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

sotiris
Δημοσιεύσεις: 422
Εγγραφή: Τρί Φεβ 10, 2009 9:49 pm

Re: Πρόβλημα #2

Δημοσίευση από sotiris » Κυρ Αύγ 01, 2010 3:41 pm

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

feedWARd
Δημοσιεύσεις: 72
Εγγραφή: Κυρ Δεκ 21, 2008 3:32 pm

Re: Πρόβλημα #2

Δημοσίευση από feedWARd » Κυρ Αύγ 01, 2010 4:06 pm

Κηπουρίδης έγραψε: Ρε feedWARd , μήπως να μας πεις αν υπάρχει μη - brute force λύση ( τουλάχιστον αν έχεις βρει εσύ κάποια ) , μη παιδευόμαστε άδικα ;
Υπάρχει μη - brute force λύση. Δεν το έβαλα το πρόβλημα για να μου πείτε "brute force" :P

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

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

Άβαταρ μέλους
thetrojan01
Δημοσιεύσεις: 712
Εγγραφή: Κυρ Δεκ 21, 2008 2:45 pm
Τοποθεσία: Ρόδος
Επικοινωνία:

Re: Πρόβλημα #2

Δημοσίευση από thetrojan01 » Κυρ Αύγ 01, 2010 4:26 pm

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

Θα το παλέψω μόλις βρω λίγη ησυχία στο σπίτι.
svyr cercrv an inevrfnv cbyl tvn an gb iyrcrvf nhgb... cvtrar xnzvn ibygn yrj tj.

Άβαταρ μέλους
kernelpanic
Δημοσιεύσεις: 404
Εγγραφή: Κυρ Δεκ 21, 2008 8:16 pm
Τοποθεσία: Αθήνα

Re: Πρόβλημα #2

Δημοσίευση από kernelpanic » Δευ Αύγ 02, 2010 3:38 pm

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

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

Θεωρητικά δουλεύει μέχρι Ν=20, μετά πρέπει να αλλάξεις τα μεγέθη των πινάκων.
Μπορεί κάποιος να μου εξηγήσει γιατί δεν παίρνει αρχεία με κατάληξη BAS;
Συνημμένα
PIXELS.TXT
Αεροτομή!!!
(2.96 KiB) Μεταφορτώθηκε 325 φορές
Τελευταία επεξεργασία από το μέλος kernelpanic την Δευ Αύγ 02, 2010 7:37 pm, έχει επεξεργασθεί 2 φορές συνολικά.
99 little bugs in the code,
99 bugs in the code,
Fix one bug,
Compile again,
104 little bugs in the code.

chris
Δημοσιεύσεις: 528
Εγγραφή: Κυρ Δεκ 28, 2008 9:27 am

Re: Πρόβλημα #2

Δημοσίευση από chris » Δευ Αύγ 02, 2010 6:11 pm

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

Τώρα το υλοποιώ σε Basic...Θα κάνω έντιτ μόλις τελειώσω.
ΟΟΟΟΟΟΟΟΟΟΟΟΧΧΧΧΧΧΧΧΧΧΧΧΧΧΧΧΧΙΙΙΙΙΙΙΙΙΙΙΙΙΙΙΙΙΙΙΙΙΙΙΙΙΙ BASIC!
Αστειεύομαι :)
Μετα από 397 δημοσιεύσεις, έβαλα και υπογραφή.

Άβαταρ μέλους
kernelpanic
Δημοσιεύσεις: 404
Εγγραφή: Κυρ Δεκ 21, 2008 8:16 pm
Τοποθεσία: Αθήνα

Re: Πρόβλημα #2

Δημοσίευση από kernelpanic » Δευ Αύγ 02, 2010 6:17 pm

QuickBasic, για να είμαι πιο ακριβής. :twisted:
Σοβαρά τώρα, τη προτιμώ όταν θέλω να κάνω διάφορα πειράματα, ειδικά όταν αφορούν γραφικά. Κυρίως για την ταχύτητα ανάπτυξης, όμως, όταν θέλω να φτιάξω κάτι απλό.
Και το πιο σημαντικό: γιατί ήταν, είναι και θα μείνει η μοναδική μου αγάπη. :lol:
99 little bugs in the code,
99 bugs in the code,
Fix one bug,
Compile again,
104 little bugs in the code.

Άβαταρ μέλους
thetrojan01
Δημοσιεύσεις: 712
Εγγραφή: Κυρ Δεκ 21, 2008 2:45 pm
Τοποθεσία: Ρόδος
Επικοινωνία:

Re: Πρόβλημα #2

Δημοσίευση από thetrojan01 » Τρί Αύγ 03, 2010 3:07 am

FUCKING BASIC?!?!?!! :evil:
WELL,

Εικόνα
Spoiler: show
No, Screw you, guys; home.
Spoiler: show
Για όποιον δεν το 'πιασε:
svyr cercrv an inevrfnv cbyl tvn an gb iyrcrvf nhgb... cvtrar xnzvn ibygn yrj tj.

Άβαταρ μέλους
kernelpanic
Δημοσιεύσεις: 404
Εγγραφή: Κυρ Δεκ 21, 2008 8:16 pm
Τοποθεσία: Αθήνα

Re: Πρόβλημα #2

Δημοσίευση από kernelpanic » Τετ Αύγ 04, 2010 4:47 pm

Βασικά έκανα λάθος πριν:
Γίνεται σε χρόνο Ν^2 και χώρο Ν, με λίγες αλλαγές.
Ποστάρω σε λίγο. :oops:
99 little bugs in the code,
99 bugs in the code,
Fix one bug,
Compile again,
104 little bugs in the code.

Άβαταρ μέλους
Κηπουρίδης
Δημοσιεύσεις: 298
Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm

Re: Πρόβλημα #2

Δημοσίευση από Κηπουρίδης » Δευ Ιαν 03, 2011 7:04 pm

Τελικά, πῶς;;;
Εικόνα

userresu
Δημοσιεύσεις: 191
Εγγραφή: Τρί Δεκ 16, 2008 9:53 pm

Re: Πρόβλημα #2

Δημοσίευση από userresu » Δευ Ιαν 03, 2011 8:42 pm

Spoiler: show
1) Πατάω το κουμπί της πρώτης γραμμής
2) Για κάθε κουμπί στήλης έστω j, το πατάω αν το στοιχείο στη θέση (1,j) είναι 1, αλλιώς δεν το πατάω.
3) Για κάθε κουμπί γραμμής (από τη 2η και μετά), αν όλα τα στοιχεία της γραμμής είναι 0 δεν το πατάω, ενώ αν όλα είναι 1 το πατάω. Σε διαφορετική περίπτωση δεν υπάρχει λύση.
4) Αν ο αριθμός των κουμπιών που πάτησα στα παραπάνω βήματα είναι a, η απάντηση είναι min(a,2N-a) (Σκεφτείτε γιατι)
Time: O(N2)
Memory: O(N) (το προφανές είναι O(N2) αλλα μπορεί να γίνει O(N), το αφήνω σαν άσκηση)
Τελευταία επεξεργασία από το μέλος thetrojan01 την Τρί Ιαν 04, 2011 3:03 pm, έχει επεξεργασθεί 2 φορές συνολικά.
Λόγος: Ο(Ν) -> Ο(Ν^2)

Άβαταρ μέλους
Κηπουρίδης
Δημοσιεύσεις: 298
Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm

Re: Πρόβλημα #2

Δημοσίευση από Κηπουρίδης » Τρί Ιαν 04, 2011 1:43 am

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

Άβαταρ μέλους
kernelpanic
Δημοσιεύσεις: 404
Εγγραφή: Κυρ Δεκ 21, 2008 8:16 pm
Τοποθεσία: Αθήνα

Re: Πρόβλημα #2

Δημοσίευση από kernelpanic » Τρί Ιαν 04, 2011 7:32 pm

To «σε λίγο» είναι σχετικό. Όπως τα τέρμινα :oops:
Συνημμένα
PIXELS2.txt
Ένα γρήγορο patch, δε ξέρω αν δουλεύει ακριβώς όπως το παλιό pixels.txt
(2.94 KiB) Μεταφορτώθηκε 344 φορές
99 little bugs in the code,
99 bugs in the code,
Fix one bug,
Compile again,
104 little bugs in the code.

Απάντηση