Να γράψω λύση ή να μη γράψω; Ιδού η απορία!
Πολλές φορές οι κώδικες που κυκλοφορούν για λύσεις σε προβλήματα διαγωνισμών και μη, είναι κατανοητοί μόνο από αυτούς που ... ξέρουν ήδη να λύσουν τα αντίστοιχα προβλήματα
Ένας κώδικας (ειδικά ενός διαγωνιζόμενου) είναι τόσο σύντομος και συχνά ακαταλαβίστικος και δεν βοηθά την κατανόηση της λύσης. Ο λόγος που γίνεται αυτό είναι γιατί ο λύτης έχει πιθανότατα χρησιμοποιήσει ένα σύνολο γνώσεων στη λύση του, με σκοπό το συντομότερο σε κώδικα ή πολυπλοκότητα αποτέλεσμα. Αυτές οι "ταρζανιές" μπορεί να αποθαρρύνουν τους νεαρούς μαθητές που δεν έχουν την ανάλογη γνώση και άνεση στο χειρισμό της γλώσσας, να ξέρετε όμως ότι αυτές οι ταρζανιές δεν είναι πάντα απαραίτητες και πολλές φορές με μοναδικό κόστος την αύξηση των γραμμών του κώδικα, μπορούν οι ίδιες λειτουργίες να γραφτούν πιο απλά.
Ας αρχίσουμε τη συζήτηση πάνω στο πρόβλημα μας. (ουφ, επιτέλους )
Στο συγκεκριμένο πρόβλημα, η ύπαρξη δυο δρόμων είναι ένα κερασάκι στο γλυκό, είναι το επιδόρπιο και δεν χρειάζεται να μας απασχολεί παρά μόνο στο τέλος. Αρκεί να βρούμε τους συνδυασμούς για τον ΕΝΑ δρόμο και να τον υψώσουμε στο τετράγωνο. Αν έχουμε δηλαδή k συνδυασμούς για τον ένα δρόμο, τότε έχουμε άλλους k για τον άλλο. Πόσοι είναι οι συνδυασμοί και για τους δύο δρόμους;
για κάθε έναν από τους k συνδυασμούς του ενός δρόμου,
έχουμε k συνδυασμούς από τον άλλο δρόμο. Αρα για τους k συνδυασμούς του πρώτου δρόμου, έχουμε συνολικά k*k συνδυασμούς με τους δύο δρόμους μαζί.
Ας δούμε ποια είναι η αρχική ιδέα αν θέλουμε να λύσουμε το πρόβλημα με τον ένα δρόμο, όχι προσπαθώντας να ακολουθήσουμε το γνωστό τύπο για εύρεση του ν-οστού όρου της γνωστής ακολουθίας (ονόματα δε λέμε), αλλά με pure δυναμικό προγραμματισμό.
Ο δυναμικός προγραμματισμός είναι μια αξιοποίηση της επαγωγικής μεθόδου που διδάσκεται στο γυμνάσιο (αν δεν κάνω λάθος):
α) υπολογίζω την αρχική τιμή (για το μικρότερο δυνατό πρόβλημα, συνήθως ενός στοιχείου) και
β) υπολογίζω την τιμή για i+1 αν ξέρω ήδη την απάντηση για i στοιχεία.
Οπότε όπως καταλαβαίνετε εφόσον ξέρουμε την απάντηση για Ν==1 (από το (α)), μπορούμε να βρούμε το επόμενο για Ν==2 (από το (β)) και το επόμενο για Ν==3 (από το (β)) κλπ
Γραμμική λύση Ο(Ν):
α) αν έχουμε 1 τμήμα δρόμου, έχουμε μόνο δυο συνδυασμούς (building=κτήριο ή void=κενό)
β) ας υπολογίσουμε πόσοι συνδυασμοί θα υπάρχουν για k+1 τμήματα.
Για κάθε αριστερό κομμάτι δρόμου k τμημάτων, τότε θα προσθέσουμε ένα ακόμα τμήμα (και να πάμε στα k+1 τμήματα). Το νέο τμήμα αυτό αν θα είναι void, θα έχει όσους συνδυασμούς είχαμε για τα k τμήματα (ανεξάρτητα αν τελείωναν σε building ή void).
Αν το νέο τμήμα είναι building, θα έχουμε όσους συνδυασμούς είχαμε για τα k τμήματα και τελείωναν σε void.
Το άθροισμα των δυο τιμών είναι οι συνολικοί συνδυασμοί των k+1 τμημάτων.
Λογαριθμική λύση O(logN):
Στην προηγούμενη λύση, ανεβαίναμε ένα ένα τα τμήματα μέχρι να φτάσουμε στα Ν του προβλήματος. Οι γραμμικές λύσεις για Ν γύρω στο 10^6, απαιτούν περίπου 1 δευτερόλεπτο. Αν το N όμως είναι 2^63 (περίπου 10^19), δεν αρκεί η παραπάνω λύση. Για μεγάλα Ν πρέπει να σκαρφαλώνουμε πιο γρήγορα στο Ν.
Η διαφορά από την προηγούμενη (γραμμική) μέθοδο, είναι ότι θέλω να προσθέτω μπλοκ δρόμου με άλλο μπλοκ δρόμου (μπλοκ = δρόμος με ένα ή περισσότερα διαδοχικά τμήματα). Προφανώς για να ενώσουμε δύο μπλόκ δεν θα πρέπει το πρώτο μπλοκ να τελειώνει σε building και το δεύτερο να αρχίζει από building. Άρα πρέπει να κρατάμε ΧΩΡΙΣΤΑ για κάθε υπολογισμένο μπλοκ, πόσοι συνδυασμοί:
- ξεκινούν από void και τελειώνουν σε void και
- ξεκινούν από void και τελειώνουν σε building και
- ξεκινούν από building και τελειώνουν σε void και
- ξεκινούν από building και τελειώνουν σε building
οπότε όταν συνδυάζουμε δυο μπλοκ, θα ξαναϋπολογίζουμε τις τέσσερις νέες τιμές του νεοϋπολογιζόμενου μεγαλύτερου μπλοκ.
Μια σημείωση ακόμα στη συνένωση δυο μπλόκ: αν από το πρώτο μπλόκ είχαμε a συνδυασμούς από building σε void και από το δεύτερο μπλοκ b συνδυασμούς από building σε building, τότε στο συνενωμένο δρόμο θα πρέπει να προσθέσουμε άλλους a*b συνδυασμούς σε αυτούς που ξεκινούν από building και τελειώνουν σε building (γιατί για οποιοδήποτε συνδυασμό του πρώτου δρόμου από τους a, έχουμε b συνδυασμούς από τον δεύτερο δρόμο, άρα συνολικά a*b συνδυασμούς)
Μια λογαριθμική λύση είναι να διαιρώ το Ν δια δύο μέχρι να φτάσω στο 1 (top down programming: ξεκινάμε από το συνολικό πρόβλημα και κόβουμε συνεχώς σε μικρότερα).
- Spoiler: show
Κώδικας: Επιλογή όλων
//https://www.pdpforum.eu.org/forum/viewtopic.php?f=3&p=9738#p9738
//dp, matrix exponantiation, fibonacci, binary exponantiation
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
using namespace std;
typedef long long ll;
const ll MOD = 1000007LL;
ll N = 19;//ll(1e18);
struct segm {
bool init;
ll sol[2][2];//sol[start_digit][end_digit], digits in {0=empty,1=building}
segm(){memset(this,0,sizeof(*this));}
ll count() const {
ll ans = 0;
for(int i=0;i<=1;i++){
for(int j=0;j<=1;j++){
ans += sol[i][j];
if(ans>=MOD)
ans -= MOD;
}
}
return ans;
}
};
map<int,segm> S;
inline ll trunc(ll x){ return x % MOD; }
segm combine(const segm& A,const segm& B){
segm res;
for(int start=0;start<=1;start++){//start res (start of combined segment)
for(int stop=0;stop<=1;stop++){//stop res (stop of combined segment)
for(int aend=0;aend<=1;aend++){//end of first subseg
for(int bstart=0;bstart<=1;bstart++){//start of second subseg
if(aend && bstart)//unaccepted: two consequtive buildings
continue;
ll r1 = trunc(A.sol[start][aend]);
ll r2 = trunc(B.sol[bstart][stop]);
res.sol[start][stop] += trunc(r1*r2);
if(res.sol[start][stop]>=MOD)
res.sol[start][stop]-=MOD;
}
}
}
}
return res;
}
segm solve(int n){
if(!S[n].init){
if(n==1){
S[1].sol[0][0] = S[1].sol[1][1] = 1;
} else {
if(n&1)
S[n] = combine(solve(n>>1),solve((n>>1)+1));
//what about n/2+1 plus n/2?
else
S[n] = combine(solve(n>>1),solve(n>>1));
}
S[n].init = true;
}
return S[n];
}
int main(){
ll ans = solve(n).count();
printf("n=%d, 1road=%lld, 2roads=%lld\n",n,ans,trunc(ans*ans));
return 0;
}
Μια εναλλακτική λογαριθμική λύση είναι να προϋπολογίσουμε μπλοκ δρόμων με μήκος δυνάμεις του 2 και μετά να συνθέσουμε τα μπλόκ για να φτάσουμε στο Ν (bottom up programming).
(ΣΣ οποιοσδήποτε φυσικός αριθμός μπορεί να γραφτεί σαν άθροισμα δυνάμεων του 2, αυτό μάλιστα χρησιμοποιεί και η συνήθης τεχνολογία των υπολογιστών -μέχρι τώρα- για την αναπαράσταση αριθμών και την ονομάζουμε δυαδικό σύστημα).
Αρα προϋπολογίζουμε τους συνδυασμούς για 1,2,4,8,16,32,64,128,... (χωρίς να ξεπεράσουμε το Ν διότι δεν θα μας χρησιμεύσει).
Ποια μπλόκ θα συνδυάσουμε για τον Ν μήκους δρόμο;
Όσες από τις παραπάνω δυνάμεις του 2 έχουν άθροισμα ακριβώς Ν. Είναι δύσκολο αυτό να το βρούμε; Όχι βέβαια, αρκεί να δούμε την αναπαράσταση του Ν στο δυαδικό σύστημα.
π.χ. ο αριθμός Ν = 1000 (στο δεκαδικό σύστημα), είναι o 001111101000(στο δυαδικό)
- Spoiler: show
- ή ο 0χ3E8 στο δεκαεξαδικό
Άρα αν ελέγχουμε τα bit με ένα loop ένα προς ένα, κάθε φορά που φτάνουμε σε ένα Bit με τιμή 1, προσθέτουμε στο μπλοκ της τελικής λύσης μας και την αντίστοιχη δύναμη.
- Spoiler: show
Κώδικας: Επιλογή όλων
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
ll N = 19;
const ll MOD = 10000007LL;
ll t(ll x){
return x % MOD;
}
struct seg {
ll s[2][2];
seg(){
memset(this,0,sizeof(*this));
}
ll sum() const {
ll ans = 0;
for (int i=0;i<2;i++)
for(int j=0;j<2;j++)
ans += s[i][j];
return t(ans);
}
} dp[8*sizeof(ll)];
seg combine(const seg& a,const seg& b){
seg ans;
for(int astart=0;astart<2;astart++)
for(int bend=0;bend<2;bend++)
for (int i=0;i<2;i++)//aend
for(int j=0;j<2;j++){//bstart
if(i && j) continue;
ans.s[astart][bend] += t(a.s[astart][i]*b.s[j][bend]);
if(ans.s[astart][bend]>=MOD)
ans.s[astart][bend]-=MOD;
}
return ans;
}
int main(){
dp[0].s[0][0] = dp[0].s[1][1] = 1;//dp[0] stands for length==1
for(ll i=1,length=2;length<=N;i++,length*=2){
dp[i] = combine(dp[i-1],dp[i-1]);
}
seg ans;
int count = 0;
for(ll i=0,length=1; length<=N;i++,length*=2){
if(N & length){
if(count++ == 0)
ans = dp[i];
else
ans = combine(ans,dp[i]);
}
}
printf("1road=%lld\t2roads=%lld\n",ans.sum(),t(ans.sum() * ans.sum()));
return 0;
}
- Spoiler: show
Κώδικας: Επιλογή όλων
//https://www.pdpforum.eu.org/forum/viewtopic.php?f=3&p=9738#p9738
//tags: dp, matrix exponentiation, fibonacci, binary exponentiation
//current solution: binary exponentiation
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cassert>
using namespace std;
typedef long long ll;
const ll MOD = 1000007LL;
ll N = 19;//ll(1e18);
//building=1, void=0
ll dp[8 * sizeof(ll) * 2][2][2]; /*[number of long long bits * 2][startofsegment][endofsegment]*/
ll sum[8 * sizeof(ll) * 2];
inline ll t(ll x){ return x % MOD; }
void combine(int dest,int seg1,int seg2){
//combine segment dp[seg1][i][j] with dp[seg2][k][l] to dp[dest][i][l]
sum[dest] = 0ll;
for(int i=0;i<2;i++)
for(int l=0;l<2;l++)
for(int j=0;j<2;j++)
for(int k=0;k<2;k++){
if(k && j)continue;//no two consecutive buildings
ll extra = t(dp[seg1][i][j] * dp[seg2][k][l]);
dp[dest][i][l] = t(dp[dest][i][l]+extra);
sum[dest] = t(sum[dest] + extra);
}
}
int main(){
//precompute fibonacci for single line road on 2's powers
dp[0][0][0] = dp[0][1][1] = 1;
int used;//entries used in dp[] array
for(used=1;(1LL<<used)<=N;used++){//only necessary powers of 2 (<=N)
//combine segment dp[used-1] with dp[used-1] to double the length
combine(used,used-1,used-1);
printf("precompute for 2^%d = %8lld gives \t%lld\n",used,1LL<<used,sum[used]);
}
//solve for N
int prevseg = -1;
for(int i=0;(1LL<<i)<=N;i++)//combine all 2's powers that forms the N
if(N & (1LL<<i))
if(prevseg<0)
prevseg = i;
else
combine(used,i,prevseg), prevseg = used++;
ll ans = (prevseg<0LL) ? 0LL : sum[prevseg];//in case N==0
printf("singleroad=%lld,\tdoubleroad=%lld\n",ans,t(ans*ans));
return 0;
}
/*
H παράσταση 1LL<<k (ολίσθηση του 1, k φορές προς τα αριστερά) μας δίνει το 2^k.
Οπότε κάνοντας μια απαρίθμηση στις δυνάμεις του 2 (με τη χρήση του 1LL<<i στο for) βρίσκουμε αν μια δύναμη
χρειάζεται στην έκφραση του Ν (η συνθήκη N & (1LL<<i) θα είναι αληθής) ή όχι (συνθήκη ψευδής).
Μια λεπτομέρια στην υλοποίηση. Η combine αποθηκεύει αποτελέσματα μόνο στον πίνακα dp[] οπότε χρησιμοποιούμε
τις πρώτες θέσεις του dp[] για τα precompute και τις επόμενες θέσεις για τη σύνθεση του Ν.
Η μεταβλητή used φροντίζει να μην ξαναχρησιμοποιήσουμε κατά λάθος κάποια θέση του dp[]
*/
Αν υπάρχουν απορίες, ρωτήστε άφοβα.
Αν βρείτε λάθη έκφρασης στο κείμενο, sorry αλλά μετά από κάποιο χρόνο δεν γίνεται άλλο edit!