Wie ich 3 von 4 Goldmedaillen bei der Computerolympiade gewonnen habe

Ich habe mich auf das Google HashCode-Weltcup-Finale 2017 vorbereitet. Dies ist der größte von Google organisierte Wettbewerb mit algorithmischen Problemen.

In der neunten Klasse habe ich angefangen, C ++ von Grund auf zu lernen. Ich wusste nichts über Programmierung, Algorithmen und Datenstrukturen. Irgendwann schrieb ich meine erste Codezeile. Sieben Monate später standen die Programmolympiade am Horizont. Ich wollte wissen, wie gut mein Programmierstil funktioniert. Es war eine ideale Gelegenheit.

Nach zwei Wettkampftagen kam das Ergebnis: Ich gewann eine Goldmedaille.

Ich war geschockt. Mit 5 Jahren Erfahrung habe ich mich vor Wettbewerbern durchgesetzt. Ich wusste, dass ich hart gearbeitet habe, aber diese Leistung hat alle meine Erwartungen übertroffen. Ich erkannte, dass Sportprogrammierung mein Thema ist und ging mit meinem Kopf darauf ein.

Ich weiß, was mich zum Erfolg geführt hat und möchte dies mit Ihnen teilen.

Dieser Artikel wurde mit Unterstützung von EDISON Software übersetzt, die sich um die Gesundheit der Programmierer und deren Frühstück kümmert und auch kundenspezifische Software entwickelt .

Welche Programmiersprache soll man wählen?

• C ++ - Sehr zu empfehlen! Er ist sehr schnell. Die Implementierung der Algorithmen nimmt aufgrund der STL wenig Zeit in Anspruch. C ++ wird in allen Wettbewerben akzeptiert. Ich habe meine erste Codezeile in C ++ geschrieben.
• C - C ++ aufgrund von STL lernen. Wenn Sie C kennen, können Sie auch in C ++ programmieren.
• Java ist eine langsame Programmiersprache. Es hat eine Big Integer-Klasse, aber es hilft dir nicht wirklich. Wenn die Konkurrenz ein Zeitlimit hat, werden Sie es wahrscheinlich mit Java überschreiten. Java wird bei allen Wettbewerben nicht akzeptiert.

Wo kannst du üben?

Ich empfehle Sphere Online Judge (SPOJ) . Es ist eine effektive Ressource in Bezug auf Quantität und Qualität. Editoren und Lösungen sind online verfügbar, wenn Sie bei der Lösung von Problemen nicht weiterkommen. Zusätzlich zu dieser Site empfehle ich das SPOJ Toolkit und den Problemklassifikator für SPOJ.pl.

Zunächst müssen Sie die Grundlagen verbessern

Sobald Sie sich an die Syntax der Sprache gewöhnt haben, müssen Sie einige Probleme lösen. Beginnen Sie mit einfachen Problemen, die Übung erfordern. In dieser Phase ist die Hauptsache, Ihren Programmierstil zu bestimmen. Vielleicht möchten Sie Code mit vielen Leerzeichen schreiben oder auch nicht. Vielleicht setzen Sie die Klammern in dieselbe Zeile wie das "Wenn", oder Sie können sie in separate Zeilen setzen.

Sie müssen Ihren Programmierstil finden, weil es IHR Stil ist.

Vergessen Sie bei der Suche nach ihm nicht zwei Grundprinzipien:

• Ihr Code sollte einfach zu implementieren sein. Sie sollten sich wohl fühlen, wenn Sie die von Ihnen entwickelte Lösung implementieren. Warum? Denn während des Wettbewerbs wollen Sie sich als letztes in Ihrem Code verlieren. Es ist immer besser darüber nachzudenken, wie die Implementierung des Codes vereinfacht werden kann, als 10 Minuten damit zu verbringen, dies herauszufinden.
• Ihr Code sollte leicht zu lesen sein. Wenn Code leicht zu lesen ist, ist es leicht zu debuggen. Seien wir ehrlich - Fehler treten ständig auf. Kennen Sie das Gefühl, wenn noch 10 Minuten bis zum Ende verbleiben und Sie den verdammten Fehler nicht finden können? Natürlich weißt du es. Um diese Situation zu vermeiden, schreiben Sie lesbaren Code. Wenn Sie mit dem Debuggen beginnen, erscheint der Code natürlich und leicht verständlich.

