Round 2H

Overview

This contest is over.

TaskTotalSubtask 1
dfs‒/20‒/20
bfs‒/20‒/20
dijkstra‒/20‒/20
bsearch‒/20‒/20
prefixsum‒/20‒/20

Tiefensuche

Diese und die nächsten paar Aufgaben handeln von der sogenannten Graphentheorie. Wenn du das Wort “Graphentheorie” nun gerade zum ersten Mal hörst/liest, sagt dir das vermutlich nicht viel. “Graphein” ist griechisch für “schreiben”, was auch nicht viel aussagt. Mit dem Zeichnen zweidimensionaler Funktionsgraphen, das du vielleicht aus dem Mathematikunterricht kennst, hat es auch nichts zu tun. Und “Theorie” soll hier nicht heissen, dass es sich um ungetestete Behauptungen handelt, sondern vielmehr um allgemeine Konzepte, die in sehr vielen Situationen anwendbar sind.

Problembeschreibung

Was ist ein Graph?

Als Graphen bezeichnen wir eine Menge von Punkten und Verbindungen zwischen diesen Punkten. Die Punkte werden meist Knoten und die Verbindungen zwischen Punktepaaren meist Kanten genannt. Im Bild 1 siehst du ein Beispiel eines solchen Graphen. Jeder Kreis ist ein Knoten und jede Linie, die zwei solche Knoten verbindet, ist also eine Kante.

2H DFS graph example

Bild 1: Ein Beispiel für einen Graphen mit 6 Knoten und 5 Kanten.

Dieser Graph besteht also aus 6 Knoten und 5 Kanten. Eine der fünf Kanten verläuft zwischen Knoten 22 und 33, daher sagen wir, dass Knoten 22 mit Knoten 33 benachbart ist. Die beiden Knoten sind auch indirekt benachbart, nämlich über den gemeinsamen Nachbarn 44. Häufig sprechen wir von der Nachbarschaft eines Knotens, was einfach die Menge aller Nachbarn bezeichnet. Die Nachbarschaft von 33 sind die Knoten 11, 22 und 44 und die Nachbarschaft von 22 sind die Knoten 33 und 44.

Einen Graphen so aufzuzeichnen ist eine Art ihn darzustellen. Auf die genaue Zeichnungsart kommt es uns aber gar nicht an. Wenn wir die Knoten ein wenig verschieben und die Kanten entsprechend mitbewegen, sagen wir immer noch, dass dies derselbe Graph ist. Es muss auch gar nicht unbedingt eine solche Zeichnung sein, wir können einen Graphen auch einfach als abstrakte Liste von Knoten und Kanten beschreiben. Dazu benennen wir oft die Knotenmenge mit VV (Englisch vertices) und die Kantenmenge mit EE (Englisch edges). Das Beispiel im Bild 1 wäre dann V={1,2,3,4,5,6}V = \{1,2,3,4,5,6\} und E={{1,3},{2,3},{2,4},{3,4},{5,6}}E=\{ \{1,3\}, \{2,3\}, \{2,4\}, \{3,4\}, \{5,6\} \}. Die Anzahl Knoten bezeichnen wir meist mit nn (im Beispiel ist n=6n=6) und die Anzahl Kanten mit mm (im Beispiel ist m=5m=5).

Wie sieht ein Graph im Computer aus?

Wenn wir nun in einer Aufgabe der SOI einem solchen Graphen begegnen, so ist dieser meist nicht als Bild gegeben, sondern als solch eine abstrakte Auflistung der Knoten und Kanten. Die Knoten sind dann meist einfach von 11 bis nn nummeriert und so enthält die Eingabe nur eine Zeile mit nn und mm und dann mm Zeilen mit den Punktepaaren der mm Kanten. Etwa so (für das Beispiel in Bild 1):

6 5
1 3
2 3
2 4
3 4
5 6

Und was machen wir jetzt damit? Wie repräsentieren wir diesen Graphen nun in unserem Programm, sodass wir nützliche Dinge damit anstellen können? Wir könnten einfach diese Kantenliste so einlesen und abspeichern. In C++ sähe das vielleicht etwa so aus:

int n = 6;
int m = 5;
vector<pair<int,int>> E = {{1,3}, {2,3}, {2,4}, {3,4}, {5,6}};

Eine solche Kantenliste ist manchmal gut genug und kann alles was wir brauchen. Häufig aber wollen wir auf den Nachbarschaften von Knoten operieren, d.h. wir wollen alle Nachbarn eines Knotens xx abfragen, was mit einer Kantenliste nur möglich ist, indem wir alle Kanten durchgehen und schauen ob xx irgendwo vorkommt.

SOI-typische Graphenaufgaben haben oft bis zu 100000100\,000 Kanten, und da kann eine solche lineare Suche durch die Kantenliste schon mal etwas länger dauern. Deshalb ist die nützlichste Speicherart für Graphen eine andere, nämlich die sogenannte Adjazenzliste. Die Idee ist simpel: Statt einer grossen langen Liste mit allen Kanten merken wir uns für jeden Knoten eine separate Liste mit all seinen Nachbarn. Die Datenstruktur besteht also aus nn Listen, und wenn wir die Nachbarschaft des Knotens xx wissen wollen, schauen wir einfach die xx-te dieser Listen an.

Implementieren lässt sich das in C++ ganz leicht mittels Vektoren, den Arrays dynamischer Grösse (hat nicht viel mit den Vektoren aus der Mathe zu tun). Wir verschachteln dazu nn Vektoren in einen grossen Vektor - die inneren Vektoren sind die Nachbarschaftslisten und der äussere Vektor hält sie alle zusammen. Ein wenig müssen wir noch wegen der nullbasierten Indexierung aufpassen: entweder wir wandeln alles in nullbasierte Indexierung um (was häufig einfacher geht), oder wir fügen einfach noch einen imaginären Knoten 00 ohne Nachbarn hinzu:

int n = 6;
int m = 5;
// Erste Variante mit nullbasierte Knoten (von 0 bis n-1 nummeriert):
vector<vector<int>> E = {{2}, {2,3}, {0,2,3}, {1,2}, {5}, {4}};
// oder mit einem 0-ten Knoten ohne Nachbarn:
vector<vector<int>> E = {{}, {3}, {3,4}, {1,3,4}, {2,3}, {6}, {5}};
// Die Nachbarn von Knoten x sind dann in E[x] zu finden.

Was stellt ein Graph dar?

Ein solcher Graph kann nun für alles mögliche stehen - zum Beispiel für den Strassenplan einer Stadt. Die Knoten stehen dann für die Kreuzungen und Plätze der Stadt und die Kanten für die Strassen dazwischen. Was wir häufig wissen wollen ist zum Beispiel der kürzeste Weg zwischen zwei Knoten (Wie komme ich am schnellsten zum Bahnhof?) oder ob es überhaupt möglich ist, von jedem Ort an jeden anderen zu kommen (Gibt es eine Insel von der man nicht mehr wegkommt?).

