Γενικά - Χριστουγεννιάτικη Συλλογή Ασκήσεων 2016-2017

Συζήτηση σχετικά με τα προβλήματα της Χριστουγεννιάτικης Συλλογής Ασκήσεων 2015-2016
Απάντηση
Άβαταρ μέλους
Κηπουρίδης
Δημοσιεύσεις: 397
Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm

Γενικά - Χριστουγεννιάτικη Συλλογή Ασκήσεων 2016-2017

Δημοσίευση από Κηπουρίδης »

Για όποιον ενδιαφέρεται να λύσει προβλήματα στις Χριστουγεννιάτικες διακοπές, θα υπάρχουν τρεις συλλογές με διαφορετικό βαθμό δυσκολίας η κάθε μία. Και οι τρεις στεγάζονται στην ιστοσελίδα vjudge και θα χρειαστείτε account για να αποκτήσετε πρόσβαση σε αυτές.
Ο κωδικός υποβολής στους διαγωνισμούς είναι pdp2017.
  • 1η Συλλογή: Εισαγωγικά θέματα προγραμματισμού.
  • 2η Συλλογή: Προβλήματα βασισμένα σε Lowest Common Ancestor, Eulerian γράφους και Αλγόριθμο Ζ. Μπορείτε να διαβάσετε για τους σχετικούς αλγορίθμους στα φυλλάδια lca, sqrt, euler, z.
  • 3η Συλλογή: Πιο προχωρημένα θέματα.
Αν έχετε οποιαδήποτε ερώτηση σχετική με τα προβλήματα μπορείτε να τη δημοσιεύσετε στο forum. Σας ενθαρρύνουμε αφού λύσετε ένα θέμα να γράψετε αναλυτική εξήγηση της λύσης σας σε μορφή κειμένου (η οποία θα αναρτηθεί στο τέλος της προετοιμασίας στο forum).

Κάποια προβλήματα χρειάζονται γρήγορη ανάγνωση (πιο γρήγορη από scanf, cin) του input. Για να διαβάσετε πιο γρήγορα ακεραίους αριθμούς στη C++ συνήθως χρησιμοποιείται ο παρακάτω κώδικας:

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

inline void Read ( int &a ) {
  register char c;
  a = 0;
  while ( c < 33 )
    c = getchar_unlocked();
  while ( c > 33 ) {
    a = a*10 + c - '0';
    c = getchar_unlocked();
  }
}
Για να επικοινωνήστε μαζί μας σχετικά με την αποστολή εξήγησης μίας λύσης σας, προς δημοσίευση μετά το τέλος της προετοιμασίας, χρησιμοποιήστε το greekcontestspdp@gmail.com

Οι διοργανωτές:
Κυριάκος Αξιώτης, Ραφαήλ Κετσετσίδης, Βαγγέλης Κηπουρίδης, Παναγιώτης Κωστοπαναγιώτης, Δημήτρης Λως, Μανώλης Μιχάλαινας, Αριστοφάνης Ροντογιάννης, Γιάννης Χατζημίχος
Τελευταία επεξεργασία από το μέλος Κηπουρίδης την Πέμ Φεβ 23, 2017 2:22 pm, έχει επεξεργασθεί 1 φορά συνολικά.
Λόγος: Ανανεώθηκε το sqrt.pdf γιατί στο Brute Force Update δεν είχε ανανέωση του sum.
Λύσεις θεμάτων ΠΔΠ: https://pdp-archive.github.io/
Μπούσουλας διαβάσματος ΠΔΠ: http://snf-800715.vm.okeanos.grnet.gr/PDP/
Tutorials: https://kallinikos.github.io/
Επίσημο forum ΠΔΠ: https://www.pdpforum.eu.org/forum/
Άβαταρ μέλους
Κηπουρίδης
Δημοσιεύσεις: 397
Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm

Re: Γενικά - Χριστουγεννιάτικη Συλλογή Ασκήσεων 2016-2017

Δημοσίευση από Κηπουρίδης »

Δίνεται παράταση, μπορείτε να υποβάλλετε λύσεις μέχρι 20/1/2016.
Λύσεις θεμάτων ΠΔΠ: https://pdp-archive.github.io/
Μπούσουλας διαβάσματος ΠΔΠ: http://snf-800715.vm.okeanos.grnet.gr/PDP/
Tutorials: https://kallinikos.github.io/
Επίσημο forum ΠΔΠ: https://www.pdpforum.eu.org/forum/
Άβαταρ μέλους
Κηπουρίδης
Δημοσιεύσεις: 397
Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm

