GeOlymp

GeOlymp ფორუმი

წერილები: 133

4 აპრილი 2012, 0:10

შორეულ 2007 წელს პროგრამირების შეჯიბრებით დაინტერესებულებს გვქონდა ჩვენი ფორუმი. იმ პერიოდში დავწერე ინსტრუქცია, რომლის საშუალებით ახალბედა დარეგისტრირდებოდა და მიიღებდა მონაწილეობას Topcoder-ის ალგორითმულ შეჯიბრებში. ეს თემა ახლაც აქტუალური ჩანს, ამიტომ ჩემი ძველი პოსტი ამოვქექე, გარკვეული ცვლილებები შევიტანე და ვაქვეყნებ აქ. იმედია გამოგადგებათ.

-----------------------------------

თავის დროზე მე ძალიან დიდი ხანი არ ვიღებდი Topcoder-ის algorithm contest-ებში მონაწილეობას იმის გამო, რომ ყოველ ჯერზე, როდესაც დაწყებას ვაპირებდი, მესმოდა სიტყვები 'არენა', 'ჩელენჯები', 'პრაქტისი', 'პეტრი' და სხვები :D
Topcoder-ზე დარეგისტრირებული 2005 წლის სექტემბრიდან ვარ, თუმცა, მიუხედავად ამისა, პირველი შეჯიბრი მხოლოდ 2006 წლის დეკემბერში დავწერე და ისიც საკმაოდ დიდი გაჭირვებით.
ამიტომ ახლა გადავწყვიტე, პატარა tutorial-ივით დავწერო topcoder-ის დამწყებთათვის, რომ ჩემსავით დიდი ხნით არ გადადონ მაგ საიტზე დებიუტი, რადგან დიდი გამოცდილების შეძენაა იქ შესაძლებელი, ასევე განსხვავებული ფორმატია შეჯიბრის და it's fun :)

-----------------------------------
Step 1. Registration
-----------------------------------

ესე იგი, დასაწყისისთვის შევდივართ Topcoder-ის საიტზე. ზედა მარჯვენა კუთხეში წესით უნდა დაინახოთ ღილაკი ტექსტით Register Now (ანაც [Hello, ვიღაცა | Logout], თუ ვინმე არის ამ დროს დალოგინებული, ამ შემთხვევაში ჯერ logout-ს დააჭირეთ):

https://geolymp.org/static/images/forum/tc/tn_TC_tutorial1.png

Register Now-ზე დაჭერისას თავიდან შემოგთავაზებენ მენიუს, რომელშიც ამჟამად არის სამი პუნქტი: "I want to start using TopCoder Direct", "Topcoder" და "Topcoder Studio". ალგორითმულ შეჯიბრებში მონაწილეობის მისაღებად მონიშნეთ "Topcoder". ამის არჩევის და submit-ის დაჭერის შემდეგ გადახვალთ შემდეგ გვერდებზე, სადაც უკვე ჩვეულებრივი ინფორმაციის შეყვანა მოგიწევთ.

პირველ გვერდზე წესით ყველაფერი გასაგები უნდა იყოს. ყურადღებას გავამახვილებ იმაზე, რომ Student/Professional ველში სკოლის მოსწავლეებმაც და სტუდენტებმაც Student უნდა აირჩიოთ. ბოლოს მონიშნავთ, რომ წაიკითხეთ Terms of Use და დააჭერთ Submit-ს.

მეორე გვერდზე უფრო სპეციფიური ინფორმაცია არის შესაყვანი - მათ შორის ასაკი, სქესი, მაისურის ზომა (მაისურები ზოგჯერ შემთხვევითაც თამაშდება, ამიტომ ურიგო არ იქნება, თუ სწორ ზომას მიუთითებთ, ხოლო პირველ გვერდზე ნამდვილ სახელ-გვარსა და მისამართს შეიყვანთ). თუ პირველ გვერდზე Student აირჩიეთ, აქ ასევე შემოგთავაზებენ მონიშნოთ სასწავლო სტატუსი (Degree Program - სკოლის მოსწავლეებმა High School უნდა აირჩიონ, სტუდენტებმა კი სწავლის შესაბამისი საფეხური). შემდეგ ასევე შეგხვდებათ ველი School - ინგლისურად ეს არა თუ სკოლას, არამედ ნებისმიერ სასწავლო დაწესებულებას გულისხმობს და შესაბამისად სტუდენტებმა ამ ველში უნდა მოძებნოთ თქვენი უმაღლესი სასწავლებელი. ცნობისთვის, თსუ-ს სრული დასახელება "Ivane Javakhishvili Tbilisi State University" გახლავთ.

