pdp forum

Συνεχίζουμε με τις μηνιαίες προκλήσεις, και μπαίνουμε στον Οκτώβριο. Κάθε αρχή του μήνα θα ανεβαίνει στο pdpforum ένα πρόβλημα προς συζήτηση. Στα σχόλια μπορεί να ξεκινήσει συζήτηση εάν έχετε κάποια απορία για το πρόβλημα, ή κάποια παρατήρηση, οσοδήποτε απλή, που πιστεύετε μπορεί να βοηθήσει αλλά δεν ξέρετε πώς. Οι απαντήσεις και οι παρατηρήσεις ας μπαίνουν σε spoiler tags βέβαια!
Περίπου 5 μέρες πριν τελειώσει ο μήνας, θα δίνεται ένα link για σύσκεψη στην οποία θα συζητάμε όλοι μαζί το πρόβλημα, τις λύσεις μας, πιθανές βελτιώσεις, κλπ.

Στο πρόβλημα μας δίνεται ένας δισδιάστατος πίνακας, που σε κάθε κελί του περιέχει είτε τον χαρακτήρα Χ (χωράφι), είτε τον χαρακτήρα Τ (τσιμέντο). Ο στόχος είναι να βρούμε τον μέγιστου εμβαδού (συνεχόμενο) υποπίνακα που όλα του τα κελιά είναι Χ.

Για παράδειγμα αν δοθεί ο πίνακας
\\ 1 2 3 4 5 6
1 Τ Τ Τ Τ Τ Τ
2 Τ Τ Τ Χ Τ Τ
3 Τ Τ Χ Χ Χ Τ
4 Τ Χ Χ Χ Χ Χ
5 Τ Τ Χ Χ Χ Τ
6 Τ Τ Τ Χ Τ Τ

τότε το μέγιστο χωράφι που μπορούμε να εντοπίσουμε έχει εμβαδό 9. Πρόκειται για το χωράφι από x=3 ως x=5, κι από y=3 ως y=5.

Προσέξτε ότι ο ρόμβος με κέντρο το (4,4) και ακτίνα 2 περιλαμβάνει όλα τα Χ (και κανένα Τ). Παρότι έχει μεγαλύτερο εμβαδό (13) δε μας ενδιαφέρει γιατί οι πλευρές του δεν είναι παράλληλες με τους άξονες, όπως με το προαναφερθέν χωράφι εμβαδού 9.

Αν ο πίνακας έχει μέγεθος Ν*Ν, τότε μας ενδιαφέρουν οι πολυπλοκότητες Ο(Ν^6), Ο(Ν^5), Ο(Ν^4), Ο(Ν^3), Ο(Ν^2). Προτείνω να σκεφτείτε το πρόβλημα 10 λεπτά και να δείτε ποια από τις παραπάνω λύσεις μπορείτε να βρείτε. Μετά, για τον υπόλοιπο μήνα, να προσπαθήσετε να βρείτε την αμέσως καλύτερη από την πρώτη που σκεφτήκατε.

Σημειώνω ότι ο Ο(Ν^2) είναι βέλτιστος, αφού τόσο είναι το μέγεθος του πίνακα!

Στις 20 του μηνός θα προσπαθήσω να δώσω ένα hint, θυμίστε το μου όμως αν το ξεχάσω.

Καλή επιτυχία!

Καλημέρα! Υπάρχει κατώτατο όριο στο τί θεωρείται χωράφι; Θα μπορούσε να είναι χωράφι μόνο μια ευθεία γραμμη από Χ ; ( διαφορετικά οι ελάχιστες διαστάσεις του χωραφιού θα πρέπει να είναι 2*2...)

Πιθανώς δεν κατάλαβα καλά την ερώτηση, οπότε ξαναρώτα αν δε σε καλύψω.

Το κάθε Χ είναι ένα χωραφάκι ενός στρέμματος. Μία ευθεία γραμμή από Χ (με μήκος πχ 5) θα ήταν ένα μεγάλο χωράφι εμβαδού 5 στρεμμάτων, που είναι πράγματι έγκυρο. Ακόμα και ένα Χ μόνο του είναι έγκυρο χωράφι.

