Hellenico Training Contest - Οκτώβριος 2011

Ελληνικοί διαγωνισμοί για τα παιδιά του ΠΔΠ.
Απάντηση
feedWARd
Δημοσιεύσεις: 72
Εγγραφή: Κυρ Δεκ 21, 2008 3:32 pm

Hellenico Training Contest - Οκτώβριος 2011

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

14-17 Οκτωβρίου. Tell your friends :D
Άβαταρ μέλους
zaxeilasfc
Δημοσιεύσεις: 118
Εγγραφή: Δευ Οκτ 18, 2010 8:15 pm
Τοποθεσία: Macintosh HD

Re: Hellenico Training Contest - Οκτώβριος 2011

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

Thanks mr. John. Περιμένουμε ενδιαφέρον θέματα.
feedWARd
Δημοσιεύσεις: 72
Εγγραφή: Κυρ Δεκ 21, 2008 3:32 pm

Re: Hellenico Training Contest - Οκτώβριος 2011

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

Μιας και κανενας δεν ξεπαρθενιασε το 4ο προβλημα (shells) θα προσπαθήσω να παρουσιάσω μια λύση πολυπλοκότητας Ο(Ν^3).

Δεν θα εξηγήσω εδώ πως χρησιμοποιούμε τον τύπο του εξωτερικού γινομένου για να δούμε αν ένα σημείο βρίσκεται αριστερά ή δεξιά ενός διανύσματος. Όσοι δεν γνωρίζετε μπορείτε να ρίξετε μια ματιά εδώ πριν συνεχίσετε: http://www.softlab.ntua.gr/~nickie/tmp/ ... ry2011.pdf

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

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

for (i=0; i<N; i++) {
  for (j=0; j<N; j++) {
    if ( i == j ) continue;
    for (k=0; k<N; k++) {
      leftcount[i][j] += (CCW(point[i], point[j], point[k]) >= 0);
    }
  }
}
Εικόνα

Έτσι, αν συμβολίσουμε με a το πλήθος των σημείων που βρίσκονται στην περιοχή Α και με b το πλήθος αυτών που βρίσκονται στην περιοχή Β είναι:
leftcount[j] = a και leftcount[j] = b

Έχοντας προϋπολογίσει τον πίνακα leftcount, μπορούμε να υπολογίσουμε το πλήθος των σημείων που βρίσκονται μέσα στο τρίγωνο που ορίζεται από τρια σημεία i, j, k σε Ο(1). Αν προεκτείνουμε την κάθε πλευρά του τριγώνου το επίπεδο χωρίζεται σε 7 περιοχές, από τις οποίες θέλουμε να απονώσουμε μόνο την Α.

Εικόνα

Συμβολίζοντας, όπως και πριν το πλήθος των σημείων που βρίσκονται στην περιοχή Α με a κ.ο.κ. έχουμε:
leftcount[j] = a + b + c + e
leftcount[j][k] = a + b + d + f
leftcount[k] = a + c + d + g
και φυσικά
Ν = a + b + c + d + e + f + g
άρα
leftcount[j] + leftcount[j][k] + leftcount[k] = 3*a + 2*b + 2*c +2*d + e + f + g
αφαιρώντας 2*Ν από το παραπάνω καταλήγουμε στον τύπο:
leftcount[j] + leftcount[j][k] + leftcount[k] - 2*Ν = a - e - f - g

Αυτός ο τύπος υπολογίζει σωστά το πλήθος των σημείων για κάθε τρίγωνο στο οποίο δεν υπάρχουν σημεία στις περιοχές E, F, G δηλαδή είναι e = f = g = 0. Σε διαφορετική περίπτωση (e > 0 ή f > 0 ή g > 0) δίνει μικρότερη απάντηση από την πραγματική. Σε αυτή την περίπτωση όμως μπορούμε να είμαστε σίγουροι ότι το τρίγωνο (i, j, k) δεν είναι η λύση που ψάχνουμε, καθώς αν χρησιμοποιήσουμε ως κορυφή κάποιο από τα σημεία που βρίσκονται στις περιοχές E, F, G παίρνουμε ένα τρίγωνο το οποίο περιέχει ένα υπερσύνολο των σημείων που περιέχει το (i, j, k).