Manchmal sind dafür noch Zusatzinformationen zu den Knoten und Kanten gegeben, zum Beispiel eine Fahrtzeit pro Kante (ein sogenanntes Kantengewicht) oder eine Richtung pro Kante (z.B. für Einbahnstrassen). In diesem Kapitel schauen wir uns aber vorerst nur mal ungewichtete, ungerichtete Graphen an.

Standardalgorithmus

Was ist nun diese ominöse DFS?

Nun wollen wir uns an den ersten Algorithmus für Graphen heranwagen. Es ist die sogenannte Tiefensuche, oft abgekürzt mit DFS, vom Englischen Depth First Search. Sie ist eine von zwei sogenannten Graphentraversierungsalgorithmen, die in den Rucksack eines jeden Informatik-Olympioniken gehören. Den anderen, die Breitensuche (BFS), schauen wir gleich nachher an. Bei beiden geht es darum, den Graphen systematisch zu erkunden und zu entdecken oder eben zu traversieren.

Stell dir vor du steckst mitten in einem Labyrinth. Das Labyrinth beschreiben wir als Graphen mit den Räumen als Knoten und den Gängen zwischen den Räumen als Kanten. Wir stecken nun völlig verloren im Raum/Knoten Nr. 11 und suchen den Ausgang (sei dies Knoten nn). Alle Räume sehen etwa gleich aus und wir haben keinen Lageplan, kein GPS, kein Wifi und auch sonst kaum Hilfsmittel. Alles was wir haben ist ein langer roter Faden und ein grosser Topf mit roter Farbe.

Wie finden wir nun den Ausgang aus dem Labyrinth? Unsere Strategie ist die folgende: Wir fixieren den Faden, den wir nachher während unserem Erkundungsgang abrollen werden, in unserem Startraum, sodass wir den Weg zurück zu diesem Startraum stets wieder finden können. Ausserdem malen wir einen roten Punkt auf den Boden, um zu markieren, dass wir den Startraum schon besucht haben. Wir starten in eine beliebige Richtung und machen in jedem neuen Raum folgendes: Wir malen einen roten Punkt auf den Boden, damit wir wissen, dass wir hier schon waren und klappern dann der Reihe nach von links nach rechts alle ausgehenden Gänge ab. Das heisst wir gehen zuerst dem linkesten Gang entlang und kommen so wieder in einen neuen Raum. Dort bringen wir eine Markierung an und gehen wieder dem linkesten Gang nach weiter. Irgendwann kommen wir so in eine Sackgasse oder in einen Raum in dem wir schon einmal waren (der also schon eine rote Markierung auf dem Boden hat). In einem solchen Fall kehren wir einfach um und gehen zurück zum Raum aus dem wir gekommen sind (der rote Faden sagt uns wo das war). Von dort probieren wir es mit dem nächsten Gang, den es noch zu erkunden gilt (den nächsten von links) und wiederholen das gleiche Verfahren. So probieren wir systematisch Gang für Gang durch. Haben wir auch den letzten, rechtesten Gang erkundet, so beenden wir die Suche in diesem Raum und gehen einen Gang zurück in Richtung Startraum (indem wir dem roten Faden folgen). Auf diese Weise finden wir früher oder später den Ausgang oder wissen, dass er vom Start aus unerreichbar ist.

Algorithmus: Tiefensuche

Genau so funktioniert nun auch die Tiefensuche. Den Farbtopf simulieren wir mit einem booleschen Array, also einem Bit pro Raum, mit dem wir uns merken, ob wir einen bestimmten Raum schon besucht haben oder nicht. Den Faden repräsentieren wir nur implizit, nämlich mit dem rekursiven Aufruf-Stack unserer DFS-Funktion. Das heisst in jedem Aufruf der DFS-Funktion besuchen wir einen neuen Knoten und rufen die Funktion rekursiv für alle von dort benachbarten, noch nicht besuchten Knoten auf. In C++ Code sieht das dann etwa so aus:

// Wir nehmen an, dass E eine nullbasierte Adjazenzliste darstellt.
vector<vector<int>> E;
vector<int> visited;

void dfs(int v) {
        // Wir sind in Knoten v und erkunden die Nachbarschaft.
        for(int e = 0; e < E[v].size(); e++) {
                int w = E[v][e];
                // Nun prüfen wir ob der Nachbar w noch unbesucht ist.
                if(!visited[w]) {
                        visited[w] = true;
                        dfs(w);
                }
        }
}

int main() {
        // Wir beginnen damit E einzulesen, z.B. so:
        int n, m;
        cin >> n >> m;
        E = vector<vector<int>>(n);
        for(int i = 0; i < m; i++) {
                int a, b;
                cin >> a >> b;
                E[a].push_back(b);
                E[b].push_back(a);
        }
        // Nun können wir unsere Tiefensuche starten
        int start = 0;
        visited = vector<int>(n, false); // Zu Beginn haben wir noch nichts besucht.
        visited[start] = true;
        dfs(start);
        // Ob der Ausgang erreicht werden kann, können wir nun ganz leicht ablesen.
        cout << "Kann der Ausgang erreicht werden?\n";
        if(visited[n-1]) {
                cout << "Ja!\n";
        } else {
                cout << "Nein!\n";
        }
}

Und wozu ist das gut?

Eine solche Tiefensuche kann uns also beantworten, ob zwei Knoten direkt oder indirekt verbunden sind oder nicht. Die Menge aller Knoten, die gegenseitig miteinander verbunden sind, nennt man auch Zusammenhangskomponente. Der Graph in Bild 1 besteht aus zwei solchen Zusammenhangskomponenten. Die Knoten 11 bis 44 bilden die eine, die Knoten 55 und 66 die andere Komponente. Um alle Zusammenhangskomponenten mittels Tiefensuche zu bestimmen, gehen wir einmal durch alle Knoten und starten bei jedem noch unbesuchten Knoten eine Tiefensuche. Jedesmal wenn wir eine neue Tiefensuche starten, entdecken wir eine neue Komponente.

Eine weitere nützliche Anwendung ist das Zweifärben von Graphen. Wir möchten dabei jeden Knoten eines Graphen entweder rot oder blau einfärben, sodass keine zwei benachbarten Knoten dieselbe Farbe bekommen. Ist das immer möglich? Nein. In einem Dreieck geht das beispielsweise nicht. Wenn du dir das ein wenig genauer überlegst, siehst du, dass eine gültige Zweifärbung genau dann möglich ist, wenn der Graph keinen Zyklus ungerader Länge enthält, es also keinen Weg gibt, der nach einer ungeraden Anzahl Schritte wieder bei seinem Startpunkt angelangt.

Der Graph in Bild 1 ist nicht zweifärbbar, da das Dreieck 2342-3-4 eine Zweifärbung verunmöglicht. Bild 2 zeigt dir einen zweifärbbaren Graphen.

2H DFS bicoloring graph example

Bild 2: Ein Beispiel eines zweifärbbaren Graphen, der aus zwei Zusammenhangskomponenten besteht.

