4800. Kod Graya [WI_GRAY]

[qazwer_sof]

Mam do was pytanie, dlaczego mój program dostaje jedynie 70 punktów za to zadanie? Błąd w algorytmie? Działa za wolno? Zły zakres zmiennych? Czy może jeszcze coś innego?

#include <iostream>
using namespace std;
int main()
{
	unsigned long long int m, n, x, y, *bin;
	cin>> n >> m;
	bin = new unsigned long long int [n];
	for(unsigned long long int i = 0; i < n; i++) bin[i] = 0;
	y = m >> 1;
	x = m ^ y;
	if(x == 0)
	{
		for(unsigned long long int i = 0; i < n; i++) cout << 0;
	}
	else
	{	
		for(unsigned long long int i = 0; x > 0; i++, x /= 2) bin[i] = x % 2;
		for(unsigned long long int i = n; i > 0; i--) cout << bin[i - 1];
	}
	cout << endl;
	return 0;
}

[mnbvcx]

(m: m >= 0 i m < 2^32000)

unsigned long long int m;

U ciebie maksymalne m to 2^64-1.

[Spykaj]

Tutaj potrzebna jest arytmetyka dużych liczb

[narbej]

1. Tak uzyskałem 100 pkt.
2. Konwersję na binarną robie "tradycyjnie" raczej wolno [może można szybciej], więc na pewno nie bezpośrednio z dziesiętnego na greya.
3. Być może z moich wcześniejszych wypowiedzi wywnioskowałeś, że istnieje inna metoda? Możliwe, ale teraz zaglądnąłem do swojego kodu i jednak nie, ja mam "tradycyjnie".

[hipcia]

Link do zadania: https://pl.spoj.com/problems/WI_GRAY/
Wynik: 80

Co powinienem uwzględnić żeby uzyskać maksymalny wynik?

[yula]

mam 90 pkt w tym zadaniu. Jakiś pomysł w czym może być problem? Typ int chyba wystarczy ? Robię “recznie” zamianę na binarny i XOR…

[narbej]

nie jestem pewny, ale chyba nie. Ile btiów ma typ int? A ile potrzeba maksymalnie w zadaniu?

Może trochę inaczej. Do zapamiętania liczby 32000, typ int w zupełności wystarczy. Do zapamiętania 32000 pojedyńczych, niezależnych bitów, niestety nie wystarczy.

[yula]

liczbę n pobieram do inta. m pobieram do stringa lub znak po znaku i wstawiam w tablicę intów o długosci 33000… operacje zamiany na binarny są ręczne na tej tablicy. Jest 90 pkt więc większość jest dobrze i zastanawiam sie na czym może sie wykładać…

[narbej]

Nie zrozumiałem Cię, gdy napisałaś, że “typ int chyba wystarczy”. może więc kod się nie wykłada, tylko dla największego testu ma TLE?

Bo swoją drogą po co robisz ręcznie, jak możesz maszynowo - komputerowo? Oczywiście żartuję. Może po prostu pokaż co robisz, a jak nie chcesz na forum to chociaż mi prywatnie, bo tak to ciężko cokolwiek więcej powiedzieć.

Pozdrawiam Cię ciepło i miłego endu weekendu

[yula]

a to jest trop (to TLE) właśnie sprawdziłam i dla wyniku 32200 wykonuje sie ok. 0,7- 0.8 sek na Ideonie…

Miłego weekendu również

[narbej]

A dla 2^32000 sprawdzałaś? https://www.wolframalpha.com/input/?i=2^32000
Jeżeli to problem z TLE, to czy masz “usprawnione”- szybsze wczytywanie?
Ja użyłem czegoś mniejszego niż int, tzn tablicy char, ale pewnie lepiej, z punktu czytelności kodu - użyć tablicy bool, które są od “środka” tym samym. Do tego zadania właściwa byłaby tablica bitów, ale takiej praktycznie nie ma - bo jeśli jest to jest mniej efektywna.

[testowyhkktr]

@narbej witam, czy mógłbyś podpowiedzieć w jaki sposób konwertować efektywnie podaną liczbę na wejściu na liczbę binarną? Obecnie mam wynik 80, ponieważ odpadam na dużych liczbach (mimo, że korzystam z własnego ala BigInta).

[narbej]

Spróbuję coś napisać dziś po pracy albo w weefend. W między czasie odpowiedz mi na pytania: W jaki sposób będziesz sprawdzał czy idziesz w dobrym kierunku? Czy przeczytałeś i przemyślałeś ten cały wątek? Czy twój kod jest w miarę “czysty”?

