Професионална програма
Loading...
+ Нов въпрос
georgi.stef.georgiev avatar georgi.stef.georgiev 921 Точки

Judge Assignment 2 (JA2) - Условия, Срокове, Въпроси, Коментари

Здравейте колеги,

EDIT: ето линк към състезанието - https://judge.softuni.bg/Contests/538/Judge-Assignment-2-JA2-OOP

Както обещах на упражненията, днес пускаме Judge Assignment 2, само че понеже не сме готови с подготовката на Judge системата още, днес ви пускам само условията, а в Judge constest-а ще можете да ги предавате от събота, 10:00 сутринта (както направихме и за първия judge assignment) - крайният срок остава непроменен. Ще ви дадем линк когато състезанието в Judge е готово.

Засега качвам условията в .shared папката в Dropbox (https://tinyurl.com/cpp-softuni-shared), и по-конкретно тук: https://www.dropbox.com/home/Projects/Cpp-Programming/.shared/Judge-Assignment-2-JA2. Възможно е да има леки изменения по ограниченията за време и памет, както и изменения ако открием бъг в някое решение или условие преди да пуснем състезанието в Judge.

Този Judge Assignment е различен от предишния с това, че освен условия, за някои задачи имате допълнителни файлове с код, които са достъпни за решенията ви. Тези "скелети" на решението са предназначени да ползвате от кода си, за да решите задачите. В някои случаи (като например задача 1) тези файлове имат main() функция, което означава, че вашият код ще трябва да допълни някакъв съществуващ код, за да може съществуващия код да работи. Не трябва да редактирате никой от тези предоставени файлове, тъй като при submit системата ще ги overwrite-не с нейната версия. В Judge системата ще предавате .zip файлове съдържащи вашите файлове нужни за решение на задачата - системата ще компилира всички .cpp файлове в .zip-а който пратите, заедно с всички файлове от "скелета" на решението, в една директория.

Ето кратки описания на задачите:

JA2-Task-1-List - от вас се иска да напишете имплементацията на един клас List, който представлява свързан списък. Дадени са ви List.h файл, както и main.cpp файл който ползва List-а от List.h за да реши някаква задача. Вие трябва да напишете имплементация (например в List.cpp), която позволява на задачата да работи вярно. (Тази задача щеше да е Matrix, не List, но реших Matrix-а да го преместя за подготовка за изпита, вместо за това домашно, най-вече защото изглежда като повече код).

JA2-Task-2-Divisible-by-45 - трябва да намерите всички числа, които се делят на 45 и се намират между две числа зададени на входа (от включително, до не-включително). Даден ви е файл BigInt.h, който можете да ползвате ако искате.

JA2-Task-3-Populations - Дадени са ви населения на градове и числата L, H и M. Трябва да намерите бройката градове, за които има поне M други градове, чиито населения са между L и H пъти по-големи. L, H и М се въвеждат от конзолата, а населенията на градовете са предварително зададени във файла populations.txt. Тук ще трябва да сте малко по-изобретателни с решението.

JA2-Task-4-Closest-Towns - Дадени са ви имена и координати на градове в двумерното пространство. Трябва да изведете 2-та най-близки града по име.

Ако имате въпроси или коментари, задавайте ги в тази тема (така най-бързо ще ги видя и ще мога да ви отговарям)

Поздрави,

Жоро

Тагове:
5
C++ Programming 22/04/2017 13:52:11
y.ivanov avatar y.ivanov 33 Точки

Привет,

Ами аз само да запитам, гарантираш ли, че ако някой успее да реши задачите, Уил Смит няма да дойде и да го застреля от упор...

Поздрави

Ясен

0
georgi.stef.georgiev avatar georgi.stef.georgiev 921 Точки

Хмм.. ами... имам бяло петно дали се е случвало нещо такова на някого :D

Иначе имате две седмици време да ги решите, не са чак толкова страшни. Ако седнете фокусирано да ги решавате трябва да ви отнеме между 6 и 8 часа горе-долу - тези задачи са по-обемни отколкото ще бъдат на изпита, но е добро упражнение по-големите и сложни задачи да са сега - вместо да са на изпита :)

1
MartinBG avatar MartinBG 3863 Точки

Първа задача уж я отметнах, но да изчакаме да чуем мението и нa Judge по въпроса. Като гледам колко време ми отне (2-3 часа, без да съм пределно фокусиран), определено ще бера ядове на изпита! blush