Στο παραπάνω παράδειγμα, υπάρχουν δύο ευθύγραμμα τμήματα, μήκους 5 το καθένα. Θα ήταν έγκυρα, απλώς έτυχε να βρούμε ένα ορθογώνιο που περιλαμβάνει περισσότερα Χ (9), οπότε προτιμήσαμε εκείνο.

Καλησπέρα σε όλους!!!
Βαγγέλη, το hint???
Ευχαριστώ!!!

Ωπ, ευχαριστώ για την υπενθύμιση!

Ο(Ν^6): Δε σχολιάζω τίποτα.
Ο(Ν^5): Αν θέλουμε να ελέγξουμε αν συγκεκριμένο ορθογώνιο έχει μόνο χωράφια, αντί να ξοδέψουμε χρόνο Ο(Ν^2) για να ελέγξουμε ένα ένα όλα τα κελιά του, μπορούμε να χρησιμοποιήσουμε την ιδέα των μερικών αθροισμάτων (prefix sums ή cumulative sums) σε κάθε γραμμή, για να επιταχύνουμε σε Ο(Ν) τον έλεγχο.
Ο(Ν^4): Η ιδέα των μερικών αθροισμάτων μπορεί να επεκταθεί και για 2 διαστάσεις, κι έτσι ο έλεγχος να γίνει σε Ο(1) χρόνο! Θέλει λίγο περισσότερη δουλειά.
Ο(Ν^3): Αν έχουμε υποθέσει το άνω και κάτω άκρο του ορθογωνίου (χρόνος Ο(Ν^2)), το πρόβλημα στην ουσία γίνεται μονοδιάστατο και λύνεται σε Ο(Ν) χρόνο.
Ο(Ν^2): Αν υποθέσουμε μόνο το κάτω άκρο του ορθογωνίου, το πρόβλημα λύνεται πάλι σε Ο(Ν) χρόνο. Πρόκειται μάλιστα για ένα πρόβλημα που μπορεί να είναι γνωστό σε αρκετούς από εσάς που μπορέσατε να βρείτε την Ο(Ν^3) λύση (όχι απαραίτητα σε όλους βέβαια).

Καλή συνέχεια!

Πώς στέλνω μια πρόταση λύσης;

alexakos έγραψε: ↑Τετ Οκτ 28, 2020 12:05 pm Πώς στέλνω μια πρόταση λύσης;

Κηπουρίδης έγραψε:Οι απαντήσεις και οι παρατηρήσεις ας μπαίνουν σε spoiler tags βέβαια!

Μπορεις και με πμ (προσωπικο μήνυμα) στον Κηπουρίδη ή σε μένα.

---

Spoiler: show

#include <stdio.h>

#ifndef N
#define N 6
#endif

int M[N][N], pRows[N][N], pCols[N][N];

void prMatr(int m[N][N])
{
register int i,j;

putchar('\n');
for (i=0; i<N; i++)
{
for (j=0; j<N; j++)
printf("%d ", m[j]);
putchar('\n');
}

}

int main()
{
int i,j;
int cornerX, cornerY,maxCorner=0;
char ch;

for (i=0; i<N; i++)
for (j=0; j<N; j++)
{

scanf("%c ", &ch);
M[j]= ((ch == 'Ô' || ch == 'ô' || ch == 'T' || ch == 't') ? 0 : 1);
pRows[j]=pCols[j]=0;
}
for (i=0; i<N; i++)
for (j=0; j<N; j++)
{
if (M[j]==0)
{
pRows[j]=pCols[j]=0; /* We want continuous 1's */
continue;
}
if (j==0)
pRows[j]=M[j];
else
pRows[j] += pRows[i][j-1]+M[i][j];
if (i==0)
pCols[i][j]=M[i][j];
else
pCols[i][j] += pCols[i-1][j]+M[i][j];
}
for (i=0; i<N; i++)
for (j=0; j<N; j++)
if (pRows[i][j]*pCols[i][j]>=maxCorner)
{
maxCorner=pRows[i][j]*pCols[i][j];
cornerX=i;
cornerY=j;
}
prMatr(M);
printf("================\n");
/*prMatr(pRows);
prMatr(pCols);*/
printf("________________________________________\n");
printf("Corner worth to be evaluated: %d , %d (having partial product: %d)\n", cornerX, cornerY, maxCorner);
return 0;
}

