May 2023
1 / 19
May 2023
May 2023
yula
May '23

Rozpatrujemy kwadratowe macierze o elementach będących pojedynczymi literami alfabetu
(‘a’… ‘z’, ‘A’… ‘Z’). Definiujemy następujący zestaw operacji (macierz wejściowa to A, a wynikowa – B, obie o rozmiarach nn):
 T – transpozycja względem głównej przekątnej: Bj, i = Ai, j
 D – transpozycja względem drugiej przekątnej: Bn-j+1, n-i+1 = Ai, j
 H – odbicie poziome (względem osi pionowej): Bi, n-j+1 = Ai, j
 V – odbicie pionowe (względem osi poziomej): Bn-i+1, j = Ai, j
 A – obrót w prawo o 90°: Bj, n-i+1 = Ai, j
 B – obrót w prawo o 180°
 C – obrót w prawo o 270°
 X – obrót w lewo o 90°: Bn-j+1, i = Ai, j
 Y – obrót w lewo o 180°
 Z – obrót w lewo o 270°
dla i, j {1, 2,…, n}
Zadanie
Napisz program, który dla danej macierzy wyjściowej obliczy rezultat złożenia nie więcej niż
100 000 powyższych operacji.
Wejście
Standardowe wejście zawiera zestaw testów. Pierwszy wiersz wejścia zawiera jedną liczbę D
(0 < D < 20) określającą liczbę testów. Kolejne wiersze zawierają dane związane z testami. W
pierwszym wierszu każdego testu występuje zawsze jedna liczba n określająca rozmiary macierzy (liczba wierszy = liczba kolumn = n; 0 < n ≤ 300; wartości n w kolejnych testach mogą
być różne). Kolejne n wierszy zawiera po n liter (bez odstępów) będących elementami wejściowej macierzy. Ostatni wiersz testu zawiera ciąg operacji do wykonania zapisany przy pomocy
ciągu znaków podanych przy ich definicjach powyżej. Ciąg ten jest zakończony znakiem ’&’
(bez apostrofów). Operacje powinny być wykonane w kolejności od lewej do prawej.
Wyjście
Każdemu testowi powinna odpowiadać w standardowym wyjściu macierz uzyskana w wyniku
wykonania ciągu zadanych operacji. Format wyprowadzonej macierzy powinien być taki sam,
jak w danych wejściowych, tzn. n wierszy po n znaków (bez spacji).

moje rozwiązanie https://ideone.com/gjH43h5 , chyba poprawne jak coś nie zepsułam, ale dużo za wolne dla większych danych. Jak można przyśpieszyć?

  • created

    May '23

  • last reply

    May '23
  • 18

    replies

  • 394

    views

  • 7

    users

  • 6

    likes

  • 2

    links

quenthui
May '23

Jeśli dobrze rozumiem, to dla całej sekwencji wykonujesz kolejne operacje na całej macierzy, co daje złożoność O(NxNxm).

Tak myślę, czy nie będzie szybciej wziąć każdy element oddzielnie i na nim wykonywać kolejne operacje. Dzięki temu unikasz skakania po tablicy, jedynie modyfikując indeksy. Nie zmienia to złożoności, ale może się szybciej wykonywać.

Powyższe podejście prowadzi do kolejnego rozwiązania: Weź skrajne elementy: (0, 0), (0, N-1), (N-1, 0), (N-1, N-1) i dla nich przeprowadź wszystkie operacje. Zobacz, gdzie wylądują w końcowej macierzy.
Zastanów się teraz, jakie są możliwe końcowe pozycje.
Znając położenie czterech narożników, jesteś w stanie wywnioskować układ całej wynikowej macierzy (położenie elementów względem siebie nie zmienia się. Może powstać co najwyżej lustrzane odbicie).
W ten sposób schodzisz do rozwiązania O(m + NxN), czyli O(m).

Co o tym myślisz? Swoją drogą bardzo fajne zadanie :+1:

yula
May '23

eeee… nie bardzo widzę jak można operować tylko na wierzchołkach… Jak widać w kodzie myślałam o sumowaniu obrotów i zmniejszaniu ilości operacji bo poza obrotami każda razy dwa wraca do początku

quenthui
May '23

Zaczynasz od wierzchołka (0, 0) i na nim wykonujesz kolejne operacje. Transpozycja względem głównej daje wierzchołek (N-1, N-1). Potem kolejny obrót o 90 w lewo to (0, N-1) itd. Po wszystkich operacjach masz nową pozycje elementu (0, 0).
Potem bierzesz element (0, 1) i powtarzasz całą procedurę.
Złożoność ta sama, ale przy maksymalnym rozmiarze macierzy, może mieć znaczenie.

quenthui
May '23

Ale jak się zastanowisz, co się dzieje z elementami podczas tych obrotów, to okaże się, że potrzebujesz sprawdzić tylko dwa (nawet nie 4, jak pisałem wcześniej) elementy, które powiedzą ci, jaka jest orientacja końcowej macierzy. Położenie reszty elementów można już z tego wywnioskować.
Tylko jedna uwaga, wybrane elementy powinny być z tego samego wiersza, albo tej samej kolumny.

yula
May '23

Obroty to prosto, ale reszta jednak miesza środek , i jak po wierzchołkach odzyskać całą macierz?

m_labanowicz
May '23

Jakby tak rozpatrzyc tylko macierz 4x4, ktora ma wydzielone grupy, ktore mozna “zamapowac” do tej oryginalnej:

