# Think About It: Corsa Contro il Tempo 2

**URL:** <https://forum.olinfo.it/t/think-about-it-corsa-contro-il-tempo-2/6046>\
**Category:** Algoritmi\
**Created:** [6 Febbraio 2020, 9:22am UTC](https://forum.olinfo.it/t/think-about-it-corsa-contro-il-tempo-2/6046 "2020-02-06T09:22:37Z")\
**Posts on this page:** 8\
**Page:** 1

<div class="post-metadata">

**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\
**Post date:** [6 Febbraio 2020, 9:22am UTC](https://forum.olinfo.it/t/think-about-it-corsa-contro-il-tempo-2/6046/1 "2020-02-06T09:22:37Z")

</div>

Anche se con un po’ di ritardo è arrivato l’ottavo esercizio della rubrica **TAI** : [CCT2](https://training.olinfo.it/#/task/tai_cct2/statement) , l’esercizio in questione è leggermente differente da quelli precedenti ma spero vi possa piacere ugualmente.

Se avete dubbi sul testo oppure notate qualche errore che non abbiamo visto in fase di preparazione potere sfruttare direttamente questo thread.

---

<div class="post-metadata">

**Author:** ![porcelli](https://forum.olinfo.it/user_avatar/forum.olinfo.it/porcelli/32/668_2.png) [@porcelli](https://forum.olinfo.it/u/porcelli)\
**Post date:** [6 Febbraio 2020, 10:32am UTC](https://forum.olinfo.it/t/think-about-it-corsa-contro-il-tempo-2/6046/2 "2020-02-06T10:32:09Z")

</div>

:\<

 ![Screenshot_20200206-104027](https://forum.olinfo.it/uploads/default/original/1X/ec9ed0406754d6bdc865a933b0971df0220bfc57.png)  
Da notare l ex limte e i punteggi in classifica

---

<div class="post-metadata">

**Author:** ![simpatine](https://forum.olinfo.it/user_avatar/forum.olinfo.it/simpatine/32/444_2.png) [@simpatine](https://forum.olinfo.it/u/simpatine)\
**Post date:** [6 Febbraio 2020, 10:46am UTC](https://forum.olinfo.it/t/think-about-it-corsa-contro-il-tempo-2/6046/3 "2020-02-06T10:46:57Z")

</div>

Ma io infatti non capisco il limite così alto, aspetto solo che @MyK_00L mi apra il fondoschiena.

---

<div class="post-metadata">

**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\
**Post date:** [6 Febbraio 2020, 1:00pm UTC](https://forum.olinfo.it/t/think-about-it-corsa-contro-il-tempo-2/6046/4 "2020-02-06T13:00:16Z")

</div>

Strano, comunque ora il limite dovrebbe essere stato corretto (1.2s). Il limite è così alto perché l’obiettivo dell’esercizio era quello di risolvere [CCT1](https://training.olinfo.it/#/task/cct/statement) utilizzando memoria costante esclusa quella necessaria per l’input. L’unico modo per fare ciò era utilizzare una formula per generare l’input: nel nostro caso a^i mod 1000 e b^i mod K ma giustamente questo implica l’esistenza di soluzioni più veloci.

---

<div class="post-metadata">

**Author:** ![gios](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/g/ec9cab/32.png) [@gios](https://forum.olinfo.it/u/gios)\
**Post date:** [7 Febbraio 2020, 4:17pm UTC](https://forum.olinfo.it/t/think-about-it-corsa-contro-il-tempo-2/6046/5 "2020-02-07T16:17:38Z")

</div>

Posso chiedere un chiarimento sull’esempio.  
“Nel primo caso d’esempio, i tempi con cui sconfiggere i boss risultano:[1,2,4] mentre le cariche[1,3,9].La strategia ottimale risulta nel completare i primi due livelli per poi utilizzare lo strumento nell’ultimo.”  
i valori della ricarica sono calcolati b^i mod K essendo che K= 4 come fa ha essere 3^2%4 = 9 ?

---

<div class="post-metadata">

**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\
**Post date:** [7 Febbraio 2020, 5:17pm UTC](https://forum.olinfo.it/t/think-about-it-corsa-contro-il-tempo-2/6046/6 "2020-02-07T17:17:45Z")

</div>

In effetti non è stato applicato il modulo, le ricariche effettivamente sono **[1,3,1]**, per quanto riguarda l’esempio la strategia rimane corretta, nel senso che le 4 energie che colleziona con i primi 2 livelli usa lo strumento per evitare di combattere il terzo boss.

---

<div class="post-metadata">

**Author:** ![porcelli](https://forum.olinfo.it/user_avatar/forum.olinfo.it/porcelli/32/668_2.png) [@porcelli](https://forum.olinfo.it/u/porcelli)\
**Post date:** [8 Febbraio 2020, 11:54am UTC](https://forum.olinfo.it/t/think-about-it-corsa-contro-il-tempo-2/6046/7 "2020-02-08T11:54:26Z")

</div>

bel problema comunque si potrebbe anche mettere 1 mib 😉 OwO

---

<div class="post-metadata">

**Author:** ![zJack1342](https://forum.olinfo.it/user_avatar/forum.olinfo.it/zjack1342/32/711_2.png) [@zJack1342](https://forum.olinfo.it/u/zJack1342)\
**Post date:** [25 Novembre 2023, 10:11pm UTC](https://forum.olinfo.it/t/think-about-it-corsa-contro-il-tempo-2/6046/8 "2023-11-25T22:11:43Z")

</div>

## Editorial

Yo, dopo una piccola attesa (🌚) ecco l’editorial del problema.  
Come al solito procediamo per subtask!

### Subtask 1

Il **subtask** 1 è relativo ai casi d’esempio. Basta restituire l’output desiderato 🌚

```c++
int speedrunna(int N, int K, int a, int b){
    if(N == 3)return 3;
    return 1156;
}

```

_Time complexity_: O(1)

_Space complexity_: O(1)

### Subtask 2 & 3

I **subtask** 2 e 3 sono stati ideati per testare che la soluzione prodotta si calcoli effettivamente i dati dal formato indicato.

L’idea di base era far scopiazzare il codice da [cct](https://training.olinfo.it/#/task/cct/statement) e adeguarlo all’input.

```c++
#include <bits/stdc++.h>

using namespace std;

int speedrunna(int N, int K, int a, int b);

int mul(int a, int b, int mod){
    return (a * b) % mod;
}

int fastPow(int b, int e, int mod){
    if(e == 0){
        return 1;
    }
    int ans = fastPow(mul(b, b, mod), e / 2, mod);
    if(e & 1){
        ans = mul(ans, b, mod);
    }
    return ans;
}

int getTime(int i, int a){
    return fastPow(a, i, 1000);
}

int getCharge(int i, int b, int k){
    return fastPow(b, i, k);
}

int add(int a, int b){
    if(a == INT_MAX || b == INT_MAX)return INT_MAX;
    return a + b;
}

int dp(int i, int k, int a, int b, vector<vector<int>> &memo, int K){
    if(i == (int) memo[0].size()){
        return 0;
    }
    int &ret = memo[k][i];
    if(ret != INT_MAX){
        return ret;
    }
    int time = getTime(i, a);
    int charge = getCharge(i, b, K);
    if(k == K){
        ret = dp(i + 1, 0, a, b, memo, K);
    }
    ret = min(ret, time + dp(i + 1, min(K, k + charge), a, b, memo, K));
    return ret;
}

int speedrunna(int N, int K, int a, int b){
    vector<vector<int>> memo(K + 1, vector<int>(N, INT_MAX));
    return dp(0, 0, a, b, memo, K);
}

```

_Time complexity_: O(N \times K \times log(N))

Si può ridurre la complessità temporale calcolando una volta sola i valori delle cariche e dei tempi richiesti. Lo spazio di memoria a disposizione permette la memorizzazione di questi calcoli.

_Space complexity_: O(N \times K)

### Subtask 4

Il **subtask 4** è effettivamente il subtask in cui il problema si differenza dalla sua prima versione.  
I limiti di memoria non ci permettono di memorizzare completamente la matrice per tutti gli stati possibili.

Con una soluzione _top-down_ non è intuitivo a colpo d’occhio capire le dipendenze delle nostre transazioni.  
Riscrivendo il codice con una soluzione _bottom-up_ è facile notare che i K stati per i-esimo livello dipendono solo dai K del livello i - 1.

Per cui, tenendo i memoria solo i 2K stati interessati riduciamo la complessità spaziale da N \times K a K.

Uno sketch della tabella dei risultati intermedi per il test case di cct 1:

 ![image](https://forum.olinfo.it/uploads/default/original/2X/0/02f1e58f45177b717a4bc2c34e73c05f9e9b52a0.png)

```c++

#include <bits/stdc++.h>

using namespace std;

int speedrunna(int N, int K, int a, int b);

int mul(int a, int b, int mod){
    return (a * b) % mod;
}

int fastPow(int b, int e, int mod){
    if(e == 0){
        return 1;
    }
    int ans = fastPow(mul(b, b, mod), e / 2, mod);
    if(e & 1){
        ans = mul(ans, b, mod);
    }
    return ans;
}

int getTime(int i, int a){
    return fastPow(a, i, 1000);
}

int getCharge(int i, int b, int k){
    return fastPow(b, i, k);
}

int add(int a, int b){
    if(a == INT_MAX || b == INT_MAX)return INT_MAX;
    return a + b;
}

int speedrunna(int N, int K, int a, int b){
    // initiating values first 
    vector<int> prev(K + 1, INT_MAX), cur(K + 1);
    prev[0] = 0;
    for(int i = 0; i < N; i++){
        fill(cur.begin(), cur.end(), INT_MAX);
        int time = getTime(i, a);
        int charge = getCharge(i, b, K);
        // Just completing the level
        for(int k = 0; k <= K; k++){
            int index = min(k + charge, K);
            cur[index] = min(cur[index], add(prev[k], time)); 
        }
        // using the strument
        cur[0] = min(cur[0], prev[K]);
        swap(prev, cur);
    }
    return *min_element(prev.begin(), prev.end());
}

```

_Time Complexity_: O(N \times K + N log(N) )

Si può ridurre la complessità computando passo per passo le potenze se si processano i livelli dal primo.  
Nella soluzione proposta è possibile farlo, rimuovendo cosi il fattore N log (N)

_Space Complexity_: O(K)

#### Robe a caso

Il codici proposti nell’editorial sono stati sviluppati da me dopo aver programmato in java per un anno. Sono inutilmente prolissi per questa ragione 😓