pdp forum

http://hellenico.gr/contest/index.php?page=news&id=38

Από Σάββατο 28 Νοεμβρίου μέχρι Τρίτη 1 Δεκεμβρίου.
Δεν ποστάρουμε λύσεις/απορίες/διορθώσεις μέχρι να τελειώσει ο διαγωνισμός.

Καλή επιτυχία σε όλους τους διαγωνιζόμενους.

Ανακοινώθηκαν τα αποτελέσματα και οι λύσεις.

http://www.hellenico.gr/monthly/

Συγχαρητήρια σε όλους τους διαγωνιζόμενους!

Καλή χρονιά σε όλους.
Στο θέμα cipherkey που έχουν προταθεί οι λύσεις με hashing και zalgo, μήπως θα έπρεπε να συμπεριληφθεί και η τυπική σύγκριση string τύπου strcmp κατά K&R; Με μια μικρή βελτιστοποίηση στην αρχιτεκτονική του υπολογιστή, έχουμε μικρότερους χρόνους από την μέθοδο με hashing.

switch έγραψε:Καλή χρονιά σε όλους.
Στο θέμα cipherkey που έχουν προταθεί οι λύσεις με hashing και zalgo, μήπως θα έπρεπε να συμπεριληφθεί και η τυπική σύγκριση string τύπου strcmp κατά K&R; Με μια μικρή βελτιστοποίηση στην αρχιτεκτονική του υπολογιστή, έχουμε μικρότερους χρόνους από την μέθοδο με hashing.

Κώδικας: Επιλογή όλων

//#define NDEBUG

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <string.h>

char S[1000001],T[1000001];
int N = 0;

/* 
//τυπική απλή συνάρτηση για σύγκριση των 2 strings του Kernigham-Richie με
//τροποποίηση για να επιτρέπει διαφορά ενός χαρακτήρα
int mystrcmp(const char *s,const char *p,unsigned n){
	int diff = 0;
	while(*p){
		if(*p++ != *s++)
			if(++diff>1)
				return 1;//not equal
	}
	return 0;
}
*/

#define min2(a,b)	(a<b)?a:b

int mystrcmp(const char *s,const char *p,int n){
/*
Η συνάρτηση αυτη ειναι μια βελτιστοποιημένη  στην αρχιτεκτονική του υπολογιστή, τεχνική σύγκρισης χαρακτήρων συμβολοσειράς.
Οι καταχωρητές (registers) του υπολογιστή που χρησιμοποιεί ο compiler, έχουν μέγεθος όσο ένας int. 
Ο επεξεργαστής αυτός μπορεί και συγκρίνει με χρόνο εκτέλεσης μιας μόνο εντολής μηχανής, 
είτε συγκρίνουμε έναν int, είτε μόνο έναν char.
Δηλαδή αν συγκρίνω με int αντί για char, και ο int είναι 4πλασιος του char, όπως συμβαίνει στις τυπικές 32bit υλοποιήσεις,
τότε κάνω 1 σύγκριση αντί για 4. 
*/
	int diff = 0;//αριθμός διαφορών που βρέθηκαν
	#define UNSΙGNED_PTR(p)	((unsigned *)p)//μετέτρεψε τον δείκτη σε char, σε δείκτη σε unsigned int

	while(n>0){
		if(n>=sizeof(unsigned) && *UNSΙGNED_PTR(p) == *UNSΙGNED_PTR(s)){//γρήγορη προσπέλαση ίδιων τμημάτων
			p += sizeof(unsigned);
			s += sizeof(unsigned);
			n -= sizeof(unsigned);
		} else {//δεν έχουμε ικανό μεγεθος τμήματος 
			//για σύγκριση ή δεν είναι ίδια τα τμήματα. 
			//έλεγξε ένα-ένα τόσα bytes όσα έχει ο ακέραιος ή
			//μέχρι να εξαντληθεί το string,
			//ώστε να μην χαλάσουμε το βέλτιστο 
			//packing της αρχιτεκτονικής του υπολογιστή
			//(βλέπε #pragma pack() της C/C++)
			int i = min2(sizeof(unsigned),n);
			while(i-->0){
				if(*p++ != *s++ && ++diff>1)
					return 1;//δεν ταιριάζουν
				n--;
			}
		}
	}
	return 0;//ταιριάζουν
}