Εικόνα

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

ans = 0;

for (i=0; i<N; i++) {
  for (j=0; j<N; j++) {
    for (k=0; k<N; k++) {
      if ( i == j || j == k || k == i ) continue;

      cur = leftcount[i][j] + leftcount[j][k] + leftcount[k][i] - 2*N;

      if ( cur > ans ) ans = cur;
    }
  }
}
NikosZ
Δημοσιεύσεις: 10
Εγγραφή: Σάβ Οκτ 08, 2011 11:23 am

Re: Hellenico Training Contest - Οκτώβριος 2011

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

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

Στην ουσία δουλεύουμε στο μιγαδικό επίπεδο(R^2). Έστω A1,A2,A3 οι εικόνες των Ζ1,Ζ2,Ζ3 κι κορυφές τριγώνου. Έστω Β εικόνα μιγαδικού W εντός τριγώνου θα ισχύει:

|Zi|<=|W| , |Zu|>=|W| , |Zj|>=|W| i,u,j=({1,2,3} ,i!=u!=j)
Άβαταρ μέλους
Κηπουρίδης
Δημοσιεύσεις: 397
Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm

Re: Hellenico Training Contest - Οκτώβριος 2011

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

@feedWard : Ρε δε πα να πνιγείς λέω ᾽ γω που θα λύναμε εμείς τέτοιο θέμα :lol: .

Σοβαρά πάντως, ένα μπράβο κι από το forum και σε εσένα και στον Κυριάκο που οργανώνετε διαγωνισμό κάθε μήνα. Βοηθάει πολύ να μάθεις πώς είναι να μην έχεις τρεις μέρες μπροστά σου να λύσεις 1 θέμα.
Λύσεις θεμάτων ΠΔΠ: 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/
feedWARd
Δημοσιεύσεις: 72
Εγγραφή: Κυρ Δεκ 21, 2008 3:32 pm

Re: Hellenico Training Contest - Οκτώβριος 2011

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

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

Στην ουσία δουλεύουμε στο μιγαδικό επίπεδο(R^2). Έστω A1,A2,A3 οι εικόνες των Ζ1,Ζ2,Ζ3 κι κορυφές τριγώνου. Έστω Β εικόνα μιγαδικού W εντός τριγώνου θα ισχύει:

|Zi|<=|W| , |Zu|>=|W| , |Zj|>=|W| i,u,j=({1,2,3} ,i!=u!=j)
Αυτό μπορεί να ισχύει και για σημεία που δεν βρίσκονται μέσα στο τρίγωνο και επίσης ισχύει μόνο για τρίγωνα με συγκεκριμένη μορφή. Σε αυτές τις διαφάνειες μπορείς να δεις έναν τρόπο για να ελέγχεις αν ένα σημείο βρίσκεται μέσα σ' ένα τρίγωνο.
Άβαταρ μέλους
compileGuy
Δημοσιεύσεις: 218
Εγγραφή: Δευ Ιαν 19, 2009 5:39 pm

Re: Hellenico Training Contest - Οκτώβριος 2011

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

Πολύ ωραία θέματα τα πρώτα τρία . Το τέταρτο , όπως αποδείχθηκε , ήταν σε άλλο επίπεδο :D

Πάντως είναι πολύ ενθαρρυντικό που υπάρχει συμμετοχή ;) . Πολλά μπράβο και συγχαρητήρια στους διοργανωτές. Ανυπομονώ τον διαγωνισμό Νοεμβρίου :P
Άβαταρ μέλους
kernelpanic
Δημοσιεύσεις: 404
Εγγραφή: Κυρ Δεκ 21, 2008 8:16 pm
Τοποθεσία: Αθήνα

Re: Hellenico Training Contest - Οκτώβριος 2011

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

