איך זכיתי ב-3 מתוך 4 מדליות זהב באולימפיאדת המחשוב

התכוננתי לגמר אליפות העולם של Google HashCode 2017. זוהי התחרות הגדולה ביותר עם בעיות אלגוריתמיות שאורגנה על ידי גוגל.

התחלתי ללמוד C++ מאפס בכיתה ט'. לא ידעתי דבר על תכנות, אלגוריתמים או מבני נתונים. בשלב מסוים כתבתי את שורת הקוד הראשונה שלי. שבעה חודשים לאחר מכן, תחרות התכנות נראתה באופק. רציתי לראות עד כמה סגנון לימודי התכנות שלי עובד. זו הייתה ההזדמנות המושלמת.

אחרי יומיים של תחרות הגיעו התוצאות: זכיתי במדליית הזהב.

הייתי בהלם. הקדמתי מתחרים עם 5 שנות ניסיון. ידעתי שעבדתי קשה, אבל ההישג הזה עלה על כל הציפיות שלי. הבנתי שתכנות ספורט הוא הנושא שלי והתעמקתי בו.

אני יודע מה הוביל אותי להצלחה ואני רוצה לחלוק את זה איתך.

המאמר תורגם בתמיכת EDISON Software, אשר דואג לבריאות המתכנתים ולארוחת הבוקר שלהםו - מפתחת תוכנה בהתאמה אישית.

באיזו שפת תכנות לבחור

• C++ - ממליץ בחום! הוא מהיר מאוד. יישום של אלגוריתמים לוקח מעט זמן בגלל STL. C++ מתקבל בכל התחרויות. כתבתי את שורת הקוד הראשונה שלי ב-C++.
• C - למד C++ בגלל ה-STL. אם אתה יודע C, אתה יכול גם לתכנת ב-C++.
• Java היא שפת תכנות איטית. יש לו מחלקה של מספר שלם גדול, אבל זה לא יעזור לך הרבה. אם לתחרות יש מגבלת זמן, עם Java אתה בוודאי תחרוג ממנה. Java לא מתקבלת בכל התחרויות.

איפה אפשר להתאמן

אני ממליץ Sphere Online Judge (SPOJ). זהו משאב יעיל מבחינת כמות ואיכות. עורכים ופתרונות זמינים באינטרנט אם אתה נתקע בתהליך של פתרון בעיות. בנוסף לאתר הזה אני ממליץ ערכת הכלים של SPOJ и מסווג בעיות עבור SPOJ.pl.

ראשית, עליך לחדד את הידע שלך ביסודות

ברגע שמתרגלים לתחביר של השפה, יש כמה בעיות שצריך להתגבר עליהן. התחל עם בעיות פשוטות הדורשות תרגול. בשלב זה, העיקר הוא לקבוע את סגנון התכנות שלך. אולי אתה אוהב לכתוב קוד עם הרבה רווחים, אולי אתה לא. יכול להיות שאתה שם את הסוגריים על אותה שורה של ה"אם", או שאתה שם אותם על שורות נפרדות.

אתה צריך למצוא את סגנון התכנות שלך כי זה הסגנון שלך.

כשאתה מחפש אותו, זכור שני עקרונות בסיסיים:

• הקוד שלך צריך להיות קל ליישום. אתה צריך להרגיש בנוח ליישם את הפתרון שהמצאת. למה? כי במהלך תחרות, הדבר האחרון שאתה רוצה הוא ללכת לאיבוד בקוד שלך. תמיד עדיף להשקיע 5 דקות נוספות במחשבה כיצד לפשט את היישום של הקוד מאשר להשקיע 10 דקות בניסיון להבין זאת.
• הקוד שלך צריך להיות קל לקריאה. כאשר קוד קל לקריאה, קל לנפות באגים. בואו נודה בזה - באגים קורים כל הזמן. אתה מכיר את ההרגשה הזו כשנותרו לך 10 דקות ואתה לא מוצא את הטעות הארורה? כמובן שאתה כן. כדי להימנע ממצב זה, כתוב קוד קריא. ברגע שתתחיל לנפות באגים, הקוד ייראה טבעי וקל להבנה.

הנה דוגמה שלי סגנון תכנות.

כיצד לשפר את כישורי הפיתוח שלך

תרגול, תרגול ועוד תרגול. אני ממליץ לך לעבור על 250 הבעיות הראשונות הניתנות לפתרון SPOJ. פתור אותם לפי הסדר. הקדישו לפחות שעה לחשוב על הפתרון לכל אחד מהם.

אל תגיד: "הבעיה הזאת קשה לי מדי, אני אנסה לפתור את הבעיה הבאה". כך חושבים לוזרים.

