[СофтУниада2017] Задачи, тестове, авторски решения
Колеги, материалите от състезателното програмиране от СофтУниада 2017 са качени:
Чувствайте се свободни да дискутирате задачите или решенията, както и да питате въпроси свързани с тях в тази тема.
Във форума е въведено ограничение, което позволява на потребителите единствено да разглеждат публикуваните въпроси.
Струва ми се, че задача 1 (Sum to 13), може да стане доста по-интересна, ако броя на числата (a, b, c) не е фиксиран на 3,
а се въвежда от потребителя (n), съответно (n1, n2, n3, ...). Ако някой има интересно решение, ще ми е интересно да го видя, моето е чрез опашка.
https://pastebin.com/hhK9cg8G
Уменията придобити от Basics и Programming Fundamentals (първа част на Tech Module) ще бъдат ли достатъчни за едно прилично представяне на СофтУниада 2018 (състезателното програмиране)?
Зависи от дефиницията ти за "прилично представяне". 
Задачите са с нарастваща сложност, като последните няма как да бъдат решени без познаването и използването на правилните алгоритми, а това не се учи в нито един от модулите на основните програми на СофтУни. Веднъж годишно има курсове по "Data Structures" и "Algorithms", които препоръчвам силно на всеки, който иска да разбере какво наистина е програмирането.
Прав си колега! Не един път съм чувал, че колкото и да се променят технологиите и езиците, алгоритмите си остават едни и същи и научиш ли ги ще са ти от полза през цялата кариера като програмист. Така че този курс със сигурност ще бъде записан. А относно Data Structures си нямам на понятие какво се преподава, даже и като гледам програма на минало издание, но съм сигурен че са важни работи щом ми ги препоръчваш. Благодаря!
И аз доста го пренебрегвах този курс и още не съм го изгледал , но в последствие разбрах , че без наученото от него , няма как да работиш в голяма фирма.Всички големи фирми работят по големи проекти и ако не можеш да боравиш със структури от данни и алгоритми по най-бързия и оптимизиран начин си обречен да бачкаш в посредствени фирми.Не те ангажирам с мнението си , просто с такова впечатление останах от интервютата.
Здравейте,
бих искал да споделя едно решение на задача 8 Color Coding. Бях зациклил до 30/100 алгоритъма за брутфорс ми куцаше, разговаряйки с приятел, ми вика, що не го направиш на 2 реда с регекс. И се получи (въпреки, че избягва алгоритмичния проблем, решението е любопитно): https://pastebin.com/ef9jWUzq
Здравейте, не съм сигурен, че темата все още се чете, но ще опитам.
Имам проблем със задача 6. Shop Keeper, чак започнах да имам известни съмнения за тест 10 (тестовете са публикувани по-горе в гитхъба). Реализирам доста прост алгоритъм, който хваща всички тестове, без 10-ти (реализацията е под 50 реда). На него, авторското решение дава: 1433 смени, а при мен са: 1431 (и в това се състои загадката, по-малко са, и в задачата се търсят най-малкото смени). Алгоритъма, който прилагам е, че при налагане на смяна, заменям стоката в магазина, която отсъства от бъдещи поръчки, ако такава няма със стоката с най-отдалечен индекс в поръчката. Часове не мога да си открия грешка в имплементацията.. Алгоритъма от авторското решение, ми идва малко трудно за разчитане (минава през няколко хеш сета). Възможно е моя алгоритъм да не е верен, или пък да имам грешка в имплементацията.
Ако някой му се занимава и може да открие проблема, ето решението: https://pastebin.com/x11wi0BZ
Ако искате да пробвате тестовете, хардкодвайте стинговете от входа, понеже са големи за конзолата.
P.S. Това, което забелязвам за входа на тест 10, е че при дистинкт дължината е с 1 по-малка, т.е. има един продукт който се повтаря, в условието не е споменто как се процедира при такъв случай, ако замениш първия, влияе ли на другата стока.
P.S.2 Това е бил проблема, като се дистинктне първия ред, входа за стоките в магазина, отговора излиза, просто не е упоменато в условието на задачата, което е некоректно според мен, понеже повторената стока по-скоро би трябвало да се разглежда като самостоятелна позиция в магазина.
Решението ти с опашка е оригинално!
Не се сещам за по-ефективен алгоритъм от О(2^N), т.е. за 3 числа имаме 2 * 2 * 2 = 8 цикъла, за 4 стават 16, за 5 - 32, а при N = 32 вариантите са над 4 милиарда, което не е никак добре.
Най-често задачи с такова условие (неизвестен брой вложени цикли) се решават с рекурсия, но този подход ще е по-бавен от твоето решение заради овърхеда от рекурсията.
И за да не ми е съвсем безполезен поста, ще си позволя и коментар по кода ти.
Четенето от конзолата може да го направиш и на един ред:
Мерси за коментара, нямам точки за да гласувам, но е интересен и полезен.
Идва ми наум още едно решение със стрингове, но е доста по-бавно, но пък може да даде точно коя комбинация е постигнала
контролната сума, което пък го няма като условие на задачата и както казва Седжуик, не си усложнявайте задачата и живота :)
Написах едно решение О(n*m) CPU и О(m) памет, където n са броя числа и m e сумата на абсолютните им стойности. За много и малки числа е супер, като станат сумите милиони обаче става бавничко. Това е, ако на някой му е интересно.