THMMY.gr

Topic που αφορά τις ασκήσεις του μαθήματος. Stay on topic!

Στις ασκησεις στο lg*n   το  *  σημαινει κατι ?

http://en.wikipedia.org/wiki/Iterated_logarithm

λιγο αργα το θυμηθηκα αλλα εχετε καμια ιδεα για το θεμα 3 προοδος 2014?

παίζει κανείς παλιός να έχει κατεβασμένες τις ασκήσεις στο κομμάτι του συμεωνίδη γιατί βαριέμαι να περιμένω να τις ανεβάσει?

Κανείς καμια ιδεα για το θεμα 3, προοδοςΒ 2014; Λεει οτι θυμιζει ενα προβλημα που εχουμε μελετησει αλλα δεν μπορω να σκεφτω ποιο εννοει...  (μεγιστη κοινη υπακολουθια;;; )

Κάνε απαγωγή σε άτοπο...μπορεί να είναι κάποιο άλλο πέραν αυτού..;
Μάλλον Μέγιστη κοινή Υπακολουθία είναι..  ;)
Ας το επιβεβαιώσει και κάποιος άλλος... μην είναι τίποτα που δεν το βλέπουμε και μας ξεγελάει.. :D

Ωραια και μενα αυτη ηταν η πρωτη μου σκεψη αλλα το κοιταω και το ξανακοιταω και δε μπορω να καταλαβω πως να χρησιμοποιησω εκεινη τη λυση για να με βοηθησει σε αυτο το προβλημα... Λιγο χελπ;

Λες να παίζει η κατανομή δραστηριοτητων σε αίθουσες;
Π.χ. Μέγιστο διάστημα ανόδου == Κάτι σαν περισσότερες δραστηριότητες... το ψάχνω λίγο ακόμα... παίζει να μοιάζει και μ'αυτό..

Ο συνάδελφος Psofia Psira προτείνει την εξης λυση, την οποια δοκιμασα για αρκετες περιπτωσεις και λειτουργει σωστα:
(και την ποσταρω εγω γιατι αυτος μας γραφει στα παπαρια του ( <3 μονο) )

