Training RCC 2014 Aufwärmen



    Die nächste Saison der größten russischen Olympiade für Programmierer, der Russian Code Cup, begann am Samstag, den 19. April 2014. Vor neuen interessanten und nicht trivialen Aufgaben, kompromisslosem Kampf und tollen Preisen.

    Die Jury des Russian Code Cup hat eine Überraschung für alle Teilnehmer vorbereitet: Am 17. April hatte jeder die Möglichkeit, seine Stärke zu bewerten. Um 19:30 Uhr Moskauer Zeit fand unter http://codeforces.ru eine Trainingsrunde zur Olympiade statt, bei der die Entwickler von RCC eine neue Portion Aufgaben stellten.

    RCC 2014 Warmup ist ein Test, der es ermöglicht hat, sich zu versuchen und zu verstehen, worauf man sich in den Runden der Meisterschaft vorbereiten muss. Und für „erfahrene“ Teilnehmer war er eine ideale Gelegenheit, vor den ersten Kämpfen des RCC 2014 zu trainieren und sich aufzuwärmen.

    Wenn die Aufgaben des Russian Code Cup für die Teilnehmer nur in russischer Sprache angeboten werden, wurden die Aufgaben der Warmup-Runde in russischer und englischer Sprache ausgeführt, wodurch die Geografie des Veranstaltungsorts erheblich erweitert wurde. Insgesamt haben sich 3265 Teilnehmer für die Runde angemeldet.

    Die Bedingungen der Aufgaben waren sehr unterschiedlich: Es war notwendig, bei der Auswahl der Teilnehmer für das Finale des russischen Code Cup von 2214 zu helfen, die Daten des Testsystems nach dem Sturz wiederherzustellen, ein Fußballturnier unter den Teilnehmern des russischen Code Cup abzuhalten, dem listigen Jungen Gene zu helfen, ein T-Shirt zu bekommen und die interessante Aufgabe des Jungen Mischa zu lösen Reisen Sie mit dem Boot nach dem Finale des Russian Code Cup, organisieren Sie das Finale des Russian Code Cup 2214 in einer großen Anzahl von Hotels und erhalten Sie ein Passwort, um während ihrer Entwicklung auf Aufgaben zuzugreifen (letzteres war nicht erfolgreich).

    Also mal sehen, wie es am besten war, sich auf die Teilnahme an der Meisterschaft vorzubereiten.

    Problem 1. Auswahlanalyse

    : Zunächst sollte beachtet werden, dass wenn k größer oder gleich n • m ist, die Antwort 0 ist. Wir müssen nur n • m - k Personen anrufen. Es gibt drei Möglichkeiten, sie zu wählen:
    • Nehmen Sie nur Runden des ersten Typs:
    • Nehmen Sie kleine Runden des zweiten Typs zu einer durch n teilbaren Zahl:
    • Nehmen Sie nur Runden des zweiten Typs: d (n • m - k).
    Auch in diesem Problem konnte eine erschöpfende Lösung geschrieben werden - wie viele Runden des ersten Typs nehmen wir und wie viele Runden des zweiten.

    Aufgabe 2. Fehleranalyse

    :Beginnen wir ein Array a mit 105 Elementen, anfänglich gefüllt mit -1, und in der Zelle mit der Nummer k speichern wir die maximale Anzahl des Pakets des k-ten Teilnehmers, das jetzt da ist. Wir werden die Pakete nacheinander bearbeiten. Lassen Sie das Paket xk bearbeiten. Wenn a [k] <x - 1 ist, ist es offensichtlich, dass die Antwort NEIN ist, andernfalls aktualisieren wir das Array - a [k] = max (a [k], x).

    Aufgabe 3. Fußballanalyse

    : Stellen Sie sich ein Turnier als Grafik vor. Von jedem Eckpunkt gibt es genau k ausgehende Kanten. Dann alle nk Kanten. Der vollständige Graph hat ein Maximum an Kanten. Wenn also n <2k + 1 ist, ist die Antwort -1. Andernfalls verbinden Sie den i-ten Eckpunkt mit i + 1, ..., i + k und schleifen Sie ihn gegebenenfalls.

    Aufgabe 4. Heikle

    Genanalyse:Sortieren wir unsere Freunde in aufsteigender Reihenfolge der erforderlichen Monitore. Wir werden die Dynamik der Masken berücksichtigen - was ist der Mindestbetrag, den Sie bezahlen müssen, um solche und solche Probleme zu lösen, wenn wir die ersten Freunde haben. Dann muss die Antwort mit der Antwort für die ersten i-Freunde plus der Anzahl der Monitore verglichen werden, die der i-te Freund benötigt. Es ist nicht schwer zu bemerken, dass Sie die Dynamik als Rucksack neu berechnen können, wenn Sie Freunde nacheinander mitnehmen. Die Laufzeit dieses Algorithmus ist O (nlog (n) + n2m).

    Aufgabe 5. Eine quadratische Tabelle

    Analyse: Lassen Sie uns alle n wir eine Reihe von Länge konstruieren n, die die Summe der Quadrate der Zahlen darauf ist ein Quadrat ist :
    • Wenn n = 1, dann nehmen Sie [1].
    • Wenn n = 2 ist, nehmen wir [3, 4].
    • Wenn n gerade ist, nehmen wir .
    • Wenn n ungerade ist, nehmen Sie.
    Wir bekommen 2 Zahlen n und m. Es sei ein Array a entsprechend der Zahl n und b entsprechend der Zahl m.
    Dann konstruieren wir das letzte Array c wie folgt: cij = ai • bj.

    Aufgabe: 6. Große Probleme der Organisatoren

    Analyse: Für dieses Problem gibt es zwei Lösungen.
    Der erste. Für einen Scheitelpunkt anhalten. Berechnen wir für jede 3 die entferntesten Scheitelpunkte in ihrem Unterbaum sowie die Tiefe für jeden Scheitelpunkt. Wir berechnen auch Arrays für binären Aufschwung. Für jeden Vertex i und Grad zwei 2j berechnen wir die folgenden Arrays - p [i] [j], up [i] [j] und down [i] [j]. p [i] [j] ist der Vorfahr des Scheitelpunkts i in einem Abstand von 2j. In up [i] [j] wird der längste Pfad von i zu den Scheitelpunkten gespeichert, die sich im Unterbaum der Scheitelpunkte befinden, die sich auf dem Pfad zwischen i und p [i] [j] befinden. down [i] [j] unterscheidet sich von up [i] [j], bei dem der Pfad vom Scheitelpunkt p [i] [j] gespeichert wird.
    Jetzt ist es zu klein. Wir erhalten eine UV-Anfrage, wir suchen nach dem kleinsten gemeinsamen Vorfahren - w. Es bleibt die Spitze hu zu finden, die sich in der Mitte dieses Pfades befindet. Schneiden Sie den Baum an diesem Scheitelpunkt und berechnen Sie die größte Entfernung vom Scheitelpunkt u in seinem Baum und die größte Entfernung vom Scheitelpunkt v in seinem Baum. Wenn wir dies im Baum darstellen und nicht löschen, können wir mit unseren vorberechneten Arrays den Wert des längsten Pfades genau neu berechnen.
    Die Lösung ist O (nlog (n)).
    Der zweite. Kurz gesagt. Finden Sie den Durchmesser dieses Baumes. Wir berechnen dort die Antwort auf das Präfix für jeden Eckpunkt. Bei der Beantwortung der Anfrage stellen wir dann fest, wann der Pfad einen Durchmesser ergibt. In diesem Segment finden wir den mittleren Peak und antworten dann auf die Anfrage mit einem Präfix oder Suffix.

    Aufgabe: 7. Tricky Passwort
    Analyse: Die theoretische Schlüsselidee dieses Problems ist, dass die 2. Zeile mit 4, 3 mit 5 usw. übereinstimmt. Daher müssen wir in der Lage sein, nur in den ersten drei Zeilen etwas zu ändern.
    Jetzt bleibt die Sache der praktische Teil. Zunächst werden alle Werte so komprimiert, dass sie 105 nicht überschreiten. Wir unterteilen das Array in Segmente der Länge LEN. In jedem Segment werden wir Folgendes berücksichtigen - für jeden Wert speichern wir, wie oft er im cnt-Präfix gefunden wurde, sowie den Fenwick-Baum, in dem die Anzahl der Zahlen in diesem Präfix, die genau k-mal vorkommen, in Zelle f [k] gespeichert wird. Es ist leicht zu bemerken, dass die Antwort auf Abfragen in der zweiten Zeile im ersten Array gespeichert ist, und um die Antwort für die dritte Zeile zu erhalten, müssen Sie f [cnt [k] ... 105] berechnen. Es ist auch klar, wie diese Dynamik neu berechnet werden kann.
    Insgesamt bekommen wir Zeit für eine Anfrage . Wenn wir annehmen , wird die Antwortzeit auf die Anfrage sein .

    Jetzt auch beliebt: