Zadanie "Gra"

Question

Cześć,

niedawno postanowiłem zrobić zadanie o nazwie "Gra" (http://ki.staszic.waw.pl/task.php?name=gra) no i oczywiście okazało się, że nie umiem znaleźć rozwiązania. Poszukałem więc w internecie i znalazłem fajny pomysł na rozwiązanie (https://www.geeksforgeeks.org/optimal-strategy-for-a-game-dp-31/). Spróbowałem to zaimplementować i wrzucić na sprawdzarkę i niby wszystko ładnie, ale na samym końcu wypisuje mi: "Naruszenie ochrony pamięci. Wywołano tgkill()", przez co zdobywam tylko 90 na 100 punktów. Zgaduję, że w którymś momencie wychodzi mi poza tablicę, ale nie mam pojęcia gdzie i dla jakich danych wejściowych. Próbowałem testować mój program dla losowych danych, ale zawsze pokazywał poprawny wynik i nigdy nie zgłaszał żadnego błędu. Serdecznie prosiłbym o pomoc w znalezieniu źródła problemu. 

Oto mój kod:

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long int ll;

#define FOR(x, y, z) for(ll z = x; z < y; ++z)
#define REP(x, y) for(ll y = 0; y < x; ++y)


int main()
{
	cin.sync_with_stdio(0);
	cin.tie(NULL);

	ll n, sum = 0;
	cin >> n;

	ll* arr = new ll[n];
	ll** dp = new ll*[n];

	REP(n, i)
	{
		cin >> arr[i];
		sum += arr[i];
	}

	REP(n, i)
		dp[i] = new ll[n];

	REP(n, i)
		REP(n, j)
			dp[i][j] = 0;

	FOR(0, n, gap)
		for (ll i = 0, j = gap; j < n; ++i, ++j)
		{
			ll x = ((i + 2) <= j) ? dp[i + 2][j] : 0;
			ll y = ((i + 1) <= (j - 1)) ? dp[i + 1][j - 1] : 0;
			ll z = (i <= (j - 2)) ? dp[i][j - 2] : 0;

			dp[i][j] = max(arr[i] + min(x, y), arr[j] + min(y, z));
		}

	cout << dp[0][n - 1] << " " << abs(sum - dp[0][n - 1]);
}

 

Answer 1

Skoro zarezerwowałeś pamięć za pomocą "new" to powinieneś ją potem zwolnić za pomocą "delete".

https://www.p-programowanie.pl/cpp/tablice-dynamiczne/

Comments

Rzeczywiście. Dzięki za odpowiedź. Ale nawet jezeli zwolnię pamięć, to i tak dla jakichś danych wejsciowych dostaję błąd.

---

A nie jest czasem tak, że odwołujesz się do wartości wskazywanej przez zmienną dynamiczną, gdy ta zmienna wskazywana jeszcze nie została utworzona?

---

@ Whistleroosh

Rzeczywiście. Dzięki za odpowiedź. Ale nawet jezeli zwolnię pamięć, to i tak dla jakichś danych wejsciowych dostaję błąd.

Tak czy tak pamięć powinna być zwolniona. Natomiast błąd który otrzymujesz jest wynikiem przekroczenia limitu pamięci. Na liczby z zakresu 1...1000000 używasz long long inta kiedy wystarczyłby spokojnie int.

@ mrspock1

A nie jest czasem tak, że odwołujesz się do wartości wskazywanej przez zmienną dynamiczną, gdy ta zmienna wskazywana jeszcze nie została utworzona?

Nie, odwołanie się do tablicy jest pod przydzieleniem do niej pamięci.

;)

---

Wejdź w tryb debuggera - śledzenie krokowe, break on exception i zobacz czy ta zmienna wskazywana ma przydzieloną wartość. Możesz tez sprawdzac wcześniej, przed odwołaniem się do zmiennej, czy ma przydzieloną wartość czy też jest nil. Po zwolnieniu zmiennej wskazywanej dobrze jest przypisac zmiennej wskazującej wartość nil, bo nie wiem czy to jest robione automatycznie po jej zwolnieniu. Była dyskusja o tym czy używać w innych jezykach free czy freeAndNil bo free zwalniało tylko pamięć i nie przypisywało zmiennej wartości nil.

Najwięcej problematycznych błędów związanych jest z tym że błędnie uważamy że kawałek kodu nie zawiera błędów i nie sprawdzamy go.

---

Wielkie dzięki! Rzeczywiście wystarczyło tylko zmienić long long int na int. Teraz wszystko wchodzi na 100 punktów.

Answer 2

Nastąpiła ciekawa sytuacja, oglądałem kiedyś filmik spotkanie z Panem Andrzej Gąsienica-Samek, prowadził je Pan Diks w Radomiu, wydaje mi się, że omawiali ten problem jako jakieś bardzo stare zadanie z międzynarodowej olimpiady i pisali, że wystarczy zsumować na pozycjach parzystych i nieparzystych i wziąć max wynik. Wydaje mi się, że to ten problem.

18 minuta: https://www.youtube.com/watch?v=lJisWn_ghdk

Comments

To prawie ten sam problem. Tylko w tym zadaniu z ki.staszic trzeba dodatkowo zmaksymalizować róźnicę. Wtedy sumowanie parzystych, nieparzystych raczej nie zadziała

---

A różnica nie będzie zawsze największą jak zrobimy suma - max_wynik?

---

Tak i to jest chyba to co robię w swoim kodzie wyżej. Dlatego potrzebny był dp, żeby policzyć tego maksa

---

Aha, okej