Eine Art eine solche Färbung zu finden (oder herauszufinden, dass es gar keine solche gibt) ist mittels Tiefensuche. Wenn wir den Startknoten rot markieren, dann müssen alle seine Nachbarn blau sein und alle deren Nachbarn wieder rot und so weiter. Sobald wir also die Farbe des Startknotens wählen, ist die Färbung für die gesamte Zusammenhangskomponente fixiert. Die Tiefensuche erlaubt uns nun diese Färbung zu simulieren und gleichzeitig zu überprüfen, ob es irgendwo zu einem Konflikt kommt, also zu zwei gleichgefärbten, benachbarten Knoten. In der Implementierung ersetzen wir dazu einfach “visited” durch “color”, wobei wir 0 für ungefärbt, 1 für rot und 2 für blau stehen lassen. Innerhalb der DFS-Schleife prüfen wir dann:

bool dfs(int v) {
        // Wir sind in Knoten v und erkunden die Nachbarschaft.
        for(int e = 0; e < E[v].size(); e++) {
                int w = E[v][e];
                // Nun prüfen wir ob der Nachbar w noch unbesucht ist.
                if(color[w]==0) {
                        // Setze w auf die andere Farbe als v.
                        color[w] = 3-color[v];
                        // Rekursiere und brich ab, sobald ein Fehler gefunden wurde:
                        if(!dfs(w)) {
                                return false;
                        }
                } else {
                        // Prüfe, dass v und w unterschiedliche Farbe haben.
                        if(color[v] == color[w]) {
                                // Der Graph ist in diesem Fall nicht zweifärbbar, was wir beispielsweise mit dem Rückgabewert mitteilen können.
                                return false;
                        }
                }
        }
        return true;
}

Aufgabe

Gegeben ein ungerichteter, ungewichteter Graph, entscheide ob es möglich ist, seine Knoten mit zwei Farben zu färben, sodass keine zwei benachbarten Knoten die selbe Farbe erhalten.

Eingabe

Auf der ersten Zeile steht die Zahl TT, die Anzahl Testfälle. Es folgen TT Graphenbeschreibungen mit jeweils dem folgenden Format: Auf der ersten Zeile steht nn und mm, die Anzahl Knoten und Kanten. Anschliessend folgen mm Zeilen, welche die mm Kanten mittels je zweier nullbasierter Indices beschreiben. Eine Zeile mit aa und bb bedeutet, dass der Knoten aa mit Knoten bb verbunden ist (und umgekehrt). Beachte, dass die Knoten nullbasiert indexiert sind. Sie sind also von 00 bis n1n-1 nummeriert.

Ausgabe

Gib für den tt-ten Testfall “Case #t:” aus, gefolgt von “YES” oder “NO”, je nachdem ob der tt-te Graph zweifärbbar ist oder nicht.

Limits

  • T=100T=100
  • N1000N \le 1\,000
  • M10000M \le 10\,000

Beispiele

Input:

1
6 5
0 2
1 2
1 3
2 3
4 5

Output:

Case #1: NO

Comment:

Das ist der Graph aus Bild 1. Das Dreieck 12311-2-3-1 verunmöglicht eine Zweifärbung.

Input:

1
7 6
0 1
2 1
5 3
4 3
4 6
5 6

Output:

Case #1: YES

Comment:

Bild 3 zeigt dir diesen Graph und eine mögliche, gültige Färbung mit zwei Farben.
DFS bicoloring second example

Bild 3: Der zweifärbbare Graph des zweiten Beispiels.

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

Download input again
You have 5 minutes and 0 seconds left.

If the time expires, or you don’t get full points, you can try again by downloading a fresh input.

You can directly run C++ solutions in your browser. For other languages, you need to download the input and manually run your solution. Please note that running in the browser is slower than running natively.

Do not navigate away while your solution is running.


            

        

Anmerkung: Eine Anwendung dieses Zweifärbeproblems war die erste Hälfte der Aufgabe “River” der ersten Runde der SOI 2015. Du kannst die Aufgabe hier nachlesen und du findest hier die Lösungsbeschreibung.

Don’t hesitate to ask us any question about this task, programming or the website via email (info@soi.ch).

Breitensuche

Der Unterschied zwischen der Tiefensuche, welche wir im vorhergehenden Tutorial kennengelernt haben, und der Breitensuche, die wir jetzt anschauen werden, ist ein kleiner aber feiner. Abgekürzt wir die Breitensuche oft einfach mit BFS (für das Englische breadth first search).

Problembeschreibung

Wie wir gesehen haben, erlaubt uns die Tiefensuche die Zusammenhangskomponenten eines Graphen zu bestimmen oder ihn mit zwei Farben zu färben. Was wir aber bisher noch nicht können, ist das Finden von kürzesten Wegen zwischen zwei Knoten. Die Breitensuche wird uns dies ermöglichen.

Standardalgorithmus

Breitensuche - Woher kommt der Name?

In der Tiefensuche stürzten wir uns Hals über Kopf in die Tiefe des Graphen. Wir schlugen einfach mal eine willkürliche Richtung ein und gingen so lange weiter bis wir umkehren mussten, weil wir nichts Neues mehr entdecken konnten. Erst dann schauten wir uns nach möglichen alternativen Abzweigungen um.

Die Breitensuche geht nun - wie der Name suggeriert - zuerst in die Breite statt in die Tiefe. Wir wollen zuerst alles erkunden, was unmittelbar zum Startpunkt benachbart ist. Erst danach schauen wir uns Knoten mit Distanz 22 an, also die Nachbarn der Nachbarn. Und erst wenn wir alle diese Nachbarn zweiten Grades besucht haben, dann erst beginnen wir mit den Nachbarn der Nachbarn der Nachbarn. Und so weiter.

Algorithmus: Breitensuche

Diese Idee lässt sich am einfachsten mit Hilfe einer Warteschlange (Englisch queue) implementieren. Darin merken wir uns alle Knoten, die wir entdeckt haben, deren Nachbarn wir uns aber noch anschauen wollen.

Bei der Tiefensuche erfolgten diese zwei Schritte jeweils unmittelbar hintereinander, also sobald wir einen Knoten entdeckt haben, haben wir auch gleich damit begonnen seine Nachbarn anzuschauen. Das hat uns erlaubt, die Tiefensuche mittels Rekursion zu implementieren. Nun wollen wir aber für die Breitensuche, dass wir zuerst alle Nachbarn ersten Grades anschauen, bevor wir den ersten Nachbarn zweiten Grades anschauen. Die Warteschlange simuliert nun dieses “Hinten-Anstellen-und-Warten” der neu entdeckten Knoten. In C++ kann das dann etwa so aussehen:

// Wir nehmen wieder an, dass E eine nullbasierte Adjazenzliste darstellt.
vector<vector<int>> E;
vector<int> visited;

void bfs(int start) {
        queue<int> Q; // Die Warteschlange für die neu entdeckten Knoten.
        Q.insert(start);
        while(!Q.empty()) {
                int v = Q.front();
                Q.pop();
                // Wir sind in Knoten v und erkunden die Nachbarschaft.
                for(int e = 0; e < E[v].size(); e++) {
                        int w = E[v][e];
                        // Nun prüfen wir, ob der Nachbar w noch unbesucht ist.
                        if(!visited[w]) {
                                visited[w] = true;
                                // Anstelle des rekursiven Aufruf der DFS,
                                // fügen wir w nun lediglich in die Schlange ein.
                                Q.insert(w);
                        }
                }
        }
}