---

Συγγνώμη για την ενημέρωση τελευταίας στιγμής. Η συνάντηση θα γίνει αύριο 31/10, στις 15.00 ώρα Ελλάδας, και το λινκ για το zoom είναι: https://ucph-ku.zoom.us/j/67586825824?p ... sveG9qZz09

Meeting ID: 675 8682 5824
Passcode: 988982

Θυμηθείτε να κατεβάσετε την εφαρμογή του zoom για να έχετε πρόσβαση στο whiteboard (η έκδοση μέσω browser δε δίνει τέτοια δυνατότητα).

Τα λέμε αύριο!

Η O(n^2) λύση μου για όποιον ενδιαφέρεται

Spoiler: show

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

#include <iostream>
#include <stack>
int histogra(int hist[], int n);
int main(){
	freopen("biggS.in", "r", stdin);
	freopen("biggS.out", "w", stdout);
	int sizeX , sizeY;
	scanf("%d%d\n", &sizeX, &sizeY);
	int map [sizeX] [sizeY];
	char c;
	for (int i = 0; i<sizeY; i++){
		for (int j = 0; j<sizeX; j++){
			scanf("%c ", &c);
			c=='T' ? map[j][i] = 0 : map[j][i] =1;
		}
		scanf("\n");
	}
	int histogram[sizeX];
	int maxEmpty = 0;
	for (int i = 0; i<sizeY; i++){
		for (int j = 0; j<sizeX; j++){
			if (map[j][i] == 1){
				histogram[j]++;
			}else{
				histogram[j] = 0;
			}
		}
		int tempBigBlock = histogra(histogram, sizeX);
		if (maxEmpty<tempBigBlock)
			maxEmpty =tempBigBlock;
	}
	printf("%d", maxEmpty);
}

int histogra(int hist[], int n){
	std::stack<int> s;
	int max_area = 0, tp, tempArea;
	int i = 0;
	while (i < n){
		if (s.empty() || hist[s.top()] <= hist[i])
			s.push(i++);
		else{
			tp = s.top();
			s.pop();
			tempArea = hist[tp] * (s.empty() ?
					i : i - s.top() - 1);
			if (max_area < tempArea)
				max_area = tempArea;
		}
	}
	while (s.empty() == false){
		tp = s.top();
		s.pop();
		tempArea = hist[tp] * (s.empty() ?
				i : i - s.top() - 1);
		if (max_area < tempArea)
			max_area = tempArea;
	}return max_area;
}

Ερώτηση: στην συνάντηση που κάναμε είχαμε πει ότι η βέλτιστη λύση είναι αυτή με το histogra που έκανα πάνω και συμπεραίναμε ότι είναι περιπλοκότητας O(n^2) αλλά αφού για κάθε σειρά τρέχω το historgra (που κοστίζει O(n)) δεν πρέπει η λύση αυτή να είναι περιπλοκότητας O(n^3)?

Τρέχεις ένα for για καθε σειρα και εκει κάνεις δυο ανεξάρτητα loop, το ένα ενημερώνει τον πίνακα histogram και αφου τελειωσε αυτο καλείς την histogra() συνάρτηση. Αυτά τα loop δεν είναι φωλιασμένα.

Αρα O(N^2) ή κάτι σαν N*(N+N) που είναι O(N^2)
Χάνω κάτι;

Σωστά, δίκαιο έχεις απλά μπερδεύτηκα με τα 3 N

Συνοψίζω πολύ γρήγορα τις λύσεις που συζητήθηκαν:

Καταρχάς δεν υπάρχει λόγος να σκεφτόμαστε με όρους Χ και Τ. Θα λέμε ότι έχουμε 0 και 1 (τα Χ είναι 0, τα Τ είναι 1).

