Loading...
BobyTopalova avatar BobyTopalova 26 Точки

Ranges от 29 юли изпитна задача

Искам да пусна тази тема, защото се опитах да реша тази задача.Избрах не особено ефективен метод, и judge дава 30/100 въпреки, че кода работи коректно. Помогна ми MarinBG. Той каза, че тази задача е една от агоритмичните задачи в този курс.(Fundamentals C++), ако искате се опитайте и вие. А тя сега е подходяща, за  да упражните асоциативните контейнери.

Тагове:
0
C++ Fundamentals 18/01/2019 13:53:45
MartinBG avatar MartinBG 4803 Точки

Задачата наистина е приятна, защото изисква намирането на по-оптимално решение.

Наивният подход е да пазим отсечките в един контейнер и за всяка точка да ги проверяваме всичките, докато не открием съвпадение или не стигнем последната. Това е валидно решение, но само за малък брой входни данни, тъй като броят операции, които се извършват клони към брой отсечки * брой точки.

В условието е казано:

There will be between 1 and 10000 ranges (inclusive).
There will be between 1 and 100000 check numbers (inclusive).
In 30% of the tests, there will be no more than 10 ranges and 10 numbers.

Или с други думи, при 7 от 10 теста може да се наложи да направим до 1 000 000 000  (10 000 * 100 000) итерации.

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

Няма какво да се направи по отношение на броя точки (ще трябва да проверим всяка една по отделно), така че остава да се помисли в посока намаляване на проверките за всяка точка в колекцията от отсечки. Има структури, при които елементите са сортирани и върху които може да се приложи двоично търсене, което е с логаритмична сложност (при 1000 елемента ще провери само до 10 от тях, при 10000 - до 14) и използването им в тази задача значително ще намали макс. брой итерации (до 14 * 100 000).

Това е популярна алгоритмична задача, макар че решението ѝ по-скоро се свежда до използването на подходяща структура за съхранение на данните, а не толкова до използването на специфичен алгоритъм.

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

int main() {
  std::ostream::sync_with_stdio(false);
  std::istream::sync_with_stdio(false);
  std::cin.tie(nullptr);
....
}

 

В линка по-горе има примерен алгоритъм за решаването на този проблем, а това е мое решение, но преди да ги погледнете, ще е добре сами да се поборите с проблема. :)

0
30/12/2018 06:41:30
BobyTopalova avatar BobyTopalova 26 Точки

  std::ostream::sync_with_stdio(false);

  std::istream::sync_with_stdio(false);

  std::cin.tie(nullptr);

  Може, ли да обясните горната част от код?

    input.clear();  защо тябва да "чистим" потока, това по-ефективно ли е? И как се разбира,кога да го използваме?
    input.str(line); с това се взима едим ред, така ли? Имаше и .get(за char), kolioi го беше използвал в задачата decomprres.

0
MartinBG avatar MartinBG 4803 Точки

Тук има добро обяснение на I/O оптимизациите. От извора: sync_with_stdiotie

Синхронизацията може да се изключи и директно през базовия (ios_base) клас:

  std::ios_base::sync_with_stdio(false);

Извиквам clear() метода върху стрийма за да изчистя всякакви грешки (error bits), ако има такива, останали от предишното му използване. В случая го правя превантивно, защото искам да преизползвам стрийма, вместо да създавам нов на всяка итерация. Ако създаваш нов стрийм това не е необходимо.

 

str(text) "зарежда" стрийма с ново съдържание.

 

 

0
MartinBG avatar MartinBG 4803 Точки

Предполагам, питаш за следните варианти:

std::lower_bound(ranges.begin(), ranges.end(), point); // Uses lower_bound method from algorithm library

ranges.lower_bound(point); // Uses lower_bound method from map class


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

 

Относно оптимизациите за вход/изход - да, задачата работи и без тях, но ако погледнеш времената в Judge, ще забележиш, че без тях решението минава за 0.350 - 0.400 сек. и за около 0.115 сек., ако ги има.

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