Dwuwymiarowe żabki - szkopuł

Question

Witam, 

Ostatnio chciałem sobie porobić zadania bardziej "do pomyślenia", zrobiłem kilka i utknąłem na zadaniu "Dwuwymiarowe żabki". https://szkopul.edu.pl/problemset/problem/jhX8ocY37sY3QxmzJLwFrWC1/site/?key=statement

Oto kod:

#include <iostream>

struct Ab {
	Ab()
	{

	}

	Ab(unsigned long int a, unsigned long int b) : a(a), b(b)
	{

	}

public:
	unsigned long int a;
	unsigned long int b;
};

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

	Ab* dimensions = new Ab[n];
	for (int i = 0; i < n; i++) {
		unsigned long int a, b;
		std::cin >> a >> b;

		dimensions[i] = Ab(a, b);
	}

	for (int i = 0; i < n; i++) {
		Ab dim = dimensions[i];
		if (dim.a == dim.b) {
			std::cout << 1 << std::endl;
			continue;
		}

		int count = 1;
		while (dim.a != dim.b) {
			if (dim.a > dim.b) {
				std::swap(dim.a, dim.b);
			}

			dim.b -= dim.a;
			count++;
		}

		std::cout << count << std::endl;
	}

	return 0;
}

Zalicza mi wszystkie testy oprócz dwóch ostatnich:

Pojęcia nie mam czemu tak się dzieje - co powoduje problem w tym kodzie?

Answer 1

1) integer overflow. Wynik może być rzędu 1e18 co nie zmieści się w int.

2) algorytm jest za wolny. Może wykonać nawet 1e18 kroków

Comments

Myślałem, że long int to już jest int64. Zrobiłem long long i overflow rzeczywiście nie ma, ale algorytm tak jak mówisz jest za wolny. Ale jak niby mam go przyśpieszyć? Muszę przecież policzyć to dla każdego elementu, więc złożoność musi być liniowa w zależności od n (w rzeczywistości nawet gorzej, bo nie wiadomo ile razy będziemy szukać kwadratów dla każdego n-tego elementu). Zawsze to była dla mnie czarna magia, jak mógłbym algorytm który coś robi dla wszystkich elementów przerobić, żeby robił to w mniejszej ilości kroków. Jedyne rozwiązanie aby przyśpieszyć ten program które przychodzi mi do głowy, to żeby zrobić coś jak parallel loop, ale nie potrafię tego zrobić w C++, a poza tym nie zmienia to złożoności. Jak Ty byś zmodyfikował ten kod?

---

To czym jest long zależy od systemu. Kluczowa obserwacja jest taka, że ten algorytm zachowuje się podobnie jak algorytm Euklidesa.

---

Rozrysowałem sobie wszystkie kwadraty i prostokąty dla 5 i 3, ale ciągle nie widzę jak tu zastosować nwd. Rzeczywiście, widzę, że te algorytmy są podobne i teoretycznie możnaby użyć tej optymalniejszej wersji z modulo, ale jakoś mi się to nie "skleja" w głowie.

---

No właśnie ta wersja z modulo. Ona jest tu potrzebna. Tylko jak?

---

Dobre pytanie. Kombinowałem żeby sumować nwd ale wyniki wychodziły dobre tylko dla 1 testu. Nie tworzy mi się w głowie żaden ciąg przyczynowo-skutkowy który doprowadziłby mnie do tego jak zastosować te nwd :/

---

Nie patrz na wynik algorytmu Euklidesa tylko jak jest zaimplementowany. Co zmienia skorzystanie z modulo w porównaniu ze standardową wersją tego algorytmu, gdzie się tylko odejmuje?

---

Będzie wykonywane mniej operacji. Rozumiem, że warunek w pętli while zmieni się na dim.b!=0, wnętrze zmieni się żeby odpowiadać wersji z modulo, ale co mam zliczać w takiej sytuacji? Przebiegi pętli nie będą dobrą odpowiedzią jak w przypadku odejmowania.

---

Musisz zrozumieć dlaczego ta wersja z modulo działa. Dlaczego zmiana odejmowania na modulo przyspiesza algorytm. Gdzie jest ta oszczędność?

---

No pętla wykona się mniej razy - szybciej znajdziemy nwd (bo w sumie do tego się sprowadza rozwiązanie). Tu jest oszczędność. Moje rozumowanie było żeby uzyskiwać kolejne prostokąty, i dopóki je uzyskujemy to możemy zwiększać licznik. Ale podejście z modulo niszczy to rozumowanie i kompletnie nie pojmuje jak do tego podejść. Bo po prostu nie przejdę przez wszystkie możliwe prostokąty. Próbowałem już nawet wszystkich kombinacji liczb które uzyskuje przy użyciu modulo, taki troche brute force xD. Patrzyłem na wszelkie zależności między liczbami, może jakieś operacje na tych wynikach należałoby zrobić i nic nie widzę. Może przedstawiłbyś swój tok myślenia?

---

hint: a = floor(a / b) * b + a % b

A w algorytmie Euklidesa w pętli masz a = a % b

---

Bardziej chodziło mi o wyjaśnienie zasady działania, z czego to wynika. Widzę, że dzielisz przez siebie dwa boki prostokąta i mnożysz przez jeden z boków. I dodać resztę z dzielenia tych boków. Ale z czego taka operacja wynika? Chciałbym poznać ciąg rozumowania (od początku do końca) który do takich wniosków prowadzi. Bo mój rozumek jest zbyt tępy żeby samemu do tego dojść.

---

Mogę powiedzieć na czym polega rozwiązanie, ale czy rozumiesz dlaczego powyższy wzór wgl działa?

---

Poza tym, że zadziała, i że zrobi to obojętnie czy a>b czy b>a, to nie rozumiem dlaczego tak jest. Ale myślę, że gdybym prześledził rozwiązanie (na czym polega) to mnie oświeci.

---

floor(a / b) mówi ile razy b mieści się w a.  Czyli w a mamy floor(a / b) pełnych b, ale do pełnego a brakuje a - floor(a / b) * b, co zdefiniowane jest jako a % b. Zatem:

a - floor(a / b) * b = a % b

a = floor(a / b) * b + a % b

Teraz jeden krok w algorytmie Euklidesa (tym wolniejszym) polegał na odjęciu mniejszej liczby od większej. Bez strat ogólności załóżmy a > b. Ale co jeśli np.  a = 11, b = 2? Będziemy robić:

a = 11 - 2 = 9, b = 2

a = 9 - 2 = 7, b = 2

...

Widać, że tych odejmowań jest dużo. A co jeśli skompresować te odejmowania do jednego kroku? Możemy skorzystać z tego, ze umiemy też dzielić i mnożyć. Skoro w 11 mieści się floor(11 / 2) = 5 dwójek, to odejmijmy 5 dwójek w jednym kroku, zamiast odejmować jedną dwójkę w 5 krokach. Co dostaniemy jak odejmiemy wszytkie dwójki? 11 % 2, czyli 1. Teraz możemy zmienić a z b, czyli a = 2, b = 1 i powtarzamy.

Widać, że wykonalismy tak naprawdę operację a' = b,  b' = a % b, Co więcej wykonalismy ją w jednym kroku, co znacznie przyspiesza algorytm.

Do rozwiązania zadania wystarczy zauważyć, że trzeba sumować floor(a / b)

---

Przespałem się i teraz to aż wstyd za tą tępote xD Ale przynajmniej teraz rozumiem, wielkie dzięki!