CyberBootcamp test 2

Table of Contents

A - L’amore non è bello se non è litigarello

Problem Statement

$\large{\text{L’amore non è bello se non è litigarello}}$

Author: magicfrank
Difficulty: ★☆☆☆☆

Lorenzinco e Alessandra stanno finalmente per andare a convivere, ma c’è un problema: Alessandra adora i gatti, mentre Lorenzinco non li sopporta molto. Dopo molte discussioni, Lorenzinco accetta un compromesso: Alessandra può portare al massimo $g$ gatti in casa.

Tutto sembra andare per il meglio, finché un giorno Alessandra torna a casa con $k$ gatti. Lorenzinco sarà contento o ci sarà una lite furiosa?

Dati i valori di $k$ e $g$, determina se Lorenzinco accetterà la situazione o se i due finiranno per litigare.

$\large{\text{Input}}$

La prima riga dell’input contiene un intero $t$ $(1 \leq t \leq 100)$ — il numero di test case.

Le successive $t$ righe contengono ciascuna due interi $k$ e $g$ $(0 \leq k, g \leq 10^{18})$, dove:

  • $k$ è il numero di gatti che Alessandra porta a casa,
  • $g$ è il numero massimo di gatti che Lorenzinco è disposto a sopportare.

$\large{\text{Output}}$

Per ogni test case, stampa una singola riga contenente:

  • $\text{FANNO L’AMORE}$, se $k \leq g$ (Lorenzinco è contento),
  • $\text{FANNO LA GUERRA}$, se $k > g$ (ci sarà una lite).

$\large{\text{Esempio}}$

Input
2
3 5
6 4

Output
FANNO L'AMORE
FANNO LA GUERRA

Soluzione

In questo problema ci viene semplicemente chiesto di calcolare se $k \leq g$ o $k > g$.

def solve(k, g) -> None:
    # MODIFICA SOLO QUESTA FUNZIONE
    if k <= g:
        print("FANNO L'AMORE")
    else:
        print("FANNO LA GUERRA")
    return

if __name__ == '__main__':
    T = int(input())
    for _ in range(T):
        k, g = map(int, input().split())
        solve(k, g)

B - Verso il quartier generale TRX

Problem Statement

$\large{\text{Verso il quartier generale TRX}}$

Author: magicfrank
Difficulty: ★★☆☆☆

Magicfrank fa parte del team TRX e oggi ha deciso di recarsi al loro quartier generale. Tuttavia, il quartier generale si trova molto lontano da Roma, fuori dal raccordo, in una vasta pianura rappresentata come una griglia di dimensioni $n \times m$.

Magicfrank parte dalla sua posizione, contrassegnata con la lettera $\text{M}$, mentre il quartier generale di TRX è indicato dalla lettera $\text{T}$. Tutte le altre celle della griglia contengono dei punti ($\text{.}$), che rappresentano terreno aperto e privo di ostacoli.

In quel posto non passano autobus, quindi Magicfrank è costretto a usare l’auto per arrivarci. Sfortunatamente, la sua YoYo elettrica è dal carrozziere per riparazioni, quindi dovrà prendere una vecchia auto a benzina… che è completamente a secco!

Arrivato al distributore, Magicfrank ha un attimo di esitazione vedendo i prezzi. Per risparmiare, decide di calcolare esattamente il carburante necessario per arrivare al quartier generale senza fare una goccia in più. Una volta arrivato, infatti, potrà fare il pieno gratuitamente grazie alla carta carburante offerta dalla Sapienza!

Ogni volta che si sposta di una posizione nella griglia (su, giù, destra o sinistra), Magicfrank consuma un litro di carburante. Il tuo compito è aiutarlo a calcolare la minima quantità di benzina che serve per raggiungere il quartier generale.

$\large{\text{Input}}$

La prima riga dell’input contiene due interi $n$ e $m$ $(1 \leq n, m \leq 2,500)$ — le dimensioni della griglia.

Le successive $n$ righe contengono ciascuna $m$ caratteri, che rappresentano la griglia. Essa contiene:

  • Esattamente un carattere $\text{T}$ (che indica il quartier generale di TRX),
  • Esattamente un carattere $\text{M}$ (che indica la posizione di partenza di Magicfrank),
  • Tutte le altre celle sono punti ($\text{.}$), che rappresentano terreno aperto.

$\large{\text{Output}}$

Per ogni test case, stampa un singolo intero — la distanza minima, in numero di passi, che Magicfrank deve percorrere per raggiungere il quartier generale di TRX.

$\large{\text{Esempio}}$

Input
10 6
......
......
T.....
....M.
......
......
......
......
......
......

Output
5

Soluzione

In questo caso non dobbiamo scrivere un algoritmo chissà quanto sofisticato per trovare il percorso minimo. Ci basta notare che, date le posizioni di partenza e arrivo, la distanza minima è la somma delle distanze orizzontali e verticali tra le due celle (distanza di Manhattan).

