Loading...
DimovIvan avatar DimovIvan 16 Точки

Code - единия ми тест гърми

In the far future, the citizens of Europa (the Jupiter moon, not the continent) decide to ban the use of links to websites, without the express permission of the owners of said websites (of course, this is a fictional story, and any correlations to actual people or events is purely accidental). The Internet community on the planet, however, did not really like this new law, so they found a way around it – they started communicating through a special code that couldn’t be read by the lawmakers. 
You work for the government of Europa, and you are tasked with analyzing the coded messages. What the government knows about the code so far, is that each message it consists of a sequence of non-negative integer numbers. The sequence is separated into “parts” – some of the integer values in the sequence are consider separators, and every value that is not a separator is an element of a part. A part is simply a sequence of values (non-separators), starting after a separator (or at the start of the sequence), and ending before a separator (or at the end of the text).
To do your analysis, you need some software that, given a message as a sequence of integers, and given search values, counts how many total parts contain each of those values. If multiple identical parts (same length, with the same values, in the same order) contain a value, count all of them (i.e. we are not searching for unique parts containing a value, but for all parts containing it).
Luckily, you know a thing or two about programming, so you will write that software yourself… well, what are you waiting for?
Input
The first line of the standard input will contain a sequence of non-negative integer values - the separators.
The second line of the standard input will contain a sequence of non-negative integer values, separated by single spaces – the message.
The following lines of the standard input will contain the search values – positive integers, each on a single line.
The last line of the standard input will contain the value 0 – this is not a search value (and no search value will be 0) – it is an indicator that the program should stop reading input.
Output
For each of the entered search values, print a single line containing the number of parts that contain that search value.
Restrictions
There will be no more than 30000 values in the message.
There will be no more than 40000 searches.
There will be no search for the value 0, but there could be searches for values that are not contained in any part.
The total running time of your program should be no more than 0.2s
The total memory allowed for use by your program is 16MB
 

https://pastebin.com/dyE10E6P

Всъщност, гърмяха ми два теста, но единия беше за време. Надявам се time limit - a да съм го оправил след като използвах  двоично търсене, но няма как да го проверя защото задачата не е активна в judge. Но така или иначе, ми гърмеше още един тест. Надявам се да ми помогнете за него. Явно пропускам нещо.

Тагове:
0
C++ Advanced
MartinBG avatar MartinBG 4803 Точки

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

Например при този вход решението ще върне 0 вместо 1:

0
1
1
0

 

Иначе, има много какво да се оптимизира по кода откъм performance:

  • Четенето на големи потоци информация от конзолата може да се забърза ако се използва std::cin.tie(nullptr);
  • Извеждането на резултата е добре да се направи наведнъж като се използва std::ostringstream за междинните резултати
  • Не се използват оптимални структура и алгоритъм и оттам идва най-голямото забавяне, защото за всяка проверка ще се обхождат числата във всички групи, т.е. имаме сложност О(M * N), където М е броят проверки (40000 по условие), а N - общият брой числа във всички групи (30000 по условие). Интересува ни в колко групи се среща дадено число. Това може да се пресметне еднократно в един unordered_map<int, size_t> и после единствено ще проверяваме в него каква е стойността за търсеното число, т.е. амортизираната сложност ще е О(M) и ще използваме значително по-малко памет.

 

0
DimovIvan avatar DimovIvan 16 Точки

Много благодаря за препоръките и за това, че ми показахте коя проверка пропускам. Наистина много съм усложнил логиката. Няма смисъл да разделям съобщението на отделните групи и да проверявам всяка група. Достатъчно е да знам всяко число колко пъти се повтаря в съобщението. В условието не е казано, че може да има повече от едно value в група, т.е. ако знам колко пъти се повтаря едно value в съобщението значи в толкова групи участва. Благодаря и за метода, който ми показахте, за по-бързо четене на входа. Четох, че има и друг начин за развързване на С и С++ потоците : cin::sync_with_stdio(false), но честно казано не можах да разбера каква е разликата между двата метода и кой кога се използва.

1
MartinBG avatar MartinBG 4803 Точки

Съобщението трябва да се обработи по групи, защото от примера, който е даден към услвието, се вижда, че дадено число може да се среща и повече от веднъж групата:

32 115 101 113 117 101 110 99 101 32

Имайте предвид, че понякога има проблеми при използването на cin::sync_with_stdio(false) - не се прочитат напълно входните данни, примерно. 

0
DimovIvan avatar DimovIvan 16 Точки

https://pastebin.com/wks54nwM

Това измислих като следвах вашите упътвания, за които благодаря. Разбира се, може и да не съм ги разбрал правилно. Имам един въпрос: Не е ли по-добре да използвам обикновен map и да търся в него с lower_bound метода отколкото да използвам unordered_map и обикновено търсене? Т.е. кое търсене е по-бързо, нормално търсене в unordered_map или  lower_bound търсене в обикновен map?

1
MartinBG avatar MartinBG 4803 Точки

Не.

lower_bound за map има сложност O(lg(N)), докато find в unordered_map има константна сложност (О(1)), т.е. за контейнер с 30000 елемента търсенето в unordered_map ще е близо 15 пъти по-бързо.

0
DimovIvan avatar DimovIvan 16 Точки

Благодаря за информацията. Тези неща би трябвало да ги знам, но ето кой не е внимавал в час... Много ми помагате! Благодаря отново!

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