Come da titolo, dato che non sono molto pratico con la dp
Direi di si, io ho usato tabelle parziali per il calcolo della somma delle cifre sia base 2 che base 3.
hai precalcolato la soluzione?
No non ho precalcolato niente. Ma un numero a x bit può essere può essere visto come composto dalla sua parte alta di x/2 bit e la sua parte bassa di x/2 bit e se è lungo come tempo ed occupazione di memoria calcolare una tabella di 2^x elementi calcolare quella di 2^x/2 è fattibile. Stesso discorso per i numeri in base 3. 100.000.000 è circa 2^27 o 3^17 se non ricordo male.
1 Mi Piace
Ah ok ho capito ,buona idea.
Io ho provato come hai detto te, ma ci sono due o tre test case dell ultimo subtask che vanno out of time e inoltre non so perché ma le maschere non funzionano sempre.
#include <bits/stdc++.h>
#define MAX 10000000 //Constraint diviso volutamente per 10 in quanto 100milioni mandano il pgm out of memory.
// bit + significativo come bit di segno
#define UPPER -21474181120 //sarebbe in binario: 11111111111111110000000000000000
#define LOWER 65535 //sarebbe in binario: 00000000000000001111111111111111
using namespace std;
unsigned int T, i,j,offset,c,num,sum2,sum3;
bool stay;
vector<int> sums;
int base2(int num);
int base3(int num);
int main() {
ifstream in("input.txt");
ofstream out("output.txt");
sums.assign(MAX,0);
in >> T;
for(i=0; i<T; i++) {
in >> num;
c=0;
offset=1;
for(j=num,stay=true;stay && j>=1;j--){
//il controllo j<Max serve perché non memorizzo nell Array il count di numeri> di 10mil per motivi prima menzionati
if(j<MAX && sums[j]>0){
c+=sums[j];
offset=j+1;
stay=false;
}
}
for(j=offset;j<=num;j++){
//controllo standard funziona, ma va out of time in alcuni test case dell ultimo subtask
/*sum2=base2(j);
sum3=base3(j);*/
//funziona solo in alcuni test case e impiega circa lo stesso tempo del metodo sopracitato
sum2=base2(j&UPPER)+base2(j&LOWER);
sum3=base3(j&UPPER)+base3(j&LOWER);
if(sum2==sum3)
c++;
//se il numero è >10mil non posso metterlo nell'array
if(j<MAX)
sums[j]=c;
}
out << c << " ";
}
out << endl;
return 0;
}
int base2(int num){
long long int sum=0;
while(num>0){
sum+=num%2;
num/=2;
}
return sum;
}
int base3(int num){
long long int sum=0;
while(num>0){
sum+=num%3;
num/=3;
}
return sum;
}
Il pgm fa in modo da non ricalcolare la quantità di numeri speciali contenuti in numero x(a partire da 1 fino ad x) così “massimizzo i tempi” , ad esempio se calcolo i numeri speciali contenuti tra 1 e 10 e il prossimo numero di input è 11, non dovrò ricalcolare niente perché nell array ho salvato il valore del range 1-10… però stranamente mi dà execution timed out🤨.
Ho pensato anche ad un altra maniera, cioè quella di calcolarmi direttamente tutti i numeri speciali in un ciclo che va da 1 a 10mil, e per i numeri > di 10 mil , calcolarli direttamente senza “intabellarli” nell’array, però credo che comunque non stia nei tempi.
Non è sicuramente la tecnica più pratica né quella più istruttiva, però facendo un precalcolo in maniera intelligente rientri abbondantemente nel tl
In particolare dopo diversi test sono arrivato alla conclusione che puoi portare questa strategia al limite precalcolando tutti i valori multipli di 4030 in base 92 (dove la cifra che corrisponde a 0 è # e quella che corrisponde a 91 è ~)
precalcolo significa che calcoli te i risultati e li carichi direttamente sul sorgente senza far eseguire operazioni al pgm, quindi a meno che tu non li calcoli esternamente al pgm(e in tal caso creeresti un sorgente troppo grande per la piattaforma) non precalcoli niente… Comunque non ho capito cosa intendi e non trovo modo migliore per risolvere l’esercizio, perchè se hai un numero tipo 100milioni, sei per forza obbligato a calcolare i numeri speciali nel range 1-100mil e come ha detto @v.bizzarri puoi spezzare l’int da 32 bit in due parti da 16 in cui alla fine andrai eseguire calcoli su un numero che è grande massimo 2^16, risparmiando un sacco di tempo. In ogni caso la mia domanda era un’altra, per qualche ragione usando le maschere UPPER e LOWER sul numero letto per spezzarlo in parte alta e bassa non funziona🤔
100 milioni è fra 2^27 e 2^28 ed il mio programma prima di tutto calcola la tabella della somma delle cifre dei primi 2^14 numeri. 100 milioni è fra 3^17 e 3^18 ed il mio programma passa a calcolare la tabella della somma delle cifre dei primi 3^9 numeri. Queste tabelle sono di dimensioni modeste e si fa presto a calcolarle e queste se usate opportunamente servono per calcolare la quantità di cifre base 2 e base 3 di tutti i numeri fino a 100 milioni.
Quello che fai tu in effetti non cambia niente rispetto alle tua versione originale e giustamente il tempo non ti cambia.
Faccio l’esempio di come puoi lavorare per la base 2:
dato un numero x:
LOW(x)=x&0x3fff;
HIGH[x]=x>>14;
totcifre[x]=tab2[LOW[x]]+tab2[HIGH[x]]
Inoltre puoi salvare tutti i numeri speciali (non sono più di 7 milioni).
Mi stava passando per la testa che avessi inteso così , solo che mi sono fissato sull’ algoritmo descritto sopra, perché qualcosa dovrebbe essere cambiato: metti che ho come numero 100mil, invece che eseguire le divisioni su 100mil (lunghe)le eseguo 4 volte su 2^16 (parte alta e basse in base 2 e base 3)…si ottimizzerebbe ma probabilmente non abbastanza
J&UPPER andrebbe shiftato a destra di 16 posizioni altrimenti base2 farà fino a 28 cicli invece di 16
inoltre quella suddivisione va bene per i numeri in base 2 non per i numeri base 3:
devi separare su potenze di tre (3^9):
alta3=j/(3^9)
bassa3=j%(3^9)
Ma com’è possibile scusa? Io nella mia ci faccio stare i multipli di 200 in base 10 