Εστω Ρ(i) το μεγιστο μηκος υπακολουθιας τασης ανοδου για τα στοιχεια απο 1 εως i (ξεκινώντας απο το πρωτο στοιχειο). Συμβολιζουμε με d(i) την ι-οστη τιμη της ακολουθιας.
Αρχικη συνθηκη Ρ(1) = 1
Αναδρομικη σχεση:
Για 2 <= j <= n :

                    {    P( i ) + 1, αν d(i) < d(j)
P ( j ) = max  {
ως προς i<j    {    P( i ) ,  διαφορετικά

Η λυση ειναι βελτιστη γιατι χρησιμοποιουμε τις λυσεις υποπροβληματων οι οποιες ειναι και αυτες βελτιστες.

Αλλη απορια: Στην ενεργειακη αναλυση , υπαρχει καποιος κανονας οσον αφορα τον ορισμο της συναρτησης δυναμικου περα απο τον περιορισμο Φ( D_n ) >= Φ( D₀ ) ? Στο βιβλιο δεν λεει τιποτα ιδιαιτερο πανω σε αυτο, παιρνει αυτος συναρτησεις δυναμικου χωρις να το δικαιολογει ιδιαιτερα...

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

Αν δεν εχεις μια απο τις περιπτωσεις που ειδαμε στη ταξη, τι κανεις  :P

έχει καταλάβει κανείς πώς υπολογίζει την συνεισφορά στο παράδειγμα που έχει το βιβλίο σελ.359??

Μπορει καποιος να ανεβασει τις ασκησεις απο τα τελυταια δυο μαθηματα με τον Θεμη?

Τι εκανε?

Στο χρονοδιαγραμμα στο ethmmy γραφει τι εκανε. Ηταν καποιες ασκησεις απο τα φυλλαδια των κεφαλαιων 17 και 23. Ειναι ολες ανεβασμενες και λυμενες.

Τα εχω δει αυτα.
Περισυ ειχε κανει μια ασκηση με χρονοπρογραμματισμο σε λιμανι η οποια επεσε σχεδον αυτουσια. Δεν υπηρχε κατι στα φυλλαδια.

Επειδη πηγα στα μαθηματα, εκανε ακριβως αυτα που λενε τα φυλλαδια, με εξαιρεση ενα παλιο θεμα που ειχε huffman και δεν ηταν τιποτα σπουδαιο.

Επειδη παλευω τις τελευταιες μερες τα προβληματα στο contests (και μου βγαλανε λιγο τη ψυχη), βρηκα τη λυση στα πρωτα δυο και τη ποσταρω και εδω:

To cable cutting, ειναι ιδιο με το ακεραιο σακιδιο στο οποιο επιτρεπονται πολλα αντιγραφα του ιδιου αντικειμενου, η λυση ειναι εδω:
http://people.cs.clemson.edu/~bcdean/dp_practice/dp_0.swf

Το valar morghulis, ειναι ιδιο με αυτο εδω:
http://people.cs.clemson.edu/~bcdean/dp_practice/dp_8.swf

Αν καποιος εχει λυσει τα αλλα δυο, δε θα ταν κακο να τα ποσταρει εδω  :)

Για τον Huffman υπάρχει αλγόριθμος στο βιβλίο, τα υπόλοιπα βήματα είναι τετριμμένα.
Για το άλλο είναι άπληστος αλγόριθμος. Βρίσκεις το μέγιστο κουτί που χωράει και θεωρείς μόνο εκείνες τις σειρές του πίνακα και τις γεμίζεις μετά με μικρότερα κ.ο.κ. Μετά από αυτό το βήμα κάποιες σειρές θα είναι γεμάτες, οπότε τις αγνοείς και συνεχίζεις με το υπόλοιπο κομμάτι του πίνακα και κάνεις τα ίδια βήματα.

Και γω καπως ετσι το σκεφτηκα, αλλα δεν μπορω να γραψω την αναδρομικη σχεση που το εκφραζει αυτο...  (Toν απληστο εννοω οχι το huffman)

 ^super^

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

Σχετικα με σωστο - λαθος στην προοδο 2014Β:

Τα πρωτα δυο μου φαινονται σωστα, δεν ξερω πως να τα αποδειξω.

Το τριτο νομιζω οτι ειναι λαθος, αν εχω καταλαβει καλα τι εννοει. Αν εννοει οτι ο κυκλος εχει μοναδικη ακμη μικροτερου βαρους e, τοτε ειναι λαθος και το αντιπαραδειγμα ειναι αυτη η ασχημη εικονα:
http://imgur.com/BfAKqL8
Το 2 ειναι η ακμη μικροτερου βαρους στον κυκλο εκεινο, αλλα οπως φαινεται μπορω να φτιαξω ΕΣΔ, χωρις να την συμπεριλαβω.

Αν εννοει οτι ειναι η μιρκοτερη σε ολοκληρο το γραφημα, τοτε παω πασο, σωστο πρεπει να ειναι. Να το αποδειξω δε μπορω  :P

Ας το επιβεβαιωσει καποιος.

Άτοπο δοκίμασες; Συν ότι τα ΕΣΔ είναι άκυκλα

Όταν λεει όμως ότι το G έχει έναν κύκλο με...
Εννοεί ότι υπάρχει ΜΟΝΟ ένας κύκλος? ή υπάρχουν κι άλλοι?

Αν υπάρχει μόνο ένας είναι Σωστό.Αν υπάρχουν κι αλλοι είναι Λάθος.

νομιζω σωστα τα λεει η παπια

Να ρωτησω
Στην περσινη 2η προοδο ποιο ειναι το λαθος του αλγοριθμου στο 3ο θεμα;  :-\

https://www.youtube.com/watch?v=4fQJGoeW5VE
αυτο για το 3ο θεμα

Αν θυμαμαι καλα ο "λαθος" αλγοριθμος ελυνε το προβλημα απληστα, αντι με δυναμικο που το λυνει βελτιστα

Αν κανεις swap νουμερα σε αυτην που εχει ως παραδειγμα εβγαινε νομιζω.Δε το χω μπροστα μου αλλα πρεπει να βαλα το 7 στη θεση του 3 or sth

3 θέμα αυτό πρόοδος 2014.πως λυνεται;

https://www.hackerrank.com/challenges/longest-increasing-subsequent

αυτο είναι, απλά έχει βάλει τον περιορισμό να μετράς μόνο αυτές που περιέχουν και το πρώτο στοιχείο.

edit:repost δεν είδα οτι έχει απαντηθεί

guys λιγη βοηθεια στα θεματα της 1η προοδου του 2014

στο Θεμα Α

2)δεν μπορουμε γιατι δε δινει αρχικες τιμες?

στο Θεμα Β
Τ_Α(n) = Θ(n^lg5)
T_B(n) = Θ(n²)
αρα ο Β εχει καλυτερο χρονο εκτελεσης?

και μια γενικοτερη βοηθεια στο Θεμα Γ αν μπορει κανεις  ::)

Ναι εννοούσα α πρόοδος. Όχι αυτό πρόοδος  :P

το βελτιστο μου φαινεται οτι ειναι αφου κανει τα request n-h(n) και του πουν ναι για 1η φορα, μετα να αρχισει να κατεβαινει 1-1 μεχρι να του πουν 2η φορα ναι.

