![]() |
![]() DAY 2 :: Task 2 :: Desciption Description in greek :: Solution :: Data sets Back to Day 2 problems - solutions - data sets TASK 2 -Tickets The Hellenic Broadcasting Company (HBC) wants to modernize its teletext broadcasting system. The HBC has a number of equal size information teletext pages that are broadcasted in D channels concerning ticket information of the Hellenic Railway Organisation. Additionally, HBC through a thorough investigation revealed the popularity (probability of viewing a page) of all Teletext pages. Based on these data, the manager of HBC has to decide which pages will be broadcasted on each channel, so that the average delay of viewing a page is minimised. The pages of the channel are cyclically broadcasted in a round-robin fashion, e.g. for a channel with 3 pages A, B, C, the broadcasting order is A,B,C,A,B,C,A,. . However, because of the used information system, all pages have an Internal Code (IC), which are given based on their popularity in decreasing order. The IC is a unique identifier for each page. For example, for three channels that serve 10 pages totally (i.e. IC ranges from 1 to 10), channel D 1 can only serve pages with IC in the range [1.. M 1 ] (where M 1 ?1), channel D 2 can only serve pages with IC in the range [ M 1 +1.. M 2 ] (where M 2 ? M 1 +1), and channel D 3 can only serve pages with IC in the range [ M 2 +1..10]. Given the number of channels, the number of pages and the popularity of each page, your task is to calculate the maximum IC page broadcasted from each channel to minimize the average delay of viewing a page. Input Your program should read the input from a file "tickets.in". The first line of the file contains an integer D representing the number of channels (where 1? D ?20) and the second line contains an integer L representing the number of pages (where 1? L ?300). Each of the next L lines contains a single real number in the range [0..1], which depicts the popularity of the page. These popularities are given in decreasing order. Output Your program should write the output into a file "tickets.out" with D lines. Each line should contain a single integer denoting the maximum page IC J served from each channel (for 1? J ? L ).
Example
In this example, the average delay value is 0.96591156199652 resulting from the following page distribution:
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 : 1 second DAY 2 :: Task 2 :: Desciption in greek Πρόβλημα 2 - Εισιτήρια Η Ελληνική εταιρεία ευρείας μετάδοσης μηνυμάτων ( Η BC ) θέλει να εκσυγχρονίσει την υπηρεσία teletext . H Η BC έχει ένα αριθμό από σελίδες ίσους μεγέθους, οι οποίες μεταδίδουν σε D κανάλια πληροφορίες που αφορούν εισιτήρια του Ελληνικού Οργανισμού Τραίνων. Επιπρόσθετα, η HBC μετά από ενδελεχή έρευνα έχει μετρήσει την δημοτικότητα κάθε σελίδας teletext (την πιθανότητα να θέλει να δει κάποιος μια σελίδα). Με βάση αυτές τις πληροφορίες , ο διευθυντής της HBC έχει αποφασίσει ποιες σελίδες θα μεταδίδονται σε κάθε κανάλι, ούτως ώστε ο μέσος όρος αναμονής για κάθε σελίδα να είναι ο ελάχιστος. Οι σελίδες του καναλιού μεταδίδονται κυκλικά χρησιμοποιώντας τη μορφή round robin , π.χ για ένα κανάλι με 3 σελίδες Α, Β, C , η σειρά μετάδοσης είναι Α,Β, C , A , B , C , A . . Παρεμπιπτόντως, λόγω της χρήσης του πληροφοριακού συστήματος , όλες οι σελίδες έχουν ένα εσωτερικό κωδικό ( IC ) o οποί o ς δίνεται με βάση τη δημοτικότητά τους κατά φθίνουσα σειρά ταξινόμησης.. Αυτός ο κωδικός είναι μοναδικός για κάθε σελίδα. Π.χ , για 3 κανάλια τα οποία εξυπηρετούν συνολικά 10 σελίδες ( δηλ. IC που αρχίζουν από 1 μέχρι το 10) , το κανάλι D 1 μπορεί να εξυπηρετήσει σελίδες με αναγνωριστικό IC στα όρια [1..Μ1] (οπού Μ1>=1), το κανάλι D 2 μπορεί να εξυπηρετήσει σελίδες με αναγνωριστικό IC στα όρια [ M 1 +1.. M 2 ] (όπου M 2 ? M 1 +1), το κανάλι D 3 μπορεί να εξυπηρετήσει σελίδες με αναγνωριστικό IC στα όρια [ M 2 +1..10]. Έχοντας τον αριθμό των καναλιών , τον αριθμό των σελίδων και την δημοτικότητα της κάθε σελίδας , ο σκοπός σας είναι να βρείτε τη σελίδα με το μέγιστο κωδικό IC που μεταδίδεται σε κάθε κανάλι ούτως ώστε ο μέσος ορός αναμονής να είναι ο ελάχιστος. Είσοδος Το πρόγραμμα σας πρέπει να διαβάζει από το αρχείο εισόδου "tickets . in". Η 1 η γραμμή περιέχει ένα ακέραιο D που αντιπροσωπεύει τον αριθμό των καναλιών (όπου 1? D ?20) και η 2 η γραμμή έναν ακέραιο L που αντιπροσωπεύει τον αριθμό των σελίδων (οπού 1? L ?300). Κάθε μια από τις επόμενες L γραμμές περιέχει ένα πραγματικό αριθμό στα όρια [0..1] , που είναι και η δημοτικότητα της σελίδας . Αυτές οι πιθανότητες δίδονται σε φθίνουσα σειρά. Έξοδος Το πρόγραμμα σας θα πρέπει να γράφει στο αρχείο εξόδου " tickets . out"
έχοντας D γραμμές. Κάθε γραμμή περιέχει μόνο ένα ακέραιο ο οποίος
αντιπροσωπεύει την σελίδα με το μέγιστο IC που εξυπηρετείται σε κάθε
κανάλι. ( όπου 1? IC ? L ). Πρόβλημα 2 - Εισιτήρια (Συνέχεια) Παράδειγμα
Σε αυτό το παράδειγμα ο μέσος όρος αναμονής είναι 0.96591156199652 το οποίο εξάγεται απο την παρακάτω κατανομή σελίδων.
Μορφή : και στα 2 αρχεία εισόδου και εξόδου, όλοι οι αριθμοί σε 1 γραμμή χωρίζονται με ένα απλό διάστημα και όλες οι γραμμές τελειώνουν με το χαρακτήρα νέας γραμμής. Χρονικό όριο : 1 δευτερόλεπτο DAY 2 :: Task 2 :: Solution This problem comes from the problem of data allocation in a broadcast
environment . The task is to allocate data to a given number of
physical broadcast channels in order to minimize the average delay for a
data item. When N i data items are cyclically broadcast on channel i, the
expected delay in receiving any particular data item j is
d j denotes the j-th data item C i denotes the i-th channel p j denotes the popularity of the j-th data item In order to achieve even better execution time, one should come up with the following idea: Any two partitions, for two channels C i , C j , if |C i | < |C j |,
then |C i | denotes the number of data items transmitted by C i channel It can be concluded that the first channel has always less data items than the second, the second has less than the third and so on. Thus, the search space is reduced and the problem can be solved using dynamic programming.
1. Yee, Wai Gen . " Efficient Data Allocation For Broadcast Disk Arrays ", CC Technical Report; GIT-CC-02-20, Georgia Institute of Technology, 2002. DAY 2 :: Task 2 :: Data sets
| ||||||||||||||||||||||||||||
Organized by |
the Greek Computer Society |
and the |
|||||||||||||||||||||||||||
![]() | |||||||||||||||||||||||||||||
|