Re: Γενικά - Χριστουγεννιάτικη Συλλογή Ασκήσεων 2016-2017

Δημοσίευση από Κηπουρίδης »

Λόγω σημαντικής προσέλευσης από πλευράς σας, δίνεται μία ακόμη παράταση μέχρι τέλος Ιανουαρίου.

Συγχαρητήρια σε όλους για τις επιδόσεις σας!
Λύσεις θεμάτων ΠΔΠ: https://pdp-archive.github.io/
Μπούσουλας διαβάσματος ΠΔΠ: http://snf-800715.vm.okeanos.grnet.gr/PDP/
Tutorials: https://kallinikos.github.io/
Επίσημο forum ΠΔΠ: https://www.pdpforum.eu.org/forum/
Άβαταρ μέλους
Κηπουρίδης
Δημοσιεύσεις: 397
Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm

Re: Γενικά - Χριστουγεννιάτικη Συλλογή Ασκήσεων 2016-2017

Δημοσίευση από Κηπουρίδης »

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

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

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

Καλή συνέχεια σε όλους!

Υ.Γ.: Σε περίπτωση που δεν κατεβαίνει για λόγους ασφάλειας το αρχείο, δοκιμάστε με άλλο browser ή αλλάξτε τις ρυθμίσεις ασφάλειας του browser σας ώστε να επιτραπεί.
Υ.Γ.2: Και μην ξεχνιόμαστε, μετά την εξάσκηση ακολουθούνε οι διαγωνισμοί...
Λύσεις θεμάτων ΠΔΠ: https://pdp-archive.github.io/
Μπούσουλας διαβάσματος ΠΔΠ: http://snf-800715.vm.okeanos.grnet.gr/PDP/
Tutorials: https://kallinikos.github.io/
Επίσημο forum ΠΔΠ: https://www.pdpforum.eu.org/forum/
infinity
Δημοσιεύσεις: 38
Εγγραφή: Σάβ Νοέμ 26, 2011 4:08 pm

Re: Γενικά - Χριστουγεννιάτικη Συλλογή Ασκήσεων 2016-2017

Δημοσίευση από infinity »

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

Το αρχείο μπορείτε να το κατεβάσετε από εδώ. Είναι ακόμα κάπως ελλειπές, λείπει η λύση για το MP3 Player της σειράς 3 και του Power Strings της σειράς 2. Εννοείται πως όποιος έχει όρεξη μπορεί να γράψει την λύση του και να την ανεβάσει στο forum.

Επίσης, αν εντοπίσετε οποιοδήποτε λάθος, είτε στην διατύπωση είτε στις λύσεις ( και τα 2 είναι πάρα πολύ πιθανά :P ), στείλτε μου να το διορθώσω.

Ελπίζουμε να σας άρεσε η συλλογή, καλή συνέχεια και καλή επιτυχία σε όλους :D
rondojim
Δημοσιεύσεις: 1
Εγγραφή: Τρί Ιαν 03, 2017 1:16 pm

Re: Γενικά - Χριστουγεννιάτικη Συλλογή Ασκήσεων 2016-2017

Δημοσίευση από rondojim »

Κώδικες για τα προβλήματα της 3ης κατηγορίας:

Digit Count: http://ideone.com/R9HCTF
Tricky Function: http://ideone.com/hksrSH
Greatest Parent: http://ideone.com/WPiR2U
A Secret Mission: http://ideone.com/XLBPiN
Seek the Name, Seek the Fame: http://ideone.com/5pPQWN
Powerful array: http://ideone.com/hBVnIb
Temple Queues : http://ideone.com/MBPXXz

Δημήτρης
Άβαταρ μέλους
switch
Δημοσιεύσεις: 90
Εγγραφή: Σάβ Δεκ 05, 2015 11:46 am
Τοποθεσία: 127.0.0.1

Re: Γενικά - Χριστουγεννιάτικη Συλλογή Ασκήσεων 2016-2017

Δημοσίευση από switch »

Το digit count μπορεί να λυθεί με DFS και DP και περνά από χρόνο λόγω μικρών απαιτησεων από την εκφώνηση.
To DP φυσικά πλεονεκτεί σε χρόνο σε σχέση με το DFS.
Spoiler: show

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

