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

tickets.in
4
8
0.28390927493533
0.17355945737314
0.13014380192001
0.10610039157939
0.09055467526374
0.07955952705969
0.07131156575676
0.06486130611193

tickets.out
1
3
5
8

In this example, the average delay value is 0.96591156199652 resulting from the following page distribution:

Channel

1

2

3

4

Pages

1

2,3

4,5

6,7,8

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

back to top


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 - Εισιτήρια (Συνέχεια)

Παράδειγμα

Tickets.in
4
8
0.28390927493533
0.17355945737314
0.13014380192001
0.10610039157939
0.09055467526374
0.07955952705969
0.07131156575676
0.06486130611193

Tickets.out
1
3
5
8

Σε αυτό το παράδειγμα ο μέσος όρος αναμονής είναι 0.96591156199652 το οποίο εξάγεται απο την παρακάτω κατανομή σελίδων.

Κανάλι

1

2

3

4

Σελίδες

1

2,3

4,5

6,7,8

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

Χρονικό όριο : 1 δευτερόλεπτο

back to top


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 . Given K channels, the average expected delay is:

, where

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 , where

|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.

back to top


DAY 2 :: Task 2 :: 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