int main(){
	FILE *in = fopen("cipherkey.in","r"), *out=fopen("cipherkey.out","w");
	const char *Send,*s;
	int lenS,lenT,sc;
	
	assert(in);
	assert(out);
	
	sc = fscanf(in,"%s",S);	assert(sc==1);
	sc = fscanf(in,"%s",T);	assert(sc==1);
	
	lenS = strlen(S); lenT = strlen(T);
	Send=S+lenS-lenT;
	for(s=S;s<=Send;s++)
		if(!mystrcmp(s,T,lenT))
			N++;
		
	fprintf(out,"%d\n",N);
	
	return 0;
}

Καλησπέρα, ο κώδικας αυτός αν δεν κάνω λάθος έχει πολυπλοκότητα O( n^2 ), απλά είναι ίσως πολύ optimised και γι' αυτό σε testcases με n περίπου 50-60k να κάνει περίπου τον ίδιο χρόνο με την hashing ( ίσως και καλύτερο ) η οποία ωστόσο έχει πολύ καλύτερη πολυπλοκότητα O( nlog^2n ).

Αν το αρχείο δοκιμής αποτελείται από τον ίδιο χαρακτήρα τόσο στο S, όσο και στο Τ τότε πάμε σε O(N*N) αλλιώς σταματά πολύ γρήγορα (σε όλα τα άλλα τέστ οι χρόνοι είναι πολλοί μικροί σε βαθμό ανακρίβειας κατά την επανάληψη, διότι σπάει πολύ γρήγορα η σύγκριση).

Είναι φυσικά κατηγορίας brute force.

switch έγραψε:Αν το αρχείο δοκιμής αποτελείται από τον ίδιο χαρακτήρα τόσο στο S, όσο και στο Τ τότε πάμε σε O(N*N) αλλιώς σταματά πολύ γρήγορα (σε όλα τα άλλα τέστ οι χρόνοι είναι πολλοί μικροί σε βαθμό ανακρίβειας κατά την επανάληψη, διότι σπάει πολύ γρήγορα η σύγκριση).

Είναι φυσικά κατηγορίας brute force.

Για την ακριβεια τα testcases για τα οποια ενας τετοιος αλγοριθμος δεν περναει με τιποτα ειναι πολυ περισσοτερα. Αρκει να χρησιμοποιηθει το μοτιβο που αναφερατε, και καπου στη μεση του string να πεταμε λιγο randomly-generated κειμενο ωστε να μη μπορει να το προβλεψει ο διαγωνιζομενος.
Βεβαιως ο αλγοριθμος που χρησιμοποιει Hashing δε θα ειχε προβλημα σε κανενα τετοιο αρχειο δοκιμης.

Σε καθε περιπτωση, η αναλυση των αλγοριθμων γινεται παντα με worst case analysis. Υπαρχουν πολλοι λογοι για αυτο.

Αρχικα υπαρχουν πολλες, και πολυ διαφορετικες μεταξυ τους, ειδικες περιπτωσεις σε καθε προβλημα. Αν ενθαρρυνουμε τους διαγωνιζομενους να μην πηγαινουν για την βελτιστη λυση, αλλα να σκεφτονται ειδικες περιπτωσεις οπου ο αλγοριθμος τους θα τρεξει γρηγορα, τοτε ο διαγωνισμος θα ηταν αδικος.
Δυο διαγωνιζομενοι που ειχαν σκεφτει καποιον αλγοριθμο για ειδικη περιπτωση μπορει να ειχαν πολυ διαφορετικα σκορ, διοτι τη μια απο αυτες την ειχαν φανταστει και αυτοι που φτιαχνουν τα test, και την αλλη οχι. Για τις περιπτωσεις λοιπον που δεχομαστε sub-optimal αλγοριθμους ανακοινωνονται στην εκφωνηση οι ιδιαιτεροτητες τους (οπως με την Πηνελοπη στο διαγωνισμο Δεκεμβριου) ωστε να υπαρχει ισοτητα.

