Επεξηγήσεις στο θέμα Β φάσης 31ου ΠΔΠ

Γενικά θέματα για το διαγωνισμό. Ερωτήσεις, προτάσεις και ό,τι άλλο ταιριάζει.
Απάντηση
Άβαταρ μέλους
switch
Δημοσιεύσεις: 90
Εγγραφή: Σάβ Δεκ 05, 2015 11:46 am
Τοποθεσία: 127.0.0.1

Επεξηγήσεις στο θέμα Β φάσης 31ου ΠΔΠ

Δημοσίευση από switch »

Επειδή ίσως να μην είναι απόλυτα κατανοητή η λύση που δημοσιεύτηκε στο γυμνάσιο από τους νεαρούς μαθητές, έγραψα μερικές σημειώσεις στα γρήγορα.

Επεξηγήσεις για το πρόβλημα του γυμνασίου Β φάσης του 31ου ΠΔΠ

Πρόκειται για ένα απλό dp ώς αναφορά τον υπολογισμό των διαφορετικών συνδιασμών στην επιλογή του διαστήματος διακοπών.
Έστω ότι S είναι ο πίνακας Ν χαρακτήρων όπου κάθε χαρακτήρας είναι m ή s.

Κάνοντας το γράφημα της διαφοράς Σ(m) - Σ(s) ως προς την ημέρα i (i<=N), θα έχουμε N διαφορετικά σημεία.
Για λόγους προβολής θα τα παραστήσω με μια τεθλασμένη γραμμή στο διάγραμμα.
gymn1.jpg
gymn1.jpg (99.86 KiB) Προβλήθηκε 2489 φορές
Το απλό σκεπτικό είναι να κάνουμε ένα O(N*N) για να βρούμε αν ανάμεσα στη μέρα i και στην αρχή των αξόνων υπήρχαν
άλλα ισοϋψή σημεία που ανάμεσα σε κάθε ένα από εκείνα τα σημεία και το i να υπάρχουν τόσα m όσα και s
και μετά να κάνουμε result = result + αριθμός_προηγούμενων_ισοϋψών_σημείων
Αυτό υποθέτω ήταν η αναμενόμενη λύση για γυμνάσιο.

Μπορούμε να το κάνουμε ποιο γρήγορο; Φυσικά.
Κρατάμε σε έναν πίνακα μεγέθους DPSIZE = 2*Ν. Πώς έγινε ο υπολογισμός του DPSIZE:
DPSIZE = |Σ(m)-Σ(s)| => -Ν <= Σ(m)-Σ(s) <= Ν
διότι αν έχουμε μόνο m, τότε Σ(m)==N ενώ αν έχουμε μόνο s, Τότε Σ(s)==N

Οπότε:

Κώδικας: Επιλογή όλων

//pdp31b-junior
#include <stdio.h>
#include <string.h>

int main(){
	long long ans = 0;
	int height = 0, N;
	scanf("%d ",&N);//warning: προσέξτε το κενό μετά το %d που πετά όλα τα trailing white spaces

	unsigned *_dp = new unsigned[2 * N + 1];
	memset(_dp,0,sizeof(*_dp)*(2*N+1));
	unsigned *dp = _dp + N;		//ή ισοδύναμα unsigned *dp = &_dp[N];
		//το dp[] είναι δείκτης στη μέση του _dp[] οπότε τις τιμές dp[i] μπορούμε να τις
		//προσπελάσουμε με i από -N έως +Ν. Εναλλακτικά κάνουμε κάθε φορά _dp[i+N] για να μην βγούμε εκτός ορίων


	dp[height] = 1;			//αρχική κατάσταση: αριθμός m==0 και αριθμός s==0 υπάρχει 1 φορά στις 0 μέρες
	
	for(int i=0;i<N;i++){
		height += (getchar()=='m')? 1 : -1;
		
		ans += dp[height]; 
		dp[height]++;
		//η πιό απλά για τις 2 πιο πάνω εντολές: ans += dp[height]++; 
		//η λίγο πιο καμμένα για τις 3 πιο πάνω εντολές: ans += dp[height += (getchar()=='m')? 1 : -1]++;;
	}
	
	printf("%llu\n",ans);
	return 0;
}