Иначе, задачата беше интересна - малко детективска работа с попълването на липсващите парчета код! Определено ми допадна повече от писането на конзолния шах 

Edit:

Втора задача също ми хареса. Математиците бързо ще я разнищят, за останалите - Google и Wikipedia. wink

0
18/04/2017 02:35:48
georgi.stef.georgiev avatar georgi.stef.georgiev 921 Точки

Да, първа си отнема време. На изпита ще има такъв тип задача, но ще гледам да не се налага да пишете толкова много код. И този тип задача ще е от по-"сложните" задачи, тоест тези, които се очаква да ви отнемат около 2 часа. Останалите ще са по-малки.

Този Judge Assignment цели да упражни много от ООП нещата, за които говорихме, затова е по-голям. На определено е по-голям от очаквания изпит като количество код, което трябва да се пише (почти всички задачи опират до ООП с не-малки класове - на изпита ще има не повече от 1-2 задачи, където ООП-то е задължително и е в тази форма).

Поздрави,

Жоро

2
krasio12356 avatar krasio12356 19 Точки

Не ми е ясен интерфейса

Като няма методи за четене на други елементи освен първия, как мога да направя копи конструктор и копи асайнмънт ?

Как да чета елементите без да разрушавам списъка ?

Какво изтървам ?

0
georgi.stef.georgiev avatar georgi.stef.georgiev 921 Точки

Методите на един клас могат да достъпват и private полетата на класа. Включително и на други обекти от класа, не само на this. Публичните методи изобщо не ти трябват за да минеш през всички елементи на обект от класа, подаден на който и да е метод на класа :)

 

Edit: виж SmartArray - неговия copy constructor не ползва публичните методи, нито пък публичните оператори, за да копира друг array

0
18/04/2017 14:42:14
MartinBG avatar MartinBG 3863 Точки

Мисля, че съм готов и с 3-та задача - чакаме Judge да отсъди.

Отне ми доста по-малко време от първите 2 и се събра на 40-ина реда, без да включвам Hint-товете от условието, които може и да (не) потрябват за Judge. 

Малко трудно ми беше да осмисля условието, което само по себе си е интересно четово - поздравления за което. smiley

Като препоръка, бих добавил, че ще е полезно да имаме повече примерни тестове към всяка от задачите (без доп. подробно описание - само вход и очакван изход), защото за задача като 3-та ще е доста трудно да си направим ръчна проверка на изпита, поради големия обем данни, с които се работи. 

0
georgi.stef.georgiev avatar georgi.stef.georgiev 921 Точки

Хм, освен ако не пропускам нещо като идея за решение, най-вероятно ще имаш time limit проблеми ако си я решил толкова бързо, ама не съм напълно сигурен :D

За повече примерни тестове съм съгласен като цяло, но за 3-та задача нарочно са малко. Идеята е, че част от задачата е да се научите как да тествате нещо такова - как да обработите на ръка големи обеми данни, за да може да измислите смислени тестове за тях - в реален проект ще имате такива ситуации, и там няма да има "примерни тестове" изобщо. И като цяло примерните тестове на тези задачи са предназначени да обясняват условието, не да оценяват дали кода работи вярно, така че не е хубаво да разчитате само на тях.

Е, разбира се на изпита имате judge, който прави оценката веднага, а в истинския живот няма да имате 6-часов deadline (в повечето случаи поне), но и в двата случая ще ви се наложи вие сами да си измисляте тестове, за да разберете какво работи и какво не работи в програмата :)

1
MartinBG avatar MartinBG 3863 Точки

Уж съм се погрижил да си подготвя и обработя добре входните данни и използвам бърз алгоритъм, но ако Judge реши да се запъне, има още мегдан за оптимизации. Хубаво е, че даваш и такива по-креативни/алгоритмични задачи, че с това OOP си изтърках клавиатурата от писане! :)

0
krasio12356 avatar krasio12356 19 Точки

Три дена се мъча да разбера, какво се иска в условието на 3 та задача и не успявам.

Нито повествованието, нито формулите ми говорят нещо. Не може ли допълнително към задачите, да се опише как се иска да се обработят данните, по какви формули, и какви резултати се очакват. 

Не знам, може би се подразбира някаква модерна наука, която изобщо не съм чувал и нямам шанс да разбера нищо от съдържанието на текста, без чужда помощ поне.

0
IvanMitkov avatar IvanMitkov 20 Точки