Quindi per risolvere il problema

  1. Troviamo le posizioni di partenza e arrivo
  2. Calcoliamo la distanza di Manhattan tra le due posizioni
def solve(N, M, GRID) -> None:
    # MODIFICA SOLO QUESTA FUNZIONE
    xT,yT = 69,69
    xM,yM = 69,69

    for i,row in enumerate(GRID):
        # enumerate è un alternativa comoda a:
        # for i in range(mat):
        #     row = GRID[i]
        if 'T' in row:
            xT,yT = i,row.index('T') # Se T sta nella riga mi prendo la posizione
        if 'M' in row:
            xM,yM = i,row.index('M') # stessa cosa per M
    
    # A questo punto ho le posizioni, e mi basta calcolare la distanza, 
    # prima sulle X e poi sulle y (distanza di manhattan)
    print(abs(xT-xM)+abs(yT-yM))
    return

if __name__ == '__main__':
    N, M = map(int, input().split())
    GRID = [input() for _ in range(N)]
    solve(N, M, GRID)

C/D - Basta, datemi un aumento

Problem Statement

$\large{\text{Basta, datemi un aumento}}$

Author: magicfrank
Difficulty: ★★★★☆

$\text{Magicfrank}$ si è stancato di scrivere problemi: non ha più fantasia e desidera un aumento.

Essendo particolarmente esigente, accetterà solo stipendi la cui somma sia un multiplo di $\text{k}$.

Il professore gli mostra una lista di buste paga, e $\text{Magicfrank}$ ha il permesso di sceglierne due qualsiasi. Tuttavia, prima di fare una scelta, vuole sapere quante sono le coppie di buste paga la cui somma è un multiplo di $\text{k}$.

Ci sono due versioni del problema:

Nella versione facile:

  • $1 \leq N \leq 2*10^3$ – la lunghezza dell’array.
  • $2 \leq k \leq 10^9$ – il divisore.
  • Gli elementi dell’array $a$ soddisfano $0 \leq a[i] \leq 10^9$.

Nella versione difficile:

  • $1 \leq N \leq 10^6$ – la lunghezza dell’array.
  • $2 \leq k \leq 10^9$ – il divisore.
  • Gli elementi dell’array $a$ soddisfano $0 \leq a[i] \leq 10^9$.

$\large{\text{Input}}$

L’input è composto da due righe:

  • La prima riga contiene due numeri interi $N$ e $k$ $(1 \leq N \leq 10^6, 2 \leq k \leq 10^9)$, dove $N$ è la lunghezza dell’array e $k$ è il divisore.
  • La seconda riga contiene $N$ numeri interi separati da spazi $a_1, a_2, \dots, a_N$ $(0 \leq a[i] \leq 10^9)$ che rappresentano gli elementi dell’array.

$\large{\text{Output}}$

L’output deve consistere in una singola riga contenente un intero: il numero di coppie $(i, j)$ $(1 \leq i < j \leq N)$ tali che la somma $a[i] + a[j]$ sia un multiplo di $k$.

$\large{\text{Esempio}}$

Input
3
7 9
2 5
4 5

Output
5

$\large{\text{Notes}}$

Per verificare se un numero è un multiplo di $k$, si può utilizzare l’operatore modulo ($\%$). In particolare, un numero $x$ è un multiplo di $k$ se e solo se $x \% k = 0$.

Nel testcase 1 le coppie valide sono:

  • $3 + 1 = 4$ (multiplo di $2$) $\quad (\text{arr}[0], \text{arr}[1])$
  • $3 + 1 = 4$ (multiplo di $2$) $\quad (\text{arr}[0], \text{arr}[3])$
  • $1 + 1 = 2$ (multiplo di $2$) $\quad (\text{arr}[1], \text{arr}[3])$

Soluzione

Partiamo dalla versione facile, in cui l’array in input è grande al massimo $2*10^3$. In questo caso possiamo risolvere il problema in $O(N^2)$ (ovvero due cicli for nestati), iterando su tutte le coppie di elementi e controllando se la loro somma è un multiplo di $k$.

Il numero di iterazioni da fare per considerare tutte le coppie è

$$ N*(N-1)/2 = 1000*1999 \approx 2*10^6 $$

Considerando che in un secondo riusciamo a fare circa $10^7$ operazioni, questa soluzione è più che sufficiente.

def slowcheck(l,k):
    c = 0
    for i in range(len(l)):
        for j in range(i+1,len(l)):
            # per ogni coppia
            if (l[i]+l[j])%k==0: # calcolo se la somma è multipla di k
                c+=1
    return c

n,k = map(int,input().split())
l = list(map(int,input().split()))
print(fastcheck(l,k))

Per la versione difficile invece questa soluzione non passerà mai, in quanto l’array ha fino a $10^6$ elementi, e quindi il numero di operazioni da fare sarebbe dell’ordine di $10^{12}$, che decisamente troppo. Ci metterebbe circa 28 ore a terminare, ma noi abbiamo 1 secondo disponibile prima che la soluzione vada in TLE.

