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

Συζήτηση σχετικά με τα προβλήματα της Χριστουγεννιάτικης Συλλογής Ασκήσεων 2015-2016

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

Δημοσίευσηαπό Κηπουρίδης » Παρ Δεκ 30, 2016 5:07 am

Για όποιον ενδιαφέρεται να λύσει προβλήματα στις Χριστουγεννιάτικες διακοπές, θα υπάρχουν τρεις συλλογές με διαφορετικό βαθμό δυσκολίας η κάθε μία. Και οι τρεις στεγάζονται στην ιστοσελίδα 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.
Εικόνα
Άβαταρ μέλους
Κηπουρίδης
 
Δημοσιεύσεις: 286
Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm

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

Δημοσίευσηαπό Κηπουρίδης » Κυρ Ιαν 08, 2017 2:18 am

Δίνεται παράταση, μπορείτε να υποβάλλετε λύσεις μέχρι 20/1/2016.
Εικόνα
Άβαταρ μέλους
Κηπουρίδης
 
Δημοσιεύσεις: 286
Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm

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

Δημοσίευσηαπό Κηπουρίδης » Παρ Ιαν 20, 2017 1:01 am

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

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

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

Δημοσίευσηαπό Κηπουρίδης » Τετ Φεβ 01, 2017 2:07 am

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

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

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

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

Υ.Γ.: Σε περίπτωση που δεν κατεβαίνει για λόγους ασφάλειας το αρχείο, δοκιμάστε με άλλο browser ή αλλάξτε τις ρυθμίσεις ασφάλειας του browser σας ώστε να επιτραπεί.
Υ.Γ.2: Και μην ξεχνιόμαστε, μετά την εξάσκηση ακολουθούνε οι διαγωνισμοί...
Εικόνα
Άβαταρ μέλους
Κηπουρίδης
 
Δημοσιεύσεις: 286
Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm

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

Δημοσίευσηαπό infinity » Τετ Φεβ 01, 2017 5:28 pm

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

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

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

Ελπίζουμε να σας άρεσε η συλλογή, καλή συνέχεια και καλή επιτυχία σε όλους :D
infinity
 
Δημοσιεύσεις: 38
Εγγραφή: Σάβ Νοέμ 26, 2011 4:08 pm

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

Δημοσίευσηαπό rondojim » Τετ Φεβ 01, 2017 10:22 pm

Κώδικες για τα προβλήματα της 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

Δημήτρης
rondojim
 
Δημοσιεύσεις: 1
Εγγραφή: Τρί Ιαν 03, 2017 1:16 pm

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

Δημοσίευσηαπό switch » Παρ Φεβ 03, 2017 1:23 am

Το 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 φορά/ες συνολικά
Άβαταρ μέλους
switch
 
Δημοσιεύσεις: 23
Εγγραφή: Σάβ Δεκ 05, 2015 11:46 am

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

Δημοσίευσηαπό infinity » Παρ Φεβ 03, 2017 1:27 am

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 ) πολυπλοκότητα για κάθε ερώτημα.
infinity
 
Δημοσιεύσεις: 38
Εγγραφή: Σάβ Νοέμ 26, 2011 4:08 pm

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

Δημοσίευσηαπό switch » Παρ Φεβ 03, 2017 1:33 am

Ευχαριστώ για την πληροφόρηση. Με ενημέρωσε και ο Βαγγέλης. Αρχικά χωρίς να έχω διαβάσει τίποτα από 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;
}


υγ. ο κώδικας μου είναι αφράτος και περιέχει σχόλια, για να γίνει κατανοητός από υποψηφίους στο ξεκίνημα τους.
Άβαταρ μέλους
switch
 
Δημοσιεύσεις: 23
Εγγραφή: Σάβ Δεκ 05, 2015 11:46 am

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

Δημοσίευσηαπό infinity » Παρ Φεβ 03, 2017 1:54 am

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/
infinity
 
Δημοσιεύσεις: 38
Εγγραφή: Σάβ Νοέμ 26, 2011 4:08 pm

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

Δημοσίευσηαπό switch » Παρ Φεβ 03, 2017 2:05 am

Για σταθερά υποθέτω εννοείς το log_b(a) στον γνωστό τύπο:
Κώδικας: Επιλογή όλων
log_a(x) = log_b(x)/log_b(a)
, οπότε για το big O notation δεν έχει σημασία.

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

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

Δημοσίευσηαπό infinity » Παρ Φεβ 03, 2017 2:07 am

switch έγραψε:Για σταθερά υποθέτω εννοείς το log_b(a) στον γνωστό τύπο:
Κώδικας: Επιλογή όλων
log_a(x) = log_b(x)/log_b(a)
, οπότε για το big O notation δεν έχει σημασία.

Thanks


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

Τίποτα, καλή συνέχεια :)
infinity
 
Δημοσιεύσεις: 38
Εγγραφή: Σάβ Νοέμ 26, 2011 4:08 pm

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

Δημοσίευσηαπό Κηπουρίδης » Πέμ Φεβ 23, 2017 2:25 pm

Ανανεώθηκε το sqrt.pdf γιατί είχα ξεχάσει να ανανεώνω το sum στην Brute Force Update. Ελπίζω να μην προκάλεσα μεγάλη σύγχιση.
Εικόνα
Άβαταρ μέλους
Κηπουρίδης
 
Δημοσιεύσεις: 286
Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm


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

Μέλη σε σύνδεση

Μέλη σε αυτή την Δ. Συζήτηση : Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης