Palindromic Moments - IEEEXtreme

[Pseudonymo1212]

Καλησπέρα,

 

Μικρή εισαγωγή (εκτός θέματος)

Το IEEEXtreme είναι ένας παγκόσμιος διαγωνισμός προγραμματισμού για που διοργανώνεται κάθε χρόνο και συνήθως Οκτώβρη μήνα. Απευθύνεται σε φοιτητές που είναι μέλη της IEEE. Για περισσότερα, Google it!

 

Μικρό-προσωπικό παράπονο (εκτός θέματος)

"Και καλά για φοιτητές". Το επίπεδο δυσκολίας είναι τέτοιο που και επαγγελματίες δεν μπορούν να σκεφτούν λύση για κάποιο πρόβλημα.

 

 

 

Στο θέμα μας,

 

Για να μην διαβάζετε τζάμπα το Spoiler, η εκφώνηση είναι ΕΔΩ

*C# 3sec limit για κάθε Case. Αν δώσει 20, θα έχεις για κάθε case 3s και όχι 3ς και για τα 20. Ισχύει για όλες τις γλώσσες με τα αντίστοιχα Limits τους.

 

 

 

Ήταν μια άσκηση (Difficulty: Easy 'και καλά') που σου έδινε μια χρονιά σαν Input, και έπρεπε για κάθε second να βγάλεις την ημερομηνία με βάση κάποια Patterns. Ουσιαστικά θα έπρεπε να μορφοποίησης την στιγμή εκείνη με βάση 10-15 Patterns και να βρεις αν είναι παλινδρομικό το αποτέλεσμα. Ήθελε να βρεις πόσες παλινδρομικές στιγμές είχε το έτος-Χ.

 

*Σου έδινε χρονιά και έπρεπε να βρεις πόσες παλινδρομικές στιγμές έχει η χρονιά αυτή. Να ελέγξεις μέχρι και Sec (κρίμα που δεν ζήταγε και τα ms)

 

Παράδειγμα Input

2015

 

Output

5000~ Palindrome moments

 

