"An error occurred while processing your request.
Loading...
+ Нов въпрос
georgi.stef.georgiev avatar georgi.stef.georgiev 906 Точки

Последен Judge Assignment (JA3) за курса - Въпроси, Коментари, Срокове

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

EDIT: като отворите линка, първо кликнете Compete - това ще ви регистрира в състезанието и ще имате достъп до задачите.

Линк към състезанието: https://judge.softuni.bg/Contests/547/Judge-Assignment-3-JA3-Algorithms-STL-Data-Structures. Условията са качени в системата.

Последният Judge Assignment за курса, който ще се фокусира предимно върху материала от последната лекция (структури данни и базови алгоритми), ще започне днес (вторник), 2 май 2017, в 10:00 сутринта и ще продължи до 14 май 2017, 23:59 (тоест имате почти 2 седмици за него).

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

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

Първа задача е сравнително тривиална, там няма много какво да мислите като алгоритъм.

Втора задача най-добре оставете за накрая, освен ако сте решавали подобна задача и се досещате какъв трик трябва да приложите. Това е от типа задачи, където ако се досетите какво да правите е почти елементарна, но ако не се досетите е доста сложна за реализация.

Трета задача ще ви изисква да използвате подходяща структура данни предвид размерите на входните данни.

Четвърта задача изисква ползване на комбинация от няколко структури данни за да работи ефикасно.

Втора, трета и четвърта задача могат да бъдат решени и с по-"наивни" алгоритми, но те няма да получат максималния брой точки, или заради time limit, или заради memory limit.

Ако имате неясноти по условията (или намерите грешки), пишете тук с въпроси.

Поздрави,

Жоро

2
C++ Programming 02/05/2017 16:54:38
gydigydi avatar gydigydi 12 Точки

Задачи

Задачите за това състезание не са публично достъпни.

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

ще започне днес (вторник), 2 май 2017, в 10:00 сутринта

1
tapunger avatar tapunger 2 Точки

При опит да сваля условието на която и да е задача получавам това: "Това състезание не може да се практикува!". Някакви идеи? 

0
02/05/2017 16:25:09
georgi.stef.georgiev avatar georgi.stef.georgiev 906 Точки

Първо трябва да кликнеш Compete на състезанието, след това трябва вече да ти дава достъп до задачите. 

0
MartinBG avatar MartinBG 765 Точки

Да са ни честити новите задачи! smiley

 

Тъкмо ми беше доскучало в обедната почивка и реших да отметна 1-ва задача (20-ина минути).

 

Поздрави!

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

На втора задача не форматираш правилно output-а когато започва с нули (виж какво ще ти изкара програмата на aaaaa00001aaaaa), оттам ти излизат грешки, иначе подходът ти е правилен като за 50% от тестовете - за останалите ти трябва нещо по-хитро.

Edit: почти правилен като за 50%, има как да си свалиш паметта почти наполовина, предвид данните, които ще има в 50% от тестовете

1
03/05/2017 02:38:51
MartinBG avatar MartinBG 765 Точки

Благодаря за подсказката! Грешните отговори от Judge доста ме озадачаваха :)

0
DimitarTraykov avatar DimitarTraykov 2 Точки

Здравейте, като се опитам да видя условията на задачите от JA3 ми дава следната грешка:

"An error occurred while processing your request.

This contest cannot be practiced!"

Някой има ли идея ?

Поздрави!

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

Здравей,

Откъде влизаш в състезанието? Трябва да има compete бутон, който да те вкара и оттам нататък кликането на линковете към задачи трябва да ги изтегля. В кой момент точно ти излиза това съобщение - като кликнеш да изтеглиш задача ли?

Поздрави,

Жоро

0
DimitarTraykov avatar DimitarTraykov 2 Точки

Здравей, Жоро,

благодаря ти за бързия отговор, не бях кликнал на compete бутона, ами директно на условията на задачите и затова ми даваше тази грешка.

Поздрави,

Димитър

 

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

Няма грижи, откъде има линкове директно към задачите, някъде до compete бутона ли? Не съм още изучил UI-а на Judge, а тези грешки се случват вече няколко пъти на различни хора и ми е интересно как се получават