#include <cstdio>
#include <cassert>
#include <cmath>
#include <algorithm>
#include <cstring>

using namespace std;

int D[11];//το σύνολο των επιτρεπόμενων ψηφίων 
int M /*αριθμός επιτρεπόμενων ψηφίων*/ ,N /*μήκος επιθυμιτού αριθμού*/;

	int _DFS(int d,int pos){
		int sum = 0;
		if(pos == N)
			sum++;
		else
			for(int i=0;i<M;i++)
				if(abs(d-D[i])<=2)
					sum += _DFS(D[i],pos+1);
		return sum;
	}
int DFS(){
	int sum = 0;
	for(int i=0;i<M;i++)
		sum += _DFS(D[i],0);
	return sum;
}

/*
στην πρώτη θέση του Ν-ψήφιου αριθμού, θα μπορούμε να έχουμε εμφάνιση κάθε ψηφίου από 1 φορά.
Για κάθε ψηφίο της πρώτης θέσης, μπορούμε να φτιάξουμε τον πίνακα με τα ψηφία της δεύτερης θέσης και τελικά
για κάθε ψηφίο της i θέσης μπορούμε να φτιάξουμε τον πίνακα με τα ψηφία της i+1 θέσης.
Θυμίζει λίγο επαγωγή έτσι; Μήπως έχει και μυρωδιά DP; Προφανώς. Ας δούμε πως θα μπορούμε να προσμετράμε τους συνδυασμούς 
κάθε θέσης στους συνδυασμούς της προηγούμενης. 

Αρχικά κάθε ψηφίο στη θέση 0 θα εμφανίζεται από 1 φορά.
Στην επόμενη θέση κάθε ψηφίο θα εμφανίζεται το άθροισμα των φορών που εμφανίζονταν τα συμβατά ψηφία
(abs()<=2) της προηγούμενης θέσης!

Ας το δούμε με το αρχικό παράδειγμα της άσκησης (1 3 6) και για έναν 3ψήφιο αριθμό.
Στη θέση του ψηφίου 0 θα εμφανιστούν τα "1","3","6" από 1 φορά.
	(εδώ προσέξτε ότι αν ήθελα να υπολογίσω για Ν=1, τότε η απάντηση είναι Μ, το άθροισμα των εμφανίσεων των ψηφίων της θέσης 0)

Στη θέση του ψηφίου 1 θα εμφανιστεί το "1", 2 φορές (1+1 φορές, 1 φορά για το "1" της θέσης 0 και 1 για το "3" της θέσης 0)
Στη θέση του ψηφίου 1 θα εμφανιστεί το "3", 2 φορές (1+1 φορές, 1 φορά για το "1" της θέσης 0 και 1 για το "3" της θέσης 0)
Στη θέση του ψηφίου 1 θα εμφανιστεί το "6", 1 φορά (1 φορά για το "6" της θέσης 0)
	(εδώ προσέξτε ότι αν ήθελα να υπολογίσω για Ν=2, τότε η απάντηση είναι 2+2+1, το άθροισμα των εμφανίσεων των ψηφίων της θέσης 1)

Στη θέση του ψηφίου 2 θα εμφανιστεί το "1", 4 φορές (2+2 φορές, 2 φορές για το "1" της θέσης 1 και 2 για το "3" της θέσης 1)
Στη θέση του ψηφίου 2 θα εμφανιστεί το "3", 4 φορές (2+2 φορές, 2 φορές για το "1" της θέσης 1 και 2 για το "3" της θέσης 1)
Στη θέση του ψηφίου 2 θα εμφανιστεί το "6", 2 φορές (2 φορές για το "6" της θέσης 1)
	(εδώ προσέξτε ότι αν ήθελα να υπολογίσω για Ν=3, τότε η απάντηση είναι 4+4+2, το άθροισμα των εμφανίσεων των ψηφίων της θέσης 2)

Καταφέραμε δηλαδή να υπολογίσουμε τη βέλτιστη λύση τοπικά και κάθε νέα θέση i να βασίζεται στην i-1, οπότε "βουαλά" το DP.
*/