Ξέχασα να αναφέρω ότι είχες 2-4-10s για να βρεις το αποτέλεσμα (C2, C#3, Java4...).

 

---

Πάμε στην λύση... τι σκεφτήκαμε

 

Σε C#,

DateTime start = new DateTime(givenYear, 1, 1, 0, 0, 0);
DateTime end   = new DateTime(givenYear +1, 1, 1, 0, 0, 0);

while(start < end)
{

    start.AddSecond(1);

    // Build the moment in x-format. Where x-format ~10 patterns (date formating patterns)
    // Example: 2015/1/1/0/0/0 > 201511000 , 1511000 ... and so...

    // Είναι τίποτα από αυτά που έβγαλες παλινδρομικό? Counter++; 

   ...
}

Στο περίπου τώρα. Σαν Solution, ήταν σωστό! το μεγάλο πρόβλημα ήταν ο χρόνος εκτέλεσης. Έτρεχε 2-3 λεπτά στα μηχανήματά μας και δεν βλέπαμε αποτέλεσμα (για 1 χρόνο). Το κατεβάσαμε στο 1 Month/Week για δοκιμές, έκανε κοντά στο μισό λεπτό.

 

Εδώ έρχονται οι 2 ερωτήσεις:

1. Πως στο καλό λύνεται αυτό το πράγμα? καμιά ιδέα? σίγουρα όχι με το να ελέγχεις κάθε Sec του έτους.
2. Πως μπορώ να προετοιμαστώ κατάλληλα για τέτοια προβλήματα? τι βιβλία να διαβάσω? ... και δεν μιλάω βιβλία του τύπου "usare Hashset αντί List..." και με Hashet τα ίδια ήταν. Το όλο πρόβλημα ήταν στην προσέγγιση της λύσης.

*Ψάχνω για βιβλία με "έξυπνους" τρόπους σε διάφορες λύσεις και όχι βιβλία που να μιλάνε για δομές, και να σου λένε usare το τάδε. Όπως είπα... αυτό δεν λυνόταν σε 3ς με ότι δομή και να είχες...

 

Πως μπορώ εγώ σαν φοιτητής να ξέρω ότι υπάρχει ένας "έξυπνος" τρόπος για αυτό και δεν χρειάζεται να ελέγξεις κάθε Sec?

 

Και για να μην ξεχνάω... "και καλά για φοιτητές ο διαγωνισμός... που πλέον κάνει μπαμ ότι σε μερικούς τα λύνουν άλλοι. Μήπως μας ελέγχει και κανείς? απλά λένε "μην κλέβετε γιατί το πνεύμα δεν είναι αυτό...".

 

Limits (τουλάχιστον για C#)

3s max runtime

512MB RAM

.NET 4 (no tasks)

0 threads allowed (so you can't use threads to solve it)

ΥΓ: Φανταστείτε η διάσχιση του while MONO (χωρίς τπτ μέσα) έπαιρνε 4-5seconds. Αυτό φυσικά (μετά στο σπίτι) το κατέβασα στα 35-40ms σε Release mode, και 125Ms~ σε Debug. (μεγάλη πατάτα είχα κάνει ε? ... )

 

To πρόβλημα που δεν ξεπερνιέται όμως είναι η παραγωγή των Strings για να δεις αν είναι παλινδρομικό...

[albNik]

Απειροι τροποι να γινει γρηγορότερο. 

Π.χ. αν έχεις time format κοιτάς τις παλινδρομικες μόνο για ένα 24ωρο, οχι για ολο το χρονο.

[Pseudonymo1212]

Απειροι τροποι να γινει γρηγορότερο. 

Π.χ. αν έχεις time format κοιτάς τις παλινδρομικες μόνο για ένα 24ωρο, οχι για ολο το χρονο.

 

Να σημειώσω ότι το σύστημα θέλει ακριβώς και όχι στο περίπου. Μπορεί π.χ το αποτέλεσμα να είναι 5600 και εσύ να βγάλεις 5500. Θα στο πάρει όλο λάθος.

 

To the point. Έχεις καμιά πρόταση(βιβλία, ιστοσελίδες) που μπορούμε να τριφτούμε σε τέτοια? γιατί όταν focus-αρεις στο συντακτικό... να μάθεις να προγραμματίζεις τις δομές κλπ... γμστα! Δηλαδή: Μπορεί κάποιος να ξέρει καλά μια γλώσσα αλλά να μην έχει αλγοριθμική σκέψη (να μην του κόβει). 

 

PS: Σκέψου... 2300 ομάδες και το αποτέλεσμα σε αυτό το πρόβλημα ήταν 7.5%. Οπότε το υπόλοιπο 92.5% ήταν Noobs που δεν σκέφτηκαν αυτό που λες  

[Kercyn]

Ψάχνω για βιβλία με "έξυπνους" τρόπους σε διάφορες λύσεις

 

Μα αυτό ακριβώς είναι προγραμματισμός. Δεν υπάρχουν βιβλία με "έξυπνους τρόπους σε διάφορες λύσεις". Και να υπήρχαν δηλαδή τι θα έκανες, θα καθόσουν να απομνημονεύσεις λύσεις; Υπάρχουν βιβλία/άρθρα/whatever για problem solving αλλά δεν έχω να προτείνω κάποιο συγκεκριμένο.

 

Καταρχάς έχεις ως input το έτος. Με βάση το format που επεξεργάζεσαι εκείνη τη στιγμή, ξέρεις άλλα 2 (τουλάχιστον) ψηφία των αριθμών που ψάχνεις και τις θέσεις τους. Με brute force αυτό το πράγμα δε βλέπω να βγαίνει σε 3-4 δευτερόλεπτα, οπότε πρέπει να βρεις τρόπους για να ψάχνεις λιγότερα ψηφία (μόλις σου είπα έναν, σίγουρα υπάρχουν κι άλλοι).

 

Φαίνεται αρκετά ενδιαφέρον και δεν καταλαβαίνω όλα τα "και καλά είναι για φοιτητές και δε μπορούν να το λύσουν επαγγελματίες". Επαγγελματίες προφανώς και μπορούν να το λύσουν, όπως και φοιτητές. Επειδή είναι πιο σοβαρό απ' τα τυπικά "να διαβάζει 10 τιμές και να βρίσκει μέσο όρο" προβλήματα δε σημαίνει ότι δεν είναι για φοιτητές.

[Pseudonymo1212]

Ρε συ... το συγκεκριμένο Xtreme (2015) με έκανε να νιώσω πολύ λίγος και γενικά πολύ "σκουπίδι". Και επειδή βγαίνω στην αγορά εργασίας σε λίγο... με έβαλε να σκεφτώ... wtf! im so useless!

PS: και φαντάσου δεν είμαι κάνα ψωνισμένο που βγαίνει και "φωνάζει" ξέρω αυτό ξέρω το άλλο.

 

Από την άλλη με παρηγορεί ότι σε πολλά προβλήματα το ποσοστό επιτυχίας ήταν πολύ χαμηλό.

 

Συγκεκριμένα

 

 

63.39% 
13.48% 
14.32%
9.69%
0.14% 
30.62% 
1.02%
7.33% 
35.00%
45.17% 
0.28% 
25.31% 
15.33% 
15.02%
33.45%
29.80% 
4.45% 
1.05%
0.91% 
56.67% 
21.40% 
15.71% 
0.72% 
20.29%
0.98%
....... 

 

 

 

0.14%/2300 ομάδες... 

 

ΥΓ: Αυτά τα ποσοστά είναι πόσοι το λύσανε και όχι προσωπικό ποσοστό.

ΥΓ2: Όσο για αυτό που λες στην 1η παράγραφο.. Σίγουρα! δεν πάω με τη λογική να μάθω απέξω... πάω με τη λογική να τριφτώ...

[Pseudonymo1212]

Εντάξ παιδιά! το πρόβλημα είναι γελοίο...

 

Λύση: Θα ψάχνεις ΜΟΝΟ 1 στιγμή κάθε μέρα

// Π.χ. 2015/1/1 > 11:20:15
Το μόνο που θα σου δώσει παλινδρομική στιγμή είναι το 115102 (11:51:02)

// Π.χ. 2015/1/2 (επόμενη μέρα)
Το μόνο που θα σου δώσει παλινδρομική στιγμή είναι το 215102 (21:51:02

....

// Π.χ.  2015/12/5 > 52:15:10:2 - ERROR
// Π.χ.  2015/8/8  > 88:51:02 - ERROR
2015/6/5 56:51:02 // ERROR
2015/1/24  42:15:10:2 // ERROR
2015/1/2   21:51:20 //ΟΚ

Οπότε: Με φορμάτ 4 ψηφίων για το έτος 2015:
1. Θα πας maximum 2η μέρα
2. Θα πας maximum 4ο μήνα
3. Και για 1&2 θα υπάρχει μόνο 1 στιγμή κάθε μέρα.
.....

Σαν να λέμε...

DateTime dt1 = new DateTime(2015, 1, 1, 11, 51, 02);
DateTime dt2 = new DateTime(2015, 4, 2, 24, 51, 02);

while(dt1 < dt2)
{
  // Check...

  // Εδώ θέλει λίγη δουλειά πόσο θα ανεβάσεις. Μερικές φορές θέλει λίγο παραπάνω.
  // Γενικά όμως, thats the logic!
  dt1.AddDays(1);

  
  // ....
} 

// Untested Code. Just the logic. Maby it is wrong! Maby all logic is wrong!

ή πολύ πιο απλά,

Για κάθε Year/Month/Day, 
- Άλλαξε το Day
- Βγάλε το αντίστροφο σε Time (πχ: 2015/12/24, which is the 42:21:51:02)
- Is valid (Hour 42? oh really?) ?

Και να αφήσετε να κάνει το λοοπ για όλο το χρόνο, με βήμα 1day, ΜΙΚΡΟ ΤΟ ΚΑΚΟ! 
ΚΑΙ ΑΣ ΞΕΡΟΥΜΕ ΟΤΙ ΑΥΤΟ ΤΟ ΦΟΡΜΑΤ ΜΟΝΟ ΜΕΧΡΙ 4ο μηνα, 2η μερα δινει παλινδρομικές στιγμές.

Δηλαδή: Για φορματ 2015/1/1 (δεν θυμάμαι ποιο είναι. yyyymmdd?),

ελέγχεις:

1-4 μήνα

ΚΑΙ ΜΟΝΟ 

μέχρι 2η μέρα του κάθε μήνα, μετά πηδάς επόμενο.

[nilosgr]

Αυτα τα προβληματα ειναι "δυναμικα προβληματα" και δεν υπαρχει γενικος τροπος λυσης περα του brute force (το οποιο κανει "αιωνες" να βρει λυση). Συνηθως οι λυσεις ειναι για συγκεκριμένο προβλημα και βασιζονται στο brute force, απλα χρησημοποιουν heuristics για να γλιτώσουν οσο το δυνατόν περισσότερες πραξεις. Παρολαυτα, χωρις brute force δεν εισαι παντα σιγουρος οτι βρηκες ολες ή τις καλυτερες λυσεις.

 

Γενικα υπαρχει πολυ πληροφορια, δες εδω: https://en.wikipedia.org/wiki/Computational_complexity_theory

[albNik]

 Παρολαυτα, χωρις brute force δεν εισαι παντα σιγουρος οτι βρηκες ολες ή τις καλυτερες λυσεις.

 

Αυτο που λες ειναι λαθος.

Ειναι σαν να λες οτι για να βρω πόσοι αριθμοί μεχρι το 10^20 διαιρούνται με 15 πρεπει να τους τεστάρω όλους για να είμαι σίγουρος οτι δεν ξέχασα κανένα . 

[Papakaliati]

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

 

Αν και δεν συμφωνω οτι το brute force ειναι ο πιο σωστος τροπος για να λυσεις το προβλημα, θεωρω οτι ειναι ο πιο σωστος,  συντομος και ασφαλης τροπος για το unit testing . 

[nilosgr]

Αυτο που λες ειναι λαθος.

Ειναι σαν να λες οτι για να βρω πόσοι αριθμοί μεχρι το 10^20 διαιρούνται με 15 πρεπει να τους τεστάρω όλους για να είμαι σίγουρος οτι δεν ξέχασα κανένα . 

Εε είπα παντα, αναλογα τη φυση του προβληματος και τη λυση

[Pseudonymo1212]

Δεν έχω ασχοληθεί ιδιαίτερα με το Brute Force... απλά ξέρω ότι είναι μέθοδος να σπας κωδικούς.

 

Μπορεί να γενικευτεί σαν μια μέθοδο που βρίσκεις εύκολα κάτι που θες?

 

Θα το μελετήσω... γιατί κάθε χρόνο βάζουν θέματα που λες "σε 3ς αυτό? σοβαρά?"... 

[παπι]

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

[Lanike71]

 

 

 

Δεν έχω ασχοληθεί ιδιαίτερα με το Brute Force... απλά ξέρω ότι είναι μέθοδος να σπας κωδικούς.

 

Μπορεί να γενικευτεί σαν μια μέθοδο που βρίσκεις εύκολα κάτι που θες?

 

Θα το μελετήσω... γιατί κάθε χρόνο βάζουν θέματα που λες "σε 3ς αυτό? σοβαρά?"... 

 

Brute force δεν είναι μέθοδος να σπας κωδικούς.

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

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

 

Ακόμα και τη λύση να μη βρεις, θα κερδίσεις πολλά ασχολούμενος με τέτοια προβλήματα.

[Pseudonymo1212]

Φαντάζομαι πως το Brute force δεν βασίζεται σε Threads και κυρίως σε RAM έτσι? γιατί οι κανόνες είναι ξεκάθαροι... 1 Thread, 512ΜΒ RAM, 3s runtime (εξαρτάται από τη γλώσσα)