0
Dimitar_Petkov_Petkov avatar Dimitar_Petkov_Petkov 156 Точки

Жоро, извинявам се, може ли подсказка за Зад.1 , къде ми се чупи, изчерпах се от към идеи :(

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

Ами на пръв поглед ти липсва едната команда :D, a тя се ползва в този тест - discard

Това малко ми напомня на девиза на софтуерните инженери - when all else fails, read the documentation. Вярно, че е малко тъпо, че не съм ви сложил пример с тази команда, но пък е описана в условието. Това всъщност е добър тренинг за изпита - там е много вероятно нещо да го няма като пример, а да е детайл в условието. 

0
Dimitar_Petkov_Petkov avatar Dimitar_Petkov_Petkov 156 Точки

Ами тя (discard) е в последния else, проверява се за всички други и ако не са те, трябва да е discard.

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

Да, вярно, извинявай, не гледам внимателно.

Обаче имплементацията ѝ не е напълно вярна. Тоест самия else e ок, обаче ти независимо от командата винаги правиш 2 пъти pop_back. Какво става ако има само 1 елемент в списъка и получиш команда discard?

0
MartinBG avatar MartinBG 765 Точки

Жорка, признавам те за майстор в измислянето на задачи! smiley

Втора задача ми изяде главата и нощта, но научих нещо ново, което може би нямаше да науча, ако не беше заложил такива рестрикции в задачата.

 

Поздрави!

 

ПП

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

0
03/05/2017 05:34:55
georgi.stef.georgiev avatar georgi.stef.georgiev 906 Точки

Хаха, мерси и браво. Иначе за изпита обещанието ми е, че ако не сте решавали Judge assignments няма да имате 6-ци, не че не може изобщо да имате 6-ци. На изпита няма да има чак такива задачи като тази, все пак е курс по C++, не по алгоритми/програмиране, задачите ще изискват по-малко хитрости и мега-оптимизации.

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

Поздрави,

Жоро

1
MartinBG avatar MartinBG 765 Точки

Благодаря! :)

Втора задача с подсказките от теб в условието и тук, сама се води към (май че е единственото) вярно решение, но наистина трябва малко по-добро познаване на езика.

Останалите 3 задачи също са приятни и имат своите тънкости и предизвикателсва - най-вече в намирането на по-елегантно, кратко или ефективно решение - кой, каквото си хареса, но оставят повече свобода на действие.

 

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

 

Поздрави!

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

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

Това всъщност е различно решение от авторското и е доста добро за тези ограничения.

Ок, значи различно предизвикателство - същата задача като оригиналната, само че DNA стойностите са по 8 символа, т.е. между 00000001 и FFFFFFFF (дори 6 символа, т.е. между 000001 и FFFFFF би било достатъчно предвид ограниченията).

1
p.yordanov avatar p.yordanov 51 Точки

Може ли още hints за втора задача - не знам вече колко решения и тестове изпратих към Judge и никои не работи на 100%. Определено ми размърда мозъчните клетки - харесва миlaugh

0
03/05/2017 14:05:10
IvanMitkov avatar IvanMitkov 19 Точки

Ееее хайде поне да останат ден два до крайния срок, няма нужда от подсказки толкова рано

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

Да, рано е за подсказки за пълното решение. Само ще кажа, че трябва да погледнете задачата от различен ъгъл, не от "очевидния" (очевиден като концепция на решението, няма значение как точно е реализиран).

Поздрави,

Жоро

0
vlad.dinev avatar vlad.dinev 16 Точки

Жоро, благодаря ти!

Задачите бяха голям купон.

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

 

Edit:

Всъщност, хайде да организираме някаква система за обмяна на решения за тези, които вече са решили задачите.

 

Edit 2:
За тези, които сте решили (вече прословутата) втора, какъв резултат успяхте да изстискате от Judge-a? Аз, със всичките магарии, го докарах до Memory: 1.86 MB, Time: 0.124 s.

1
03/05/2017 19:23:31
georgi.stef.georgiev avatar georgi.stef.georgiev 906 Точки

Пак заповядай :D (буквално, остават изпита и подготовката за изпит). Ти първи ги реши всичките, така че поздравления.

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