Zanim odpowiesz, zastanów się dobrze, masz trochę czasu.

[testowyhkktr]

Wydaje mi się, że rozumiem algorytm obliczania kodu Graya, w czym pomógł mi ten wątek.

Obecnie mój kod jest w pełni czytelny, lecz niezbyt wydajny. Kroki postępowania: podaną liczbę m wczytuję jako BigInt (wykorzystywałem go do zadań związanych z arytmetyką dużych liczb i całkiem sobie radzi), a następnie konwertuję na liczbę binarną (tutaj jest moje wąskie gardło, pole do optymalizacji). Mając liczbę m w postaci binarnej mogę od razu przejść do działania XOR (wykorzystując to, że dzielenie przez 2 to po prostu przesunięcie bitów w prawą stronę, więc nawet nie ma potrzeby wykorzystywania dodatkowej zmiennej z podzielonym m). XOR obliczam prawidłowo, w czasie O(n), wydaje mi się, że tutaj wszystko jest w porządku. Wynik działania wypisuje na standardowe wyjście. Wykorzystuje język C++ z optymalizacją strumienii wejścia/wyjścia.

Wydaje mi się, że problemem jest przekształcanie liczby na system binarny, chyba, że jest całkiem inny sposób na całe zadanie Sprawdzać czy idę w dobrym kierunku mogę przez konwertowanie liczby 2^32’000 - 1 na binarną, która jest końcem przedziału wejścia (składa się z 32’000 bitów, same jedynki). U mnie przekształcanie takiej liczby trwa tragicznie długo, zostawiłem komputer w tle i po czasie obliczyło, ale nie na tym to polega Będę wdzięczny jeśli dasz jakąś podpowiedź, bo obecnie jestem w kropce.

[narbej]

Sposób obliczania liczby-kodu graya opisany jest w zadaniu, w tym wątku, są jakieś podpowiedzi jak to zoptymalizować, czyż nie?

W dobrym kierunku - chodziło mi, jak sprawdzisz, czy twój nowy kod jest lepszy - szybszy od poprzedniego. Bo jeżeli zostawiasz komputer, to jak sprawdzasz różnicę czasów między pierwszą wersją a drugą? Jedna kawa, przy drugim, a trzy kawy przy pierwszym? Musisz powinieneś wykonywać pomiar czasu wykonania się programu!! Inaczej jak ocenisz ten aspekt - szybkość poszczególnych wersji? Jeżeli program wykonuje się tak długo, to na początku dobierz i testuj na mniejszym, ale nie za małym teście. Jak mierzyć czas? Jak nie wiesz, to rób to np na ideon, “wkładając” dobrany, odpowiedniej wielkości test. Jeżeli za mały, będziesz miał zawsze time = 0, jeżeli za duży timelimit.

W tym zadaniu BigInt, który jest dobre do innych zadań, jest niepotrzebne. Wczytujesz liczbę jako string, konwertujesz na postać binarną robisz xor i wypisujesz.

Czy dla xor, potrzebujesz dwóch liczb [dwóch stringów]
Czy możesz to zrobić “w miejscu” na jednym stringu, poruszając się w odpowiednim kierunku!?

A może, ewentualnie odpuść sobie na razie, a jak nabierzesz wprawy wróc do tego zadania?

PS
Czysty kod. Warto wiedzieć, że istnieja takie cuś i starać się do niego dążyć - do pisania czystego kodu [Clean Code]

PS 2
Możliwe, z twojego opisu wygląda, że właśnie tak robisz xor

PS 3
Można być może, zapisać liczę binarną in reverse - jeżeli to pomoże. Powinienem w końcu zaglądnąć do mojego starego i brzydkiego [not clean] kodu i go wyczyśćić i poprawić Ale z drugiej strony, skoro jest już dostępny “na świecie” C++20, a na spoju ciągle "tylko C++14, [w tym zadaniu nawet nie], to czy warto się w to angażować? Możesz zawsze [po]prosić adminów, aby coś z tym w tym kierunku [z]robili! Mi na tym nie zależy.

[testowyhkktr]

Dziękuję za podpowiedzi. Zapomniałem dodać, że metody porównuje oczywiście mierząc czas W takim razie wąskim gardłem u mnie jest konwersja na postać binarną. Operację XOR robię tak jak mówisz, na jednym stringu uwzględniając shift w prawo.

