pdp forum

Ετοιμαστείτε, ο διαγωνισμός Hellenico Ιανουαρίου ξεκινάει το Σάββατο, διαρκεί τρεις μέρες, και παίρνουμε μέρος όποτε θέλουμε.
Άντε να ξεσκουριάζουμε.

Έχει κανείς ιδέα πως λύνουμε το "Παρακολούθηση Πολυκατοικιών";

Όταν μας λένε ότι η πολυκατοικία Α βλέπει την Β, τι πληροφορίες παίρνουμε;
i) Η Α είναι μικρότερη της Β.
ii) Όλες οι πολυκατοικίες μεταξύ της Α και της Β είναι μικρότερες της Α ( αν δεν ήταν μικρότερες, τότε η Α θα έβλεπε κάποια από αυτές, κι όχι τη Β ).

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

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

Καλή συνέχεια