За първата задача трябва ли да е свързан списък или можем да го направим отдолу както си искаме, стига да работи с List.h.

0
georgi.stef.georgiev avatar georgi.stef.georgiev 921 Точки

Идеята на задачата е да е свързан списък и полетата, които List.h декларира предполагат такава имплементация.

Кодът в main() също е направен да работи добре за linked list.

Обаче кодът няма да се преглежда от човек - оценката, която получиш в Judge е финалната. Тоест ако ти минава в Judge със 100% няма значение как си го написал.

Принципно съм се постарал да ви накарам да напишете свързан списък, ама няма как да го enforce-на на 100%, така че ако мине номерът, мине :D

0
IvanMitkov avatar IvanMitkov 20 Точки

Аз мислех с бинарно дърво за търсене да го направя, просто ми се струва по-логично, ако ще изкарваме сортирани данни.

0
georgi.stef.georgiev avatar georgi.stef.georgiev 921 Точки

Това на пръв поглед изглежда по-логично за задачата (всъщност не е, после ще обясня защо), но не е правилно за самата структура данни. Предвид, че този List никъде не казва, че е сортиран, ако решиш да го ползваш извън тази задача за несортирани данни няма да работи вярно, защото постоянно ще ги сортира. Един клас трябва да прави това, което казва името му, иначе преизползването му става много трудно - ако прави други неща, всеки път като ти трябва List ще трябва да пишеш нов. Представи си std::vector или std::string сами да си сортираха елементите, без изрочно да им кажеш - нямаше да може да ги ползваш за нищо.

Така - относно логиката на задачата - тази задача очаква сортирани списъци на входа и после ги слива. Сливането на два сортирани списъка е линейна операция, отнема точно толкова стъпки, колкото общо елементи ще има резултата. Тоест сложността е O(N) (където N е общият брой елементи). Ако обаче ползваш двоично дърво, всяка операция на вмъкване е O(log(N)), защото дървото се опитва да сложи елемента на правилното място, тоест за N елемента това ти е O(N * log(N)) - с две думи дървото ти ще прави излишни операции, защото елементите вече са сортирани и то на практика ги сортира наново. Тоест няма да работи по-бързо, а освен това и ще ти отнеме доста повече време да напишеш балансирано двоично дърво :)

0
MartinBG avatar MartinBG 3863 Точки

Приключих и с последната задача, като отново ми се стори по-лесна от другите ( < 1 час и < 50 реда код), но подходих съвсем прагматично в решението си, като избрах най-лесният и бърз начин за удовлетворяване на условието, което може би е добра идея за изпитна задача, която се оценява автоматично, а не от човек. :)

 

Иначе - интересни задачи! Аз лично се забавлявах, докато ги решавах, но ще мога да ги оценя като сложност, едва след като минат и в Judge.

 

Поздрави!

1
georgi.stef.georgiev avatar georgi.stef.georgiev 921 Точки

Да, четвърта задача бих казал, че наистина е най-лесната и 50 реда код са си съвсем възможни за нея. Даже най-вероятно и 30 ще стигнат (общо). Авторското решение е по-дълго, защото прави повечко ООП за да може всичко да е обект, но определено задачата може да се реши на малко редове код - дори и без да ползвате Vector2D.h решението почти не се променя, ако е в минималния си вид.

1
netherblood avatar netherblood 95 Точки

Ще има ли ограничения за време? По-точно: brute-force решения ли се очакват (на последните 2 задачи главно) или нещо по-умно?

0
georgi.stef.georgiev avatar georgi.stef.georgiev 921 Точки

Има ограничения, да, виж в условията на задачите частта Restrictions. Системата, на която се тества, можеш да приемеш, че е със съвременен desktop процесор от порядъка на хубавите intel неща, които има в момента. Част от задачата е да прецениш при дадените обеми входни данни дали даденото време е достатъчно за brute-force алгоритъм, или се налага да пишеш нещо по-умно :)

Hint: за 4 задача имаш N = 100 - със 100 елемента общо взето каквото и да направиш един съвременен компютър надали ще успее дори да засече колко време ти е отнело

0
MartinBG avatar MartinBG 3863 Точки

Judge-a е отворен! :)

 

На първи опит минаха 3 от 4 при мен. 

1. List 100/100 - Memory: 2.80 MB, Time: 0.265 s

2. Divisible by 45 30/100 - Memory: 1.88 MB, Time: 0.015 s 

3. Populations 100/100 - Memory: 1.84 MB, Time: 0.000 s