int calcDP(){
	int DP[11][11];
	int sum = 0;
	memset(DP,0,sizeof(DP));
	
	for(int i=0;i<M;i++)
		DP[0][D[i]] = 1;//στη θέση 1 το κάθε ψηφίο θα εμφανιστεί μια και μόνο φορά
	
	for(int pos=1;pos<N;pos++){//για κάθε επόμενο ψηφίο στον n-ψήφιο αριθμό
		for(int dcurr=0;dcurr<M;dcurr++){//βρες τις δυνατές τιμές του ψηφίου στη θέση i
			for(int dprev=0;dprev<M;dprev++)//που είναι συμβατά με τα ψηφία της προηγούμενης θέσης
				if(abs(D[dprev]-D[dcurr]) <= 2)
					DP[pos][D[dcurr]] += DP[pos-1][D[dprev]];
		}
	}
	
	//απλώς άθροισε τις εμφανίσεις όλων των ψηφίων της θέσης N-1 (ξεκινάμε το μέτρημα από το 0)
	for(int i=0;i<M;i++)
		sum += DP[N-1][D[i]];

#if 0	//αν θέλουμε να δούμε τα περιεχόμενα του πίνακα
	for(int i=0;i<=N;i++){
		printf("%2d: ",i);
		for(int j=0;j<M;j++){
			printf("%6d ",DP[i][D[j]]);
		}
		printf("\n");
	}
	printf("Sum=%d\n",sum);
#endif

	return sum;
}

int main(){
	int test_cases;
	scanf("%d",&test_cases);
	for(int t=1;t<=test_cases;t++){
		memset(D,0,sizeof(D));
		scanf("%d%d",&M,&N);
		for(int i=0;i<M;i++)
			scanf("%d",&D[i]);
		printf("Case %d:\n%d\n",t,DFS());
		printf("Case %d: %d\n",t,calcDP());
	}
	return 0;
}

η απάντηση για συνδυασμούς 9 ψηφία σε 10ψήφιο αριθμό είναι 7'172'423
Τελευταία επεξεργασία από το μέλος switch την Παρ Φεβ 03, 2017 1:28 am, έχει επεξεργασθεί 1 φορά συνολικά.
infinity
Δημοσιεύσεις: 38
Εγγραφή: Σάβ Νοέμ 26, 2011 4:08 pm

Re: Γενικά - Χριστουγεννιάτικη Συλλογή Ασκήσεων 2016-2017

Δημοσίευση από infinity »

switch έγραψε:Το digit count μπορεί να λυθεί και με DFS
Spoiler: show

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

#include <cstdio>
#include <cassert>
#include <cmath>
#include <algorithm>
#include <cstring>

using namespace std;

int D[11];//το σύνολο των επιτρεπόμενων ψηφίων 
int M /*αριθμός επιτρεπόμενων ψηφίων*/ ,N /*μήκος επιθυμιτού αριθμού*/;

	int _DFS(int d,int pos){
		int sum = 0;
		if(pos == N)
			sum++;
		else
			for(int i=0;i<M;i++)
				if(abs(d-D[i])<=2)
					sum += _DFS(D[i],pos+1);
		return sum;
	}
int DFS(){
	int sum = 0;
	for(int i=0;i<M;i++)
		sum += _DFS(D[i],0);
	return sum;
}

int calcDP(){
	int DP[11][11];
	int sum = 0;
	memset(DP,0,sizeof(DP));
	
	for(int i=0;i<M;i++)
		DP[0][D[i]] = 1;//στη θέση 1 το κάθε ψηφίο θα εμφανιστεί μια και μόνο φορά
	
	for(int pos=1;pos<N;pos++){//για κάθε επόμενο ψηφίο στον n-ψήφιο αριθμό
		for(int dcurr=0;dcurr<M;dcurr++){//βρες τις δυνατές τιμές του ψηφίου στη θέση i
			for(int dprev=0;dprev<M;dprev++)//που είναι συμβατά με τα ψηφία της προηγούμενης θέσης
				if(abs(D[dprev]-D[dcurr]) <= 2)
					DP[pos][D[dcurr]] += DP[pos-1][D[dprev]];
		}
	}
	
	//απλώς άθροισε τις εμφανίσεις όλων των ψηφίων της θέσης N-1 (ξεκινάμε το μέτρημα από το 0)
	for(int i=0;i<M;i++)
		sum += DP[N-1][D[i]];

#if 0	//αν θέλουμε να δούμε τα περιεχόμενα του πίνακα
	for(int i=0;i<=N;i++){
		printf("%2d: ",i);
		for(int j=0;j<M;j++){
			printf("%6d ",DP[i][D[j]]);
		}
		printf("\n");
	}
	printf("Sum=%d\n",sum);
#endif

	return sum;
}

