DAY 1 :: Task 1 :: Desciption

Description in greek :: Solution :: Data sets

Back to Day 1 problems - solutions - data sets

TASK 1 - CPU

John is attempting to design a low cost processor that he can build on a circuit board using standard components. The components need to be connected together with connecting wires ("connections"). The connections cannot cross components or each other, but do not have to follow straight lines.

John has already made the basic design, in which all the components are connected together in a loop (called the main loop). The components in the main loop are in a consecutive order. However, to speed up the processor he wants to add direct connections between some pairs of components. For each component he will wish to add at most one connection. He has made a list of all the connections he wants to add, and has ordered them by importance. He will incorporate the K most important of these connections, where K is as large as possible without forcing wires to cross. Your task is to write a program and help John to determine the largest possible value of K .

Input

Your program should read the input from a file "cpu.in". The first line of the file contains an integer N (where 1<N <200.000) representing the number of components that John has already in the main loop. The second line contains an integer M (where 1<M <50.000) representing the number of extra connections that John is considering to add. The remaining M lines contain two positive integers P and Q , indicating that John wishes to connect P to Q .

Note : there is never a connection from a component to itself, although a component may be connected to an adjacent component in the main loop. The connections are listed in descending order of importance.

Output

Your program should write the output into a file "cpu.out" with 1 line containing a single integer, the maximum possible value of K .

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 : 2 seconds

back to top

DAY 1 :: Task 1 :: Desciption in greek

Θέμα 1 - CPU

Ο Γιάννης προσπαθεί να σχεδιάσει έναν επεξεργαστή χαμηλού κόστους ο οποίος μπορεί να χτιστεί σε μια βάση κυκλωμάτων χρησιμοποιώντας δεδομένα ( standard ) εξαρτήματα. Τα εξαρτήματα απαιτείται να συνδεθούν μεταξύ τους με καλωδιακές συνδέσεις. Οι συνδέσεις δεν πρέπει να διασταυρώνουν τα εξαρτήματα ή άλλες συνδέσεις, αλλά δεν είναι αναγκαίο να ακολουθήσουν ευθείες γραμμές

Ο Γιάννης έχει ήδη κάνει τη βασική σχεδίαση, στην οποία όλα τα εξαρτήματα είναι συνδεδεμένα μεταξύ τους σε ένα βρόγχο, τον οποίο καλούμε κύριο βρόγχο. ( Αυτές οι συνδέσεις είναι το 1 με 2 , το 2 με το 3 , ..., το Ν με το 1 ). Τα εξαρτήματα στον κύριο βρόγχο είναι διαδοχικά αριθμημένα. Ωστόσο για να αυξηθεί η ταχύτητα του επεξεργαστή, απαιτείται να συνδεθούν απ' ευθείας κάποια από τα ζευγάρια των εξαρτημάτων. Για κάθε εξάρτημα θα επιθυμήσει να προσθέσει το πολύ μία επιπλέον σύνδεση. Αυτός έχει φτιάξει μια λίστα με όλες τις συνδέσεις που θέλει να προσθέσει και τις έχει ταξινομήσει με βάση τη σειρά προτεραιότητας (σημασία τους). Θα προσθέσει τις K ποιο σημαντικές από αυτές τις συνδέσεις, όπου το Κ πρέπει να είναι όσο πιο μεγάλο γίνεται χωρίς να επιβάλει διασταυρώσεις καλωδίων. Έργο σας είναι να γράψετε ένα πρόγραμμα και να βοηθήσετε το Γιάννη να προσδιορίσει τη μέγιστη δυνατή τιμή του Κ .

Είσοδος

Το πρόγραμμά σας θα διαβάζει τα δεδομένα εισόδου από ένα αρχείο "cpu.in" . Η πρώτη γραμμή του αρχείου περιέχει ένα ακέραιο N (όπου 1<N <200.000) ο οποίος εκφράζει τον αριθμό των εξαρτημάτων που ήδη ο Γιάννης έχει στον κύριο βρόγχο. Η δεύτερη γραμμή περιέχει έναν ακέραιο M (όπου 1<M <50.000) ) ο οποίος εκφράζει τον αριθμό των επιπλέον συνδέσεων τις οποίες ο Γιάννης σκοπεύει να προσθέσει. Οι υπόλοιπες M γραμμές περιέχουν δύο θετικούς ακέραιους P και Q , που δείχνουν ότι ο Γιάννης θέλει να συνδέσει το εξάρτημα P με το Q .

Προσοχή : Δεν υπάρχει καμία σύνδεση ενός εξαρτήματος με τον εαυτό του, κάθε εξάρτημα μπορεί να είναι συνδεδεμένο με ένα γειτονικό εξάρτημα στον κύριο βρόγχο. Οι συνδέσεις είναι καταγεγραμμένες με φθίνουσα σειρά σημαντικότητας.

Output

Το πρόγραμμά σας πρέπει να επιστρέφει την έξοδο στο αρχείο " cpu.out" με 1 γραμμή που θα περιέχει έναν απλό ακέραιο, τη μέγιστη δυνατή τιμή του Κ.

Παράδειγμα

Μορφή : Και στο input και στο output file , όλοι οι αριθμοί σε μια γραμμή ξεχωρίζουν με ένα μόνο κενό και όλες οι γραμμές τελειώνουν με ένα χαρακτήρα new line .

Όριο Χρόνου : 2 seconds

back to top

DAY 1 :: Task 1 :: Solution

This problem is inspired by the general problem of determining whether a given graph is planar. However, the main loop of the processor makes the problem significantly easier, and the optimisation (rather than decision) nature of the problem opens it up to some interesting approaches. Consider a graph whose vertices are the connections. An edge joins two connections if they cannot be placed on the same side (inside or outside) of the main loop. Now if this graph can be two-coloured, then the red connections can be routed around the outside and the blue connections through the inside of the main loop.

In order to solve the problem one must maintain an extension of the standard Union/Find tree structure. Each edge in this structure also indicates whether the two nodes are the same or opposite colours. The connections are added one at a time. For each connection, its conflicts with existing connections are determined and used to update the structure. The algorithm terminates when one attempts to join two connections that must have the same colour. The complexity of the proposed solution is O(n²alpha(n)) to O(n³), depending on the implementation of the union/find structure.

back to top

DAY 1 :: Task 1 :: Data sets

Download Data Sets

back to top