4. Closest Towns 100/100 - Memory: 1.86 MB, Time: 0.000 s

 

EDIT:

И втора задача мина :)

2. Divisible by 45 100/100 - Memory: 1.87 MB, Time: 0.000 s

 

 

Ето и крайното ми мнение за задачите в JA2

1. Сложност - над средното ниво. Всеки, който е внимавал в лекциите и се е упражнявал, би следвало да успее да ги реши, но разликата ще дойде от времето, което ще отнеме намирането на решенията. 

2. Време (6 часа) - конкретно за тези задачи и при условията от т. 1, времето би следвало да стигне. Най-ощетени ще са тези от нас, които са се подготвили и идват с амбицията за 100/100, но поради някаква причина ударим на камък в Judge с една или повече задачи. Ако тази задача е като 3-та, нещата ще са още по-тегави, но това са рисковете на живото предаване :)

3. Съдържание - задачите покриват основните неща, които сме учили, като оставят и място за импровизации и креативност в решенията. За някои от задачите си е задължителен достъпа до интернет за бързи справки и рисърч.

4. Дължина на решенията (кода) - 1-ва задача изискваше най-много писане, но не беше прекалено. Кодът за останалите задачи много зависи от знанията на студента и способността му да използва вградените в езика методи и структури. Задачите се решават и без тях, но за сметка на повече код, време и риск от грешки.

5. Яснота на условията - аз лично бих предпочел пределно кратки и конкретни задания към задачите за изпита, въпреки че се забавлявах с описанията към JA2. С няколко прочитания всичко си идва на мястото (т.е. цялата информация е там), но отнема малко повече време.

Поздрави!

3
22/04/2017 10:57:00
krasio12356 avatar krasio12356 19 Точки

Къде е линка за джадж асайнмънта ?

0
georgi.stef.georgiev avatar georgi.stef.georgiev 921 Точки

Поздравления, сега ти погледнах решението на 3-та и си обясних как си го написал толкова бързо - и да, точно това се очаква като решение. Даже мисля да кача твоето решение заедно с авторското като свърши състезанието, ако нямаш против (авторското не ползва нещата, които ти ползваш, защото не са учени още, и съответно е по-дълго)

Като цяло съм съгласен с коментарите ти за JA2, за изпита няма 4 задачи да изискват ООП, най-вероятно ще са 2 или 3, така че това ще съкрати времето прекарано в писане (и ще увеличи това, прекарано в мислене).

За описанията на задачите - честно казано освен 3-та, където нарочно си съчинявах история, не мисля, че мога да ги направя по-кратки и конкретни. Проблемът е, че колкото и да предположа, че някое изречение се "подразбира", винаги ще има някаква част, която е неясна на някой (нормално, различни хора сме) - съответно трябва всяко описание да покрива всички въпроси, за които мога да се сетя, или да ползва текст, който няма никакви двусмислици, а това прави крайния резултат доста по-дълъг, отколкото бих искал. Затова ви пуснах кратки описания в тази тема, за да ви е ясна идеята на задачите, без да трябва да четете цялото условие.

На изпита ще има поне една задача с "история" като 3-та, и е възможно да няма толкова пояснителни формули като 3-та. Идеята на това е да умеете да изваждате какво се иска като алгоритъм от описание в реална ситуация (защото в реалния живот почти никога няма да имате примерен вход и изход, дълго и терминологично описание и формули). Също така на изпита ще съм на място, така че ще мога да ви отговарям при неясноти (стига отговорите да не издават решението).

Поздрави,

Жоро

1
netherblood avatar netherblood 95 Точки

Големи проблеми с Judge, много отвратително се получава.

 

На 1ва не изпринтирвам нищо (нали само List.cpp се слага в .zip?), въпреки че при мене си работи. Възможно ли е да дава seg fault или някаква друга грешка, но judge да не показва? Все пак нулевите би трябвало да ми минат поне.
На 3та не мога да чета от файла въобще. Пробвах и с двете, но не чете нищо и съответно принтира 0.

    std::ifstream myfile ("../populations.txt");
    std::ifstream myfile ("./populations.txt");

Локално при мене работи с ../populations.txt
 

0
georgi.stef.georgiev avatar georgi.stef.georgiev 921 Точки