int main(){
	int test_cases;
	scanf("%d",&test_cases);
	for(int t=1;t<=test_cases;t++){
		memset(D,0,sizeof(D));
		scanf("%d%d",&M,&N);
		for(int i=0;i<M;i++)
			scanf("%d",&D[i]);
		printf("Case %d:\n%d\n",t,DFS());
		printf("Case %d: %d\n",t,calcDP());
	}
	return 0;
}

η απάντηση για συνδυασμούς 9 ψηφία σε 10ψήφιο αριθμό είναι 7'172'423
Ενδιαφέρουσα λύση, ευχαριστούμε :)

Btw όσον αφορά την λύση σου στο LCA, στην ανάλυση πολυπλοκότητας η χειρότερη περίπτωση είναι να έχουμε δέντρο γραμμή και ο πρώτος κόμβος να βρίσκεται στην κορυφή του δέντρου και ο δεύτερος στο τέλος. Οπότε προκύπτει O( n ) πολυπλοκότητα για κάθε ερώτημα.
Άβαταρ μέλους
switch
Δημοσιεύσεις: 90
Εγγραφή: Σάβ Δεκ 05, 2015 11:46 am
Τοποθεσία: 127.0.0.1

Re: Γενικά - Χριστουγεννιάτικη Συλλογή Ασκήσεων 2016-2017

Δημοσίευση από switch »

Ευχαριστώ για την πληροφόρηση. Με ενημέρωσε και ο Βαγγέλης. Αρχικά χωρίς να έχω διαβάσει τίποτα από LCA, έκανα το πρόβλημα έχοντας υπόψιν την worst case γραμμής και μου έκανε εντύπωση που πέρασε. Μετά έπαιξα στην 3η ομάδα (greatest parent) και χρειάστηκε λύση λογαριθμικής πολυπλοκότητας (φυσικά) για να περάσει.

Οπότε με την απλή λύση έχουμε O(N*Q) ενώ στην άλλη O(N*logN + Q*logN).
Το "επιασα" :mrgreen:

Greatest parent
Spoiler: show

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

/*
problem: https://vjudge.net/contest/146075#problem/C
Title: C - Greatest Parent 

το πρόβλημα λύνεται με τη χρήση του αλγορίθμου LCA (lowest common ancestor), όπου σε κάθε
κόμβο, αποθηκεύουμε επιλεγμένους προγόνους. Συγκεκριμένα αποθηκεύουμε τον 1ο,2ο,4ο,8ο κλπ δηλαδή τις δυνάμεις του 2.
Χρόνος προετοιμασίας: O(N * log2(n)). 
Χρόνος για κάθε query: O(log2(n))

Λεπτομέρειες για τον LCA: 
	http://s000.tinyupload.com/index.php?file_id=86514268981766956934
	https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/
	http://www.geeksforgeeks.org/lca-for-general-or-n-ary-trees-sparse-matrix-dp-approach-onlogn-ologn/
*/

//#define NDEBUG

#include <cstdio>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>

using namespace std;

#ifdef _MSC_VER	
	//τρέχουμε σε Miscosoft Visual C.
	//Η MSVC δεν είχε log2 μέχρι το msdev2012 και δεν έχει getchar_unlocked
	#define GETCHP	getchar
	//To log2(n) μπορεί να υπολογιστεί ώς ln(n)/ln(2) αλλά επειδή ο υπολογιστής είναι καλύτερος στις δυνάμεις του 2,
	//αντί να παίζουμε με σειρές/πίνακες μαθηματικών (συναρτήσεις ln(n) της math.h) κάνουμε:
	double log2(unsigned x){
		unsigned ans = 0;
		while( x>>=1 ) ans++;
		return ans;
	}
	#define dprintf(expr,...)	printf(expr,__VA_ARGS__)//θέλουμε debug πρηροφορίες
#else
	#define GETCHP	getchar_unlocked
	#define dprintf(expr,...)	((void)0)	//δεν θελουμε debug πληροφορίες
#endif

inline void getval(int& n){
	n = 0;
	register unsigned c;
	while((c=GETCHP()) <= ' ') ;//waste blanks
	//read digits
	do {
		n = (n << 1) + (n << 3) + c-'0'; //n = n*10 ή n = n*2 + n*8 ή n = n<<1 + n << 3
	} while((c=GETCHP())>='0');
}

