.
Die Punkte des Inhaltsverzeichnisses sollten am besten der Reihe nach gelesen werden. Wer lieber von Papier liest kann sich natürlich auch gerne die Druckversion ausdrucken. Auf jeden Fall solltest du zuerst versuchen, dir selber zu überlegen, wie du die Aufgabe lösen könntest. Die Analyse, die du hier zu dieser Musteraufgabe findest ist sehr viel mehr, als du dir während des Contests überlegen solltest, allerdings werden viele Zwischenergebnisse nach etwas Training auch ziemlich offensichtlich, z.B. was die Abschätzung der Laufzeit deines Programms angeht. Du solltest jeden Teil der Analyse so oft lesen, bis du ihn verstanden hast.
Um auf die tatsächliche Musterlösung zu kommen, braucht man schon ein wenig Erfahrung und es wird nicht ganz leicht sein, nachzuvollziehen, warum die Lösung richtig ist. Davon solltest du dich allerdings nicht entmutigen lassen, denn die Aufgaben im Online-Contest werden wohl nicht so trickreiche Lösungen haben.
Es gibt viele verschiedene Methoden, um an solche Aufgaben heranzugehen. Letztendlich ist es unheimlich schwierig, einzelne Herangehensweisen zu vermitteln und vermutlich findet jeder nach einer Weile seine eigenen Strategien. Auf jeden Fall sollte an dieser Stelle gesagt werden, dass das Lösen sehr vieler Aufgaben das beste Training ist. Meistens kommen einem dann die Problemstellungen schon bekannt vor, oder man hat wenigstens Teilproblemstellungen schon häufig gelöst.
Oft hilft es, zumindest die Beispielfälle und evtl. auch selbstausgedachte Testfälle erstmal per Hand zu lösen. Die Testfälle können erstens später zum Verifizieren des endgültigen Algorithmus verwendet werden und helfen außerdem dabei, Muster im Lösungsverfahren und Spezialfälle zu erkennen. Wenn man in diesem Fall einfach alle Möglichkeiten durchzuprobiert, was dem ersten Lösungsansatz der Musteraufgabe entspricht, wird man relativ schnell merken, dass man nicht jedesmal wieder alle Zahlen aufaddieren muss und endet so zumindest bei dem zweiten Algorithmus.
Um auf den dritten Lösungsansatz zu kommen, muss man schon einiges an Erfahrung haben und evtl. den Trick auch schonmal gesehen haben. Es gibt auch verschiedene Programmierkonzepte, wie z.B. die dynamische Programmierung, Flood-Fill-Algorithmen, Tiefen- und Breitensuche in Graphen, etc. Viele dieser Konzepte sind in den Büchern, die auf der Ressourcenseite empfohlen sind, erklärt.
Anhand der Eingabegrößen kann man die geforderte Laufzeitkomplexität abschätzen. In diesem Beispiel ist mit der Beschränkung N≤1000000 ein deutlicher Hinweis darauf gegeben, dass ein Algorithmus mit linearer Zeitkomplexität gesucht ist. Für Eingabegrößen bis zu 5000 existieren normalerweise Algorithmen mit quadratischer Laufzeit und für Eingabegrößen bis etwa 300 lassen sich Algorithmen mit kubischer Laufzeit finden. Ist die Eingabegröße auf etwa 25 beschrängt, ist das Problem wohl nur durch Durchprobieren aller Kombinationen lösbar.
Kennt man einmal die ungefähre Zeitkomplexität, fallen einem normalerweise einige nützliche Algorithmen und ähnliche Probleme ein.
Ganz wichtig ist, dass man sein Programm testet, bevor man es einschickt. Am besten machst du dir zu Beginn ein paar eigene Testfälle, die du später immer wieder verwendest, um dein Programm zu testen.
Selbst wenn deine Lösung nicht für den schlimmsten Fall der Eingabedaten ausreicht, solltest du sie auf jeden Fall einschicken — wenn sie korrekt ist, gibt es auf jeden Fall trotzdem ein paar Punkte. Im Normalfall kann man gut die Hälfte der Punkte mit einer nicht ganz optimalen Lösung, so wie im zweiten Lösungsansatz, erzielen.