Loading...
ArmenPotourlyan+deleted! avatar ArmenPotourlyan+deleted! 488 Точки

[Useful Info][Exercises] - Advanced C# - Stacks and Queues - Problem{11} - Poisonous Plants [Spoiler Alert]

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

 

Как ви се струва C# Advanced в SoftUni 3.0 засега? Мен лично много ме кефи, най-вече понеже е пълно със задачки за уплътняване на времето. Задачите за речници и множества бяха доста приятни, тези за матрици – отвратителни, а пък за стекове и опашки... еми, безобидни (ха-ха). Някои ги решавах по 15 минути, а други по ... 15 часаsurprise. В обобщение:

Ах, тези отровни растения!!! angry

 

В крайна сметка след редица съвети от инструкторите и малко четене за 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 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).

 

ПП. Прощавайте за дългия пост blushblush

Тагове:
28
C# Advanced 21/05/2016 18:16:42
valenteeeen avatar valenteeeen 6 Точки

Здравейте!

Опитах да реша задачата и със стек, и без стек, но последните два теста "гърмят" за време и Judge - а ми дава само 77 точки за 11. Poisonous Plants.

Тук използвам стек и лист:

using System;
using System.Collections.Generic;
using System.Linq;

class _11_06_PoisonousPlants
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine()), k = 0, p = 0;
        List<int> numbers = Console.ReadLine().Split().Select(int.Parse).ToList();
        int length = numbers.Count;
        Stack<int> que = new Stack<int>();
        while(true)
        {
            for (int i = 0; i < length - 1; i++)
                if (numbers[i] < numbers[i + 1])que.Push(i + 1);
            p = que.Count();
            for (int i = 0; i < p; i++) 
                numbers.RemoveAt(que.Pop());
            if (length > numbers.Count)
                k++;
            else
            {
                Console.WriteLine(k); break;
            }
            length = numbers.Count;
        }
    }
}
 

0
29/05/2016 00:34:01
valenteeeen avatar valenteeeen 6 Точки

Без да използвам стек - но последните два теста "гърмят" за време и Judge - а ми дава само 77 точки за 11. Poisonous Plants.

Тук не използвам стек, а само  лист:

using System;
using System.Collections.Generic;
using System.Linq;

class _11_04_PoisonousPlants
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine()), k = 0;
        List<int> numbers = Console.ReadLine().Split().Select(int.Parse).ToList();
        int length = numbers.Count;
        while(true)
        {
            for (int i = length - 1; i > 0; i--)
            {
                if (numbers[i - 1] < numbers[i])
                {
                    numbers.RemoveAt(i);
                      if(i==1)break;
                }
            }
            if (length > numbers.Count)
                k++;
            else break;
            length = numbers.Count;
        }
        Console.WriteLine(k);
    }
}

/*
6
3 10 9 7 6 5        
5

7
6 5 8 4 7 10 9        
2

25
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
7
*/

0
29/05/2016 00:36:08
ArmenPotourlyan+deleted! avatar ArmenPotourlyan+deleted! 488 Точки

Колегата AntyfrizZz е дал идея за решение без стек. Аз лично не съм я решавал без стек. Изглежда, че ако се поставят достатъчно хитри условия, за да не се върти вътрешния цикъл излишно, може да се излъже Judge-a.

 

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

0
DimoUrumov avatar DimoUrumov 2 Точки

Така и не схванах как бачка кода от видеото. (Може би трябва да го изгледам още няколко пъти)

Но кода (на Java) бачка без проблеми. yes

И е бърз! Минават и тестовете за време.

0
21/05/2017 18:39:34
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.