მესამე გვერდზე შეძლებთ გადახედოთ შეყვანილ ინფორმაციას და Submit ღილაკის მეშვეობით საბოლოოდ დაადასტუროთ თქვენი მომხმარებლის შექმნა.

-----------------------------------
Step 2. Downloading Arena
-----------------------------------

დავიწყოთ იმით, თუ რა არის საერთოდ ეგ არენა :D
Topcoder-ის ალგორითმული შეჯიბრებები ტარდება სხვებისგან მკვეთრად განსხვავებულ გარემოში. იმის მაგივრად, რომ რაღაცა გვერდებზე ვპოულობდეთ ამოცანების პირობებს, რაღაცა გვერდიდან ვაგზავნიდეთ ამოხსნებს და ა.შ., java-ში დაწერილია სპეციალური ე.წ. applet, რომელიც მაგ ფუნქციებს ბევრ სხვა ყველაფერთან ერთად ასრულებს algorithm contest-ების დროს. მაგ applet-ს ჰქვია Topcoder Competition Arena, ანუ ჩვენში უბრალოდ არენა.
Topcoder-ის გვერდზე შესვლისას ზედა მარცხენა კუთხეში ნახავთ ასეთ პრიჩინდალს:

https://geolymp.org/static/images/forum/tc/TC_tutorial2.png

O(n) არის ალგორითმული შეჯიბრების სიმბოლო. მასზე დაჭერისას ან დაიწყება Topcoder Competition Arena-ს გადმოწერა, ან მოხდება მისი გაშვება (თუ იგი თქვენს კომპიუტერზე ისედაც არის), ან შეიძლება გადმოგიხტეთ ფანჯარა, რომელშიც ეწერება 'Java Web Start not found!' და ბევრი სხვა გინება. თუ jre მართლა არ გიყენიათ, მაშინ ის უნდა გადმოწეროთ იმავე გვერდზე მოთავსებული ბმულიდან. კომპიუტერზე jre-ს დაყენების შემდეგ Load Competition Arena-ზე დაჭერას უნდა მოჰყვეს Topcoder Competition Arena-ს გადმოწერა/გაშვება.

წესით, არენის პირველად გადმოწერის შემდეგ მისი icon თქვენს desktop-ზეც უნდა განთავსდეს და საიტზე შემოსვლა აღარ უნდა დაგჭირდეთ ხოლმე ამის გულისთვის.

როდესაც, როგორც იქნა, გაიშვება არენა, ავისრულებთ ამდენი ხნის ნატვრას და შევიყვანთ ჩვენს username-სა და password-ს. ასევე იქ უნდა ამოირჩიოთ connection. ბოლო წლების მანძილზე Direct-ით უპრობლემოდ შევდივარ, თუმცა შეგიძლიათ ტუნელებიც სცადოთ. შემდეგ ვაჭერთ Go-ს :)

https://geolymp.org/static/images/forum/tc/tn_TC_tutorial3.png

-----------------------------------
Step 3. Inside The Arena
-----------------------------------

ახლა თვითონ არენის ფუნქციები განვიხილოთ მოკლედ.
შესვლისას დაგხვდებათ დაახლოებით მსგავსი ფანჯარა:

https://geolymp.org/static/images/forum/tc/tn_TC_tutorial4.png

Who's here და Chat Area სათაურების ქვეშ მოთავსებული ფანჯრები არის საჩატაო ხელსაწყოები, რომლებიც ალბათ ჩემზე უკეთ გეცოდინებათ :D
ერთადერთი, რაც მინდა აღვნიშნო - იმისთვის, რომ ვინმესთვის მიწერილი ტექსტი მარტო ადრესატმა წაიკითხოს და არა მთელმა chatroom-მა, ჩატის ტექსტური სტრიქონის მარცხნივ მოთავსებულ >>-ს უნდა დააჭიროთ და გამოსულ სიაში whisper ამოირჩიოთ, ხოლო მის მარჯვნივ გამოყოფილ ტექსტურ ფანჯარაში ადრესატის ნიკი.

https://geolymp.org/static/images/forum/tc/tn_TC_tutorial5.png