#define MAXN		100001
#define MAXDEPTH	18	//ceil(log2(MN))

struct node {//ενας κόμβος
	int value;
//	int level;//το επίπεδο (απόσταση κόμβου από ρίζα). Στο πρόβλημα αυτό δεν είναι απαραίτητο
	int anc[MAXDEPTH];//ancestors. anc[0] is the parent of the node (2^0), anc[1] is the grand father (2^1), anc[2] is the pre-pre-grand-father (s^2)
	void set(int val,int dad);
} nodes[MAXN+1];//sequencial array with the nodes. nodes[i] is the node with number i

void node::set(int value1,int dad){
	value = value1;
//	level = (dad>=0) ? (nodes[dad].level+1) : 0;
	memset(anc,-1,sizeof(anc));
	anc[0] = dad;
}

int 	nnodes, //αριθμος κομβων στην test case (N)
	depth = int(log2(nnodes)+0.5);//πραγματικο βαθος πίνακα DP, με τιμή ceil(log2(nnodes))

void drop_tree(){ nodes[0].set(1, -1); }//μηδενισμός της ρίζας του δέντρου

int lca_modified(int x /*node starting*/,int v /*required value*/){
	int answer = x;//ξεκινάμε με το χαμηλότερο επίπεδο. Τον ίδιο τον κόμβο του ερωτήματος
	dprintf("query node=%d v=%d [depth=%d, log2(%d)=%d]\n",x,v,depth,nnodes,int(log2(nnodes) + 0.5));

	for(int i=depth;i>=0;i--){
		int ntest = nodes[answer].anc[i];
		dprintf("\ti=%d, answer=%d, testn=%d, [v=%d]\n", i,answer, ntest,nodes[ntest].value);
		if(ntest>=0 && nodes[ntest].value >= v)
			answer = ntest;//μεταφορά στον πρόγονο anc[i]
	}
	
	dprintf("\tanswer = %d\n", answer);
	return answer;
}

int main(){
	assert( (1<<MAXDEPTH) >= MAXN);//make sure we reserved enough space
	
	int test_cases;
	getval(test_cases);
	
	for(int c=1;c<=test_cases;c++){
		int queries;
		getval(nnodes);
		getval(queries);

		drop_tree();//read in a fresh tree
		for(int n=1;n<nnodes;n++){
			int dad,val;
			getval(dad);
			getval(val);
			nodes[n].set(val,dad);
		}
		
		{//dp calc sparce matrix
		 //populate 2^i parent for each node
		 //O(nlogn) time complexity
			depth = (0.5 + log2(nnodes));
			for(int j=1;j<=depth;j++)
				for(int i=0;i<nnodes;i++)
					if(nodes[i].anc[j-1]!=-1)
						nodes[i].anc[j] = nodes[ nodes[i].anc[j-1] ].anc[j-1];
		}
		
		//run queries O(qlogn) complexity
		printf("Case %d:\n",c);
		for(int q=0;q<queries;q++){
			int x,v;
			getval(x);
			getval(v);
			printf("%d\n",lca_modified(x,v));
		}
	}
	return 0;
}
υγ. ο κώδικας μου είναι αφράτος και περιέχει σχόλια, για να γίνει κατανοητός από υποψηφίους στο ξεκίνημα τους.
infinity
Δημοσιεύσεις: 38
Εγγραφή: Σάβ Νοέμ 26, 2011 4:08 pm

Re: Γενικά - Χριστουγεννιάτικη Συλλογή Ασκήσεων 2016-2017

Δημοσίευση από infinity »

switch έγραψε:Ευχαριστώ για την πληροφόρηση. Με ενημέρωσε και ο Βαγγέλης. Αρχικά χωρίς να έχω διαβάσει τίποτα από LCA, έκανα το πρόβλημα έχοντας υπόψιν την worst case γραμμής και μου έκανε εντύπωση που πέρασε. Μετά έπαιξα στην 3η ομάδα (greatest parent) και χρειάστηκε λύση λογαριθμικής πολυπλοκότητας (φυσικά) για να περάσει.

Οπότε με την απλή λύση έχουμε O(N*Q) ενώ στην άλλη O(N*logN + Q*logN).
Το "επιασα" :mrgreen:

