21 March - 26 March

КН, групи 5 и 6 - Counting Sort, Двоично търсене, Троично търсене

Задачи, които решихме:

1) 2013 Контролно 1 - Coaching Sort - задачата се решава с директна имплементация на Counting Sort

2) 2015 ДАА Тренировка 1 -  Sysadmin - задачата се решава с Binary Search по отговора. В какви граници може да бъде нашият отговор? Т.е. какви са минималните и максималните възможни дължини за тези поне K парчета кабел с еднаква дължина? Минималната възможна дължина за всяко от тези парчета е 1 (=left), а максималната е 100,000,000 (=right) (може вместо 1*10^8, да ползвате дължината на най-дългото парче кабел от входа, но така ще направите линейно повече операции). Имайки този range от възможни отговори, правим Binary search в него. На всяка стъпка хващаме mid = (left+right)/2, като след това, линейно по входните парчета кабел, проверяваме колко парчета кабел с дължина mid можем да изрежем от тях. Ако се получава < K, трябва да намалим дължината (за да се увеличи бройката) и съответно right = mid-1. Ако се получава >= K, запомняме текущия отговор (mid) и пробваме с по-голяма дължина, т.е. left = mid+1. Update-ваме mid, т.е. mid = (left+right) / 2, и повтаряме същите стъпки докато left <= right. Накрая печатаме отговора.

3) 2013 Упражнение 4 - Разделяй и владей:

Сума - В тази задача е важно да забележим малкия брой суми, за които трябва да проверяваме, а именно <= 10. За всяка една сума (sum[i]), проверяваме, във вече сортирания масив от N елемента, дали може да се получи като сбор на 2 елемента от него по следния начин: вземаме първия елемент (a[0]), намираме разликата между сумата и текущия елемент - diff = sum[i] - a[0], и търсим diff с двоично търсене в масива с N елемента, като внимаваме да не счетем, че сме намерили diff, а реално да сме намерили a[0]. T.e. ако sum[i] = 2, а a[0] = 1 и трябва да търсим diff = sum - a[0] = 2 - 1 = 1, трябва да изключим от търсенето a[0].

Задачи за упражнение:

1) 2013 Упражнение 4 - Разделяй и владей:

Алкохолици

Намери числата

Тръби

2) 2015 Домашно 2 Двоично търсене:

Elliot