იმათთვის, ვინც პირველად იღებს ტოპკორის შეჯიბრში მონაწილეობას, ჯობია თავიდან practice room-ებში შეიხედონ და სცადონ, წინა შეჯიბრებზე შეთავაზებული ამოცანები ამოხსნან და არენას შეეჩვიონ. ამისთვის ზედა მენიუში უნდა დააჭიროთ Practice Rooms-ს და შემდეგ ამოირჩიოთ რომელიმე შეჯიბრი, მაგალითად SRM 353 DIV 2. გაითვალისწინეთ, რომ თუ უახლოეს დროში იწყება ან უკვე დაიწყო ალგორითმული შეჯიბრი, მაშინ Practice Rooms სიაში მხოლოდ 2 შეჯიბრი გამოჩნდება (ეს კეთდება შეჯიბრის დროს სისტემაზე დატვირთვის მინიმიზაციისთვის).

https://geolymp.org/static/images/forum/tc/tn_TC_tutorial6.png

-----------------------------------
Step 4. Practice Rooms
-----------------------------------

Practice Room-ში შეგიძლიათ, ამოხსნათ იმ კონკრეტული შეჯიბრის ამოცანები და ასევე სცადოთ სხვა ხალხის კოდების ნახვა და ჩაჭრა (დაჩელენჯება), რაზეც მოგვიანებით მოგიყვებით.

ამოცანების პირობების წასაკითხად chatbox-ის ზევით მდებარე Select one-ს უნდა დააჭიროთ და შემდეგ ამოირჩიოთ სამიდან ერთ-ერთი ამოცანა. ყოველ ამოცანას აქვს თავისი წონა, ანუ მაქსიმალური ქულა, რომელიც შეგიძლიათ ამ ამოცანაში აიღოთ პოტენციალურად. წონები დარიგებულია ამოცანების სირთულეების მიხედვით. სტანდარტულად შედარებით ადვილ ამოცანას აძლევენ 250 ქულას, საშუალოს 500-ს და ძნელს 1000-ს.

https://geolymp.org/static/images/forum/tc/tn_TC_tutorial7.png

ერთ-ერთი ამოცანის ამორჩევის შემდეგ, გაგეხსნებათ ფორმა, სადაც იქნება ამ ამოცანის პირობა. ფორმის ქვედა ნახევარს შეადგენს ფანჯარა, სადაც უნდა დაწეროთ (ან დააკოპიროთ სხვა ინტერფეისში დაწერილი) ამოხსნის კოდი. შემდეგ ის უნდა დააკომპილიროთ ტოპკოდერის სერვერზე (ღილაკი Compile ფორმის ქვედა მარჯვენა ნაწილში, შეგიძლიათ გაატესტიროთ ამოცანის პირობაში მოცემულ ტესტებზე (Test) და გააგზავნოთ (Submit). აქ უნდა გაითვალისწინოთ, რომ რაც უფრო ადრე გააგზავნით ამოცანას, მით უფრო მეტი ქულა დაგეწერებათ. ასევე ამოცანის მეორედ გაგზავნის შემთხვევაში მასში ქულები დაგაკლდებათ.
რაც შეეხება თვითონ ამოხსნის ფორმატს, ისიც ძალიან განსხვავდება სხვა შეჯიბრებზე შემოთავაზებულისგან. ტოპკოდერისთვის ამოხსნად ითვლება კლასი, რომელიც შეიცავს მეთოდს (ფუნქციას), რომელიც ამოხსნის პირობის შესაბამის ამოცანას. კლასის სახელი, მეთოდის სახელი და პარამეტრები ამოცანის პირობაშია მოცემული Definition ნაწილში.

ანუ მაგალითად თუ ჩვენი ამოცანაა ორი შემოსული რიცხვის შეკრება, ტოპკოდერისთვის ეს აღარ გამოიყურება როგორც


#include <iostream>
using namespace std;
int main()
{
  int a, b;
  cin >> a >> b;
  cout << a + b << endl;
  return 0;
}

ტოპკოდერზე ეგ იქნება რაღაც ამის მსგავსი:

class ClassName
{
public:
  int sum(int a, int b)
  {
    return a + b;
  }
};

ტოპკოდერზე არასდროს არაა საჭირო standard input-იდან (ეკრანიდან) წაკითხვა ან standard output-ში (ეკრანზე) რაიმეს დაბეჭდვა. ამოცანის ყველა შემავალი პარამეტრი ამომხსნელ მეთოდს გადაეცემა და პასუხსაც ეგ მეთოდი უნდა აბრუნებდეს.
რამოდენიმე შენიშვნა:
1. მეთოდი, რომელსაც ამოცანის პირობაში მოითხოვენ, აუცილებლად კლასის ღია წევრი უნდა იყოს.
2. კლასის აღწერის დამამთავრებელი }-ს შემდეგ აუცილებლად ; უნდა დასვათ.
3. მეთოდის პარამეტრების სახელები შეგიძლიათ ამოცანის პირობაში მოცემულებისგან განსხვავებულები გამოიყენოთ.
4. ამოცანის ფორმის ზედა მარჯვენა კუთხეში უნდა აირჩიოთ ენა, რომელზეც დაწერეთ ამოხსნა. ამის დაყენება by default-იც შეიძლება.

