Loading...
Jovanna avatar Jovanna 186 Точки

JA1 - Задача 4 Roxettes - друга версия?

Чудя се, ако се търси уникален елемент, но появата на всички останали , освен четен брой е и нечетен, как може да стане ? XOR май няма да помогне тук... //и пак да е бързо и с малко памет

Примерно aaaaabbbbb22222bbbbb22222bbbbb

 

Тагове:
0
C++ Fundamentals 09/12/2017 14:48:17
MartinBG avatar MartinBG 4803 Точки

Жоро е отговорил как стоят нещата по-принцип, но конкретно за ограниченията на тази задача има решение, което отговаря на твоя въпрос. smiley

Стигнах до него в предишното издание на курса след една нощ главоблъскане. Решението не e алгоритмично, колкото решениетo с XOR, но пък използва една по-малко известна структура - bitset.

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

Най-общо - за всяко число във входните данни се инвертира стойността (бит, т.е. 1 или 0) на индекса, който отговаря на това число. Накрая се обхожда битсет-а, като всеки индекс, чиято стойност е 1 означава, че това число е било намерено нечетен брой пъти във входните данни. Алгоритъмът е по-скоро с линейна сложност (N + maxNum).

Пишете като мине срока за това домашно и ще си постна кода на решението тук.

 

 

EDIT:

Сега ти прочетох по-внимателно въпроса и виждам, че съм отговорил на друг въпрос. :)

Ако търсиш всички числа, които се срещнат само веднъж във входните данни, най-простото решение е да използваш масив, на който индексите отговарят на числата, а стойностите в масива - на броя срещания във входните данни. Накрая изкарваш само тези индекси, чиито стойности в масива са 1. Това е и първото решение, което е написал Жоро.

Втората му идея (с set) не успявам да си я представя при вариант, в който числото се среща повече от 2 пъти (при първата среща го добавяме в set-a, при втората - го махаме и при третата ще го добавим отново, защото нямаме знанието, че вече е срещано), но сигурно отново изпускам нещо. :)

 

ЕDIT 2:

В някои случаи (входни данни, които не са числа или пък числа, по-големи от size_t или при широк диапазон на входните данни, но малко на брой уникални стойности, комбинирано с ограниение в паметта), може използването на map вместо масив да е по-подходящото решение.

1
09/12/2017 22:55:13
Jovanna avatar Jovanna 186 Точки

Пробвах с bitset, не ми минаха половината тестове, Жоро е сложил перфектните ограничения за памет (и бързодействие).

На половината тестове гърми, защото трябва да направиш променлива std::bitset<32> resultBinaryEcsclusiveOr заради fffff - с 5 символна последователност най-дългото binarno представяне е 20 нули/единици;

Може би тук ще върви подсказката , че половината от тестовете са с малки числа, до 10000, което е 16 броя 0/1 и ще стане с std::bitset<16>, + една проверка числото дали е <= 10000, едно switch-че , еднакъв код два пъти, с единствена разлика обема на bitset променливата.

Незнам в подробности как се работи с bitset, за това което правя чета в нета, може и да бъркам?

Ще го учим ли?

0
MartinBG avatar MartinBG 4803 Точки

Моето решение с bitset минава в Judge с тези резултати:

Memory: 1.96 MB 
Time: 0.642 s

Сета ми е с тези параметри:

const int MAX_DNA_TYPES = 0xFFFFF;

int main()
{
    std::bitset<MAX_DNA_TYPES> uniqueDNA;
...
}

 

1
MartinBG avatar MartinBG 4803 Точки

Ето решението ми с bitset, в случай, че все още представлява интерес.

(линка ще expire-не след 1 месец).

0
kolioi avatar kolioi 641 Точки

Ето няколко различни решения и от мен. Имайте предвид, че Джадж дава различно време за изпълнение, често разликата е до няколко милисекунди. Освен това се показват само на-големите стойности за памет и време от всичките тестове. За тази задача най-бавен е последния тест, където входните данни са около 10 МВ.

решение с unordered_map Memory: 14.89 MB Time : 1.570 s

решение с четене символ по символ Memory: 1.76 MB Time : 0.388 s

и две решения с различна дължина на буфера

https://pastebin.com/e2Uy8h8r Memory: 1.54 MB Time: 0.079 s

https://pastebin.com/k8iDdjdz Memory: 1.52 MB Time : 0.073 s

 

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