Για το θέμα λυκείου, ήταν ένα απλό dp σαν το παραπάνω με ένα επιπλέον stack.
Η λύση δίνεται γραμμικά με ένα loop για το string.
Κρατάμε στο stack<int> μόνο τα ανοίγματα παρενθέσεων αποθηκεύοντας το i (τη θέση τους στο string
Κρατάμε σε ένα int dp[N] το πόσους συνδυασμούς έχουμε με ισορροπημένες παρενθέσεις που τελειώνουν στη θέση i
Κάθε φορά που συναντάμε ένα κλείσιμο παρένθεσης, ελέγχουμε το top στο stack και αν υπάρχει προσθέτουμε
και τους προηγούμενους συνδυασμούς

Κώδικας: Επιλογή όλων

/* USER: username
LANG: C++
TASK: cntbal */

#include <cstdio>
#include <stack>

using namespace std;

int main(){
	FILE *in = fopen("cntbal.in","r"), *out = fopen("cntbal.out","w");
	int n;
	static long long dp0[1000003], *dp = dp0 + 1; 
	static char s[1000003];
	while(fscanf(in,"%d %s",&n,s) == 2){
		long long ans = 0;
		memset(dp0,0,sizeof(dp0));
		stack<int> S;
		for(int i=0;s[i];i++){
			if(s[i] == '('){
				S.push(i);
			} else if(S.size()){
				dp[i] = dp[S.top()-1] + 1;
				ans += dp[i];
				S.pop();
			}
		}
		fprintf(out,"%lld\n",ans);
	}
	return 0;
}
Τελευταία επεξεργασία από το μέλος switch την Τετ Απρ 03, 2019 8:01 pm, έχει επεξεργασθεί 2 φορές συνολικά.
Άβαταρ μέλους
switch
Δημοσιεύσεις: 90
Εγγραφή: Σάβ Δεκ 05, 2015 11:46 am
Τοποθεσία: 127.0.0.1

Re: Επεξηγήσεις στο θέμα Β φάσης 31ου ΠΔΠ

Δημοσίευση από switch »

Αν το θέμα του λυκείου έγινε κατανοητό, πάμε να δούμε ένα optimization
Spoiler: show
Αρκεί να σκεφτούμε ότι σε κάθε push ανοίγματος παρένθεσης, μας ενδιαφέρει το πόσους συνδυασμούς έχουμε μέχρι τη θέση i-1, άρα δεν χρειαζόμαστε όλο τον πίνακα dp αλλά μια και μόνο τιμή. Αν τύχει και έχουμε μια άσχετη παρένθεση (unbalanced) τότε χάνεται η συνέχεια με τα προηγούμενα συνεχόμενα i και ξεκινάμε από την αρχή.

Κώδικας: Επιλογή όλων

/* USER: username
LANG: C++
TASK: cntbal */

#include <cstdio>
#include <stack>

using namespace std;

int main(){
	FILE *in = fopen("cntbal.in","r"), *out = fopen("cntbal.out","w");
	int n;
	static char s[1000003];
	while(fscanf(in,"%d %s",&n,s) == 2){
		long long ans = 0, 
			prev = 0;
		int 	iprev = -2;//θέση που αναφέρεται στο prev
		stack<long long> S;
		for(int i=0;s[i];i++){
			if(s[i] == '('){
				S.push( iprev==i-1 ?prev:0);
			} else if(S.size()){
				ans += prev = S.top() + 1;
				iprev = i;
				S.pop();
			}
		}
		fprintf(out,"%lld\n",ans);
	}
	return 0;
}
προτεινόμενο πρόβλημα:
https://www.hackerrank.com/challenges/j ... rs/problem
Απάντηση