קח פיסת נייר ועיפרון. תחשוב על זה. אולי תמצא פתרון, אולי לא. לכל הפחות, תפתח חשיבה אלגוריתמית. אם אינכם מצליחים להגיע לפתרון תוך שעה, חפשו פתרון מוכן בפורום או במאמרים.

מה תשיג עם גישה זו? למד ליישם במהירות את הרעיונות שלך באמצעות קוד. ולמד בעיות ואלגוריתמים קלאסיים.

שנית, עליך לשלוט באלגוריתמים ובמבני נתונים

פעל לפי גישה היררכית. התחלת לרוץ בלי לדעת ללכת? לא. האם אתה יכול לבנות גורד שחקים ללא בסיס מוצק? לא שוב.

אי אפשר להתעלם מהשלבים לאורך מסלול הלמידה. אם תתעלם מהם, תישאר עם פערי ידע. עם הזמן הם רק יחמירו.

התחל עם אלגוריתמים בסיסיים ומבני נתונים

קשה להתחיל. אולי בגלל שאתה לא יודע מה ללמוד קודם. בגלל זה יצרתי קורס וידאו "אלגוריתמים ומבני נתונים". בעת יצירת הקורס הזה, ביססתי אותו על האופן שבו הייתי רוצה שילמדו אותי. התגובה הייתה מדהימה! יותר מ-3000 תלמידים מלמעלה מ-100 מדינות נרשמו לקורס בחודש הראשון.

אם תעבוד על פתרון בעיות קלות, לעולם לא תשתפר.

הדרך היעילה ביותר להבין את מה שאינך יודע היא לחוות זאת בפועל. כך למדתי. למדתי טכניקות חדשות רבות שלא שמעתי עליהן קודם לכן על ידי בחירת משימה מאתגרת.

כל בעיה שלישית שאתה עובד עליה אמורה ללמד אותך משהו חדש. היזהר יותר בבחירת בעיות. בחר בעיות קשות יותר!

לאחר שתשלים את 250 הבעיות הללו מ-SPOJ, תהיה לך הבנה בסיסית של נושאי הליבה של תכנות ספורט. עם הבנה עמוקה של ההיגיון מאחורי אלגוריתמים בסיסיים, אלגוריתמים ברמה גבוהה ייראו פחות מורכבים. כך תוכל להפיק את המרב מהידע שלך.

חפרו עמוק יותר בכל אחד מהנושאים המרכזיים

הנה משאב יקר ערך עם הרבה מידע. שם תמצאו את 10 האלגוריתמים ומבני הנתונים המובילים לכל נושא. אחרי 250 בעיות מ-SPOJ, תדע הרבה מהרשימה הזו. אבל אתה גם תיתקל בהרבה דברים שלא שמעתם עליהם קודם. אז התחל ללמוד את הנושאים האלה בסדר עולה.

אם לא תחזק את הידע שלך אחרי שלמדת משהו חדש, מהר מאוד תשכח הכל.
אני ממליץ שאחרי שתלמדו אלגוריתם חדש, השתמשו בו בפועל. עבדו על זה באמצעות 2-3 משימות. חפש את תג האלגוריתם ב-SPOJ. שם תמצאו בעיות שצריכות לפתור את האלגוריתם הזה. טפל בבעיות אלו תחילה.

אמן תכנות דינמי כי זה יוביל אותך לניצחון
מניסיוני, לכל תחרות יש לפחות בעיה אחת תכנות דינמי. אנשים רבים סובלים מכאב ראש כשהם שומעים את הביטוי "תכנות דינמי", כי הם לא מבינים אותו כלל.

וזה טוב. כי אם אתה מבין בתכנות דינמי, אז תנצח.

אני אוהב תכנות דינמי, זה הנושא האהוב עליי. הסוד של תכנות דינמי הוא לעשות בחירות אופטימליות בעולם, לא רק מקומיות. אתה חייב לפרק את הבעיה לתת-בעיות פשוטות יותר. פתור כל אחת מבעיות המשנה הללו פעם אחת בלבד. לאחר מכן צור פתרון המשלב את בעיות המשנה שנפתרו. אלגוריתם חמדן - ההיפך מתכנות דינמי. זה דורש בחירה אופטימלית מקומית בכל שלב. ובחירה אופטימלית מקומית יכולה להוביל לפתרון גלובלי רע.

תוך כדי לימוד מושגים חדשים, בדוק הדרכות TopCoder. הם מאוד מפורטים ומובנים. בזכותם הצלחתי להבין עצים באינדקס בינארי.

עובד קשה

שמעתם פעם על ספורטאים שמנצחים באולימפיאדה ללא שנים של תרגול? אני לא.

מדי שנה החלו ההכנות לאולימפיאדת המחשבים בספטמבר והסתיימו באפריל.

כל יום במשך 8 החודשים הללו התאמנתי במשך 5 שעות.