W jaki sposób następuje konwersja bezpośrednio ze stringa na liczbę binarną? Istnieje na to jakiś trik? Przeglądam internet i jedyną metodą wydaje się dzielenie przez 2 i zapisywanie reszty (co na stringu odpada + nie jest efektywne) lub odejmowanie co raz to niższych potęg 2 (co też w stringu nam odpada) .
Mógłbyś podpowiedzieć w jaki sposób przeprowadzać konwersję bezpośrednio na łańcuchu znaków?

[narbej]

W jaki sposób następuje konwersja bezpośrednio ze stringa na liczbę binarną? Istnieje na to jakiś trik?

Właśnie tak robię, z tym że używam dwóch tablic char, a nie stringów. Dokładniej użyłem, bo to stary kod - jeszcze w zasadzie w C.

[testowyhkktr]

Zmieniłem obecne przeliczanie liczby na binarny na system oparty na stringu. Konwersja jest standardowa - oparta na reszty z dzielenia oraz dzieleniu liczby w stringu przez 2. Opierałem się na tym algorytmie: https://www.geeksforgeeks.org/divide-large-number-represented-string/. Wynik się poprawił z 80 na 90. Pełnego AC nie ma, więc nadal coś pozostaje do poprawienia. Istnieje wydajniejszy sposób na konwersję stringa na liczbę binarną? Poproszę o podpowiedź jak taką konwersję optymalniej wykonać

[narbej]

Algorytm i kod w podanym linku dotyczył ogólnego przypadku dzielenia dużej liczby zapisanej w/na stringu przez liczbę int. Tu, w tym zadaniu masz/potrzebujesz dzielenie TYLKO przez dwa.

0. Zamień wszystkie elementy string’a - kody ASCII - na cyfry - liczby, np “1” [= 49] na 1
1. Zamiast / użyj >> 1
2. Zamiast % 2 użyj & 1
3. Dzieląc, zamiast od lewej do prawej “idź” [przesuwaj się, pełznij ] od prawej do lewej - mam na myśli string
4. Zacznij używać najnowszych wersji narzędzi, np C++14
5. Nie zgaduj, gdzie jest wąskie gardło - powinieneś użyć profilera - może także i/o jest za wolne?
6. Może BigNumbers jest dobre - jeżeli jest dostosowane do tego zadania, a nie ogólne. Ja użyłem prostego rozwiązania, ale moje nie jest najszybsze, są lepsi ode mnie.
7. Nawet jak uzyskasz pełne AC, nie oznacza to, że nie ma nic do poprawienia - zawsze coś jest, np chociażby Czystość kodu, jeszcze szybsze rozwiązanie itd…
   Dla kompilatora i dla “sędziego” na spoju i dla uzyskania AC to bez znaczenia, ale gdybyś kiedyś, gdzieś chciał się pochwalić swoim kodem, pokazać innemu programiście, lub zamieścić w swoim portfolio - to…? Czy jest już odpowiednio i wystarczająco CZYSTY?

.
.
.
.

[EDIT]
Widziałem ostatnio fajny rysunek, z opisem [po angielsku - tu wolne tłumaczennie]: Czy jestem dobrym programistą czy dobrym googlerem?
Na forum spoja, też o tym było dyskutowane wiele razy. Niektórzy uważają, że rozwiązując dowolne zadanie [może nie dowolne ale np średnie i trudne], pierwszą rzeczą jest przeszukanie internetu pod kątem ewentualnych gotowych rozwiązań. Ja jestem starej daty i oczywiście przeciwny takiej koncepcji rozwiązywania. Rozwiązywanie i przy okazji nauka programowania to raczej samodzielna i ciężka praca-myślenie, a nie poleganie na podpowiedziach czy gotowcach z internetu. Nie bierz tego do siebie - piszę ogólnie.

Jednak umiejętność przeszukiwania internetu też jest ważna i potrzebna. Przydaje się umiejętność zadawania pytań i znajomość angielskiego, ale nie zawsze przyniesie to oczekiwany rezultat. W twoim wypadku sądzę, że lepszym zapytaniem byłoby np:

How to convert a very large number from decimal string to binary representation?

Ale i tak, w wynikach wyszukiwania dla takiego pytania nie znalazłem mojego sposobu Więc może jednak czasami trzeba samemu, a olać wyszukiwanie? No i myślę, że mój sposób można zastosować do BigNamber, ale do swoich Big, a nie do gotowych rozwiązań. Bo przeba np wiedzieć jak pełzać z prawej na lewo w BN [Big Numbers], a tego raczej nie ma w gotowcach.