Λιγοτερο σημαντικο ειναι το γεγονος οτι και στον Πανελληνιο αλλα κυριως στους διεθνεις Διαγωνισμους τα testcases ειναι πολυ σκληρα. Πολυ πολυ σκληρα. Σε σημειο που αν δεν εχεις βελτιστη πολυπλοκοτητα, ειναι σιγουρο οτι δε θα παρεις ποντους.

Το πιο σημαντικο ομως κατα τη γνωμη μου ειναι οτι ευελπιστουμε ο διαγωνισμος αυτος να μην ειναι αλλος ενας χωρος οπου τα παιδια θα ανταγωνιστουν (φροντισαν οι Πανελληνιες να καλλιεργησουν αυτο το κλιμα, δε χρειαζομαστε εμεις).
Το αν μια μη βελτιστη λυση παρει η δεν παρει βαθμους απο τα συγκεκριμενα testcases ειναι στην πραγματικοτητα αδιαφορο.
Ο στοχος ειναι να εθιστουν τα παιδια στην κομψοτητα, στη μαθηματικη ομορφια, στον λακωνικο εκφραστικοτατο αλγοριθμο . Οπως και να το κανουμε, μια brute-force σημαινει στην ουσια και επιφανειακη κατανοηση του προβληματος. Προφανως και αυτο δεν ειναι κακο, για να μαθουμε ηρθαμε ολοι. Μια ομορφη ομως λυση που χρειαζεται οχι 5 και 6 φορες λιγοτερο χρονο, αλλα Ν φορες (!) σημαινει οτι κατι εχει πιασει απο τους εσωτερικους μηχανισμους, απο τις σχεσεις που διεπουν τα στοιχεια του προβληματος.
Η διαφορα μια λεπτοδουλεμενης λυσης απο μια brute force (βλασφημο αυτο που θα πω, τηρουμενων των αναλογιων παντα) ειναι τοσο μεγαλη οσο η διαφορα του νησιωτικου σπιτιου με την πολυκατοικια. Βεβαια και τα δυο την κανουν την δουλεια τους, αλλα το ενα φροντισε να μπει και να δεσει με το περιβαλλον του και το αλλο επιβαλλεται με τον ιδιο ακριβως τροπο, ειτε στην Ελλαδα ειτε στη Γερμανια.

Ελπιζω να βοηθησα.

Φυσικά βοηθήσατε. Οπότε αν κατάλαβα καλά, στους δοκιμαστικούς διαγωνισμούς usaco όταν π.χ. βγάζει πολλές επιτυχημένες λύσεις με 1000/1000 στη Gold κατηγορία, γίνεται διότι δεν έχουν αρκετά μεγάλο δείγμα από στοχευμένα test cases, ενώ αν ήταν ο πραγματικός διαγωνισμός, θα ήταν πραγματικό "ξεσκόνισμα".

switch έγραψε:Φυσικά βοηθήσατε. Οπότε αν κατάλαβα καλά, στους δοκιμαστικούς διαγωνισμούς usaco όταν π.χ. βγάζει πολλές επιτυχημένες λύσεις με 1000/1000 στη Gold κατηγορία, γίνεται διότι δεν έχουν αρκετά μεγάλο δείγμα από στοχευμένα test cases, ενώ αν ήταν ο πραγματικός διαγωνισμός, θα ήταν πραγματικό "ξεσκόνισμα".

Ακριβώς!