На MartinBG едното решение на втора, което взе макс точки, е интересно, защото играе по ръба на ограниченията на задачата и я решава вярно. Свържете се, ако той е съгласен може да ти прати това решение (и двамата сте решили всички задачи, така че няма проблем да обменяте решения, стига да искате).

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

 

Edit: на 3-та задача има решение, което е малко по-бързо от твоето, и става все по-бързо колкото по-голяма е разликата между N и M (общата бройка и нужната бройка). Може и върху това да помислиш, или просто виж авторското решение, когато го публикувам

0
03/05/2017 19:33:42
MartinBG avatar MartinBG 765 Точки

На втора задача моето време е доста по-високо от твоето (Memory: 1.83 MB, Time: 1.843 s), като предполагам, че разликата идва от тромав алгоритъм за парсване на входните данни.

Решенията ми на задачите от минали домашни са качени в GitHub (изчаквам да изтекат сроковете, откакто колега се натъкна на мое решение, прикачено в чуждо домашно).

Поздрави!

0
vlad.dinev avatar vlad.dinev 16 Точки

Като каза по ръба, успях да изцедя още малко.

Memory: 2.00 MB 
Time: 0.062 s

Такъв резултат получих и от .cpp и от .c (plain C позволява за буфер с 2 пъти повече памет, което всъщност не помогна много). Най-голям ефект имаше премислянето на кода и пренареждането (и премахването) на проверките.

Мислиш ли, че има по-ефективен начин от това? Две уникални DNA определено правят нещата по-интересни. А за 3та ще трябва да помисля.

Edit:
MartinBG, ще се радвам да ги видя, когато ги качиш. Благодаря ти.

Поздрави!

0
03/05/2017 23:30:27
p.yordanov avatar p.yordanov 51 Точки

Привет Жоро,

Мисля че и аз открих най-накрая ключа за палатката на 2-ра задача smiley При мен върви, но когато го кача в Джъдж ми изкарва грешка при компилация. Погледнах за неициализирани променливи, но не видях нищо нередно. Може ли да погледнеш последните ми решения и да ме насочиш защо ми избива тази грешка.

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

Здравей,

При мен също не се компилира под CodeBlocks, липсва ти един #include за едната STL структура данни, която ползваш за решението (напиши #include<структурата> и си готов) - другите std:: неща си ги #include-нал, но това не си. Нарочно казвам "нещо" за да не подсказвам на другите, предполагам ще се сетиш за кое говоря.

Най-вероятно компилаторът който ползваш го #include-ва автоматично, или в имплементацията на твоя компилатор има #include за това нещо в една от другите библиотеки, които ползваш, затова при теб се компилира. Като цяло ако ти даде компилационна грешка Judge-а, пробвай да компилираш под различно IDE/компилатор за да видиш какво може да го причинява.

Иначе като го огледах набързо ми се струва като правилното, но не съм разглеждал с детайли.

Поздрави,

Жоро

EDIT: Judge ползва GCC 6.3 компилатора ако не се лъжа, така че ако си го настроиш него за някоя среда би получавал същата компилация като когато го пратиш на Judge

1
04/05/2017 15:29:53
p.yordanov avatar p.yordanov 51 Точки

Благодаря за бързия отговор. Иначе от много структури накрая забравям да ги добавя :D. Извинявай, че те безпокоя пак, но имаш ли някаква идея, защо не минава някои от тестовете. Има ли нещо case-sensitive?

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

Случва се :D

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

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

0
krasio12356 avatar krasio12356 19 Точки

На първа задача ме няма в таблицата с резултатите. В общата таблица има резултата на 1ва, а в таблицата на 1ва ме няма.

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

Хм, и при мен така излиза, дори след cache clear и пробване от различни браузъри. Това прилича на bug в Judge.

Става ли да те помоля да им пратиш един bug report от тук: https://judge.softuni.bg/Feedback? Дай им линк към състезанието и им опиши че те няма в таблицата, която се появява като отвориш задачата (дай им линк към задачата: https://judge.softuni.bg/Contests/Compete/Index/547#0), а те има в общата таблица с резултати за състезанието.

0
krasio12356 avatar krasio12356 19 Точки

Благодаря! Изпратих обратна връзка.

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