Ci sono almeno tre soluzioni diverse,

  • sfrutta un approccio $\textit{two-pointer}$ sortando, che va in $O(N\log N)$
  • due sfruttano un $\textit{hash-map}$ (dizionario di python), che vanno in $O(N)$

La più semplice in assoluto da implementare è la seguente

def solve(l,k):
    c = 0
    d = {}
    for a in l:
        if (-a%k) in d:
            c+=d[-a%k]
        d[a%k] = d.get(a%k,0)+1
    return c

Ma da dove spunta fuori? funziona per magia?

Prima idea

Arriviamo alla soluzione piano piano, partiamo risolvendo un problema più semplice (e molto simile):

Data una lista di numeri (positivi e negativi), 
trovare una coppia (se esiste) che somma a 0

(Qua basta trovare 1 coppia, non il numero di coppie)

Anche qua, non è necessario iterare su tutte le possibili coppie.

Dato un numero $x$ della coppia abbiamo due possibilità:

  • nell’array è presente $-x$
  • nell’array non è presente $-x$

Se $-x$ non è presente non c’è modo di arrivare a 0 con $x$. Se è presente allora abbiamo trovato una coppia valida.

Una prima idea (lenta, in $O(N^2)$) è la seguente:

for el in arr:
    if -el in arr: # assumendo el != 0
        print(el,-el)
        break

Questa soluzione è lenta per l’uso dell’operatore $\text{in}$, ed è equivalente a fare due cicli for annidati.

In alternativa possiamo man mano che scorriamo la lista ricordarci quali numeri abbiamo già visto con un $\text{set}$, e controllare se $-x$ è presente in questo set.

seen = set()
for el in arr:
    if -el in seen:
        print(el,-el)
        break
    seen.add(el)

Questa soluzione è praticamente identica a quella sopra, con l’unica differenza che la coppia la troviamo quando vediamo $-x$ e non quando vediamo $x$ (al contrario in pratica). Ma facendo così passiamo da $O(N^2)$ a $O(N)$.

Seconda idea

Adesso risolviamo

Data una lista di numeri (positivi e negativi), 
trovare il numero di coppie che sommano a 0

Stesso approccio di prima, ma con un $\text{dizionario}$ invece di un $\text{set}$. Così contiamo quante volte abbiamo visto $-x$.

seen = {}
count = 0
for el in arr:
    if -el in seen: # quindi abbiamo già visto -el
        count+=seen[-el] # seen[-el] è il numero di volte in cui è presente
    seen[el] = seen.get(el,0)+1 # incrementiamo il contatore
print(count)

.get(el,0) semplicemente ci evita di fare il classico

if el in seen:
    seen[el]+=1
else:
    seen[el]=1

Ma non cambia nulla dal punto di vista della velocità del codice.

Esempio

Facciamo un esempio con l’array [1,2,-1,-1,1]

1

  • seen = {}
  • vediamo 1, e non abbiamo mai visto -1
  • Il counter non viene incrementato, e per finire settiamo seen[1]=1 (ovvero ci ricordiamo di averlo visto 1 volta)

2

  • seen = {1:1}
  • vediamo 2, e non abbiamo mai visto -2
  • Il counter non viene incrementato, e per finire settiamo seen[2]=1

3

  • seen = {1:1, 2:1}
  • vediamo -1, ma a questo punto ci ricordiamo di aver visto 1 una volta, quindi abbiamo trovato una coppia valida!
  • Il counter viene incrementato di 1, e per finire settiamo seen[-1]=1

4

  • seen = {1:1, 2:1, -1:1}
  • vediamo -1, e come prima abbiamo già visto 1 una volta
  • Il counter viene incrementato di 1, e per finire settiamo seen[-1]=2 (dato che è la seconda volta che vediamo -1)

5

  • seen = {1:1, 2:1, -1:2}
  • vediamo 1, ma abbiamo già visto -1 due volte, quindi ci sono 2 coppie valide che possiamo formare
  • Il counter viene incrementato di 2, e per finire settiamo seen[1]=2 (dato che è la seconda volta che vediamo 1)

Terza idea

Ora risolviamo il nostro problema iniziale.

Per ogni numero ci chiediamo se ne esiste un altro per cui $(x+y)\%k=0$.

Questo è equivalente a chiedersi se dato $x$ esiste $y$ tale che $y = -x\%k$, in quanto

$$(x + -x\%k) \% k = 0$$

In pratica, al posto di cercare per $-x$, cerchiamo per $-x\%k$.

Con una piccolissima modifica dalla soluzione precedente arriviamo a

seen = {}
count = 0
for el in arr:
    if -el%k in seen: # quindi abbiamo già visto -el
        count+=seen[-el%k] # seen[-el] è il numero di volte in cui è presente
    seen[el%k] = seen.get(el%k,0)+1 # incrementiamo il contatore
print(count)

In pratica abbiamo messo il modulo $k$ ovunque