Timeout per Bases Conversion (ois_23)

Salve, ho provato a risolvere ois_23, ma ho avuto qualche problema con la complessità di tempo (va oltre i 3 secondi previsti per input arbitrariamente grandi – ho fatto 65/100). Ci ho sbattuto la testa, ma non ho trovato soluzioni alternative alla mia, motivo per cui mi rivolgo direttamente al forum.

Questo è il mio codice:

#include <algorithm>
#include <iostream>
#include <map>
#include <vector>

unsigned int T, i;
unsigned long k, c;

using namespace std;

unsigned int sum(unsigned int n, unsigned int base)
{
    unsigned int result = 0;

    while (n > 0)
    {
        result += n % base;
        n /= base;
    }

    return result;
}

int32_t main()
{
    cin >> T;

    vector<unsigned long> input(T);
    map<unsigned long, unsigned long> special_numbers;

    for (i = 0; i < T; i++)
    {
        cin >> input[i];
        special_numbers[input[i]] = 0;
        k = max(k, input[i]);
    }

    for (i = 1; i <= k; i++)
    {
        if (sum(i, 2) == sum(i, 3))
        {
            c++;
        }

        if (special_numbers.count(i) == 1)
            special_numbers[i] = c;
    }

    for (i = 0; i < T; i++)
    {
        cout << special_numbers[input[i]] << " ";
    }

    return 0;
}

L’idea era di prendere gli input, inserirli in un apposito vettore e adottarli come chiave per una mappa (utile per poi inserire i “numeri speciali”). Credo che a prendere molto tempo siano le funzioni che calcolano la somma delle cifre in base 2 e 3. Come potrei migliorare questa soluzione? Vi ringrazio in anticipo.

Per risolvere l’esercizio io ho evitato di utilizzare la mappa, ma semplicemente mi tengo in un array ordinato i vari N_i e poi calcolo, come hai fatto tu, le somme delle cifre in base 2/3 di tutti i numeri fino al massimo tra gli N_i.
Per rendere più veloce la cosa, invece di usare la funziona che somma le cifre in una determinata base tengo 2 array che mantengono la rappresentazione in base 2 ed in base 3 del numero attuale. In questo modo posso implementare a mano l’incremento e, per sapere la somma delle cifre X+1, non devo ricalcolarlo da 0 ma mi baso sulla somma delle cifre di X e l’aggiorno in base alle cifre che ho cambiato incrementando X.

È poi possibile, è veloce ma non è molto costruttivo, precalcolarsi degli specifici valori da scrivere direttamente nel sorgente in modo da evitare calcoli successivi.

2 Mi Piace

image

3 Mi Piace

Ti ringrazio. In effetti, avevo pensato di precalcolarmi dei valori fino a 10\,000\,000, ma non ho ancora trovato un modo per inserirli in un array con constexpr.

Ottimo approccio quello di mantenere la rappresentazione del numero attuale nelle 2 basi in 2 array distinti, ma non ho capito bene come gestire l’incremento.

Il sorgente che puoi caricare deve avere dimensione entro un limite massimo che è abbastanza ridotto, e non ti permette quindi di scrivere dunque i risultati per ogni possibile N_i, in ogni caso puoi caricare solo alcune informazioni che ti evitano parzialmente dei calcoli.
Per quanto riguarda l’incremento manuale, tu puoi rappresentare X in base b come un array v[] dove v[i] è l’iesima cifra di X in base b, allora quando incrementi X dovrai incrementare di 1 v[0] e nel caso in cui v[0] diventi uguale a b allora v[0] diventa 0 ed incrementi v[1] e nel caso in cui v[1] diventi uguale a b…(procedi con lo stesso ragionamento)[In pratica stai semplicemente incrementando un numero in base b]. Mentre cambi i valori relativi all’incremento puoi aggiornare la somma delle precedenti.

