Competitive Programming Guide

Das CP-Handbuch ist der einzige Ort für alle wettbewerbsfähigen Programmierliebhaber, da es alle Algorithmen und Datenstrukturen enthält. Außerdem enthält jedes Thema Beispiele und ungelöste Probleme für die Praxis.

Competitive Programming ist ein Sport, ich meine wörtlich. Nehmen Sie eine Sportart, lassen Sie uns Cricket in Betracht ziehen, Sie gehen zum ersten Mal hinein, um zu schlagen. Swing und ein Miss, mach es ein paar Mal und du wirst irgendwann einen über die Seile schlagen. Betrachten Sie einen Programmierwettbewerb metaphorisch als Cricketspiel. Kompilieren Sie einen Code und senden Sie ihn ab. Möglicherweise erhalten Sie eine WA (Falsche Antwort).

Nehmen Sie Änderungen am Code vor und Sie erhalten schließlich Ihre erste AC (Akzeptierte / Richtige Antwort). Lassen Sie mich einen kleinen Einblick geben. Etwa 20% der Fragen in einem Programmierwettbewerb sind einfache Konvertierungen von einfachem Englisch in einen Code Ihrer bevorzugten Programmiersprache.

Wenn Sie direkt hineingehen, lernen Sie die ungeschriebenen Spielregeln, wenn Sie härter spielen und besser werden.

 Und glauben Sie mir, Sie müssen keinen "Fancy Name" -Algorithmus oder keine Datenstruktur kennen, um loszulegen. Schon mal was von "Waft Shot" gehört, aber du bist der beste Schlagmann in deiner Straße, oder?

Okay, lassen Sie uns die ersten 20% der Programmierprobleme da draußen überwinden.

Du musst wissen:

Halten Sie eine Programmiersprache zwischenzeitlich fest

Englisch! Konvertieren Sie Englisch in Code!

Nehmen wir ein Beispielproblem dieses Levels: Terrible Chandu

Sie müssen lediglich die Eingabezeile von STDIN lesen und die Rückseite dieser Zeile an STDOUT drucken. Gehen Sie voran, machen Sie eine Einreichung. Suchen Sie Ihren ersten AC. Mehr wollen? Wir haben jede Menge in unserer Übungsabteilung. Suchen Sie nach denen mit Tausenden von korrekten Einsendungen.

Okay, jetzt sind Sie bereit, sich einer echten Herausforderung zu stellen. Halt dich fest, wir tauchen tiefer.

Du musst wissen:

1. Sortier- und Suchalgorithmen

2. Hashing

3. Zahlentheorie

4. Gierige Technik

Noch wichtiger ist, dass Sie herausfinden müssen, was, wann und wo Sie sie anwenden sollen. Es wird sehr schwierig und um Anfängern ein Gefühl des Vertrauens zu vermitteln, veranstalten wir eine Reihe von Wettbewerben als Code Monk. Vor jedem Wettbewerb veröffentlichen wir ein Tutorial zu einem bestimmten Thema. Später im Wettbewerb konzentrieren sich die Probleme nur auf dieses bestimmte Thema. Ich würde Ihnen empfehlen, die Tutorials durchzugehen und ein oder zwei Fragen zu jedem Thema zu lösen.

Inzwischen haben Sie erkannt, dass die Fragen so gestaltet sind, dass sie unsere Denkweise täuschen. Wenn Sie einfaches Englisch in Code konvertieren, erhalten Sie manchmal das Urteil TLE (Time Limit Exceeded). Sie müssen eine Reihe neuer Techniken und Algorithmen erlernen, um die Zeitlimits einzuhalten. In bestimmten Fällen hilft Dynamic Programming (DP). Tatsächlich haben Sie diese Technik möglicherweise bereits intuitiv angewendet. In jedem Wettbewerb gibt es immer mindestens eine Frage, die von DP gelöst werden kann.

Außerdem haben Sie bemerkt, dass es Fragen gibt, die mit linearen Array-Datenstrukturen einfach nicht gelöst werden können.

1. Graphentheorie

2. Disjoint Set Union (Union-Fund)

3. Minimum Spanning Tree

Diese Datenstrukturen bringen Sie ziemlich weit genug. Außerdem hätten Sie gedacht, dass die wahre Kunst darin besteht, die Ihnen bekannten Techniken zu modifizieren, um eine Frage zu lösen. Alle Easy-Medium- und Medium-Level-Fragen können auf diese Weise beantwortet werden.

Sie sind alle bereit, die Bestenlisten der Short Programming Challenges anzuführen. Behalten Sie einfach Ihre Beständigkeit bei. Wie ich bereits erwähnt habe, ist es ein Sport, den Sie erst beherrschen, wenn Sie ihn tatsächlich ausführen. Nehmen Sie an einem kurzen Wettbewerb teil, kennen Sie Ihre Stärken und Schwächen und sehen Sie, wie Sie mit dem Adrenalin-Modus umgehen, wenn die Uhr tickt.

Halten Sie sich so lange wie möglich an Ihre eigene Logik. Sie werden schließlich etwas Ähnliches wie den Algorithmus finden, der zur Lösung der Frage erforderlich ist. Sie müssen es nur auffrischen. Einige dieser Techniken helfen Ihnen dabei, einige der schwierigsten Probleme zu lösen.

1. Segmentbaum

2. String-Algorithmen

3. Versuche, Suffixbaum, Suffixarray.

4. Schwere leichte Zersetzung

5. Diagrammfarbe, Netzwerkfluss

6. Sqrt-Zerlegung.

Laden Sie dieses CP-Handbuch herunter und genießen Sie es, neue Dinge zu lernen. Vergessen Sie auch nicht, sie mit weniger Zeitkomplexität zu codieren.