32ος ΠΔΠ Γ' Φάση: Push-Complement-Reverse (pcr) - Λύση
Επεξήγηση εκφώνησης
Μας δίνεται μία ακολουθία από ακεραίους \(\lbrace 0, 1, 2, 3 \rbrace\). Μας ζητείται να βρούμε την βέλτιστη , δηλαδή τη μικρότερη σε μήκος (και σε περίπτωση ισοβαθμίας, την λεξικογραφικά μικρότερη), ακολουθία από push, reverse και complement, ώστε να μετατρέψουμε μία αριστερή ακολουθία σε μία δεξιά ακολουθία όπου όλα τα \(0\), \(1\), \(2\) και \(3\) είναι ομαδοποιημένα.
Ξεκινάμε με μία παρατήρηση που δεν είναι αναγκαία για την κατανόηση των παρακάτω λύσεων αλλά δίνει πληροφορίες για την διαδικασία.
Παρατήρηση 0: Για οποιαδήποτε δοσμένη αριστερή ακολουθία, υπάρχει μία τέτοια ακολουθία κινήσεων.
Αν οι αριθμοί ήταν \(0\) και \(1\), τότε μπορούμε να διατηρήσουμε την ακολουθία \(00\ldots 011 \ldots 1\). Όποτε συναντάμε \(1\) κάνουμε \(p\), ενώ όποτε συναντάμε \(0\) κάνουμε \(rpr\) (δηλαδή το προσθέτουμε στα αριστερά). Αφού οι αριθμοί είναι από \(0\) έως \(3\), όποτε συναντάμε \(2\) κάνουμε \(cpc\) (προσθέτουμε \(1\) στα δεξιά) και όποτε συναντάμε \(3\) κάνουμε \(crprc\) (προσθέτουμε \(0\) στα αριστερά). Επομένως, πάντοτε υπάρχει μία τέτοια ακολουθία.
Κάνουμε τις εξής απλές παρατηρήσεις, οι οποίες είναι χρήσιμες για όλες τις παρακάτω λύσεις:
Παρατήρηση 1: Τα στοιχεία εισάγονται (γίνονται pushed) με τη σειρά της δοσμένης αριστερής ακολουθίας.
(Αιτιολόγηση) Καμία από τις κινήσεις δεν αλλάζει την σειρά των στοιχείων στην αριστερή ακολουθία, άρα τα στοιχεία θα γίνουν push με την σειρά που μας δίνονται.
Παρατήρηση 2: Δεν συμφέρει να κάνουμε δύο complement χωρίς να μεσολαβεί push.
(Αιτιολόγηση) Κάνουμε δύο κινήσεις που δεν επηρεάζουν κανένα στοιχείο που γίνεται push. Αφού ψάχνουμε τη μικρότερη ακολουθία , δεν μπορεί να υπάρχουν αυτές οι κινήσεις.
Παρατήρηση 3: Δεν συμφέρει να κάνουμε δύο reverse χωρίς να μεσολαβεί push.
(Αιτιολόγηση) Ξανά, κάνουμε δύο κινήσεις που δεν επηρεάζουν κανένα στοιχείο που γίνεται push.
Παρατήρηση 4: Η βέλτιστη ακολουθία κινήσεων δεν θα περιέχει ποτέ \(rcp\).
(Αιτιολόγηση) Το reverse επηρεάζει την δεξιά ακολουθία ενώ το complement επηρεάζει την αριστερή. Άρα μπορούμε να τους αλλάξουμε θέση (δηλαδή κάνουμε \(crp\) αντί για \(rcp\)) και να πάρουμε μία ακολουθία κινήσεων με την ίδια επίδραση και το ίδιο πλήθος, αλλά λεξικογραφικά μικρότερη.
Χρησιμοποιώντας αυτές τις παρατηρήσεις, μπορούμε να δούμε το πρόβλημα ως εξής: Μας δίνονται \(N\) στοιχεία και για κάθε ένα επιλέγουμε μία από τις κινήσεις \(\lbrace p, rp, cp, crp \rbrace\) ώστε στο τέλος να έχουμε μία δεξιά ακολουθία που τα στοιχεία είναι ομαδοποιημένα. Από όλες τις ακολουθίες κινήσεων, ψάχνουμε για την βέλτιστη (όπως την ορίσαμε προηγουμένως).
Brute force λύση – \(\mathcal{O}(4^N)\)
Η brute force λύση είναι να δοκιμάσουμε σε κάθε βήμα όλες τις δυνατές κινήσεις. Από τις ακολουθίες κινήσεων που θα οδηγήσουν σε ομαδοποιημένες δεξιές ακολουθίες κρατάμε την βέλτιστη. Κάνουμε μία κίνηση για κάθε στοιχείο και υπάρχουν το πολύ \(4\) επιλογές. Άρα ο αλγόριθμος θέλει \(\mathcal{O}(4^N)\) χρόνο, που είναι πολύ αργό για τα περισσότερα testcases.
Λύση με δυναμικό προγραμματισμό – \(\mathcal{O}(N^2)\)
Παρατήρηση 5: Για να ελέγξουμε αν μπορούμε να εισάγουμε ένα στοιχείο σε μία ομαδοποιημένη αριστερή ακολουθία, χρειάζεται να ξέρουμε μόνο:
- την σειρά που εμφανίζονται τα στοιχεία στην δεξιά ακολουθία
- αν τα στοιχεία στην αριστερή ακολουθία είναι αντεστραμμένα
Πιο συγκεκριμένα, το στοιχείο \(x_i\) μπορεί να εισαχθεί μόνο αν:
- το δεξιότερο στοιχείο \(r = x_i\) (ή \(r = 3 - x_i\) αν τα στοιχεία της αριστερής ακολουθίας είναι αντεστραμμένα), ή
- δεν υπάρχει το στοιχείο \(x_i\) στην δεξιά ακολουθία (ή το \(3 - x_i\) αν τα στοιχεία της αριστερής ακολουθίας είναι αντεστραμμένα)
(Αιτιολόγηση) Ας δούμε την περίπτωση που δεν έχουμε αντιστροφή (η αντιστροφή έχει το ίδιο επιχείρημα με \(3-x_i\) αντί για \(x_i\)).
- Προφανώς αν το δεξιότερο στοιχείο είναι \(x_i\), τότε μπορούμε απλά να το κάνουμε push χωρίς να αλλάξει η ομαδοποίηση.
- Αν δεν υπάρχει το \(x_i\), τότε δημιουργούμε για αυτό μία καινούργια ομάδα.
Αν δεν ισχύει καμία από τις δύο συνθήκες, τότε άμα το κάνουμε push, θα δημιουργηθεί μία δεύτερη ομαδοποίηση (πχ αν \(x_i = 2\), τότε για \(1 1 2 2 3\), κάνοντας push το \(2\) δημιουργεί μία δεύτερη ομάδα για το \(2\)).
Επίσης, γνωρίζοντας αυτές τις δύο πληροφορίες, μπορούμε να κάνουμε complement και reverse. Ορίζουμε ως κατάσταση s = (positions, is_complemented), όπου positions[x] είναι η θέση της ομάδας του x (ή \(0\) αν δεν εμφανίζεται) και is_complemented είναι η boolean που δείχνει αν τα στοιχεία στην αριστερή ακολουθία είναι αντεστραμμένα. Θα κάνουμε δυναμικό προγραμματισμό στο dp(i, s), που μας δίνει την βέλτιστη ακολουθία όταν επεξεργαζόμαστε το \(i\)-οστό στοιχείο και είμαστε στην κατάσταση s. Χρησιμοποιούμε forward DP όπου οι μεταβάσεις είναι οι δυνατές κινήσεις \(\lbrace p, cp, crp, rp \rbrace\) (σύμφωνα με τις παρατηρήσεις 1-4).
Στον κώδικα, για ευκολία, για κάθε κατάσταση s κρατάμε:
- ένα πίνακα
positionμε την σειρά των \(4\) τιμών - τις αριστερότερες (
leftmost) και δεξιότερες (rightmost) τιμές - το πλήθος
countτων διαφορετικών τιμών που έχουν εμφανιστεί - το
is_complemented, αν η αριστερή ακολουθία έχει γίνει complemented μονό αριθμών φορών.
Για παράδειγμα, για την εξής δεξιά ακολουθία
\[\underbrace{2\; 2 \; 2 \; 2}_{1} \; \; \; \underbrace{3\; 3 \; 3}_{2} \; \; \;\underbrace{0\; 0 \; 0 \; 0 \; 0}_{3}\]το positions = [3, 0, 1, 2], το leftmost = 2, το rightmost = 0, count = 3 και το is_complemented θα μπορούσε να είναι true ή false. Θα δούμε στην τέταρτη λύση, πώς μπορούμε να συμπιέσουμε αυτή την αναπαράσταση.
struct State {
vector<int> positions;
int rightmost;
int leftmost;
int count;
bool is_complemented;
State reverse() const {
State other = *this;
// Αντιστρέφουμε τις θέσεις των στοιχείων που έχουμε δει.
for (size_t i = 0; i < 4; ++i) {
if (other.positions[i] != 0) other.positions[i] = (count + 1) - other.positions[i];
}
other.leftmost = rightmost;
other.rightmost = leftmost;
return other;
}
void appendRight(int val) {
if (positions[val] == 0) {
++count;
positions[val] = count;
if (count == 1) leftmost = val;
rightmost = val;
}
}
bool canAppend(int val) const {
return rightmost == val || positions[val] == 0;
}
/* Χρειάζεται ώστε το State να μπορεί να είναι κλειδί σε set. */
bool operator<(const State& other) const {
if (count != other.count) return count < other.count;
if (rightmost != other.rightmost) return rightmost < other.rightmost;
if (leftmost != other.leftmost) return leftmost < other.leftmost;
if (count != other.count) return count < other.count;
if (is_complemented != other.is_complemented) return is_complemented < other.is_complemented;
return positions < other.positions;
}
State() {
positions.push_back(0); positions.push_back(0); positions.push_back(0); positions.push_back(0);
leftmost = rightmost = -1;
count = 0;
is_complemented = false;
}
};
Κρατάμε μόνο τις δυνατές καταστάσεις για το \(i\) και υπολογίζουμε τις δυνατές καταστάσεις για το \(i + 1\). Για να μπορούμε να συγκρίνουμε γρήγορα, βάζουμε τις τιμές σε ένα map, όπου το κλειδί είναι η κατάσταση και η τιμή είναι η βέλτιστη ακολουθία κινήσεων που μας οδήγησε εκεί. Κρατάμε την ακολουθία κινήσεων σε μορφή string ώστε να μπορούμε να συγκρίνουμε εύκολα ποια είναι λεξικογραφικά μικρότερη. Αυτό κάνει τον αλγόριθμό μας πιο αργό (γιατί συγκρίνουμε και αντιγράφουμε strings μεγέθους \(O(N)\)). Θα δούμε στην τρίτη λύση πώς μπορούμε να το αποφύγουμε.
Πιο συγκεκριμένα, ορίζουμε map<State, string> current, next; που κρατάει τις δυνατές καταστάσεις στην θέση \(i\) (και αντίστοιχα \(i+1\)) μαζί με την βέλτιση ακολουθία κινήσεων που οδήγησε σε αυτή.
Για ευκολία ορίζουμε την compare_and_add για να συγκρίνει αν για την ίδια κατάσταση έχουμε βρει μία καλυτερη ακολουθία από την μέχρι στιγμής βέλτιστη:
bool is_smaller(const string& s1, const string& s2) {
if (s1.size() != s2.size()) return s1.size() < s2.size();
return s1 < s2;
}
void compare_and_add(map<State, string>& mp, State& state, string& val) {
if (mp.find(state) == mp.end()) {
mp[state] = val;
} else if (is_smaller(val, mp[state])){
mp[state] = val;
}
}
Αυτό μας επιτρέπει να ορίσουμε τις μεταβάσεις ως εξής:
int current_val = state.is_complemented ? (3 - x[i]) : x[i];
- Για την κίνηση \(p\):
if (state.canAppend(current_val)) {
string new_sequence = sequence + "p";
State new_state = state;
new_state.appendRight(current_val);
compare_and_add(next, new_state, new_sequence);
}
- Για την κίνηση \(rp\):
State reverse_state = state.reverse();
if (reverse_state.canAppend(current_val)) {
string new_sequence = sequence + "rp";
reverse_state.appendRight(current_val);
compare_and_add(next, reverse_state, new_sequence);
}
- Για την κίνηση \(cp\):
if (state.canAppend(3-current_val)) {
string new_sequence = sequence + "cp";
State new_state = state;
new_state.appendRight(3-current_val);
new_state.is_complemented = !new_state.is_complemented;
compare_and_add(next, new_state, new_sequence);
}
- Για την κίνηση \(crp\):
State complement_and_reverse_state = state.reverse();
if (complement_and_reverse_state.canAppend(3-current_val)) {
string new_sequence = sequence + "crp";
complement_and_reverse_state.appendRight(3-current_val);
complement_and_reverse_state.is_complemented = !complement_and_reverse_state.is_complemented;
compare_and_add(next, complement_and_reverse_state, new_sequence);
}
Επειδή υπάρχουν μόνο \(4\) στοιχεία, το πλήθος των δυνατών positions είναι σταθερός αριθμός (για την ακρίβεια1 \(65\)), αρά υπάρχουν το πολύ οι διπλάσιες καταστάσεις (για complemented και όχι complemented). Οι δυνατές μεταβάσεις είναι \(4\), και η σύγκριση μεταξύ ακολουθιών θέλει \(\mathcal{O}(N)\) χρόνο, άρα ο αλγόριθμος θέλει συνολικά \(\mathcal{O}(N^2)\) χρόνο, που είναι αρκετό για να περάσει περίπου το 50% των testcases. Θα βρείτε ολόκληρο τον κώδικα εδώ.
Γρηγορότερη εύρεση βέλτιστης ακολουθίας κινήσεων – \(\mathcal{O}(N)\)
Το μεγαλύτερο πρόβλημα της προηγούμενης λύσης είναι η εύρεση της βέλτιστης ακολουθίας σε \(\mathcal{O}(N^2)\). Τώρα, θα δούμε πώς μπορεί να γίνει πιο αποδοτικά.
Η ιδέα είναι να κρατάμε τις δυνατές καταστάσεις της στιγμής \(i\) ταξινομημένες με την λεξικογραφική σειρά των βέλτιστων ακολουθιών κινήσεων για να φτάσουμε σε αυτές. Μετά, εξετάζουμε τις δυνατές κινήσεις για κάθε μία από αυτές με λεξικογραφική σειρά, δηλαδή \(\lbrace cp, crp, p, rp \rbrace\). Όπως πριν για κάθε κατάσταση κρατάμε την μικρότερη ακολουθία, αλλά αν υπάρχουν δύο με ίσο μήκος, τότε κρατάμε αυτή που κοιτάξαμε πρώτη (γιατί είναι λεξικογραφικά μικρότερη). Τέλος, ταξινομούμε τις καταστάσεις του \(i+1\), με βάση την σειρά των ακολουθιών κινήσεων που οδήγησαν σε αυτές. Η εικόνα παρακάτω δείχνει δύο πιθανές εκδοχές.
Οι μεταβάσεις αλλάζουν ως εξής:
map<State, tuple<int /* order ID */, long /* state ID */, long /* length */> > next;
vector<pair<int /* operation ID */, long /* ordered ID */> > par;
set<tuple<int /* order ID */, long /* state ID */, long /* length */, State> > ordered_current;
// Κατάσταση cp (πρώτη λεξικογραφικά).
State cp_state; cp_state.append_right(3 - x[0]); cp_state.is_complemented = true;
ordered_current.insert(make_tuple(0, 0, 2, cp_state));
par.push_back({par.size(), -1});
// Κατάσταση p.
State p_state; p_state.append_right(x[0]);
ordered_current.insert(make_tuple(1, 1, 1, p_state));
par.push_back({par.size(), -1});
// Δεν έχει νόημα να κάνουμε rp στην αρχή.
for (size_t i = 1; i < x.size(); ++i) {
long order_id = 0;
for (const auto cur : ordered_current) {
const State state = std::get<3>(cur);
int cur_id = std::get<1>(cur);
int length = std::get<2>(cur);
int current_val = state.is_complemented ? (3 - x[i]) : x[i];
// Complement και push.
if (state.can_append(3-current_val)) {
State new_state = state;
new_state.append_right(3-current_val);
new_state.is_complemented = !new_state.is_complemented;
compare_and_add(next, par, new_state, order_id, length + 2, cur_id, CP);
}
// Complement, reverse και push.
State complement_reverse_state = state.reverse();
complement_reverse_state.is_complemented = !complement_reverse_state.is_complemented;
if (complement_reverse_state.can_append(3 - current_val)) {
complement_reverse_state.append_right(3 - current_val);
compare_and_add(next, par, complement_reverse_state, order_id, length + 3, cur_id, CRP);
}
// Push.
if (state.can_append(current_val)) {
State new_state = state;
new_state.append_right(current_val);
compare_and_add(next, par, new_state, order_id, length + 1, cur_id, P);
}
// Reverse και push.
State reverse_state = state.reverse();
if (reverse_state.can_append(current_val)) {
reverse_state.append_right(current_val);
compare_and_add(next, par, reverse_state, order_id, length + 2, cur_id, RP);
}
++order_id;
}
// Λεξικογραφική ταξινόμηση.
ordered_current.clear();
for (const auto& val : next) {
ordered_current.insert(
make_tuple(std::get<0>(val.second), std::get<1>(val.second), std::get<2>(val.second), val.first));
}
next.clear();
}
Όπου η compare_and_add αλλάζει ως εξής:
void compare_and_add(
map<State, tuple<int, long, long> >& next, vector<pair<int, long> >& par, State state,
long order_id, long length, long par_id, long operation_id) {
if (next.find(state) == next.end() || std::get<2>(next[state]) > length) {
next[state] = make_tuple(order_id, par.size(), length);
par.push_back({operation_id, par_id});
}
}
Κρατώντας για κάθε κατάσταση s την κατάσταση par[s] που οδήγησε στην βέλτιστη ακολουθία κινήσεων στο s, μπορούμε να ανακτήσουμε την βέλτιστη ακολουθία, ακολουθώντας τους δείκτες par[s].
string str;
// Εύρεση κατάστασης με την βέλτιστη ακολουθία.
long smallest_val = std::get<2>(*ordered_current.begin()),
smallest_id = std::get<1>(*ordered_current.begin());
for (const auto val : ordered_current) {
if (smallest_val > std::get<2>(val)) {
smallest_val = std::get<2>(val);
smallest_id = std::get<1>(val);
}
}
long cur = smallest_id;
while (cur != -1) {
long val = par[cur].first;
if (val == CP) str += "pc";
else if (val == 1) str += "p";
else if (val == 2) str += "pr";
else if (val == 3) str += "prc";
cur = par[cur].second;
}
reverse(str.begin(), str.end());
Η χρονική πολυπλοκότητα αυτού του αλγορίθμου είναι \(\mathcal{O}(N)\), αλλά επειδή η σταθερά του \(N\) είναι μεγάλη, η λύση παίρνει περίπου 70%. Θα βρείτε ολόκληρο τον κώδικα εδώ.
Βέλτιστη λύση – \(\mathcal{O}(N)\)
Η παραπάνω λύση αφιερώνει αρκετό χρόνο στη σύγκριση και δημιουργία καταστάσεων. Πιο συγκεκριμένα, κάθε ένα από τα positions, leftmost, rightmost και count, κρατάνε έναν ακέραιο \(\leq 5\). Άρα χρησιμοποιούμε μόνο \(21\) bits από \(7\) ακεραίους. Επειδή χρειαζόμαστε μόνο \(22\) bits (\(21\) συν ένα για το is_complemented), μπορούμε να τα αποθηκεύσουμε όλα σε έναν ακέραιο \(32\) bit. Διαλέγουμε την εξής αναπαράσταση (αλλά υπάρχουν πολλές παρόμοιες):
Για το παράδειγμα
\[\underbrace{2\; 2 \; 2 \; 2}_{1} \; \; \; \underbrace{3\; 3 \; 3}_{2} \; \; \;\underbrace{0\; 0 \; 0 \; 0 \; 0}_{3}\]η αναπαράσταση είναι η παρακάτω (όπου το \(x\) αναπαριστά αν είναι complemented ή όχι η κατάσταση). Ας σημειωθεί ότι στην παρακάτω εικόνα έχουμε γράψει αριστερά τα λιγότερο σημαντικά ψηφία της δυαδικής αναπαράστασης, και δεξιά τα περισσότερο σημαντικά, οπότε με \(110\) στο δυαδικό εννοούμε \(3\) στο δεκαδικό (όχι \(6\)).
Γι’αυτό θα χρειαστούμε κάποια bit tricks (μπορείτε να διαβάσετε περισσότερα εδώ). Πιο συγκεκριμένα, χρειαζόμαστε τα εξής:
- Διάβασμα τριών bits από έναν ακέραιο (όπου
_111 = 7):
/* Επιστρέφει τα τρία bits στην θέση offset. */
int get_three_bits(int offset) const {
// 1. Δημιουργούμε ένα ακέραιο _111με μόνο τρία bits.
// 2. Μετακινούμε αυτά τα bits κατά offset θέσεις.
// 3. Κάνοντας state & (_111 << offset) μένουν μόνο οι θέσεις
// [offset, offset + 3) του state.
// 3. Μετακινώντας αριστερά (state & (_111 << offset)) κατά offset
// μας μένει ο αριθμός στα τρία αυτά bits.
return (state & (_111 << offset)) >> offset;
}
- Αλλαγή τριών bits σε ένα ακέραιο:
/* Θέτει τα τρία bits στην θέση offset. */
void set_three_bits(int offset, int val) {
// 1. Δημιουργούμε έναν ακέραιο ~(_111 << offset) με bit 1 παντού
// εκτός από τις θέσεις [offset, offset + 3).
// 2. Κάνοντας state & ~(_111 << offset) μένουν όλες οι άλλες θέσεις του state.
// 3. Μετακινώντας δεξιά την τιμή val, πηγαίνει στην θέση offset.
// 4. Κάνοντας |= (val << offset) μεταφέρουμε αυτή την τιμή στο state.
state &= ~(_111 << offset);
state |= (val << offset);
}
- Διάβασμα ενός bit:
bool is_complemented() const { return state & 1; }
- Αλλαγή ενός bit:
void flip_complemented() { state ^= 1; }
Το μόνο που χρειάζεται να αλλάξουμε από την προηγούμενη λύση είναι το State:
struct State {
unsigned long state;
/* Επιστρέφει τα τρία bits στην θέση offset. */
int get_three_bits(int offset) const {
// 1. Δημιουργούμε ένα ακέραιο _111με μόνο τρία bits.
// 2. Μετακινούμε αυτά τα bits κατά offset θέσεις.
// 3. Κάνοντας state & (_111 << offset) μένουν μόνο οι θέσεις
// [offset, offset + 3) του state.
// 3. Μετακινώντας αριστερά (state & (_111 << offset)) κατά offset
// μας μένει ο αριθμός στα τρία αυτά bits.
return (state & (_111 << offset)) >> offset;
}
/* Θέτει τα τρία bits στην θέση offset. */
void set_three_bits(int offset, int val) {
// 1. Δημιουργούμε έναν ακέραιο ~(_111 << offset) με bit 1 παντού
// εκτός από τις θέσεις [offset, offset + 3).
// 2. Κάνοντας state & ~(_111 << offset) μένουν όλες οι άλλες θέσεις του state.
// 3. Μετακινώντας δεξιά την τιμή val, πηγαίνει στην θέση offset.
// 4. Κάνοντας |= (val << offset) μεταφέρουμε αυτή την τιμή στο state.
state &= ~(_111 << offset);
state |= (val << offset);
}
int positions(int i) const {
int offset = 1 + 3 + 3 + 3 * i;
return get_three_bits(offset);
}
void set_position(int i, int val) {
int offset = 1 + 3 + 3 + 3 * i;
set_three_bits(offset, val);
}
int rightmost() const { return get_three_bits(1); }
int leftmost() const { return get_three_bits(1 + 3); }
bool is_complemented() const { return state & 1; }
void set_rightmost(int val) { set_three_bits(1, val); }
void set_leftmost(int val) { set_three_bits(1 + 3, val); }
void flip_complemented() { state ^= 1; }
int count() const {
int offset = 1 + 3 + 3 + 12;
return get_three_bits(offset);
}
void set_count(int val) {
int offset = 1 + 3 + 3 + 12;
set_three_bits(offset, val);
}
State reverse() const {
State other = *this;
// Αντιστρέφουμε τις θέσεις των στοιχείων που έχουμε δει.
int cnt = count();
for (size_t i = 0; i < 4; ++i) {
int cur_position = other.positions(i);
if (cur_position != 0) other.set_position(i, (cnt + 1) - cur_position);
}
other.set_leftmost(rightmost());
other.set_rightmost(leftmost());
return other;
}
void append_right(int val) {
if (positions(val) == 0) {
int cnt = count();
++cnt;
set_count(cnt);
set_position(val, cnt);
if (cnt == 1) set_leftmost(val);
set_rightmost(val);
}
}
bool can_append(int val) const {
return rightmost() == val || positions(val) == 0;
}
bool operator<(const State& other) const {
return state < other.state;
}
State() {
state = 0;
set_leftmost(5);
set_rightmost(5);
}
};
Υπάρχουν και άλλες βελτιστοποιήσεις που θα μπορούσαν να γίνουν, αλλά αυτή είναι αρκετή ώστε ο κώδικας περάσει όλα τα testcases. Θα βρείτε ολόκληρο τον κώδικα εδώ.