Greatest parent
Spoiler: show

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

/*
problem: https://vjudge.net/contest/146075#problem/C
Title: C - Greatest Parent 

το πρόβλημα λύνεται με τη χρήση του αλγορίθμου LCA (lowest common ancestor), όπου σε κάθε
κόμβο, αποθηκεύουμε επιλεγμένους προγόνους. Συγκεκριμένα αποθηκεύουμε τον 1ο,2ο,4ο,8ο κλπ δηλαδή τις δυνάμεις του 2.
Χρόνος προετοιμασίας: O(N * log2(n)). 
Χρόνος για κάθε query: O(log2(n))

Λεπτομέρειες για τον LCA: 
	http://s000.tinyupload.com/index.php?file_id=86514268981766956934
	https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/
	http://www.geeksforgeeks.org/lca-for-general-or-n-ary-trees-sparse-matrix-dp-approach-onlogn-ologn/
*/

//#define NDEBUG

#include <cstdio>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>

using namespace std;

#ifdef _MSC_VER	
	//τρέχουμε σε Miscosoft Visual C.
	//Η MSVC δεν είχε log2 μέχρι το msdev2012 και δεν έχει getchar_unlocked
	#define GETCHP	getchar
	//To log2(n) μπορεί να υπολογιστεί ώς ln(n)/ln(2) αλλά επειδή ο υπολογιστής είναι καλύτερος στις δυνάμεις του 2,
	//αντί να παίζουμε με σειρές/πίνακες μαθηματικών (συναρτήσεις ln(n) της math.h) κάνουμε:
	double log2(unsigned x){
		unsigned ans = 0;
		while( x>>=1 ) ans++;
		return ans;
	}
	#define dprintf(expr,...)	printf(expr,__VA_ARGS__)//θέλουμε debug πρηροφορίες
#else
	#define GETCHP	getchar_unlocked
	#define dprintf(expr,...)	((void)0)	//δεν θελουμε debug πληροφορίες
#endif

inline void getval(int& n){
	n = 0;
	register unsigned c;
	while((c=GETCHP()) <= ' ') ;//waste blanks
	//read digits
	do {
		n = (n << 1) + (n << 3) + c-'0'; //n = n*10 ή n = n*2 + n*8 ή n = n<<1 + n << 3
	} while((c=GETCHP())>='0');
}

#define MAXN		100001
#define MAXDEPTH	18	//ceil(log2(MN))

struct node {//ενας κόμβος
	int value;
//	int level;//το επίπεδο (απόσταση κόμβου από ρίζα). Στο πρόβλημα αυτό δεν είναι απαραίτητο
	int anc[MAXDEPTH];//ancestors. anc[0] is the parent of the node (2^0), anc[1] is the grand father (2^1), anc[2] is the pre-pre-grand-father (s^2)
	void set(int val,int dad);
} nodes[MAXN+1];//sequencial array with the nodes. nodes[i] is the node with number i

void node::set(int value1,int dad){
	value = value1;
//	level = (dad>=0) ? (nodes[dad].level+1) : 0;
	memset(anc,-1,sizeof(anc));
	anc[0] = dad;
}

int 	nnodes, //αριθμος κομβων στην test case (N)
	depth = int(log2(nnodes)+0.5);//πραγματικο βαθος πίνακα DP, με τιμή ceil(log2(nnodes))

void drop_tree(){ nodes[0].set(1, -1); }//μηδενισμός της ρίζας του δέντρου

int lca_modified(int x /*node starting*/,int v /*required value*/){
	int answer = x;//ξεκινάμε με το χαμηλότερο επίπεδο. Τον ίδιο τον κόμβο του ερωτήματος
	dprintf("query node=%d v=%d [depth=%d, log2(%d)=%d]\n",x,v,depth,nnodes,int(log2(nnodes) + 0.5));

	for(int i=depth;i>=0;i--){
		int ntest = nodes[answer].anc[i];
		dprintf("\ti=%d, answer=%d, testn=%d, [v=%d]\n", i,answer, ntest,nodes[ntest].value);
		if(ntest>=0 && nodes[ntest].value >= v)
			answer = ntest;//μεταφορά στον πρόγονο anc[i]
	}
	
	dprintf("\tanswer = %d\n", answer);
	return answer;
}