וכן, ביליתי את 5 השעות הללו רק בפתרון בעיות אלגוריתמיות. אני זוכר את הימים שבהם התאמנתי 8 ואפילו 10 שעות. למה? כי אהבתי את זה. בכל יום כשחזרתי הביתה מבית הספר, הלכתי ישר לחדר השינה, התיישבתי ליד המחשב והתחלתי לנתח בעיה חדשה. או שלמדתי אלגוריתם חדש שהייתי צריך לדעת כדי לפתור את הבעיה הזו.

אם אתה רוצה לנצח, אתה צריך לעשות את אותו הדבר. בחר בעיה והיצמד אליה. חשבו על זה בזמן הליכה לסופר או בזמן נהיגה.

האם ידעת שכאשר אתה ישן, המוח שלך מאחה את המידע שנאסף באותו יום? נראה שהוא עורם ספרים בסדר אלפביתי על מדף ספרים. בעיקרו של דבר, המוח שלך חושב על הבעיות השונות שאתה מתמודד איתם.

זה יכול לשמש במיומנות. לפני השינה, קרא בעיה קשה וזכור מה נדרש כדי לפתור אותה. בשלב זה אין צורך לחפש את הפתרון עצמו. לך למיטה. המוח שלך יתחיל לעבד את הבעיה הזו. כשתתעוררו, תופתעו להבין שמצאתם את הפתרון בזמן שישנתם.

נסה זאת בעצמך. זה כמו קסם.

יצרתי בלוג וידאו

הפסקה הקצרה הזו לא קשורה לתכנות ספורט. אם אתה בשנות העשרים לחייך ותוהה איך אני רואה את העולם, אולי תרצה לבדוק בלוג הווידאו שלי ביוטיוב. אני מדבר על העולם, החיים ומדעי המחשב שבו.

תעבוד חכם

זהו סוד ההצלחה. אתה צריך מטרות.

אנחנו אנשים ואנחנו אוהבים את זה לְהִתְמַהֲמֵהַ. אנחנו תמיד רוצים לדחות את מה שצריך לעשות עכשיו. צפייה בנטפליקס היא תמיד מהנה יותר מהתמודדות עם בעיות תכנות דינמיות. אתה יודע את זה ואתה צריך לתקן את זה.

איך לנצח את הדחיינות

הציבו לעצמכם מטרות. תמיד תמצא בעיות מעניינות מהן תוכל ללמוד משהו חדש (בדוק את המשאבים שהזכרתי למעלה). אבל צריך לפתור את הבעיות האלה, לא רק לקרוא עליהן.

אז הנה איך התגברתי על הדחיינות. פתחתי יומן נייר ומילאתי ​​כל יום בבעיות שרציתי לפתור. תמיד מילאתי ​​בעיות יומיים מראש. אז ידעתי איך לנהל את הזמן שלי בימים הבאים.

אז תמיד הייתה לי מוטיבציה. הייתי צריך לפתור כמה בעיות ולמצוא חדשות למלא את הימים הבאים בלוח השנה. חציית בעיות שנפתרו מרגיש נהדר. אני יודע שגם אתה אוהב את זה.

קבל יומן נייר משלך. אל תיצור עוד רשימת מטלות בטלפון שלך שתשכח ממנה מחר.

כיצד לבצע ניפוי באגים ביעילות

האם אתה רוצה להיות מקצוען? אם כן, אז אתה צריך "לפתור את זה בראש שלך."
זוהי ללא ספק טכניקת ניפוי הבאגים היעילה ביותר שאני מכיר כי היא אינה דורשת כלל ניפוי באגים. המוח שלך בוחן מספר ענפי קוד בבת אחת ונותן לך סקירה הרבה יותר רחבה של הקוד בהשוואה לו ניפוי באגים קלאסי.

אתה יכול להשוות את עצמך לרב-מאסטר שמשחק שח וחושב 3 מהלכים קדימה.

אני משתמש בטכניקה זו אך ורק כקו ההגנה הראשוני שלי. אחר כך אני משתמש באגים אמיתי.

כדי ללמוד איך לבצע ניפוי באגים בראש שלך, אתה צריך להתאמן. כאשר אתה מאמת פתרון לבעיה ומקבל "תשובה שגויה", אל תלך ישר ללחצן ניפוי הבאגים. קראו שוב את הקוד וחשבו: "מה קורה בשורה הזו?", "איך ה"אם" כאן משפיע על התוכנית?", "כשנצא מהלולאה, מה הערך של האיטרטור?"

ככה אתה חושב בעצמך. עם הזמן, תלמד לכתוב קוד ולנסות באגים תוך כדי תנועה.

על המחבר

אנדריי מרגלו הוא מתכנת נלהב עם עניין ביזמות, סטארטאפים וחיק הטבע. אתה יכול לפנות אליו בלינקדאין.

תרגום: דיאנה שרמייבה

מקור: www.habr.com