[Useful Info][Exercises] - Advanced C# - Stacks and Queues - Problem{11} - Poisonous Plants [Spoiler Alert]
Здравейте, колеги,
Как ви се струва C# Advanced в SoftUni 3.0 засега? Мен лично много ме кефи, най-вече понеже е пълно със задачки за уплътняване на времето. Задачите за речници и множества бяха доста приятни, тези за матрици – отвратителни, а пък за стекове и опашки... еми, безобидни (ха-ха). Някои ги решавах по 15 минути, а други по ... 15 часа
. В обобщение:
Ах, тези отровни растения!!! 
В крайна сметка след редица съвети от инструкторите и малко четене за The Stock Span Problem успях да излъжа Judge и да взема максималните точки за Poisonous Plants. Ще нахвърля идеята без да поствам кода.
Нека имаме следната колекция от растения (всяко число показва количеството пестициди):
{ 6 5 8 4 7 10 9 2 3 11 6 9 8 7 5 4 13 10 8 9 6 15 4 3 8 }
Растенията, които съдържат повече пестициди от съседите им вляво, умират. Ето как се развива това във времето:
Day 0: 6 5 8 4 7 10 9 2 3 11 6 9 8 7 5 4 13 10 8 9 6 15 4 3 8
Day 1: 6 5 8 4 7 10 9 2 3 11 6 9 8 7 5 4 13 10 8 9 6 15 4 3 8
Day 2: 6 5 8 4 7 10 9 2 3 11 6 9 8 7 5 4 13 10 8 9 6 15 4 3 8
Day 3: 6 5 8 4 7 10 9 2 3 11 6 9 8 7 5 4 13 10 8 9 6 15 4 3 8
Day 4: 6 5 8 4 7 10 9 2 3 11 6 9 8 7 5 4 13 10 8 9 6 15 4 3 8
Day 5: 6 5 8 4 7 10 9 2 3 11 6 9 8 7 5 4 13 10 8 9 6 15 4 3 8
Day 6: 6 5 8 4 7 10 9 2 3 11 6 9 8 7 5 4 13 10 8 9 6 15 4 3 8
Day 7: 6 5 8 4 7 10 9 2 3 11 6 9 8 7 5 4 13 10 8 9 6 15 4 3 8
Ако съпоставим на всяко едно растение i дните daySpan[i], които то живее:
{ ∞ ∞ 1 ∞ 1 1 2 ∞ 1 1 2 1 2 3 4 5 1 2 3 1 4 1 6 7 1 }
Оттук можем да измислим алгоритъм за решаване на задачата:
- Ще обхождаме масива от растения отляво надясно.
- Ще пазим растението с най-малко пестициди до момента (текущите минимални стойности показват растенията, които ще живеят вечно).
- Ще пресмятаме колко дни живот има дадено растение и ще ги отбелязваме в допълнителен масив daySpan[i].
- За да изпълним горната стъпка, ще пазим индексите на избрани предишни растения в стек.
- Ще пазим максималното време на живот(максималния елемент в daySpan) до момента.
В стека на някои стъпки се вкарва по повече от един елемент и се изкарва по повече от един елемент, но въпреки това като цяло мисля, че можем да приемем, че алгоритъмът е със сложност O(n). След като обходим всички растения променливата, която пази максималното време на живот, съдържа отговора, след колко дни растенията ще престанат да умират.
[SPOILER ALERT] Стъпка по стъпка:
| plant | iteration | min | daySpan | indexStack | indexStack | maxSpan |
| 6 | 0 | 6 | Infinity | Empty >> | Empty | 1 |
| 5 | 1 | 5 | Infinity | Empty >> | Empty | 1 |
| 8 | 2 | 5 | 1 | Empty >> | { 2 } | 1 |
| 4 | 3 | 4 | Infinity | { 2 } >> | Empty | 1 |
| 7 | 4 | 4 | 1 | Empty >> | { 4 } | 1 |
| 10 | 5 | 4 | 1 | { 4 } >> | { 5 } | 1 |
| 9 | 6 | 4 | 2 | { 5 } >> | { 6 } | 2 |
| 2 | 7 | 2 | Infinity | { 6 } >> | Empty | 2 |
| 3 | 8 | 2 | 1 | Empty >> | { 8 } | 2 |
| 11 | 9 | 2 | 1 | { 8 } >> | { 9 } | 2 |
| 6 | 10 | 2 | 2 | { 9 } >> | { 10 } | 2 |
| 9 | 11 | 2 | 1 | { 10 } >> | { 11, 10 } | 2 |
| 8 | 12 | 2 | 2 | { 11, 10 } >> | { 12 } | 2 |
| 7 | 13 | 2 | 3 | { 12 } >> | { 13 } | 3 |
| 5 | 14 | 2 | 4 | { 13 } >> | { 14 } | 4 |
| 4 | 15 | 2 | 5 | { 14 } >> | { 15 } | 5 |
| 13 | 16 | 2 | 1 | { 15 } >> | { 16, 15 } | 5 |
| 10 | 17 | 2 | 2 | { 16, 15 } >> | { 17, 15 } | 5 |
| 8 | 18 | 2 | 3 | { 17, 15 } >> | { 18, 15 } | 5 |
| 9 | 19 | 2 | 1 | { 18, 15 } >> | { 19, 18, 15 } | 5 |
| 6 | 20 | 2 | 4 | { 19, 18, 15 } >> | { 20, 15 } | 5 |
| 15 | 21 | 2 | 1 | { 20, 15 } >> | { 21, 20, 15 } | 5 |
| 4 | 22 | 2 | 6 | { 21, 20, 15} >> | { 22 } | 6 |
| 3 | 23 | 2 | 7 | { 22 } >> | { 23 } | 7 |
| 8 | 24 | 2 | 1 | { 23 } >> | { 24, 23 } | 7 |
Мистериозното намиране на стойността daySpan[i]:
- Ако plant[i] <= min, изчисти стека, сложи daySpan[i] = Infinity, continue;
- Ако няма нищо в стека, вкарай текущия индекс, daySpan[i] = 1, continue;
Нека poppedIndex = indexStack.Pop().
- Ако plant[i] > plant [poppedIndex], сложи daySpan[i] = 1;
- Докато plant[i] <= plant [poppedIndex], daySpan[i] = daySpan[poppedIndex] + 1;
На всяка стъпка се вкарва текущия индекс в стека. Трябва обаче да се преценят случаите, когато трябва да върнем обратно в стека индекс (с Push), който вече сме изкарали (с Pop).
ПП. Прощавайте за дългия пост 