| a b c d |
| e f g h |
| i j k l |
| m n o p |

Wtedy może po tych wszystkich operacjach bedzie mozna stwierdzic, gdzie i w jaki sposob dana grupa "wylądowała’.

yula
May '23

Tam są maksymalne rozmiary 300x300… Głowa zaraz wybuchnie…

quenthui
May '23

Własnie, że nie miesza. Wyobraź sobie, że macierz to prześwitująca kartka papieru z obrazkiem. Jakbyś go nie obracała i przekładała na drugą stronę, obrazek pozostanie ten sam (co najwyżej jego lustrzane odbicie).

Wyobraź sobie, że na obrazku masz strzałkę (skierowaną do dołu) w lewym górnym rogu, która wskazuje kierunek wypisywania wierszy.
Po wszystkich transformacjach, strzałka może znajdować się w jednym z 4 rogów i wskazywać kierunek poziomy lub pionowy. I to będzie kierunek rysowania macierzy. Masz tylko 8 przypadków, które musisz na koniec sprawdzić.

Strzałką może być to, co wcześniej pisałem. Bierzesz elementy: (0,0) i (1,0) - lewy górny róg i element pod nim. Na obu elementach wykonujesz wszystkie przekształcenia, sprawdzasz ich końcowe położenie i względem nich rysujesz całą macierz.

Przyjrzyj się wynikowym macierzom, które generuje Twoje rozwiązanie.

narbej
May '23

Powinny? Ale nie muszą?
Jeżeli tak, to może posortować je, pozsumować, skrócić itd…

yula
May '23

tu raczej oznacza że muszą (wynik ma być taki), chyba że czegoś nie zauważyłam, skracanie co wymyśliłam to wyżej pisałam, (sumowanie obrotów i podwójne inne)

narbej
May '23
1

Może się mylę, jestem w pracy… Czy obrót, transpozycja, obrót, to pewnie nie to samo co obrót, obrót, transpozycja?

Ps
Ale pomysł z “wzorcową” macierzą 4x4 wydaje mi się sensowny.

Ps 2
A to zadanie jest na jakimś portalu?

pawoj20
May '23

obrót, odbicie lustrzane poziome, obrót
nie jest tym samym co
obrót, obrót, odbicie lustrzane poziome.
Gdy obroty są jeden po drugim można je sumowac.

yula
May '23
narbej

Niestety nie na portalu, przynajmniej ja mam nie z portalu. Chyba dzięki odpowiedziom mam pomysł jak zrobić . Jutro spróbuję doprowadzić do ładu, bo dziś gdzieś sie machnęłam, i potestuje czy dobrze myślę :slight_smile:

hipcia
May '23
quenthui

Idąc krok dalej nie ma potrzeby modyfikowania ani jednego elementu macierzy. Wszystkie osiem końcowych pozycji można utworzyć przez zamianę zakresów pętli, lub samych indeksów:

#include <iostream>
#include <numeric>
#include <string>

struct Matrix {
	int n = 3;
	std::string data;
public:
	Matrix() :data(n * n, ' ') {
		std::iota(data.begin(), data.end(), 'a');
	}

	void show(int k) const {
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				int idx = access(i, j, k);
				std::cout << data[idx] << " ";
			}
			std::cout << "\n";
		}
		std::cout << std::string(5, '-') << "\n";
	}

protected:
	int access(int i, int j, int k) const {     
		// A[i][j] - origin
		// A[j][i] - T
		// A[i][n - j - 1] - H
		// A[j][n - i - 1] - C, X
		// A[n - i - 1][j] - V
		// A[n - j - 1][i] - A, Z
		// A[n - j - 1][n - i - 1] - D
		// A[n - i - 1][n - j - 1] - B, Y

		bool flip_x  = (k >> 0) & 1;
		bool flip_y  = (k >> 1) & 1;
		bool flip_xy = (k >> 2) & 1;

		if (flip_x)
			i = n - i - 1;
		if (flip_y)
			j = n - j - 1;
		if (flip_xy)
			std::swap(i, j);
		return i * n + j;
	}
};

int main() {
	Matrix m;
	for (int i = 0; i < 8; ++i) {
		m.show(i);
	}
}

Każda zamiana może być nanoszona na kolejną np:

...
	void vertical_reflection() {
		flip_x = !flip_x;
	}

	void horizontal_reflection() {
		flip_y = !flip_y;
	}

    void transpose_first_diagonal() {
		flip_xy = !flip_xy;
		std::swap(flip_x, flip_y);
	}
...

switch (move) {
case 'A': rotate90(); break;
case 'C': reverse_rotate90(); break;
case 'X': reverse_rotate90(); break;
case 'Z': rotate90(); break;

case 'Y':
case 'B': rotate180(); break;

case 'T': transpose_first_diagonal(); break;
case 'D': transpose_second_diagonal(); break;
case 'H': horizontal_reflection(); break;
case 'V': vertical_reflection(); break;
}
...
korkirw
May '23

No, trochę atramentu na to poszło… : Chyba sobie kiedyś spokojnie usiądę i przeanalizuję Twój kod

yula
May '23

Ja już widzę że można sporo skrócić, sporo nadmiaru, ale w tej chwili nie mam siły na to patrzeć :slight_smile: A i tam analize robi krok po kroku przekształcenia macierzy, analiza - próbuję skracać ale afekty słabe. No i poszczególne funkcje przekształcania, też parę nadmiarowych i nie wyrzuconych…