Hier ist ein Beispiel für meinen Programmierstil.

So verbessern Sie Ihre Entwicklungsfähigkeiten

Übe, übe und übe wieder. Ich empfehle Ihnen, die ersten 250 der am meisten gelösten Aufgaben auf SPOJ durchzuarbeiten . Löse sie in der richtigen Reihenfolge. Nehmen Sie sich mindestens eine Stunde Zeit, um über die Lösungen für jede dieser Lösungen nachzudenken.

Sagen Sie nicht: "Dieses Problem ist mir zu kompliziert, ich werde versuchen, Folgendes zu lösen." Also denken Verlierer.

Nimm ein Stück Papier und einen Bleistift. Denk darüber nach. Vielleicht können Sie eine Lösung finden oder vielleicht auch nicht. Zumindest entwickeln Sie algorithmisches Denken. Wenn Sie innerhalb einer Stunde keine Lösung finden können, suchen Sie im Forum oder in den Artikeln nach einer vorgefertigten Lösung.

Was werden Sie mit diesem Ansatz erreichen? Erfahren Sie, wie Sie Ihre Ideen schnell mit Code umsetzen können. Und lernen Sie klassische Probleme und Algorithmen.

Zweitens müssen Sie die Algorithmen und Datenstrukturen beherrschen

Folgen Sie einem hierarchischen Ansatz. Hast du angefangen zu laufen ohne zu laufen? Nein. Können Sie einen Wolkenkratzer ohne solides Fundament bauen? Nicht schon wieder.

Sie können die Schritte im Lernpfad nicht ignorieren. Wenn Sie sie ignorieren, haben Sie immer noch Wissenslücken. Mit der Zeit werden sie sich nur verschlechtern.

Beginnen Sie mit grundlegenden Algorithmen und Datenstrukturen

Es ist schwer, loszulegen. Vielleicht, weil Sie nicht wissen, was Sie zuerst lernen sollen. Deshalb habe ich einen Videokurs "Algorithmen und Datenstrukturen" erstellt. Bei der Erstellung dieses Kurses habe ich mich darauf verlassen, wie ich unterrichtet werden möchte. Die Reaktion war unglaublich! Mehr als 3.000 Studenten aus mehr als 100 Ländern haben sich im ersten Monat für den Kurs angemeldet.

Wenn Sie daran arbeiten, einfache Probleme zu lösen, werden Sie nie besser.

Der effektivste Weg, um herauszufinden, was Sie nicht wissen, besteht darin, dies in der Praxis zu tun. Also habe ich studiert. Ich lernte viele neue Techniken, von denen ich noch nie zuvor gehört hatte, und entschied mich für eine schwierige Aufgabe.

Jedes dritte Problem, an dem Sie arbeiten, sollte Ihnen etwas Neues beibringen. Seien Sie vorsichtig bei der Auswahl eines Problems. Wählen Sie Probleme schwieriger!

Nachdem Sie diese 250 Aufgaben von SPOJ erledigt haben, haben Sie ein gemeinsames Verständnis für die Hauptthemen der Sportprogrammierung. Dank eines tiefen Verständnisses der Logik, die grundlegenden Algorithmen zugrunde liegt, werden Algorithmen auf hoher Ebene weniger kompliziert erscheinen. So können Sie Ihr Wissen maximal nutzen.

Erfahren Sie mehr über jedes der Hauptthemen.