int main() {
        // Graph einlesen, wie zuvor.
        ...
        // Nun können wir die Breitensuche starten
        int start = 0;
        visited = vector<int>(n, false); // Zu Beginn haben wir noch nichts besucht.
        visited[start] = true;
        bfs(start);
        // In visited[] können wir nun wiederum ablesen, ob
        // ein bestimmter Knoten erreicht werden kann.
}

Bild 1 zeigt dir an einem Beispiel wie sich die Besuchsreihenfolge der Knoten in einer Breitensuche und einer Tiefensuche unterscheiden können.

2H BFS example

Bild 1: Die Breitensuche (links) und Tiefensuche (rechts) auf dem selben Graphen. Die Zahlen geben die Entdeckungsreihenfolge der Knoten an und die Pfeile bezeichnen die Kanten entlang welcher die Knoten entdeckt wurden.

Kürzeste Wege

Für ungerichtete, ungewichtete Graphen erlaubt uns die Breitensuche die Länge des kürzesten Weges zwischen dem Startpunkt und jedem beliebigen anderen Knoten zu bestimmen. Die Länge eines Pfades messen wir in der Anzahl Kanten, denen wir entlanggehen. Ungewichtet heisst hier also, dass jede Kante als gleich lang gezählt wird. Falls die Kanten unterschiedliche Länge haben, genügt die Breitensuche nicht mehr, um den kürzesten Weg zu berechnen. Der Algorithmus von Dijkstra, welcher dir in einer anderen Aufgabe erklärt wird, löst aber genau dieses Problem. Aber wie berechnen wir nun die ungewichtete Länge des kürzesten Weges von aa nach bb mit Hilfe der Breitensuche?

Die Erkundungsreihenfolge der BFS hat die schöne Eigenschaft, dass wir die Knoten in aufsteigender Distanz zum Startknoten besuchen. Das heisst, alle Knoten mit Distanz 55 besuchen wir unmittelbar nach den Knoten mit Distanz 44 und umittelbar vor den Knoten mit Distanz 66. Wenn immer wir also einen neuen Knoten entdecken, können wir dessen Distanz zum Start direkt bestimmen, nämlich als die Distanz zum aktuellen Knoten plus 11.

In der Implementierung von oben können wir dies einbauen, indem wir zum Beispiel einen Vektor dist hinzufügen, den wir für jeden Knoten mit unendlich initialisieren (oder einfach einer fixen, sehr grossen Zahl) und dann dist[start] auf Null setzen. Die Distanz der neu entdeckten Knoten setzen wir dann hier mit einer einzigen neuen Zeile:

...
if(!visited[w]) {
        visited[w] = true;
        // Anstelle des rekursiven Aufruf der DFS,
        // fügen wir w nun lediglich in die Schlange ein.
        Q.insert(w);
        dist[w] = dist[v] + 1; // Neue Zeile!
}
...

Bild 2 zeigt nochmals denselben Graphen aber jetzt mit den Distanzangaben zwischen den Knoten und dem Start.

2H BFS example

Bild 2: Die Distanzen nach einer Breitensuche, die beim obersten Knoten begonnen hat.

Aufgabe

Du sollst nun diese Breitensuche implementieren, um die Distanz zwischen dem ersten und letzten Knoten eines Graphens zu bestimmen.

Eingabe

Auf der ersten Zeile steht die Zahl TT, die Anzahl Testfälle. Es folgen TT Graphenbeschreibungen mit jeweils dem folgenden Format: Auf der ersten Zeile steht nn und mm, die Anzahl Knoten und Kanten. Anschliessend folgen mm Zeilen, welche die mm Kanten mittels je zweier nullbasierter Indices beschreiben. Eine Zeile mit aa und bb bedeutet, dass der Knoten aa mit Knoten bb verbunden ist (und umgekehrt). Beachte, dass die Knoten nullbasiert indexiert sind. Sie sind also von 00 bis n1n-1 nummeriert.

Ausgabe

Gib für den tt-ten Testfall “Case #t:” aus, gefolgt von einer Zahl, die Länge des kürzesten Weges von Knoten 00 zu Knoten n1n-1 im tt-ten Graphen. Die Eingaben sind so gewählt, dass es immer ein Weg zwischen diesen beiden Knoten gibt.

Limits

  • T=100T=100
  • N1000N \le 1\,000
  • M10000M \le 10\,000

Beispiel

Input:

2
7 8
0 1
2 0
0 3
1 4
2 4
5 3
4 6
6 5
7 7
0 1
2 1
2 0
4 0
4 3
5 3
5 6

Output:

Case #1: 3
Case #2: 4

Comment:

Bild 3 zeigt dir diesen Graphen. Es ist der selbe Graph wie auf den Bildern 1 und 2.
2H BFS example

Bild 3: Illustration des ersten Beispiels.

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

Download input again
You have 5 minutes and 0 seconds left.

If the time expires, or you don’t get full points, you can try again by downloading a fresh input.

You can directly run C++ solutions in your browser. For other languages, you need to download the input and manually run your solution. Please note that running in the browser is slower than running natively.

Do not navigate away while your solution is running.


            

        

Zusatzaufgabe: Überlege dir, wie du nicht nur die Länge des Weges sondern auch einen kürzesten Weg (als Abfolge von Knoten) ausgeben kannst.

Don’t hesitate to ask us any question about this task, programming or the website via email (info@soi.ch).

Dijkstra

Mit Breitensuche lassen sich kürzeste Wege in Graphen finden, solange alle Kanten gleich lang sind. Häufig ist das jedoch nicht der Fall: Es kann zum Beispiel unterschiedlich lange dauern, von AA nach BB zu gelangen, wie von CC nach DD zu gelangen, obwohl es direkte Kanten von AA nach BB, sowie von CC nach DD gibt. In solchen Fällen geben wir jeder Kante zusätzlich ein Gewicht, welches diese zusätzliche Information beinhaltet.

In dieser Aufgabe geht es um Dijkstras Algorithmus zur Bestimmung von kürzesten Wegen in gerichteten Graphen mit nichtnegativen Kantengewichten.

Problembeschreibung

Gegeben ist ein gerichteter gewichteter Graph G=(V,E)G=(V,E), das heisst einige Knoten vVv\in V, welche durch Pfeile/Kanten eEe\in E verbunden sind, wobei jeder Kante eine Zahl zugeordnet wird, ihr Kantengewicht. Wir stellen Kanten als Tupel e=(u,v,w)e=(u,v,w) dar, wobei uu und vv die Anfangs- und Endknoten der Kante sind und ww das Kantengewicht ist. Ein Weg von ss nach tt ist eine Reihe von Kanten (s,k2,w1),(k2,k3,w2),(k3,k4,w3),,(kn2,kn1,wn2),(kn1,t,wn1)(s,k_{2},w_{1}),(k_{2},k_{3},w_{2}),(k_{3},k_{4},w_{3}),{\dots},(k_{n-2},k_{n-1},w_{n-2}),(k_{n-1},t,w_{n-1}). Das heisst, wenn man bei ss beginnt und dann der Reihe nach den Kanten folgt, erreicht man Knoten tt. Die Länge des Weges ist durch die Summe aller Kantengewichte gegeben: w1+w2++wn1w_{1}+w_{2}+\cdots+w_{n-1}. Ein kürzester Weg von ss nach tt ist ein Weg von ss nach tt dessen Länge kleinstmöglich ist.