Practice Room-ის 'select one' ღილაკის გვერდზე არის ღილაკი Summary. მასზე დაჭერისას თქვენი ოთახის (რომელიც practice-ის დროს შეიცავს ყველა ამ შეჯიბრზე დარეგისტრირებულ მონაწილეს) ცხრილს იხილავთ. მასში აღნიშნულია, ყოველმა მონაწილემ თითო ამოცანაში რამდენი ქულა აიღო და რა ჯამური ქულა აქვს მას. მონაწილეს სახელის და ამოცანის გადაკვეთაზე დაწერილ ქულაზე ორჯერ დაწკაპუნებისას იხილავთ მაგ მონაწილის შესაბამისი ამოცანის კოდს.
თუ გგონიათ, რომ ამოხსნა, რომელსაც უყურებთ, არაა სწორი, შეგიძლიათ თავისუფლად სცადოთ მისი ჩაჭრა, ანუ დაჩელენჯება, რაც გამოიხატება ისეთი (ამოცანის პირობით დაშვებული) ტესტის შედგენაში, რომელზეც ეგ ამოხსნა არასწორ პასუხს დააბრუნებს. ამოცანის ფორმის ქვედა მარცხენა ნაწილში ნახავთ ღილაკს Challenge, რომელზე დაჭერისას გამოხტება ფანჯარა, რომელზეც უნდა შეიყვანოთ არგუმენტების მნივნელობები, რომლებისთვისაც ამოხსნა ჩავარდება.
თუ ამოხსნას ჩაჭრით, მაშინ 50 ქულა გემატებათ, წინააღმდეგ შემთხვევაში 25 გაკლდებათ.

ამოცანების გაგზავნისას თქვენ ნახავთ შეტყობინებას 'The problem was submitted successfully', მაგრამ ეს სულაც არ ნიშნავს, რომ თქვენი ამოხსნა სწორია. ეგ მხოლოდ იმას ნიშნავს, რომ ამოხსნის კოდი დაკომპილირებული გაქვთ. Practice Room-ში იმის შესამოწმებლად, სწორია თუ არა თქვენი ამოხსნა, შეიძლება შემდეგი რამის გაკეთება:
მენიუში Practice Options-ში დააჭირეთ Run System Test-ს. ის გატესტავს თქვენს მიერ დაწერილ ამოცანებს და ან ყველა ტესტზე 'Passed'-ს დაწერს და მწვანე ჩიტს დაუსვამს, ანაც სადმე გაწითლდება და დაწერს 'Failed!', რაც იმას ნიშნავს, რომ ამოხსნა რომელიღაც ტესტზე ვარდება. თვითონ ტესტის და სწორი პასუხის ნახვას იქვე შეძლებთ.

რეალური შეჯიბრის დროს ამოხსნის სისწორე მხოლოდ შეჯიბრის შემდეგ დგინდება.

-----------------------------------
Step 5. Contests
-----------------------------------

Practice-ებში გავარჯიშების შემდეგ მეტ-ნაკლებად მზად იქნებით რეალური შეჯიბრებებისთვის. ცოტას მაგათზეც მოვყვები.
ტოპკოდერის ალგორითმული შეჯიბრები ძირითადად ორ კატეგორიად იყოფიან: SRM-ები (ანუ Single Round Match, ცალკეული შეჯიბრები ნებისმიერი მონაწილისთვის) და Tournament-ები, ანუ ჩემპიონატები, სადაც ყოველ შემდეგ სტადიაზე მოსახვედრად წინაში კარგი შედეგის ჩვენებაა საჭირო.
შეჯიბრამდე რამოდენიმე საათით ადრე ის მენიუში Active Contest-ში ჩნდება, ხოლო მასზე რეგისტრაცია მის დაწყებამდე 3 საათით ადრე იხსნება და 5 წუთით ადრე იხურება. დარეგისტრირება აუცილებელია მონაწილეობის მისაღებად და პრაქტიკულად 'I Accept'-ზე დაჭერისგან შედგება ხოლმე Register-ზე დაჭერის შედეგად ამომხტარ ფანჯარაში (სურათზე Register-ის მაგივრად Enter არის, ეს უკვე შეჯიბრის დროს და მის შემდეგაა ასე)