Какво ИДЕ ще се ползва. Служебни компютри ли има или трябва всеки да си носи. Може ли да си носим свои компютри.

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

Ще имате достъп до интернет, до материалите от курса, до всичко. Единствено нямате право на комуникация - нямате право на Facebook, на всякакви messengers, нямате право и на Dropbox и други cloud sync неща, и като цяло на неща които биха ви позволили да преписвате или някой друг да ви реши задачите. Просто казано, имате право на "read-only достъп до интернет" :) Но не е лошо да имате запазени локално разни документации, защото с много хора в залата интернет връзката не е стабилна.

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

Казано накратко, условията на изпита и на judge assignments са еднакви, само че на изпита аз съм там и отговарям на въпроси (и следя за преписване :D) - това е и част от причината за judge assignments - да свикнете с формата.

0
fantom4e avatar fantom4e 24 Точки

Здравей, Георги.
Може би, ще съм малко нагъл, но може ли да ми погледнеш решението на 2ра задача Рокс.Вписвам се във времето и тайм лимита, но стигам до 40 точки и тестовете почват да ми дава некоректен отговор...3ти ден се мъча с тази задача и съм вече в безизходица :).

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

Здравей,

Поразгледах ти решението, но ми изглежда малко като нагаждане, не като реално решаване - правиш нещо ако броят елементи е под еди-колко си и затова ти работи за първите тестове, но иначе просто извеждаш нещо, което със сигурност няма да е отговор. Просто няма как да очакваш да ти работи решението, когато директно си казал "недей да работиш когато елементите са над X" :D

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

Ето ти няколко съвета все пак:

- НАЙ-ВАЖНОТО - ако една задача ти отнема повечко време, остави я и реши друга задача. Има още 2 задачи които не си решил, които са по-лесни от пълното решение на втора задача. Това даже съм го написал в тази публикация - щом съм стигнал до това да ви подскажа коя задача да избягвате, значи определено не е добра идея да забиваш на нея. Това е от нещата, които като цяло смятам, че един програмист трябва да се научи сам да прави - да си разпределя времето и приоритетите. Но щом чак съм хванал да го напиша изрично да избягвате задачата до последно, значи определено трябва да се заслушате. Проблемът не е в теб, проблемът е в задачата (наистина, не като когато някоя мома ти каже, че проблемът не е в теб, тогава със сигурност е в теб, но тук е различно :D) - реши другите и се върни на свежа глава и с нови перспективи към тази задача

- Като за начало текущото ти решение за 40% не е оптимално. Имаш някои неща, които не е напълно ясно защо ги правиш (правиш една определена операция върху входните данни, но реално не я ползваш - и с нея и без нея, алгоритъмът ти ще работи по един и същи начин). Има по-ефикасни начини да вземеш тези 40% - виж какви структури от данни сме учили, виж в какво са добри и в какво не и помисли как можеш да ги ползваш тях за да напишеш доста по-изчистено и ясно решение като за тези 40%. Като цяло когато пишеш някакъв алгоритъм от този тип (т.е. сравнително "праволинеен" алгоритъм, т.е. близък до това, което би направил ти самия ако имаш такава задача и нямаш компютър), винаги си го представяй действие по действие. Мисли дали можеш да го опишеш на един човек така че той да изпълни действията вярно и виж от кои действия има смисъл. И отново, разгледай структурите от данни и помисли как те могат да ти помогнат да решиш тази задача за 40% с доста по-малко код

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

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

- Напиши си тестове с големи количества данни. Недей разчита на Judge лотарията, в която пращаш решение и след това гадаеш какво може да не му работи. Даже можеш да напишеш програма, която генерира тестове (аз така правя за тези задачи, защото няма как на ръка да генерирам стотици хиляди елементи). Напиши и тривиалното решение, което няма да влезе в judge time и memory ограниченията, но пък ще си сигурен, че ще ти дава верни отговори - за да можеш да сравняваш после реалното решение което напишеш с това, което си сигурен, че получава верни резултати.

 

0
fantom4e avatar fantom4e 24 Точки

Ах, помислих че ще излъжа системата  с по - простовато решение, но уви :).
Мерси за подсказките и съветите и пак се извинявам за моята наглост.
Поздрави!

0