Hier ist eine wertvolle Ressource mit vielen Informationen. Dort finden Sie die Top 10 Algorithmen und Datenstrukturen für jedes Thema. Nach 250 Problemen von SPOJ werden Sie viel von dieser Liste wissen. Aber auch über eine Menge stolpern, von der noch nie etwas gehört wurde. Beginnen Sie daher damit, diese Themen in aufsteigender Reihenfolge zu untersuchen.

Wenn Sie Ihr Wissen nicht stärken, nachdem Sie etwas Neues gelernt haben, werden Sie schnell alles vergessen.
Ich empfehle, den neuen Algorithmus nach dem Erlernen in der Praxis anzuwenden. Arbeiten Sie an 2-3 Aufgaben. Suchen Sie in SPOJ nach dem Algorithmus-Tag. Dort finden Sie Probleme, für deren Lösung dieser Algorithmus benötigt wird. Sortieren Sie diese Probleme zuerst.

Beschäftige dich mit dynamischer Programmierung, weil sie dich zum Sieg führen wird
Nach meiner Erfahrung gibt es in jedem Wettbewerb mindestens ein Problem der dynamischen Programmierung . Viele Menschen haben Kopfschmerzen, wenn sie den Ausdruck "dynamische Programmierung" hören, weil sie ihn überhaupt nicht verstehen.

Und das ist gut. Denn wenn Sie dynamische Programmierung verstehen, werden Sie gewinnen.

Ich mag dynamische Programmierung, das ist mein Lieblingsthema. Das Geheimnis der dynamischen Programmierung besteht darin, global optimale Entscheidungen zu treffen, nicht nur lokale. Sie müssen das Problem in einfachere Unteraufgaben aufteilen. Lösen Sie jede dieser Unteraufgaben nur einmal. Erstellen Sie dann eine Lösung, die die gelösten Unteraufgaben kombiniert. Ein gieriger Algorithmus ist das Gegenteil von dynamischer Programmierung. Darin müssen Sie bei jedem Schritt eine lokal optimale Wahl treffen. Eine lokal optimale Wahl kann zu einer schlechten globalen Lösung führen.

Lesen Sie die TopCoder-Tutorials , wenn Sie neue Konzepte kennenlernen . Sie sind sehr detailliert und verständlich. Dank ihnen konnte ich binär indizierte Bäume verstehen.

Arbeite hart

Haben Sie jemals von Athleten gehört, die die Olympiade ohne jahrelanges Training gewinnen? Ich nicht.

Die Vorbereitungen für die Computerolympiade begannen jedes Jahr im September und endeten im April.

Während dieser 8 Monate habe ich jeden Tag 5 Stunden geübt.

Und ja, ich habe diese 5 Stunden nur damit verbracht, algorithmische Probleme zu lösen. Ich erinnere mich an die Tage, als ich 8 und sogar 10 Stunden geübt habe. Warum? Weil es mir gefallen hat. Jeden Tag, als ich von der Schule nach Hause kam, ging ich direkt ins Schlafzimmer, setzte mich an den Computer und begann, ein neues Problem zu lösen. Oder Sie haben einen neuen Algorithmus studiert, den Sie kennen müssen, um dieses Problem zu lösen.

Wenn Sie gewinnen möchten, müssen Sie dasselbe tun. Wählen Sie ein Problem und bleiben Sie dabei. Denken Sie darüber nach, während Sie die Straße zum Supermarkt entlang gehen oder fahren.



Wissen Sie, dass Ihr Gehirn im Schlaf die an diesem Tag gesammelten Informationen defragmentiert? Er scheint Bücher in alphabetischer Reihenfolge auf einem Bücherregal zu stapeln. Im Wesentlichen denkt Ihr Gehirn über die verschiedenen Probleme nach, auf die Sie gestoßen sind.

