Competitive Programming Guide

CP Handbook est le seul endroit pour tous les amateurs de programmation compétitifs car il contient tous les algorithmes et structures de données. De plus, chaque sujet contient des exemples et des problèmes non résolus pour la pratique.

La programmation compétitive est un sport, je veux dire littéralement. Pratiquez n'importe quel sport, considérons le cricket d'ailleurs, vous entrez pour battre pour la première fois. Balancer et manquer, faites-le plusieurs fois et vous finirez par en frapper un sur les cordes. Maintenant, considérez un concours de programmation comme un jeu de cricket, métaphoriquement. Compilez un code et soumettez, vous pouvez obtenir une WA (mauvaise réponse).

Apportez des modifications au code et vous obtiendrez éventuellement votre premier AC (réponse acceptée / correcte). Permettez-moi de vous donner un aperçu, environ 20% des questions dans un concours de programmation sont une simple conversion de l'anglais simple en un code de votre langage de programmation préféré.

Allez-y, vous apprendrez les règles non écrites du jeu en jouant plus fort et en vous améliorant.

 Et croyez-moi, vous n'avez pas besoin de connaître un algorithme de "nom de fantaisie" ou une structure de données pour commencer. Vous avez déjà entendu parler de "Waft shot", pourtant vous êtes le meilleur batteur de votre rue, non?

Très bien, conquérons les 20 premiers% des problèmes de programmation.

Tu dois savoir:

Maintien intermédiaire sur n'importe quel langage de programmation

Anglais! Convertissez l'anglais en code!

Prenons un exemple de problème de ce niveau: Terrible Chandu

Tout ce que vous avez à faire est de lire la ligne d'entrée de STDIN et d'imprimer le verso de cette ligne dans STDOUT. Allez-y, faites une soumission. Cherchez votre premier AC. Vouloir plus? Nous avons des charges dans notre section de pratique. Recherchez ceux avec des milliers de soumissions correctes.

Bon, maintenant vous êtes prêt à relever un vrai défi. Tenez bien, nous plongeons plus profondément.

Tu dois savoir:

1. Algorithmes de tri et de recherche

2. Hachage

3. Théorie des nombres

4. Technique gourmande

Plus important encore, vous devez déterminer quoi, quand et où les appliquer. Cela devient vraiment difficile et donc pour aider les débutants à gagner un sentiment de confiance, nous organisons une série de concours en tant que Code Monk. Avant chaque concours, nous publions un didacticiel sur certains sujets et plus tard dans le concours, les problèmes ne visent que ce sujet particulier. Je vous recommande de parcourir les didacticiels et de résoudre une ou deux questions sur chaque sujet.

Vous avez maintenant réalisé que les questions sont conçues pour tromper notre façon de penser. Parfois, si vous convertissez un anglais simple en code, vous vous retrouverez avec le verdict TLE (Time Limit Exceeded). Vous devez apprendre un ensemble de nouvelles techniques et algorithmes pour faire face aux délais. Dans certains cas, la programmation dynamique (DP) vient à la rescousse. En fait, vous avez peut-être déjà utilisé intuitivement cette technique. Il y a toujours au moins une question dans un concours qui peut être résolue par DP.

De plus, vous auriez remarqué qu'il y a des questions qui ne peuvent tout simplement pas être résolues par des structures de données de tableau linéaire.

1. Théorie des graphes

2. Union d'ensemble disjoint (recherche d'union)

3. Arbre couvrant minimum

Cet ensemble de structures de données vous mènera assez loin. De plus, vous auriez pensé que le véritable art est de modifier les techniques que vous connaissez afin de résoudre une question. Toutes les questions de niveau facile-moyen et moyen peuvent être abordées de cette façon.

Vous êtes tous prêts à surpasser les classements des défis de programmation courte, gardez juste une persistance constante. Comme je l’ai déjà mentionné, c’est un sport, vous ne le maîtriserez pas avant de le faire. Allez-y, participez à un court concours, connaissez vos forces et vos faiblesses et voyez comment vous gérez le mode adrénaline lorsque l'horloge tourne.

Restez fidèle à votre propre logique le plus longtemps possible, vous finirez par trouver quelque chose de similaire à l'algorithme requis pour résoudre la question. Vous avez juste besoin de le rafraîchir. Plusieurs de ces techniques vous aideront à résoudre certains des problèmes les plus difficiles.

1. Arbre de segment

2. Algorithmes de chaîne

3. Essais, Suffix Tree, Suffix Array.

4. Décomposition légère intense

5. Coloration graphique, flux réseau

6. Décomposition Sqrt.

Alors téléchargez ce manuel CP et profitez d'apprendre de nouvelles choses, n'oubliez pas de les coder avec moins de complexité temporelle.