int main(){
	assert( (1<<MAXDEPTH) >= MAXN);//make sure we reserved enough space
	
	int test_cases;
	getval(test_cases);
	
	for(int c=1;c<=test_cases;c++){
		int queries;
		getval(nnodes);
		getval(queries);

		drop_tree();//read in a fresh tree
		for(int n=1;n<nnodes;n++){
			int dad,val;
			getval(dad);
			getval(val);
			nodes[n].set(val,dad);
		}
		
		{//dp calc sparce matrix
		 //populate 2^i parent for each node
		 //O(nlogn) time complexity
			depth = (0.5 + log2(nnodes));
			for(int j=1;j<=depth;j++)
				for(int i=0;i<nnodes;i++)
					if(nodes[i].anc[j-1]!=-1)
						nodes[i].anc[j] = nodes[ nodes[i].anc[j-1] ].anc[j-1];
		}
		
		//run queries O(qlogn) complexity
		printf("Case %d:\n",c);
		for(int q=0;q<queries;q++){
			int x,v;
			getval(x);
			getval(v);
			printf("%d\n",lca_modified(x,v));
		}
	}
	return 0;
}
υγ. ο κώδικας μου είναι αφράτος και περιέχει σχόλια, για να γίνει κατανοητός από υποψηφίους στο ξεκίνημα τους.
Τέλεια :D ευχαριστούμε πάρα πολύ για την βοήθεια με τις λύσεις.

Επίσης μια ακόμα ψιλόλεπτομέρεια, όταν στην πολυπλοκότητα έχουμε λογαρίθμους δεν έχει νόημα να περιγράφουμε την βάση του εν λόγω λογαρίθμου ( ούτως ή άλλως σχεδόν πάντα 2 είναι :P ). Ο λόγος είναι ότι μπορούμε να μετατρέψουμε κάθε λογάριθμο συγκεκριμένης βάσης, σε οποιαδήποτε άλλη πολλαπλασιάζοντάς τον με μια σταθερά, ισχύει δηλαδή log_a(x) = c*log_b(x) και άρα είναι O( log_a(x) ) = O( log_b(x) ) για κάθε a,b. Δεν έχει και πολύ σημασία βασικά, απλά το αναφέρω.

Για όποιον ενδιαφέρεται γενικά, ένα ενδιαφέρον άρθρο που περιγράφει το πως να βρίσκουμε πολυπλοκότητες με πιο "χειροπιαστό" τρόπο απ' ότι τα περισσότερα αλγοριθμοβιβλία είναι αυτό: http://discrete.gr/complexity/
Άβαταρ μέλους
switch
Δημοσιεύσεις: 90
Εγγραφή: Σάβ Δεκ 05, 2015 11:46 am
Τοποθεσία: 127.0.0.1

Re: Γενικά - Χριστουγεννιάτικη Συλλογή Ασκήσεων 2016-2017

Δημοσίευση από switch »

Για σταθερά υποθέτω εννοείς το log_b(a) στον γνωστό τύπο:

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

log_a(x) = log_b(x)/log_b(a)
, οπότε για το big O notation δεν έχει σημασία.

Thanks
infinity
Δημοσιεύσεις: 38
Εγγραφή: Σάβ Νοέμ 26, 2011 4:08 pm

Re: Γενικά - Χριστουγεννιάτικη Συλλογή Ασκήσεων 2016-2017

Δημοσίευση από infinity »

switch έγραψε:Για σταθερά υποθέτω εννοείς το log_b(a) στον γνωστό τύπο:

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

log_a(x) = log_b(x)/log_b(a)
, οπότε για το big O notation δεν έχει σημασία.

Thanks
Ναι, δεν θυμόμουν ακριβώς ποιός ήταν ο τύπος :P

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

Re: Γενικά - Χριστουγεννιάτικη Συλλογή Ασκήσεων 2016-2017

Δημοσίευση από Κηπουρίδης »

Ανανεώθηκε το sqrt.pdf γιατί είχα ξεχάσει να ανανεώνω το sum στην Brute Force Update. Ελπίζω να μην προκάλεσα μεγάλη σύγχιση.
Λύσεις θεμάτων ΠΔΠ: https://pdp-archive.github.io/
Μπούσουλας διαβάσματος ΠΔΠ: http://snf-800715.vm.okeanos.grnet.gr/PDP/
Tutorials: https://kallinikos.github.io/
Επίσημο forum ΠΔΠ: https://www.pdpforum.eu.org/forum/
Απάντηση