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

[feedWARd]

14-17 Οκτωβρίου. Tell your friends

[zaxeilasfc]

Thanks mr. John. Περιμένουμε ενδιαφέρον θέματα.

[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]

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

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

|Zi|<=|W| , |Zu|>=|W| , |Zj|>=|W| i,u,j=({1,2,3} ,i!=u!=j)

[Κηπουρίδης]

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

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

[feedWARd]

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

Στην ουσία δουλεύουμε στο μιγαδικό επίπεδο(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]

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

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

[kernelpanic]

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

Είναι εύκολο τα 2 πρώτα προβλήματα να είναι διαθέσιμα προς επίλυση και σε ΓΛΩΣΣΑ;

[pman]

Είναι εύκολο τα 2 πρώτα προβλήματα να είναι διαθέσιμα προς επίλυση και σε ΓΛΩΣΣΑ;

Γιατί να μην είναι;

[feedWARd]

Είναι εύκολο τα 2 πρώτα προβλήματα να είναι διαθέσιμα προς επίλυση και σε ΓΛΩΣΣΑ;

Έχεις υπ'όψιν σου κανέναν compiler/interpreter που να δουλεύει σε linux;

[Memas]

Να πώ και εγώ μία λογική να μου πείτε αν είναι σωστή αν και δεν συμμετείχα στο διαγωνισμό ..
Αν βρίσκαμε σημεία με μεγαλύτερο y για κορυφές μικρότερο χ και y για αριστερή πλευρά και με μεφαλύτερο χ και μικρότερο y για δεξιά πλευρά; Μετά ελένχουμε τα χ και τα y των σημείων μας αν είναι ανάμεσα στις κορυφές ή και ελένχουμε αν τα σημεία επαληθεύουν τις εξισώσεις των ευθειών των πλευρών...Βασικά κενό θα έχει άμα υπάρχουν 2-3 ίδια max y ή minx,miny καταλάβατε... Τι λέτε..;

[Κηπουρίδης]

Να πώ και εγώ μία λογική να μου πείτε αν είναι σωστή αν και δεν συμμετείχα στο διαγωνισμό ..
Αν βρίσκαμε σημεία με μεγαλύτερο y για κορυφές μικρότερο χ και y για αριστερή πλευρά και με μεφαλύτερο χ και μικρότερο y για δεξιά πλευρά; Μετά ελένχουμε τα χ και τα y των σημείων μας αν είναι ανάμεσα στις κορυφές ή και ελένχουμε αν τα σημεία επαληθεύουν τις εξισώσεις των ευθειών των πλευρών...Βασικά κενό θα έχει άμα υπάρχουν 2-3 ίδια max y ή minx,miny καταλάβατε... Τι λέτε..;

Δε θα δουλέψει.
Σκέψου ένα μεγάλο τετράγωνο. Τράβα τη μιά διαγώνιο, και μέσα στο ένα από τα δύο τρίγωνα χώσε 400 σημεία. Το τρίγωνο που θα πάρεις εσύ για λύση θα είναι ένα άδειο τρίγωνο ( 3 σημεία ), ενώ το άλλο θα έχει 403 σημεία.

[Κηπουρίδης]

Να πώ και εγώ μία λογική να μου πείτε αν είναι σωστή αν και δεν συμμετείχα στο διαγωνισμό ..
Αν βρίσκαμε σημεία με μεγαλύτερο y για κορυφές μικρότερο χ και y για αριστερή πλευρά και με μεφαλύτερο χ και μικρότερο y για δεξιά πλευρά; Μετά ελένχουμε τα χ και τα y των σημείων μας αν είναι ανάμεσα στις κορυφές ή και ελένχουμε αν τα σημεία επαληθεύουν τις εξισώσεις των ευθειών των πλευρών...Βασικά κενό θα έχει άμα υπάρχουν 2-3 ίδια max y ή minx,miny καταλάβατε... Τι λέτε..;

Δε θα δουλέψει.
Σκέψου ένα μεγάλο τετράγωνο. Τράβα τη μιά διαγώνιο, και μέσα στο ένα από τα δύο τρίγωνα χώσε 400 σημεία. Το τρίγωνο που θα πάρεις εσύ για λύση θα είναι ένα άδειο τρίγωνο ( 3 σημεία ), ενώ το άλλο θα έχει 403 σημεία.
Υ.Γ.: Χωρίς διάθεση να στην πω... ε, αυτό δεν ήταν διατύπωση ρε φίλε. Το γάμησες και ψόφησε.

[Memas]

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

[Κηπουρίδης]

Ναί, κατάλαβα γιατί εἶχε περάσει ἡ σκέψη αὐτὴ ἀπ`τὸ μυαλό μου, γιὰ κανέναν ἄλλο λόγο.
Τῶρα σκέψου στὸ προηγούμενο παράδειγμα νὰ τοποθετήσεις 200 ( ἀντὶ γιὰ κανένα ) σημεῖα μέσα στὸ ἕνα τρίγωνο, καὶ 200 ( ἀντὶ γιὰ 400 ) στὸ ἄλλο. Τοποθέτησέ τα ἔτσι ὥστε νὰ μποροῦν νὰ κλειστοῦν ἀπὸ ἕνα μικρότερο τρίγωνο, ποὺ καμμία κορυφή του δὲν ἀνήκει στὸ convex hull.
Τὰ δύο μεγάλα τρίγωνα θὰ ἔχουν 203 σημεῖα, ἐνὼ τὸ τελευταῖο τρίγωνο 403.

[thanos713]

Ρε παίδες πρόκειται να βρούμε από πουθενά τα testcases των προβλημάτων;

[Κηπουρίδης]

Μπες http://hellenico.gr/contest/?page=competitions και πάτα στο διαγωνισμό Οκτωβρίου.
Μετά προβολή όλων των υποβολών, και στην ενεργή υποβολή του προβλήματος που θέλεις. Θα σε δείξει ποια testcases πέρασες και ποια όχι, κι από δίπλα έχει και ένα κουμπάκι ΠΡΟΒΟΛΗ. Αυτό είναι που ψάχνεις.

[thanos713]

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