πχ η εταιρεια θα του δωσει 20 και αυτος αρχιζει απο το 30 και κατεβαινει με βημα 15. Θα πει 30, θα παρει οχι, θα πει 15 θα παρει ναι, και μετα θα αρχισει να κατεβαινει 1-1 απο το 30 μεχρι να παρει ναι ουσιαστικα στο ποσο που η εταιρεια θα εδινε.

Για τους χρονους τωρα δεν ειμαι 100% σιγουρος, αλλα για το ερωτημα 1, το χειροτερο ειναι να αρχισει απο ν και ο μισθος να ναι 1 και να τους ρωτησει ολους εναν εναν μεχρι να φτασει.

Για το 3) το χειροτερο θα βγαινει καπως αν κανει πολυ μεγαλο αλμα με το h(n) και μετα χρειαζεται να τα ρωταει ενα ενα ολα. πχ αν ο μισθος του ειναι 2 και αυτος αρχισει απο το 30 να κατεβαινει με βημα 29 , μετα θα πρεπει να τα ρωταει ολα απο το 29 μεχρι το 2 ενα ενα.

μην παρω κανενα στο λαιμο μου δεν ειμαι σιγουρος αλλα εγω καπως ετσι θα το πηγαινα

Μηπως εχει κανεις καμια ιδεα για το β) υποερωτημα απο Θεμα Γ της Α' προοδου 2015 ?

Το θέμα συνέχιζε  ...αν τρέξουμε τον αλγόριθμο από 1 ως 10.

ρε για πειτε μια στο Β της α προοδου 2015 τελικα ποιο ειναι σωστο;

+1

επισης αν μπορει καποιος να μας πει πως λυνοταν το θεμα 2 της προοδου που γραψαμε την προηγουμενη εβδομαδα

εγω βρηκα οτι T(n) = 3n/2 - 2

παιζει να υπαρχουν πουθενα τα θεματα?

Το θέμα που έπεσε στο δυναμικό υπάρχει στο http://contests.ee.auth.gr (συγκεκριμένα το Valar Morghulis)

Στο θεμα Α της 1ης προοδου του 2015 βρηκατε τις προτασεις ΛΑΘΟΣ ετσι?

ετσι νομιζω εγω το εκανα στην πρωτη με αντιπαραδειγμα οπου f(n) = n και g(n) = n+1
και στην δευτερη με αντιπαραδειγμα οπου f(n) = 2ⁿ και g(n) = 2²ⁿ  f(n) = 2²ⁿ και  g(n) = 2ⁿ

πως το κανες;
Βασικα εγω πηρα το πρωτο και το ελεγξα με ανισοτητα και ψιλο βγαινει
Επισης εχει μια παρομοια λυμενη στο 4ο κεφ στις ασκησεις

το 1ο πως βγαινει σαν αντιπαραδειγμα;
εντιτ:
το 2ο πως βγαινει σαν αντιπαραδειγμα;

εγω το εκανα ως εξης, λεω εστω οτι ειναι το πρωτο αρα Τ(n) = 2lgn -1.
ελεγχω αν Τ(2) = 1 (Τ(2) = 2lg2 -1 = 1 αρα ισχυει για n=1) και στη συνεχεια κανω οτι λεει η ασκηση 2.3-3. Δοκιμαζοντας και τις 3 περιπτωσεις βγαινει το γ ως σωστο

σωστος εισαι

καταρχας ειπα βλακεια το 1ο δεν ειναι λαθος ειναι σωστο (δεν το χω αποδειξει ακομα μαθηματικα αλλα i'm working on it :P )
το 2ο τωρα... λοιπον εχεις f(n) = 2²ⁿ αρα lgf(n)= 2n ομοια για g(n) βγαζεις οτι lgg(n)=n και ισχυει οτι 2n=Θ(n) ομως αμα δεις δεν ισχυει οτι 2²ⁿ=Θ(2ⁿ) (τσεκαρε ασκηση 6 κεφαλαιο 3 απο αυτες που εκανε ο Θεμης)

Λεει παντως να μην θεωρησουμε οτι οι ολες οι ακμες εχουν διαφορετικα βαρη,εκτος αν το λεει ρητα.Αρα η ακμη ειναι η μικροτερη απο ολες.

ναι αλλα στο αντιπαραδειγμα, σου λεει οτι πρεπει να ισχυει το 1ο και να μην ισχυει το 2ο.Δεν εχει διπλη συνεπαγωγη.
Τελοσπαντων,το 1ο συμφωνω οτι ειναι σωστο και το 2ο οτι ειναι λαθος.
Το αντιπαραδειγμα μου ειναι
f(n)=n² και g(n)=n

Στην προοδο 14Β στο θεμα 2 ποια ειναι η συναρτηση δυναμικου?