Dies kann geschickt eingesetzt werden. Lesen Sie vor dem Schlafengehen das schwierige Problem und denken Sie daran, was Sie zur Lösung benötigen. Zu diesem Zeitpunkt müssen Sie nicht nach der Lösung selbst suchen. Geh ins Bett. Ihr Gehirn wird anfangen, mit diesem Problem umzugehen. Wenn Sie aufwachen, werden Sie überrascht sein, dass Sie im Schlaf eine Lösung gefunden haben.

Probieren Sie es selbst aus. Es sieht aus wie Magie.

Ich habe einen Videoblog erstellt

Dieser kurze Absatz bezieht sich nicht auf Sportprogramme. Wenn Sie über zwanzig sind und daran interessiert sind, wie ich die Welt sehe, können Sie meinen Videoblog auf Youtube ansehen. Ich spreche darin über die Welt, das Leben und die Informatik.

Arbeiten Sie mit Bedacht

Dies ist das Erfolgsgeheimnis. Du brauchst Ziele.

Wir sind Menschen und zögern gerne. Wir wollen immer verschieben, was gerade getan werden muss. Das Anschauen von Netflix ist immer schöner als die Behandlung dynamischer Programmierprobleme. Sie wissen das und müssen es beheben.

Wie man den Aufschub besiegt

Setzen Sie sich Ziele. Sie werden immer interessante Probleme finden, aus denen Sie etwas Neues lernen können (siehe die oben genannten Ressourcen). Aber diese Probleme müssen gelöst werden, nicht nur darüber gelesen werden.

Auf diese Weise habe ich den Aufschub überwunden. Ich startete einen Papierkalender und füllte mich jeden Tag mit den Problemen, die ich lösen wollte. Ich habe die Probleme immer zwei Tage zuvor im Voraus ausgefüllt. Daher wusste ich, wie ich meine Zeit in den folgenden Tagen verwalten sollte.



So hatte ich immer Motivation. Ich musste einige Probleme lösen und neue finden, um sie in den folgenden Tagen im Kalender auszufüllen. Die gelösten Probleme zu streichen ist sehr schön. Ich weiß, dass es dir auch gefällt.

Holen Sie sich Ihren eigenen Papierkalender. Erstellen Sie auf Ihrem Telefon keine weitere Aufgabenliste, die Sie morgen vergessen werden.

Wie man effektiv debütiert

Willst du ein Profi werden? Wenn ja, dann müssen Sie im Kopf entwerten.
Dies ist bei weitem die effektivste Debugging-Technik, die ich kenne, da dafür überhaupt kein Debugger erforderlich ist. Ihr Gehirn untersucht mehrere Codezweige gleichzeitig und gibt Ihnen im Vergleich zum klassischen Debugger einen viel umfassenderen Überblick über den Code.

Sie können sich mit einem Großmeister vergleichen, der Schach spielt und 3 Züge voraus denkt.

Ich benutze diese Technik ausschließlich als meine Verteidigungslinie. Dann benutze ich einen echten Debugger.

Um zu lernen, wie man im Kopf schwächt, muss man üben. Wenn Sie eine Lösung für ein Problem genehmigen und eine „falsche Antwort“ erhalten, gehen Sie nicht direkt zur Debugger-Schaltfläche. Lesen Sie den Code erneut und denken Sie: "Was passiert in dieser Zeile?", "Wie wirkt sich" wenn "auf das Programm aus?", "Wenn wir die Schleife verlassen, wie hoch ist der Wert des Iterators?".

Sie denken also alleine. Im Laufe der Zeit werden Sie lernen, wie Sie Code schreiben und unterwegs debütieren.

Über den Autor

Andrei Margeloiu ist ein begeisterter Programmierer, der sich für Unternehmertum, Startups und Natur interessiert. Sie können ihn auf LinkedIn kontaktieren.

Übersetzung: Diana Sheremyova

Lesen Sie auch den Blog
EDISON Unternehmen:

20 Bibliotheken für
spektakuläre iOS-Anwendung