https://geolymp.org/static/images/forum/tc/tn_TC_tutorial8.png

ყურადღებას გავამახვილებ SRM-ებზე. ამ დროს ყველა მონაწილე იყოფა ორ დივიზიონად, რომლებსაც სხვადასხვა problemset-ს სთავაზობენ. ყველა ახალი, რუხი (0-899 რეიტინგის მქონე) და მწვანე (900-1199 რეიტინგის მქონე) წევრი მეორე დივიზიონში ხვდება, ხოლო ლურჯები (1200-1499), ყვითლები (1500-2199) და წითლები (2200+) პირველ დივიზიონში. შესაბამისად, ამოცანებიც უფრო ძნელია პირველ დივიზიონში.
დივიზიონის შიგნით მონაწილეები იყოფიან ოთახებად. ყოველი ოთახი შეიცავს არაუმეტეს 20 კოდერის.
შეჯიბრი შედგება 2 ფაზისგან: coding phase, რომელიც 1 საათი და 15 წუთის განმავლობაში გრძლედება და რომლის დროსაც ხდება მოცემული სამი ამოცანის გაგზავნა, და challenge phase, რომელზეც 15 წუთია გამოყოფილი და რომლის დროსაც შესაძლებელია სხვა ამავე ოთახში მყოფი მონაწილეების კოდების ნახვა და დაჩელენჯება. ეს ორი ფაზა ერთმანეთისგან 5-წუთიანი შესვენებითაა გამოყოფილი. challenge phase-ის შემდეგ არაუმეტეს 20-30 წუთში საბოლოო შედეგები ვლინდება, ანუ ყველა კოდი, რომელიც ჩელენჯების შემდეგ გადარჩა, ტესტირდება ავტომატურად ბევრ ტესტზე და თუ ყველას გაივლის, სწორად ითვლება.

ასევე შეჯიბრების წერის დროს გაითვალისწინეთ, რომ ამოცანაზე დახარჯული დროის ათვლა შეჯიბრის დაწყების შემდეგ კი არა, არამედ ამოცანის გახსნის შემდეგ იწყება, ხოლო ამოცანაში დაწერილი ქულა არის ამ დროის უკუპროპორციული. ამიტომ უცებ სამივეს ნუ გახსნით :) ცნობისთვის, სწორ ამოხსნაში არ დაიწერება ამოცანის საწყისი წონის 30%-ზე ნაკლები. ასევე ამოხსნის ხელმეორედ გაგზავნისას ეს ამოხსნა ჯარიმდება ქულების 10%-ით.

და ბოლოს, რეიტინგი.
ყოველი SRM-ის ან tournament შეჯიბრის დაწერის შემდეგ ყოველი მასში მონაწილეობამიღებული კოდერის რეიტინგი იცვლება. მისი ცვლილების ფორმულა სადღაც საიტზე წერია, მაგრამ მაგაში დიდად ჩაღრმავებას არ გირჩევთ. არსი იმაშია, რომ რაც უფრო დიდია რეიტინგი, მით უფრო მაღალი ადგილი უნდა დაიკავოთ შეჯიბრის საერთო ცხრილში, რომ რეიტინგი კიდევ აგეწიოთ. აქ არსებითია, რომ სწორედ ცხრილის პოზიცია განსაზღვრავს მონაწილის წარმატებულობას და არა მის მიერ მოგროვებული ქულები (ხშირად 0 ამოხსნილი ამოცანით და 1 წარმატებული ჩელენჯითაც კი ამწევია რეიტინგი :) )
ცალკეული მონაწილეების რეიტინგის გარდა, არსებობს სასწავლებლების და ქვეყნების რეიტინგი, რომელიც გამოითვლება, როგორც სასწავლებლის ან ქვეყნის წარმომადგენელი მონაწილეების რეიტინგების წონითი საშუალო, სადაც პირველ ათეულს აქვს ბევრად უფრო დიდი წონა, ვიდრე დანარჩენ ნაწილს.

-----------------------------------

That's all folks. შეკითხვები თუ გექნებათ, დაწერეთ. Good luck and have fun!

თემიდან: ღია თასის მე-4 რაუნდი

წერილები: 133