Drzewo Sterna-Brocota - szkopuł

Question

Witam.

Chciałem rozwiązać zadanie: https://szkopul.edu.pl/problemset/problem/zFA7joqxZZ9lbwA0FoqjmZwP/site/?key=submissions

I to jest mój kod:

#include <iostream>
#include <vector>
#include <string>

std::pair<uint32_t, uint32_t> read_fraction(const std::string& fraction) {
	uint32_t i = 0;
	uint32_t nominator = 0;
	while (fraction[i] != '/') {
		nominator = nominator * 10 + (fraction[i] - '0');
		i++;
	}

	// Omit the '/'
	i++;

	uint32_t denominator = 0;
	while (i < fraction.size()) {
		denominator = denominator * 10 + (fraction[i] - '0');
		i++;
	}

	return std::make_pair(nominator, denominator);
}

int main()
{
	uint32_t n;
	std::cin >> n;

	std::vector<std::string> level{"0/1", "1/0"};
	std::vector<std::string> next_level(3);
	for (uint32_t i = 0; i < n; i++) {
		uint32_t added = 0;
		for (uint32_t j = 0; j < level.size() - 1; j++) {
			next_level[j + added] = level[j];

			std::pair<uint32_t, uint32_t> left = read_fraction(level[j]);
			std::pair<uint32_t, uint32_t> right = read_fraction(level[j + 1]);

			std::string result = std::to_string(left.first + right.first) + "/" + std::to_string(left.second + right.second);
			next_level[j + added + 1] = result;
			added++;
		}

		next_level[level.size() - 1 + added] = level[level.size() - 1];
		level = next_level;
		next_level.erase(next_level.begin(), next_level.end());
		next_level.resize(level.size() * 2 - 1);
	}

	for (const std::string& fraction : level)
		std::cout << fraction << " ";

	return 0;
}

Ale niestety nie mogę zaliczyć ostatniego testu, bo zużywam zbyt dużo pamięci. Właściwie zauważyłem że wystarczy około 5s i już zużywam 400mb. Przechowuję tylko ostatni level i kolejny, żeby właśnie tej pamięci oszczędzić. Co tu mogę jeszcze poprawić, żeby zaliczyć na 100?

W tagach zadania wskazane jest użycie rekurencji - ale czy to tylko nie pogorszy problemu z pamięcią? Poza tym takie rozwiązanie wydaje mi się trudniejsze

Comments

Jakąś wizję już mam, ale po 1. nie mam kompletnie pomysłu na przypadek podstawowy, a po 2. w którym momencie mogę wypisać ułamek? https://pastebin.com/R4dGGBnp

Jeśli w ogóle będę w którymś momencie wypisywał któryś ułamek - to zawsze będą duplikaty (jeśli dobrze myślę). A czy w ogóle podejście jest dobre? Najpierw liczę wszystkie ułamki dla lewego i potem wszystkie dla lewego i tego nowo powstałego, a potem tak samo dla prawego.

---

1. Spójrz na liczbe n i co ona oznacza

2. Podejście jest dobre. Spójrz na kod który wysłałem wczesniej on dokładnie rozwiązuje ten problem

---

Ok, mam takie coś: https://pastebin.com/Ki3Sr1nX

Oczywiście nie działa. Mój max który konstruuje w main mówi ile elementów musi się znaleźć w ostatnim levelu drzewa.

Rozumiem, że po 1 jest problem z synchronizacją tego count (ta gałąź która pójdzie na lewo i na prawo się nie dogadują, jakby liczone jest dwa razy więcej niż potrzeba jeśli dobrze myślę). Ale jest też jakiś inny problem, bo nawet jak zrobiłem count jako zmienną globalną to i tak źle działało.

---

Jest dobrze tylko max jest za duży. To nie powinna być liczba elementów na levelu

---

Aha. Zrobiłem max jako n i działa. Jeszcze nie kumam czemu ale jak rozrysuje to może się dowiem.

Answer 1

#include <iostream>
#include <vector>
#include <string>
 
std::pair<uint32_t, uint32_t> read_fraction(const std::string& fraction) {
    uint32_t i = 0;
    uint32_t nominator = 0;
    while (fraction[i] != '/') {
        nominator = nominator * 10 + (fraction[i] - '0');
        i++;
    }
 
    // Omit the '/'
    i++;
 
    uint32_t denominator = 0;
    while (i < fraction.size()) {
        denominator = denominator * 10 + (fraction[i] - '0');
        i++;
    }
 
    return std::make_pair(nominator, denominator);
}
 
int main()
{
    uint32_t n;
    std::cin >> n;
 
    std::vector<std::string> level{"0/1", "1/0"};
 
    for (uint32_t i = 0; i < n; i++) {
        std::vector<std::string> next_level(level.size() * 2 - 1);
        uint32_t added = 0;
 
        for (uint32_t j = 0; j < level.size() - 1; j++) {
            next_level[j + added] = level[j];
 
            std::pair<uint32_t, uint32_t> left = read_fraction(level[j]);
            std::pair<uint32_t, uint32_t> right = read_fraction(level[j + 1]);
 
            std::string result = std::to_string(left.first + right.first) + "/" + std::to_string(left.second + right.second);
            next_level[j + added + 1] = result;
            added++;
        }
 
        next_level[level.size() - 1 + added] = level[level.size() - 1];
        level = std::move(next_level);
    }
 
    for (const std::string& fraction : level)
        std::cout << fraction << " ";
 
    return 0;
}

1. Zamiast tworzyć kopię wektora next_level, użyłem semantyki przenoszenia (std::move) do przeniesienia zawartości next_level do level. Działa to szybciej i zużywa mniej pamięci.
   
   pozdrawiam

Answer 2

Hmm, czemu w vectorach przechowujesz stringi, po czym z powrotem rozpakowujesz je do pary?

Na intuicję, przechowywanie par w vectorach i wyrzucenie stringów powinno poprawić zużycie pamięci (i czas) dobrych kilka razy.

Comments

Nie wiem czemu, chyba zamknąłem się w jakiejś dziwnej bańce podczas pisania xD. Czas jest sporo krótszy, zużycie pamięci też, ale to wciąż za mało dla ostatniego testu. Tak to wygląda obecnie: https://pastebin.com/gvHrbm1a