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

couples.in
5 6 3
0 5 0 1 2 4 5
1 5 1 2 3 4 5
2 4 1 2 4 5
3 2 0 3
4 3 1 2 5

couples.out
3

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

back to top


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 γραμμή αποτελούμενη από ένα ακέραιο αριθμό που θα δίδει τον αριθμό των απαραίτητων δημοσιαγραφων.

Παράδειγμα

couples.in
5 6 3
0 5 0 1 2 4 5
1 5 1 2 3 4 5
2 4 1 2 4 5
3 2 0 3
4 3 1 2 5

couples.out
3

Στο πιο πάνω παράδειγμα , τα 3 ζευγάρια που εμφανίζονται περισσότερο από 3 φορές είναι : 1-2, 1-5 και 2-5

Μορφή : Και στα 2 αρχεία εισόδου και εξόδου , όλοι οι αριθμοί στη κάθε γραμμή χωρίζονται μεταξύ τους από ένα κενό διάστημα και όλες οι γραμμές τελειώνουν με το χαρακτήρα νέας γραμμής ( newline character ).

Χρονικό όριο : 15 δευτερόλεπτα.

back to top


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.

back to top


DAY 1 :: Task 3 :: Data sets

Download Data Sets

back to top


 

 

 

Organized by
the Greek
Computer Society

and the
University of the Aegean

under the auspices
of the Ministry of National Education and Relegious Affairs
design by Ad Hoc Applied Informatics Ltd