ήμουν πεπεισμένος οτι τα σημεία κάθε ημιεπιπέδου έπρεπε να τα βάλω σε λίστα και να πάρω τομή συνόλων, οπότε έβγαινε Ο(Ν^4),damn :?

Είναι εύκολο τα 2 πρώτα προβλήματα να είναι διαθέσιμα προς επίλυση και σε ΓΛΩΣΣΑ;
99 little bugs in the code,
99 bugs in the code,
Fix one bug,
Compile again,
104 little bugs in the code.
pman
Δημοσιεύσεις: 419
Εγγραφή: Τρί Φεβ 10, 2009 9:49 pm

Re: Hellenico Training Contest - Οκτώβριος 2011

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

kernelpanic έγραψε: Είναι εύκολο τα 2 πρώτα προβλήματα να είναι διαθέσιμα προς επίλυση και σε ΓΛΩΣΣΑ;
Γιατί να μην είναι;
feedWARd
Δημοσιεύσεις: 72
Εγγραφή: Κυρ Δεκ 21, 2008 3:32 pm

Re: Hellenico Training Contest - Οκτώβριος 2011

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

kernelpanic έγραψε:Είναι εύκολο τα 2 πρώτα προβλήματα να είναι διαθέσιμα προς επίλυση και σε ΓΛΩΣΣΑ;
Έχεις υπ'όψιν σου κανέναν compiler/interpreter που να δουλεύει σε linux;
Memas
Δημοσιεύσεις: 87
Εγγραφή: Παρ Δεκ 31, 2010 4:13 pm
Επικοινωνία:

Re: Hellenico Training Contest - Οκτώβριος 2011

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

Να πώ και εγώ μία λογική να μου πείτε αν είναι σωστή αν και δεν συμμετείχα στο διαγωνισμό :P ..
Αν βρίσκαμε σημεία με μεγαλύτερο y για κορυφές μικρότερο χ και y για αριστερή πλευρά και με μεφαλύτερο χ και μικρότερο y για δεξιά πλευρά; Μετά ελένχουμε τα χ και τα y των σημείων μας αν είναι ανάμεσα στις κορυφές ή και ελένχουμε αν τα σημεία επαληθεύουν τις εξισώσεις των ευθειών των πλευρών...Βασικά κενό θα έχει άμα υπάρχουν 2-3 ίδια max y ή minx,miny καταλάβατε... Τι λέτε..;
Άβαταρ μέλους
Κηπουρίδης
Δημοσιεύσεις: 397
Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm

Re: Hellenico Training Contest - Οκτώβριος 2011

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

Memas έγραψε:Να πώ και εγώ μία λογική να μου πείτε αν είναι σωστή αν και δεν συμμετείχα στο διαγωνισμό :P ..
Αν βρίσκαμε σημεία με μεγαλύτερο y για κορυφές μικρότερο χ και y για αριστερή πλευρά και με μεφαλύτερο χ και μικρότερο y για δεξιά πλευρά; Μετά ελένχουμε τα χ και τα y των σημείων μας αν είναι ανάμεσα στις κορυφές ή και ελένχουμε αν τα σημεία επαληθεύουν τις εξισώσεις των ευθειών των πλευρών...Βασικά κενό θα έχει άμα υπάρχουν 2-3 ίδια max y ή minx,miny καταλάβατε... Τι λέτε..;
Δε θα δουλέψει.
Σκέψου ένα μεγάλο τετράγωνο. Τράβα τη μιά διαγώνιο, και μέσα στο ένα από τα δύο τρίγωνα χώσε 400 σημεία. Το τρίγωνο που θα πάρεις εσύ για λύση θα είναι ένα άδειο τρίγωνο ( 3 σημεία ), ενώ το άλλο θα έχει 403 σημεία.
Λύσεις θεμάτων ΠΔΠ: 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: Hellenico Training Contest - Οκτώβριος 2011

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

