[JA 3 - Task 4] Message - Софтуерен университет

m.nikolov97 25 Точки

[JA 3 - Task 4] Message

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

Въпросът ми е относно 4-тата задача от Judge Assignment 3 - Message.

Не знам защо, но напоследък все по-често ми се случва да издокарвам решението на задачите, но само според моя компютър/компилатор. Щом предам в Judge, ми става лошо.

Този случай е подобен. Мислех си, че съм решил задачката (поне логически) правилно, но получавам 20/100 на тестовете в Judge. Тъй като има само един примерен input/output в условието, пробвах други варианти, за да тествам, поиграх си с дебъгера, но отново не намерих къде съм сгрешил. Паметта, използвана за програмата е 1.90 MB, а времето за компилиране е 0.015 секунди, което ме навежда на мисълта, че проблемът не е в опитимизацията на кода ми, а по-скоро в логиката..

Моля, ако някой има възможност, да ми даде съвет какво да направя. Ето и кодът ми, сложил съм и кометнари (извинявам се, ако има грешки в тях - английският ми не е много добър): https://pastebin.com/DYgAV9qb.

Благодаря ви за отделеното време!

Тагове:

04/11/2019 18:00:28 C++ Fundamentals

MartinBG 4803 Точки

Best Answer

На пръв поглед виждам, че ще прочетеш "." като валидна дума и ще добавиш "." в списъка с входните думи.

Опитай да ги прочетеш по този начин:

std::unordered_map<std::string, int> words; // нямаме нужда от сортировка -> unordered_map

std::string word;
while (std::cin >> word && word != ".") {
  words[word]++;
}

Или просто направи проверка дали думатa не е ".", преди да я добавиш:

if (words.find(result) == words.end()) {
  if(result != ".") {
    words.insert (pair <string, int> {result, 1});
  }
} else {
  words[result]++;
}

За да вземеш елемент на конкретен "индекс" в set, може да използваш advance:

std::set<int> mySet{ 1, 2, 3 };
auto it = mySet.begin();
std::advance(it, 1); // it сочи към вторият елемент в сета (т.е. 2)

05/11/2019 01:08:08 05/11/2019 01:10:19

dmartinov 37 Точки

Според мен подхода с map не е погрешен. Да, map-а е по-бавен от unordered_map, но пък освен "брояч" печелиш и лексикографска подредба още от самото начало. Това спестява доста от if проверките и set-a, които правиш по-надолу, a те сами по себе си са предпоставка за забавяне. Ето моето решение, в което използвам map: https://pastebin.com/nKscE4EC

Резултата от този код е Memory: 1.89 MB, Time: 0.015 s

05/11/2019 12:04:26

MartinBG 4803 Точки

Има много решения на конкретната задача, както и варианти с различни контейнери. Като правило се използва този контейнер, който най-добре обслужва конкретното решение. В случая не става дума толкова за performance, колкото за ясно комуникиране на идеята ни и за улесняване четенето на кода (ако видя map, очаквам подредбата да е ключова за конкретното решение).

05/11/2019 14:20:33 05/11/2019 14:23:47

galin_kostadinov 166 Точки

Привет!

1. В първата част на задачата трябва да не добавяш точка, за целта:

if (result == ".") {
    break;
}

- в случая по-удобно би било да четеш директно от конзолата, както предлага MartinBG, ти имаш отделена от думите точка, така че когато я достигнеш спираш да четеш.

- иначе ако имаш само спейсове и ти се налага да вземеш целия ред, то по добре да си направиш

istringstream iss(input);

2. В следвата част на решението отдели логиката за трупането на думите отговарящи на зададената бройка от добадянето на думата в резултатната колекция, отговаряща на дадения индекс.

set<string> tempWords;

Те не зависят една от друга. А така или иначе чакаш да стигнеш до края на колекцията:

if (it == words.end()){...}

3. Тъй като резултата го колекционираш и го печаташ накрая, то същато трябва да напарвиш и с ".". В момента думите ги печаташ накрая, а точките веднага. Просто ги добави в резултатната колекция вместо да ги печаташ при проверката.

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

Поздрави!

05/11/2019 21:36:32 05/11/2019 22:02:40

m.nikolov97 25 Точки

Благодаря на всички колеги за помощта, коригирах си решението, като използвах съвети от всички коментари. Ако можех щях да дам точки на всички, но не ми достига 1 точка, за да мога да гласувам 😁

06/11/2019 13:49:50