Решението на първа задача вярно си го предал, но като го пусна при мен гърми още при първия ред от входа с (0xC0000005) под Windows, което, да, означава seg fault. Може би го компилираш при теб в някакъв debug режим, който скрива проблема от теб, или адресите които се е случило да достъпваш не се оказват извън паметта на твоята програма. И да, ако решението ти не дава output, значи judge-а не е успял да вземе output от него, което означава, че най-вероятно е crash-нало. Judge системите не винаги могат да дадат хубава информация за това какво се е случило с някакво предадено решение - не разчитайте напълно на тях за feedback.

На втора задача не е добра идея да четеш от файл, особено от такъв голям файл (трябват ли ти наистина имената на градовете във файла?) - твърде бавно ще ти работи кода. Ти си качил само решението си - системата няма файла populations.txt качен (това го пише в условието), но дори и да го качиш, системата в момента не поддържа четене от файлове (или по-конкретно файловете които качваш не отиват в същата директория, в която се случва компилацията EDIT: имах предвид "в която се изпълнява .exe файла получен от компилацията"). Така че за втора задача данните не трябва да са ти в друг файл. Трябва да измислиш друг, малко по-особен подход.

1
22/04/2017 15:53:47
Dimitar_Petkov_Petkov avatar Dimitar_Petkov_Petkov 169 Точки

Жоро, привет! При задача 2 получавам странни резултати от системата. Когато пусна  задачата с входни данни върнати като грешен отговор , при мен си работи коректно.  Идея?

0
georgi.stef.georgiev avatar georgi.stef.georgiev 921 Точки

Здравей,

И при мен твоето решение работи добре за този пример, обаче като цяло не работи вярно - пробвах с някои от другите тестове (които не виждате) и дава доста грешни отговори.

Като преглеждам какво правиш е много вероятно някъде да достъпваш неинициализирана памет - правиш един масив, на който не му инициализираш стойностите. Сигурно си го писал с идеята да не стигаш до тези неинициализирани полета, но е много вероятно да са ти грешни някъде проверките и съответно да стигаш до неинициализираните.

Съответно, понеже най-вероятно достъпваш неинициализирани полета, на различни машини ще ти работи по различен начин кода (недефинирано поведение). Пробвай да си измислиш повече примери с които ти да тестваш (особено с по-големи числа и по-големи разлики между двете входни числа) и ще видиш грешките.

Поздрави,

Жоро

0
Dimitar_Petkov_Petkov avatar Dimitar_Petkov_Petkov 169 Точки

Благодаря, аз грешно съм разбрал условието , че интервалът  от числа ще е до 100 , а не че възможните отговори са до 100 числа. Почвам я наново. 

0
krasio12356 avatar krasio12356 19 Точки

Тези задачи с история, не знам. Освен да питам и да досаждам на изпита, и ако не ме изгоните. 

Като обяснихте какво се иска, разбрах. Даже си помислих, че е лесна. Обаче имало още една врътка. И днес уж беше готова да я пусна и да забравя, а още 6 часа докато я доизкусуря.

На изпита ако с една задача се занимавам толкова време, работата не е добре.

0
georgi.stef.georgiev avatar georgi.stef.georgiev 921 Точки

Обикновено това, което се иска от задачите, е достатъчно просто, за да бъде обяснено накратко от автора, ако условието не е ясно, така че на самия изпит надали това ще е голям проблем.

Рискътедна задача да ти изгуби цялото време винаги го има. Затова в сутиация на изпит ако една задача почне да отнема много време, се пропуска и се правят другите, а после се връща към нея. Иначе на изпита със сигурност ще има задачи, които имат тривиално, но бавно решение, и изискват по-сложно решение, което да влезе в ограничението за време. Всъщност повечето разработка на софтуер е така - нещата привидно изглеждат лесни, но като данните станат много и потребителите не искат да чакат 5 секунди, а очакват нещата да станат "веднага", това прави писането на код сложно.

0
22/04/2017 17:01:11
DimitarTraykov avatar DimitarTraykov 2 Точки

Привет,

имам въпрос към Георги (georgi.stef.georgiev) за трета задача - Populations. В Judge системата включен ли е файла populations.txt или ние трябва да го включим в zip файла, който се ъплодва. Имам малък проблем и затова питам. Ако го включа към zip-a, не мога да ъплодна, защото системата ми казва, че файла е твърде голям. Ако не го включа към zip-a, програмата ми казва, че не може да го намери този файл и излиза.

Поздрави,

Димитър

0
MartinBG avatar MartinBG 3863 Точки

Този въпрос вече беше задаван. smiley

Ето и отговора: линк

0