Memas έγραψε:Να πώ και εγώ μία λογική να μου πείτε αν είναι σωστή αν και δεν συμμετείχα στο διαγωνισμό :P ..
Αν βρίσκαμε σημεία με μεγαλύτερο y για κορυφές μικρότερο χ και y για αριστερή πλευρά και με μεφαλύτερο χ και μικρότερο y για δεξιά πλευρά; Μετά ελένχουμε τα χ και τα y των σημείων μας αν είναι ανάμεσα στις κορυφές ή και ελένχουμε αν τα σημεία επαληθεύουν τις εξισώσεις των ευθειών των πλευρών...Βασικά κενό θα έχει άμα υπάρχουν 2-3 ίδια max y ή minx,miny καταλάβατε... Τι λέτε..;
Δε θα δουλέψει.
Σκέψου ένα μεγάλο τετράγωνο. Τράβα τη μιά διαγώνιο, και μέσα στο ένα από τα δύο τρίγωνα χώσε 400 σημεία. Το τρίγωνο που θα πάρεις εσύ για λύση θα είναι ένα άδειο τρίγωνο ( 3 σημεία ), ενώ το άλλο θα έχει 403 σημεία.
Υ.Γ.: Χωρίς διάθεση να στην πω... ε, αυτό δεν ήταν διατύπωση ρε φίλε. Το γάμησες και ψόφησε.
Λύσεις θεμάτων ΠΔΠ: 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/
Memas
Δημοσιεύσεις: 87
Εγγραφή: Παρ Δεκ 31, 2010 4:13 pm
Επικοινωνία:

Re: Hellenico Training Contest - Οκτώβριος 2011

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

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

Re: Hellenico Training Contest - Οκτώβριος 2011

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

Ναί, κατάλαβα γιατί εἶχε περάσει ἡ σκέψη αὐτὴ ἀπ`τὸ μυαλό μου, γιὰ κανέναν ἄλλο λόγο.
Τῶρα σκέψου στὸ προηγούμενο παράδειγμα νὰ τοποθετήσεις 200 ( ἀντὶ γιὰ κανένα ) σημεῖα μέσα στὸ ἕνα τρίγωνο, καὶ 200 ( ἀντὶ γιὰ 400 ) στὸ ἄλλο. Τοποθέτησέ τα ἔτσι ὥστε νὰ μποροῦν νὰ κλειστοῦν ἀπὸ ἕνα μικρότερο τρίγωνο, ποὺ καμμία κορυφή του δὲν ἀνήκει στὸ convex hull.
Τὰ δύο μεγάλα τρίγωνα θὰ ἔχουν 203 σημεῖα, ἐνὼ τὸ τελευταῖο τρίγωνο 403.
Λύσεις θεμάτων ΠΔΠ: 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/
thanos713
Δημοσιεύσεις: 72
Εγγραφή: Τετ Αύγ 11, 2010 5:59 pm

Re: Hellenico Training Contest - Οκτώβριος 2011

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

Ρε παίδες πρόκειται να βρούμε από πουθενά τα testcases των προβλημάτων;
Άβαταρ μέλους
Κηπουρίδης
Δημοσιεύσεις: 397
Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm

Re: Hellenico Training Contest - Οκτώβριος 2011

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

Μπες http://hellenico.gr/contest/?page=competitions και πάτα στο διαγωνισμό Οκτωβρίου.
Μετά προβολή όλων των υποβολών, και στην ενεργή υποβολή του προβλήματος που θέλεις. Θα σε δείξει ποια testcases πέρασες και ποια όχι, κι από δίπλα έχει και ένα κουμπάκι ΠΡΟΒΟΛΗ. Αυτό είναι που ψάχνεις.
Λύσεις θεμάτων ΠΔΠ: 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/
thanos713
Δημοσιεύσεις: 72
Εγγραφή: Τετ Αύγ 11, 2010 5:59 pm

Re: Hellenico Training Contest - Οκτώβριος 2011

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

Το θέμα είναι ότι δεν έκανα καμία υποβολή για το πρόβλημα που ψάχνω τα testcases...
Απάντηση