![]() |
![]() DAY 1 :: Task 3 :: Desciption Description in greek :: Solution :: Data sets Back to Day 1 problems - solutions - data sets TASK 3 - Couples The editor - in - chief of the weekly magazine Rhodian Matchmaker wishes to dedicate the next issue to introduce the list of couples that keep their relationship secret. The only source of information to locate these couples that have not announced yet their relationship is their common visits at the parties that take place on the island. The editor-in-chief decided to assign a dedicated journalist for each couple that appeared at more than K parties to verify their relationship. Your task is to write a program that: (a) reads from the input file information about the persons that were present at each party, (b) calculates the number of journalists the editor-in-chief will require, and (c) write the result to the output file. Input Your program should read the input from a file "couples.in". The first line of the file contains three integers N (where 1? N ?600.000), M (where 1? M ?20.000), and K (where 3? K ? 1.000), representing the number of parties, the number of persons and the maximum number of combined appearances to verify a non-relationship, respectively. That is, for two persons to be considered as a potential couple, they must appear together at least K +1 times. The next N lines contain information about the parties. In particular, each of the next N lines contains one integer X (where 0? X < N ) standing for the id of the party, one integer Y (where 1? Y ? M ) for the number of persons that were present at the party and a set of Y numbers representing the id's of the present persons, ids are in the range [0,M). Output Your program should write the output into a file "couples.out" with 1 line containing a single integer denoting the number of necessary journalists. Example
Format : In both input and output files, all numbers in a line are separated with a single space and all lines terminate with a newline character. Time limit : 15 seconds DAY 1 :: Task 3 :: Desciption in greek Θέμα 3 - Ζευγάρια Ο Αρχισυντάκτης του εβδομαδιαίου περιοδικού Rhodian Matchmaker , επιθυμεί να αφιερώσει το επόμενο τεύχος, στην παρουσίαση καταλόγου ζευγαριών τα οποία κρατούν μυστικό το δεσμό τους. Η μονή πηγή πληροφόρησης για τον εντοπισμό των ζευγαριών τα οποία δεν έχουν ανακοινώσει ακόμα την σχέση τους είναι , οι κοινές επισκέψεις σε συγκεντρώσεις ( parties ) που έχουν γίνει στο νησί. Ο Αρχισυντάκτης αποφάσισε την ανάθεση ενός αφοσιωμένου δημοσιογράφου για κάθε ζευγάρι, που παρουσιάζεται σε περισσότερες από Κ συγκεντρώσεις ( parties ) , προς επιβεβαίωση της σχέσης τους. Στόχος σας είναι να γράψετε ένα πρόγραμμα το οποίο : • Να διαβάζει από ένα αρχείο ( Input File ) με πληροφορίες σχετικά με τα άτομα που παρουσιαστήκαν σε κάθε συγκέντρωση ( party ). • Να υπολογίζει των αριθμό των δημοσιογράφων που θα χρειαστεί ο Αρχισυντάκτης . • Τα αποτελέσματα να γραφούν σε αρχείο εξόδου ( output file ). Είσοδος Το πρόγραμμα σας πρέπει να διαβάζει τα δεδομένα από το αρχείο εισόδου "couples.in". Η 1 η γραμμή από το αρχείο περιέχει 3 ακεραίους Ν (όπου 1 <=Ν<=600.000) , Μ (όπου 1 <=Μ<=20.000), και Κ (όπου 3 <=Κ<=1.000). Ο ακέραιος Ν αντιπροσωπεύει τον αριθμό συγκεντρώσεων ( parties ), Μ αντιπροσωπεύει τον αριθμό των ατόμων , και Κ αντιπροσωπεύει τον μέγιστο αριθμό των συνδυασμένων εμφανίσεων προς μη απόδειξη της σχέσης. Επομένως 2 άτομα για να θεωρηθούν σαν πιθανό ζευγάρι, πρέπει να εμφανισθούν μαζί τουλάχιστον Κ+1 φορές. Οι επόμενες Ν γραμμές περιέχουν πληροφορίες σχετικές για τις συγκεντρώσεις ( parties ). Συγκεκριμένα , κάθε μια από τις επόμενες Ν γραμμές περιέχει ένα ακέραιο Χ ( όπου 0 <= Χ < Ν) για την ταυτότητα ( Id ) της συγκέντρωσης ( party ), ένα ακέραιο Υ (όπου 1 <= Υ <= Μ) για τον αριθμό των ατόμων που παρευρίσκοντο στην συγκέντρωση ( party ) , και ένα σύνολο από Υ αριθμούς αντιπροσωπεύοντας τις ταυτότητες ( Id ' s ) των παρευρισκομένων ατόμων , οι ταυτότητες ( Id ' s ) πρέπει να είναι μεταξύ [0,Μ). Έξοδος Το πρόγραμμα σας θα πρέπει γράφει τ o αποτέλεσμα στο αρχείο "couples.out" σε 1 γραμμή αποτελούμενη από ένα ακέραιο αριθμό που θα δίδει τον αριθμό των απαραίτητων δημοσιαγραφων. Παράδειγμα
Στο πιο πάνω παράδειγμα , τα 3 ζευγάρια που εμφανίζονται περισσότερο από 3 φορές είναι : 1-2, 1-5 και 2-5 Μορφή : Και στα 2 αρχεία εισόδου και εξόδου , όλοι οι αριθμοί στη κάθε γραμμή χωρίζονται μεταξύ τους από ένα κενό διάστημα και όλες οι γραμμές τελειώνουν με το χαρακτήρα νέας γραμμής ( newline character ). Χρονικό όριο : 15 δευτερόλεπτα. DAY 1 :: Task 3 :: Solution This problem is motivated from the problem of discovering association rules between items in a large database of sales transactions. Given a set of transactions D, the problem of mining association rules is to generate all association rules that have support greater than the user specified minimum support (called minsup). The problem of discovering all association rules can be attacked by finding all sets of items (itemsets) that have transaction support above minimum support. The support for an itemset is the number of transactions that contain the itemset. Itemsets with minimum support are called large itemsets, and all others small itemsets. Algorithms for discovering large itemsets make two passes over the
data. In the first pass, we count the support of individual items and
determine which of them are large. The small items are discarded. In the
next pass, we only consider the large items in order to discover couples
that appeared at more than minsup parties. DAY 1 :: Task 3 :: Data sets
| ||||||||||
Organized by |
the Greek Computer Society |
and the |
|||||||||
![]() | |||||||||||
|