- O(N^6): Για κάθε ένα από τα O(N^4) ορθογώνια, ξοδεύουμε O(N^2) χρόνο για να ελέγξουμε ένα-ένα όλα τα κελιά του, και να δούμε αν είναι όλα ίσα με 0.
- O(N^5): Για κάθε ένα από τα O(N^4) ορθογώνια, ξοδεύουμε Ο(Ν) χρόνο για να ελέγξουμε μία-μία όλες τις γραμμές του, και να δούμε αν όλες περιέχουν μόνο μηδενικά.
Για να απαντάμε σε Ο(1) ανά γραμμή, παρατηρούμε ότι μία γραμμή έχει μόνο μηδενικά, αν και μόνο αν το άθροισμα των στοιχείων της τα οποία μας ενδιαφέρουν είναι ακριβώς 0.
Αυτό μπορούμε να το πετύχουμε με χρήση της τεχνικής prefix sums. Δηλαδή για κάθε γραμμή, χτίζουμε, κατά την προεργασία, τον αντίστοιχα πίνακα των prefix sums.
- O(N^4): Για κάθε ένα από τα Ο(Ν^4) ορθογώνια, ξοδεύουμε Ο(1) χρόνο για να το ελέγξουμε.
Για να το πετύχουμε αυτό, παρατηρούμε ότι ένα ορθογώνιο περιέχει μόνο μηδενικά, αν και μόνο αν το άθροισμα των στοιχείων του είναι 0.
Απαντάμε το άθροισμα ορθογωνίου με 2d prefix sum!
- O(N^3): Σε Ο(Ν^2) χρόνο δοκιμάζουμε κάθε συνδυασμό για την άνω και κάτω πλευρά των ορθογωνίων που μας νοιάζουν. Έπειτα, το πρόβλημα γίνεται 'μονοδιάστατο', δηλαδή σε κάθε θέση i έχουμε ως τιμή το άθροισμα των στοιχείων της στήλης i που βρίσκονται ανάμεσα στις 2 κατακόρυφες γραμμές. Αρκεί να εντοπίσουμε το μέγιστο συνεχόμενο διάστημα (στον νέο μονοδιάστατο πίνακα) που έχει μόνο μηδενικά. Αυτό λύνεται σε Ο(Ν), το πώς αφήνεται ως άσκηση για τον αναγνώστη.
- Ο(Ν^2): Χρειάζεται να λύσουμε πρώτα γραμμικά το πρόβλημα https://www.spoj.com/problems/HISTOGRA/ Θεωρώντας ότι μπορούμε να το λύσουμε, τότε για κάθε οριζόντια γραμμή (τις διατρέχουμε από πάνω προς τα κάτω), η οποία ορίζει την κάτω πλευρά των ορθογωνίων μας, αρκεί να εφαρμόσουμε τη λύση του προβλήματος histogra σε έναν νέο πίνακα.
Ο νέος πίνακας προκύπτει αν σε κάθε θέση του γράψουμε το πλήθος των συνεχόμενων μηδενικών κελιών στη συγκεκριμένη στήλη, από την οριζόντια γραμμή που θεωρήσαμε, και πάνω.
Κατόπιν δοκιμάζουμε την επόμενη (αμέσως από κάτω) οριζόντια γραμμή. Αφήνεται ως άσκηση στον αναγνώστη πώς ανανεώνουμε γρήγορα τον βοηθητικό πίνακα, πάνω στον οποίο εφαρμόζουμε τη λύση του histogra.

Εννοείται μπορείτε να ρωτήσετε εδώ πέρα ό,τι δεν έχετε καταλάβει.

Μια ακόμα παραλλαγή του προβλήματος

https://hsin.hr/coci/contest1_tasks.pdf
πρόβλημα 3d histogram

Οι περιορισμοί που δίνονται (N<=200000) σημαίνει ότι είναι αποδεκτές λύσεις γραμμικές (φυσικά), λογαριθμικές και τετράγωνο λογαριθμικής λύσης το πολύ. Τετράγωνα και μετά... δεν....

hint

Spoiler: show

Φυσικά τα παραλληλεπιπεδα θα εχουν τουλάχιστο ένα α ή ένα β από κάποια ράβδο. Προσοχή όμως μπορεί να έχουν το άλλο (β ή α) από άλλη ράβδο.

Αλλο ενα: http://www.usaco.org/index.php?page=vi ... &cpid=1087
Γραμμικο ή και λογαριθμικο.