Wir wollen nun die Länge des kürzesten Weges zwischen zwei gegebenen Knoten bestimmen. Dies wird deine Aufgabe sein. Dijkstras Algorithmus kann verwendet werden, um dieses Problem effizient zu lösen, gegeben dass alle Kantengewichte mindestens 00 sind.

(Dijkstras Algorithmus löst eigentlich sogar ein noch allgemeineres Problem: Er findet für einen gegebenen Startpunkt uu kürzeste Wege zu allen anderen Knoten. Er kann natürlich auch verwendet werden um für einen gegebenen Endpunkt vv kürzeste Wege von allen anderen Knoten her zu finden.)

Dijkstras Algorithmus

Sei SP(s,t)\text{SP}(s,t) die Länge des kürzesten Weges zwischen ss und tt. Eine Eigenschaft von kürzesten Wegen ist, dass

SP(s,t)=0,\text{SP}(s,t) = 0,

SP(s,t)=min(t,t,w)E SP(s,t)+w\text{SP}(s,t) = \min_{(t',t,w)\in E} \text{ SP}(s,t') + w für sts\neq t

Hier machen wir einfach eine Fallunterscheidung über die letzte Kante auf dem kürzesten Pfad von ss nach tt. Falls eine gegebene Kante (t,t,w)(t',t,w) die letzte Kante auf dem kürzesten Weg von ss nach tt ist, dann ist SP(s,t)\text{SP}(s,t) einfach SP(s,t)+w\text{SP}(s,t') + w. SP(s,t)\text{SP}(s,t) ist dann die kleinste dieser Möglichkeiten.

Wir definieren SP(s,t)=\text{SP}(s,t) = \infty falls es gar keinen Weg von ss nach tt gibt.

Für Graphen, die keine Wege von einem Knoten zu sich selbst haben, definieren die obigen Gleichungen bereits einen funktionierenden Algorithmus für die Berechnung von kürzesten Wegen, weil es keine zyklischen Abhängigkeiten zwischen Werten von SP\text{SP} gibt.

Im Allgemeinen gibt es aber solche zyklische Abhängigkeiten.

Dijkstras Algorithmus löst dieses Problem, in dem er für ein gegebenes ss für alle tt die Werte von SP(s,t)\text{SP}(s,t) in aufsteigender Reihenfolge berechnet. Es kann dabei dann natürlich vorkommen, dass nicht für jedes mögliche tt' (in der zweiten Gleichung oben) der Wert SP(s,t)\text{SP}(s,t') bereits bekannt ist. Allerdings spielen diese Werte SP(s,t)\text{SP}(s,t') dann natürlich keine Rolle, weil sie wegen der geschickt gewählten Reihenfolge mindestens so gross sind wie SP(s,t)\text{SP}(s,t). Hier verwenden wir die Annahme, dass alle ww mindestens 00 sind.

Während jedem Zeitpunkt in der Ausführung von Dijkstras Algoritmus gibt es also einige Knoten tt für die wir SP(s,t)\text{SP}(s,t) bereits kennen, die bekannten Knoten und einige Knoten, für die dieser Wert noch nicht bekannt ist, die unbekannten Knoten. Ausserdem wissen wir, dass alle unbekannten Werte mindestens so gross sind wie jeder bekannte Wert.

Für jeden unbekannten Wert SP(s,t)\text{SP}(s,t) gibt es dann drei Möglichkeiten:

  1. SP(s,t)=SP(s,t)+w\text{SP}(s,t)=\text{SP}(s,t') + w für (t,t,w)E(t',t,w)\in E und SP(s,t)\text{SP}(s,t') ist bekannt.
  2. SP(s,t)=SP(s,t)+w\text{SP}(s,t)=\text{SP}(s,t') + w für (t,t,w)E(t',t,w)\in E und SP(s,t)\text{SP}(s,t') ist unbekannt.
  3. SP(s,t)=\text{SP}(s,t)=\infty. (Falls tt von ss aus gar nicht erreichbar ist.)

(Merke, dass Möglichkeiten 1. und 2. sich nicht gegenseitig ausschliessen. Wieso?)

Dijkstras Algorithmus berechnet für alle (t,t,w)E(t',t,w)\in E mit bekanntem SP(s,t)\text{SP}(s,t') und unbekanntem SP(s,t)\text{SP}(s,t) den Wert SP(s,t)+w\text{SP}(s,t') + w als möglichen Kandidaten für den Wert von SP(s,t)\text{SP}(s,t).

Die zentrale Beobachtung ist, dass der kleinste Kandidatenwert über alle solchen (t,t,w)(t',t,w) tatsächlich der korrekte Wert für das entsprechende SP(s,t)\text{SP}(s,t) ist.

(Das sollte intuitiv klar sein. Falls nicht, hier ein Beweis:

Es reicht zu zeigen, dass falls es erreichbare unbekannte Knoten gibt, es für mindestens einen unbekannten Knoten tt mit minimalem SP(s,t)\text{SP}(s,t) gelten muss, dass ein kürzester Weg zu ihm von einem bekannten Knoten aus über eine einzige Kante geht.

Beweis: Nimm an, dass die Behauptung nicht stimmt. Für jeden unbekannten Knoten hat mindestens ein kürzester Weg von ss zu ihm genau eine Kante zwischen bekannten und unbekannten Knoten. Schaue einen unbekannten Knoten tt mit minimalem SP(s,t)\text{SP}(s,t) an für den einer der solchen kürzesten Wege pp die kleinste Anzahl Kanten zwischen unbekannten Knoten hat. Nach Annahme gibt es auf dem Weg mindestens eine solche Kante. Sei tt' der zweitletzte Knoten auf dem gewählten Weg. Dann ist SP(s,t)SP(s,t)\text{SP}(s,t')\leq \text{SP}(s,t) und ein kürzester Weg von ss nach tt' hat weniger Kanten zwischen Knoten mit unbekannten Werten als pp, ein Widerspruch.)

Dijkstras Algorithmus funktioniert wie folgt:

  • Führe einen Kandidatenwert 00 für Knoten ss ein.
  • Solange es noch Kandidatenwerte gibt:
    • Setze SP(s,t)=c\text{SP}(s,t')=c für den kleinsten Kandidatenwert cc, so dass tt' der zugehörige Knoten ist, sowie SP(s,t)\text{SP}(s,t') noch nicht bekannt ist.
    • Immer dann wenn ein neuer Wert SP(s,t)\text{SP}(s,t') bekannt wird, berechne Kandidatenwerte SP(s,t)+w\text{SP}(s,t') + w für alle tt mit (t,t,w)E(t',t,w)\in E.

Es folgt eine Implementierung in C++11:

#include <queue>
using namespace std;

#define OG(T) bool operator>(const T& o)const
struct E{ int t,w; OG(E){ return w>o.w; } };
using VE=vector<E>;
struct V{ VE in; bool v; };
using VV=vector<V>;
using HE=priority_queue<E,VE,greater<E>>;

int dijkstra(VV& g,int s,int t){
    HE q; q.push({s,0});
    while(!q.empty()){
        E c=q.top(); q.pop();
        if(g[c.t].v) continue;
        g[c.t].v=1;
        if(c.t==t) return c.w;
        for(auto&e:g[c.t].in)
            q.push({e.t,c.w+e.w});
    }
    return -1;
}

Der Graph wird dargestellt als ein vector<V>, wobei eine Instanz von VV einen einzelnen Knoten beschreibt: in ist ein vector<E> mit allen ausgehenden Kanten. v ist ein bool, welcher speichert, ob der Knoten bereits bekannt ist oder nicht. Eine Instanz von E beschreibt den Zielknoten t sowie das Kantengewicht w.

Wir verwenden eine priority_queue um die Menge der Kandidatenwerte zu verwalten. (Merke, dass die eingebaute priority_queue dummerweise standardmässig den grössten Wert zurückgibt anstatt den kleinsten.)

  • q.push({s,0}) startet die Berechnung indem der Kandidatenwert 0 für Knoten s eingeführt wird.
  • if(g[c.t].v) continue; verhindert, dass bereits bekannte Werte überschrieben werden. (Das ist notwendig. Wieso?)
  • if(c.t==t) return c.w; gibt das Resultat aus, falls der Zielknoten gefunden wurde. An dieser Stelle könnte man z.B. auch die Werte von SP\text{SP} speichern.
  • for(auto&e:g[c.t].in) geht über alle Kanten, die vom aktuellen Knoten weggehen.
  • q.push({e.t,c.w+e.w}); führt neue Kandidatenwerte ein.
  • In return -1; steht -1 für \infty, also dafür, dass es keinen Weg von s nach t gibt.

Die Laufzeit dieser Version von Dijkstras Algorithmus ist O(MlogN)O(M \log N), wobei NN die Anzahl Knoten und MM die Anzahl Kanten ist.

Aufgabe

Gegeben mehrere gerichtete Graphen mit nicht-negativen Kantengewichten, finde jeweils die Länge des kürzesten Weges vom ersten zum zweiten Knoten.

Eingabe

Auf der ersten Zeile steht die Zahl TT, die Anzahl Testfälle. Es folgen TT Zeilen mit jeweils den ganzen Zahlen NN, MM, sowie MM Trippeln von ganzen Zahlen uu vv ww (1u,vN,0w10001\le u,v\le N,0\le w\le 1000), welche Kanten von uu nach vv mit Gewicht ww beschreiben. Die Knoten sind von 11 bis NN durchnummeriert.

Die Zahlen sind durch jeweils ein oder zwei Leerzeichen getrennt (siehe Beispiel).

Ausgabe

Gib für den tt-ten Testfall “Case #t:” aus, gefolgt von der Länge des kürzesten Weges von Knoten 11 zu Knoten 22. Falls es von Knoten 11 zu Knoten 22 keinen Weg gibt, gib “Infinity” aus.

Limits

  • T=100T=100
  • 2N10002\le N\le 1\,000
  • 0M100000\le M\le 10\,000

Beispiel

Input:

3
3 2  1 3 5  3 2 7
3 3  1 2 7  1 3 4  3 2 1
3 1  1 3 4

Output:

Case #1: 12
Case #2: 5
Case #3: Infinity

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

Download input again
You have 5 minutes and 0 seconds left.

If the time expires, or you don’t get full points, you can try again by downloading a fresh input.

You can directly run C++ solutions in your browser. For other languages, you need to download the input and manually run your solution. Please note that running in the browser is slower than running natively.

Do not navigate away while your solution is running.


            

        

Don’t hesitate to ask us any question about this task, programming or the website via email (info@soi.ch).

Binäre Suche

Problem

Gegeben sei eine sortierte Liste AA von NN Zahlen (a1a_{1}, a2a_{2}, …, aNa_N). Wir wollen nun herausfinden, ob eine bestimmte Zahl XX in dieser Liste vorhanden ist. Falls XX in der Liste vorhanden ist, wollen wir zusätzlich die Position bestimmen.

Die triviale Lösung, die jede Position der Liste mit XX vergleicht, hat eine Laufzeit von O(N)O(N) (Diese funktioniert jedoch auch bei unsortieren Listen, wo die binäre Suche fehlschlägt). Mit der binären Suche können wir das Problem jedoch in O(logN)O(log N) lösen.

Lösung

Der Algorithmus der binären Suche ist Greedy und funktioniert nach dem Prinzip Teile und Herrsche.

Die folgenden Schritte wiederholen wir, bis die gesuchte Zahl XX gefunden wurde oder die Liste leer ist:

  1. Wir vergleichen die Zahl B=aiB = a_i (mit i=N2i = \lfloor{\frac{N}{2}}\rfloor, wobei \lfloor \cdot \rfloor für abrunden steht) in der Mitte der Liste mit XX, dabei können folgende Fälle auftreten:
    • B=XB = X: Die Zahl ist gefunden. Wir können die Position berechnen und zurück geben.
    • B>XB > X: Da XX kleiner ist als BB, muss XX vor BB sein, falls es in der Liste vorkommt. Wir können uns also auf die linke Hälfte beschränken.
    • B<XB < X: Analog zum vorigen Fall können wir uns in diesem Fall auf die rechte Hälfte beschränken.
  2. Ist die neue Liste leer, kommt XX nicht in der Liste vor. Andernfalls beginnen wir mit der nun halbierten Liste wieder bei 1.

Am einfachsten schränken wir dazu die Liste durch einen oberen (OO) und unteren (UU) Index ein, die wir dann iterativ anpassen:

Seien A, N, X gegeben
Setze U = 1, O = N
Setze I = U+(O-U)/2
Solange U != O und  A[I] != X
  Falls A[I] > X
    Setze O = I-1
  Falls A[I] < X
    Setze U = I+1
  Setze I = U+(O-U)/2
Falls A[I] = X
  "X ist an Position I in A"
Sonst
  "X ist nicht in A"

Aufgabe

Gegeben eine monotone diskrete Funktion PP und ein y-Wert YY, finde den zu YY gehörigen x-Wert XX.

P(x)=Ax1/4+Bx1/3+Cx1/2+Dx+Ex2+Fx3+Gx4P(x) = A*x^{1/4} + B*x^{1/3} + C*x^{1/2} + D*x + E*x^{2}+ F*x^{3}+ G*x^{4} mit dem Definitionsbereich D={xN1xN}D = \{x \in \mathbb{N} \mid 1 \le x \le N\}

Monoton bedeutet, dass die Werte der Funktion immer steigen (d.h. wenn man nach rechts geht, werden die Werte immer grösser). Die gegebene Funktion ist in jedem Fall monoton.

Wir betrachten nur diskrete Werte von PP, das heisst die abgerundeten Funktionswerte.

Werte von Funktionen berechnen

Wollen wir den Wert einer Funktion P(x)=2x1/2+3x+2x2P(x) = 2*x^{1/2} + 3*x + 2*x^{2} an einer bestimmten Stelle, z.B. x=4x = 4 berechnen, so setzen wir einfach den Wert (44) für xx ein und rechnen aus:

P(4)=241/2+34+242=22+34+216=4+12+32=48P(4) = 2*4^{1/2} + 3*4 + 2*4^{2}= 2*2 + 3*4 + 2*16 = 4 + 12 + 32 = 48

Beachte dass x1/nx^{1/n} die nn-te Wurzel von xx ist: x1/n=xnx^{1/n} = \sqrt[n]{x}.

In Computerprogrammen geht das ausrechnen sehr einfach. Wir schreiben einfach eine Funktion, die den Wert ausrechnet, in C++ z.B. so:

double P(double x) {
    return 2*pow(x, 1.0/2) + 3*x + 2*pow(x, 2);
}

Hinweis: die Funktion pow befindet sich in math.h. Beachte auch, dass du 1.0/21.0/2 schreiben solltest und nicht 1/21/2. 1/21/2 ist 00, denn die Division rundet bei Integern ab. Da 1.01.0 ein Double ist, wird die Division mit Nachkommastellen durchgeführt.

Hinweis: die Funktion pow befindet sich in math.h.

Eingabe

Auf der ersten Zeile steht eine ganze Zahl TT, die Anzahl Testfälle. Für jeden Testfall folgt eine Zeile mit jeweils den Zahlen NN, AA, BB, CC, DD, EE, FF, GG, YY. Hierbei stehen:

  • NN (Ganzzahl) für die obere Schranke des zu betrachtenden Definitionsbereichs von PP, die untere Schranke ist immer 11,
  • AA, BB, CC, DD, EE, FF, GG (Fliesskommazahlen) für die Koeffizienten der monotonen diskreten Funktion PP,
  • YY (Ganzzahl) für den gesuchten Funktionswert.

Ausgabe

Für den tt-ten Testfall gib eine Zeile “Case #t: X”, wobei XX ein zu YY gehöriger x-Wert, oder 00, falls die Funktion PP den Wert YY im vorgegebenen Bereich nicht annimmt.

Limits

  • T=100T = 100
  • N10000000N \le 10000000
  • 0A,B,C,D,E,F,G10000 \le A, B, C, D, E, F, G \le 1000
  • YP(N)Y \le P(N)

Beispiel

Input:

2
10 0 0 0 0 1 0 0 4
10 0 0 0 0 1 0 0 6

Output:

Case #1: 2
Case #2: 0

Comment:

Die Funktion im Beispiel ist P(x)=x2P(x) = x^{2}. Im ersten Fall ist P(2)=4P(2) = 4. Aber für kein ganzzahliges x wird P(x)=6P(x) = 6.

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

Download input again
You have 5 minutes and 0 seconds left.

If the time expires, or you don’t get full points, you can try again by downloading a fresh input.

You can directly run C++ solutions in your browser. For other languages, you need to download the input and manually run your solution. Please note that running in the browser is slower than running natively.

Do not navigate away while your solution is running.


            

        

Don’t hesitate to ask us any question about this task, programming or the website via email (info@soi.ch).

Präfixsumme

Problem

Es ist ein grosses M×NM\times N Rechteck von Zahlen gegeben. Nun sollen für QQ verschiedene Teilrechtecke die Summe aller Zahlen in diesem Teilrechteck berechnet werden. Betrachten wir zunächst den eindimensionalen Fall, bei dem man nur eine Liste mit NN Zahlen hat. Der offensichtliche Ansatz wäre, für jeden gefragten Bereich die einzelnen Zahlen zu addieren, also etwas in der Art:

for range in ranges:
  sum = 0
  for i in range(range.start, range.end):
    sum += list_of_numbers[i]
  print(sum)

Dies ist jedoch für viele Anfragen zu langsam, da jede der QQ Abfragen bis zu NN Operationen benötigt, der Algorithmus also in O(NQ)O(N\cdot Q) läuft.

Lösung

Statt für jede Abfrage viel zu berechnen, erstellen wir zu Beginn eine zweite Hilfsliste, die vorberechnete Werte enthält. Diese Werte erlauben uns dann, jede der Abfragen in konstanter Zeit (O(1)O(1)) zu beantworten. Da wir die Berechnung der Hilfsliste nur einmal durchführen müssen, ist die Gesamtlaufzeit somit viel besser.

Nennen wir unsere Liste AA mit den Elementen a1a_{1}, a2a_{2}, a3a_{3}, …, aNa_N. Wenn wir nun unsere Hilfsliste - nennen wir sie BB mit den Elementen b1b_{1}, b2b_{2}, b3b_{3}, …, bNb_N - so berechnen, dass in bib_i gerade die Summe aller Zahlen der Liste AA bis und mit ii drin stehen, können wir die Summe des Bereichs von ii (inklusive) bis jj (inklusive) mit bjbi1b_j - b_{i-1} berechnen. Warum ist dies so?

Schauen wir uns z.B. den Bereich 363 - 6 an. Die Summe die wir berechnen wollen ist also a3+a4+a5+a6a_{3}+ a_{4}+ a_{5}+ a_{6}. Dann ist b6=a1+a2+a3+a4+a5+a6b_{6}= a_{1}+ a_{2}+ a_{3}+ a_{4}+ a_{5}+ a_{6} und b2=a1+a2b_{2}= a_{1}+ a_{2}. Rechnen wir nun b6b2b_{6}- b_{2}, so ergibt dies b6b2=(a1+a2+a3+a4+a5+a6)(a1+a2)=a1a1+a2a2+a3+a4+a5+a6=a3+a4+a5+a6b_{6}- b_{2}= (a_{1}+ a_{2}+ a_{3}+ a_{4}+ a_{5}+ a_{6}) - (a_{1}+ a_{2}) = a_{1}- a_{1}+ a_{2}- a_{2}+ a_{3}+ a_{4}+ a_{5}+ a_{6}= a_{3}+ a_{4}+ a_{5}+ a_{6}. Dies ist genau die Summe, die wir suchen. Wir können also durch die Subtraktion die zu viel hinzuaddierten Elemente wieder “entfernen”.

Liste A Liste B 5 1 2 4 9 7 5 3 4 8 6 5 6 8 12 21 28 33 36 40 48 54 = - 28 36 8

Implementieren kann man das z.B. folgendermassen:

# vorberechnen
b = [a[0]]
for i in a[1:]:
  b.append(b[-1] + i)

# Abfragen
for range in ranges:
  if range.start == 0:
    print(b[range.end])
  else:
    print(b[range.end] - b[range.start-1])

Das Vorberechnen können wir in O(NM)O(N\cdot M) durchführen und alle Abfragen in O(Q)O(Q) (da jede Abfrage in konstanter Zeit beantwortet werden kann). Somit verbessert sich unsere Lösung von O(NMQ)O(N\cdot M\cdot Q) auf O(NM+Q)O(N\cdot M+Q).

Diese Idee kann nun einfach auf den zweidimensionalen Fall erweitert werden.

Ist nun AA das gegebene Rechteck mit Zahlen, so füllen wir das vorberechnete Rechteck BB jeweils mit der Summe des Teilrechtecks von der oberen linken Ecke bis zum aktuellen Feld. Dies kann man auf verschiedene Arten effizient berechnen. Eine Möglichkeit ist, das Rechteck von oben links durchzugehen und jeweils by,x=by1,x+by,x1by1,x1b_{y,x} = b_{y-1,x} + b_{y,x-1} - b_{y-1,x-1} zu setzen. Die Subtraktion wird benötigt, da wir sonst dieses Teilrechteck doppelt zählen würden.

Nun kann die Summe des Teilrechtecks von (ix/iy)(i_x/i_y) bis (jx/jy)(j_x/j_y) ausgerechnet werden mit bjy,jxbiy1,jxbjy,ix1+biy1,ix1b_{j_y,j_x} - b_{i_y-1,j_x} - b_{j_y,i_x-1} + b_{i_y-1,i_x-1}. Wir nehmen also wieder den zu grossen Bereich, der bis (jx/jy)(j_x/j_y) geht. Anschliessend ziehen wir den linken Bereich sowie den oberen Bereich ab, den wir zu viel hinzugezählt haben. Nun haben wir den Bereich bis (ix1/iy1)(i_x-1/i_y-1) jedoch zweimal abgezogen, weshalb wir ihn wieder hinzuaddieren.

= - - +

Eingabe

Auf der ersten Zeile steht eine ganze Zahl TT, die Anzahl Testfälle. Für jeden Testfall folgen:

  • eine Zeile mit NN MM QQ, die Anzahl Spalten, Anzahl Zeilen und Anzahl Abfragen.
  • eine Zeile mit f0f_{0} afa_f cfc_f mfm_f. Dies definiert eine Folge mit fi+1=(fiaf+cf)\textvisiblespacemod\textvisiblespacemff_{i+1} = (f_i \cdot a_f + c_f) \textvisiblespace\mathrm{mod}\textvisiblespace m_f. Die Folge startet beim gegebenen f0f_{0}.
  • eine Zeile mit h0h_{0} aha_h chc_h mhm_h. Dies definiert eine Folge mit hi+1=(hiah+ch)\textvisiblespacemod\textvisiblespacemhh_{i+1} = (h_i \cdot a_h + c_h) \textvisiblespace\mathrm{mod}\textvisiblespace m_h. Die Folge startet beim gegebenen h0h_{0}.

Das M×NM\times N Rechteck ist nun gegeben durch ay,x=fyN+xa_{y,x} = f_{y\cdot N+x}.

Die QQ Abfragen sind gegeben durch rsxrs_x, rsyrs_y, rexre_x, reyre_y, gesucht ist jeweils die Summe der Zahlen im Rechteck zwischen den Eckpunkten (rsx/rsy)(rs_x/rs_y) und (rex/rey)(re_x/re_y), jeweils inklusive. Für die Abfrage qq (0q<Q0 \le q < Q) gilt rsx=min(hq4+0\textvisiblespacemod\textvisiblespaceN,hq4+1\textvisiblespacemod\textvisiblespaceN)rs_x = \mathrm{min}(h_{q\cdot 4+0} \textvisiblespace\mathrm{mod}\textvisiblespace N,h_{q\cdot 4+1} \textvisiblespace\mathrm{mod}\textvisiblespace N), rex=max(hq4+0\textvisiblespacemod\textvisiblespaceN,hq4+1\textvisiblespacemod\textvisiblespaceN)re_x = max(h_{q\cdot 4+0} \textvisiblespace\mathrm{mod}\textvisiblespace N,h_{q\cdot 4+1} \textvisiblespace\mathrm{mod}\textvisiblespace N), rsy=min(hq4+2\textvisiblespacemod\textvisiblespaceM,hq4+3\textvisiblespacemod\textvisiblespaceM)rs_y = \mathrm{min}(h_{q\cdot 4+2} \textvisiblespace\mathrm{mod}\textvisiblespace M,h_{q\cdot 4+3} \textvisiblespace\mathrm{mod}\textvisiblespace M) und rey=max(hq4+2\textvisiblespacemod\textvisiblespaceM,hq4+3\textvisiblespacemod\textvisiblespaceM)re_y = max(h_{q\cdot 4+2} \textvisiblespace\mathrm{mod}\textvisiblespace M,h_{q\cdot 4+3} \textvisiblespace\mathrm{mod}\textvisiblespace M).

Die etwas komplizierte Eingabe verwenden wir, damit du nicht riesige Mengen an Daten herunterladen musst. Du kannst folgenden Code für C++ verwenden, um die Zahlen zu generieren:

struct range{
  int startX, startY, endX, endY;

  range(int sx, int sy, int ex, int ey) : startX(sx), startY(sy), endX(ex), endY(ey){}
};

void readInput(int& N, int&M, int& Q, vector<vector<int> >& field, vector<range>& queries){
  cin >> N >> M >> Q;
  field.clear();
  field.resize(M, vector<int>(N));
  queries.clear();

  int f0, a, c, m;

  cin >> f0 >> a >> c >> m;
  for(int y = 0; y < M; y++){
    for(int x = 0; x < N; x++){
      field[y][x] = f0;
      f0 = (f0 * a + c) % m;
    }
  }

  cin >> f0 >> a >> c >> m;
  for(int q = 0; q < Q; q++){
    int r[4];
    for(int i = 0; i < 4; i++){
      r[i] = f0;
      f0 = (f0 * a + c) % m;
    }
    queries.push_back(range(min(r[0]%N, r[1]%N), min(r[2]%M, r[3]%M), max(r[0]%N, r[1]%N), max(r[2]%M, r[3]%M)));
  }
}

// in your code
int N, M, Q;
vector<vector<int> > field;
vector<range> queries;
readInput(N, M, Q, field, queries);

Ausgabe

Gib für jeden Testfall eine Zeile mit “Case #t:” aus (tt ist die Nummer des Testfalls), gefolgt von QQ leerzeichengetrennte Zahlen sis_i, die Summe der Zahlen in des Teilrechtecks ii.

Limits

  • 1N,M1031 \le N,M \le 10^{3}
  • 1Q1061 \le Q \le 10^{6}
  • 0<fi,af,cf,mf1090 < f_i, a_f, c_f, m_f \le 10^{9}
  • 0ay,x1090 \le a_{y,x} \le 10^{9}
  • 0rsxrex<N0 \le rs_x \le re_x < N
  • 0rsyrey<M0 \le rs_y \le re_y < M

Beispiele

Input:

2
7 2 7
67 56 86 101
62 34 71 71
5 3 8
31 28 65 79
2 15 48 79

Output:

Case #1: 298 216 140 290 445 86 126
Case #2: 40 493 277 275 339 372 151 129

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

Download input again
You have 5 minutes and 0 seconds left.

If the time expires, or you don’t get full points, you can try again by downloading a fresh input.

You can directly run C++ solutions in your browser. For other languages, you need to download the input and manually run your solution. Please note that running in the browser is slower than running natively.

Do not navigate away while your solution is running.


            

        

Don’t hesitate to ask us any question about this task, programming or the website via email (info@soi.ch).

Ranking

RankUsernameTotal (100)dfs (20)bfs (20)dijkstra (20)bsearch (20)prefixsum (20)
loading ...