Se hai X = 11_{10} = 1011_2 e somma delle cifre S = 1+0+1+1=3 incrementando X ottieni
X+1 = 1100_2 (tramite il ragionamento di prima) , e mentre modifichi le ultime 3 cifre puoi aggiornare la somma che risulterà = S -1 -1 +1 =S - 1 = 2.
Questo ha il vantaggio che in molti casi (soprattutto quando il X ha molte cifre) andrai a modificare un numero di cifre molto piccolo.

1 Mi Piace

Ho implementato ciò ed effettivamente vi è stato un netto miglioramento in termini di prestazione, ma non tale da garantirmi di stare sotto i 3 secondi in tutti i testcase. Magari utilizzare una mappa e controllare se un valore vi appartiene è troppo dispendioso in termini di tempo? Quale sarebbe la cosa migliore?

In ogni caso, ecco il codice aggiornato:

#include <algorithm>
#include <iostream>
#include <map>
#include <vector>

unsigned int T, i;

unsigned short c_2, c_3;
unsigned short base2[27]; // 27 is the maximum number of digits a number can have in base 2 without being greater than 100_000_000 (base 10)
unsigned short base3[17]; // See base2
unsigned short j;

unsigned long k, c;

using namespace std;

int32_t main()
{
    cin >> T;

    vector<unsigned long> input(T);
    map<unsigned long, unsigned long> special_numbers;

    for (i = 0; i < T; i++)
    {
        cin >> input[i];

        special_numbers[input[i]] = 0;

        k = max(k, input[i]);
    }

    for (i = 1; i <= k; i++)
    {
        for (j = 0;; j++)
        {
            if (++base2[j] >= 2)
            {
                c_2 -= base2[j]-1;
                base2[j] = 0;
                continue;
            }

            c_2++;
            break;
        }

        for (j = 0;; j++)
        {
            if (++base3[j] >= 3)
            {
                c_3 -= base3[j]-1;
                base3[j] = 0;
                continue;
            }

            c_3++;
            break;
        }

        if (c_2 == c_3)
            c++;

        if (special_numbers.count(i) == 1)
            special_numbers[i] = c;
    }

    for (i = 0; i < T; i++)
    {
        cout << special_numbers[input[i]] << " ";
    }

    return 0;
}

Io semplicemente metto tutti gli N_i in un array che poi ordino in modo crescente, tenendomi un indice che mi dice quale è il prossimo N_i e quando lo incontro lo salvo (ricordati di mantenere l’ordine originale). E poi non utilizzare i long, non sono necessari e rallentano l’esecuzione.

1 Mi Piace

Un approccio un po’ più semplice per sapere la somma delle cifre è in base 2 è:

  • precalcolarsi la somma dei primi 2^{14} numeri,
  • sia b_0 b_1 b_2 \ldots b_{27} la rappresentazione in binario di x, possiamo notare che
    \underbrace{b_0 b_1 \ldots b_{13}}_{x\mod 2^{14}} \underbrace{b_{14} b_{15} \ldots b_{27}}_{\left\lfloor\frac{x}{2^{14}}\right\rfloor}
    per cui
    S(x)=S\left(x\mod 2^{14}\right)+S\left(\left\lfloor\frac{x}{2^{14}}\right\rfloor\right).

Lo stesso ragionamento si può fare in base 3.

1 Mi Piace

E poi ti basta farlo in base 3, per la base 2 c’è __builtin_popcount() che è molto più fast :new_moon_with_face:

2 Mi Piace

Ringrazio tutti voi; ho avuto la possibilità di ottenere, finalmente direi, 100/100 su quell’esercizio. Ho pubblicato il codice, il quale è visibile a tutti e da cui ho tolto tutti i valori precalcolati (non mi era possibile caricare il file altrimenti).


Ottima funzione built-in! La utilizzerò sicuramente in futuro, ovviamente solo se avrò a che fare con un compilatore GCC (ho letto che è una funzione appartenente solo a questa specie di compilatore).


Alla fine ho adottato questa splendida soluzione, che appare molto semplice e dà un senso effettivo al precalcolo dei numeri. Ti ringrazio in particolare.

1 Mi Piace