Wall
Problem
Το πρόβλημα μας ζητά να πρσθέσουμε κάποια blocks έτσι ώστε να "γεμίσουμε" ένα συνεχόμενο κομμάτι του τείχου. Πρέπει αυτό το κομμάτι να είναι ορθογώνιο (δηλαδή ο κάθε πύργος να έχει το ίδιο ύψος), και το ύψος του κομματιού να μην ξεπερνά το μέγιστο ύψος κάποιου πύργου μέσα στο κομμάτι.
Solution
Subtask 1 (20 points)
\(1 \le N \le 500\) and \(1 \le S \le 1000\)
Το ότι το \(N \le 500\) μας επιτρέπει να χρησιμοποιήσουμε λύση με χρονική πολυπλοκότητα \(O(N^3)\). Αυτό μπορούμε να το κάνουμε με το να περνούμε πάνω από κάθε πιθανό συνδιασμό. Υπάρχουν \(\frac{N \times (N+1)}{2}\) (άρα \(O(N^2)\)) διαφορετικά κομμάτια στον τοίχο, τα οποία μπορούμε να δοκιμάσουμε να "γεμίσουμε". Για κάθε ένα από αυτά τα κομμάτια θα περάσουμε από όλους τους πύργους και θα βρούμε το μέγιστο ύψος \(M_i\), και το άθροισμα όλων των πύργων \(S_i\). Αν το \(i\)-οστό κομμάτι ξεκινά στην θέση \(l\) και τελειώνει στην θέση \(r\), τότε ο αριθμός πετρών που θα χρειαστούν για να "γεμίσει" το \(i\)-οστό κομάτι είναι \((r-l+1)\times M_i - S_i\). Αν αυτός ο αριθμός είναι ίσος με το \(S\), τότε βρήκαμε μια λύση. Αν βρούμε πολλές τέτοιες λύσεις, επιλέγουμε την καλύτερη όπως εξηγά το πρόβλημα.
pair<int, pair<int, int> > ans;
for(int l=0;l<n;l++){
for(int r=l;r<n;r++){
int s_i = 0;
int m_i = 0;
for(int j=l;j<=r;j++){
s_i += a[j];
m_i = max(m_i, a[j]);
}
if(m_i * (r-l+1) - s_i == S){
ans = max(ans, {r-l+1, {m_i, -l}});
}
}
}
cout<<ans.first<<" "<<ans.second.second<<endl;
Σημείωση
Για να μην χρειάζετε να ελέγχουμε κατά πόσο η λύση μας είναι "καλύτερη" από την προηγούμενη που βρήκαμε, χρησιμοποιούμε την συνάρτηση max.
Το πρόβλημα μας ζητά να βρούμε την λύση με:
- Tο μεγαλύτερο μήκος
- Tο μεγαλύτερο ύψος
- Tη μικρότερη αριστερή θέση
Θέλουμε τα κριτήρια να εφαρμόζονται με αυτή την σειρά, άρα δημιουργούμε ένα pair, όπου το πρώτο στοιχείο να είναι το μήκος, το δεύτερο στοιχείο να είναι το ύψος, και το τρίτο η αριστερή θέση. Αφού θέλουμε να είναι όλα μέγιστα, χρησιμοποιούμε το max. Αφού η θέση πρέπει να είναι ελάχιστη, μπορούμε να την εισάγουμε στο pair με αρνητικό πρόσημο, έτσι ώστε όσο πιο μικρή είναι η θέση, τόσο λίγοτερο αρνητική να γίνεται, άρα και μεγαλύτερη.
Subtask 2 (44 points)
\(1 \le N,S \le 10000\)
Σε αυτό το subtask η λύση μας πρέπει να είναι σε χρόνο \(O(N^2)\). Για να το πετύχουμε αυτό, μπορούμε να δοκιμάζουμε τα πιθανά κομμάτια με τέτοια σειρά, έτσι ώστε να μπορούμε σε Ο(1) χρόνο να βρίσκουμε πόσες πέτρες θα χρειαστούν για να συμπληρωθεί το κομμάτι.
Πως μπορούμε να το πετύχουμε αυτό;
Μπορούμε να ξεκινούμε από αριστερά, και σε κάθε iteration να μεγαλώνουμε το κομμάτι μας κατά ένα στα δεξιά. Έτσι, μπορούμε να κρατούμε το μέγιστο \(M_i\), και το άθροισμα \(S_i\).
\(A_j\) είναι το ύψος του πύργου που θα προσθέσουμε στο κομμάτι. Άρα έτσι μπορούμε κάθε φορά που θέλουμε να μεγαλώσουμε το κομμάτι που δοκιμάζουμε, να το κάνουμε σε \(O(1)\) χρόνο, και όταν φτάσουμε στο πιο δεξιά πύργο, να ξαναξεκινούμε από αριστερά, αγνoώντας τον πιο αριστερά πύργο.
pair<int, pair<int, int> > ans;
for(int l=0;l<n;l++){
int s_i = 0;
int m_i = 0;
for(int r=l;r<n;r++){
s_i += a[r];
m_i = max(m_i, a[r]);
if(m_i * (r-l+1) - s_i == S){
ans = max(ans, {r-l+1, {m_i, -l}});
}
}
}
cout<<ans.first<<" "<<ans.second.second<<endl;
Σημείωση
Μπορούμε να χρησιμοποιήσουμε την συγκεκριμένη σειρά για να περνούμε πάνω από subarrays, για να μετατρέπουμε τον κώδικα μας από \(O(N^3)\) σε \(O(N^2)\) σε πολλά προβλήματα. Κάποιες φορές όμως, δεν μπορούμε σε \(O(1)\) χρόνο να προσθέσουμε το στοιχείο στο subarray μας, όπου ίσως να μην συμφέρει να χρησιμοποιήσουμε αυτή την τεχνική.
Subtask 3 (84 points)
Για να πιάσουμε περισσότερους πόντους, χρειάζεται να κάνουμε μερικές παρατηρήσεις για το πρόβλημα.
Παρατήρηση 1
Στην λύση μας για το Subtask 2, μπορούμε να προσέξουμε ότι κάθε φορά που προσθέτουμε ένα στοιχείο στα δεξιά, το άθροισμα \(S_i\) ανεβαίνει κατά \(A_i\), και το μέγιστο ή θα μείνει σταθερό, ή θα γίνει ίσο με το \(A_i\). Συνολικά, ο αριθμός πετρών που χρειαζόμαστε για να "γεμίσουμε" το ορθογώνιο [l,r] αυξάνεται.
Απόδειξη
Υπάρχουν 2 περιπτώσεις. Ορίζουμε το \(P_i\) ως τον αριθμό πετρών που χρειάζεται για να γεμίσει το \(i\)-οστό κομμάτι. Αν το \(A_i \le M_{i-1}\):
Αφού \(M_{i-1} \ge A_i\), τότε ισχύει \(P_i \ge P_{i-1}\).
Η δεύτερη περίπτωση είναι όταν \(A_i >= M_{i-1}\)
Και πάλι \(P_i > P_{i-1}\).
Άρα μπορούμε να είμαστε σίγουροι ότι για κάθε αρχική θέση \(l\), o αριθμός πετρών που χρειαζόμαστε αυξάνεται καθώς αυξάνεται το \(r\). Αφού εμείς θέλουμε να βρούμε θέση στην οποία χρειαζόμαστε ακριβώς \(S\) πέτρες, μπορούμε να χρησιμοποιήσουμε BS.
Παρατήρηση 2
Για να χρησιμοποιήσουμε BS, πρέπει να βρούμε ένα τρόπο να βρίσκουμε τον αριθμό πετρών που χρειαζόμαστε αρκετά γρήγορα, για κάθε πιθανό \(r\), για όλα τα \(l\). Μπορούμε να δούμε αυτές τις τιμές ως range queries στο εύρος \([l,r]\) της μορφής \(\max{A_i}\) και \(\sum{A_i}\). Αυτό μπορεί αρκετά εύκολα να υπολογιστεί χρησιμοποιώντας segment trees.
Χρησιμοποιώντας αυτές τις δύο παρατηρήσεις, έχουμε την εξής λύση:
Δοκιμάζουμε το κάθε starting point (δηλαδή την τιμή του \(l\)), από το 1 μέχρι το \(N\). Για το συγκεκριμένο \(l\), κάνουμε binary search για να βρούμε το \(r\). Στο κάθε iteration του binary search, βρίσκουμε το πόσες πέτρες θα χρειαστούμε για να καλύψουμε το συγκεκριμένο εύρος, κάνοντας query το segment tree. Αν χρειαζόμαστε λιγότερες από \(S\) πέτρες, θα δοκιμάσουμε μεγαλύτερες τιμές για το \(r\), ενώ αν χρειαζόμαστε περισσότερες, θα δοκιμάσουμε μικρότερες τιμές.
Η συνολική χρονική πολυπλοκότητα είναι \(O(N\log^2N)\)
Subtask 4 (100 points)
Η ίδια ιδέα με την λύση του 3ου subtask, αλλά χρησιμοποιώντας την τεχνική descending the tree, έτσι ώστε η πολυπλοκότητα να γίνει \(O(N\log N)\).
Author: cfalas