Sto provando a risolvere questo problema della gara ore EGOI, ma non riesco ad andare oltre un algoritmo di forza bruta che fa 20punti. Qualcuno mi può suggerire cosa andare a studiare per affrontare il problema? Grazie.
hint: basta simularlo duh.
hint: devi sortare ovviamente.
sol: eventi: un tizio va in vacanza, un tizio torna. sorta, simula e profit.
Mi sa che è un po’ tardi, ma lo scrivo almeno per chi leggerà in futuro.
La parola “simulare” è abusata, come anche “greedy”. Simulare significa che hai un processo, un sistema che evolve nel tempo, questo processo è descritto nel testo e la soluzione consiste, appunto, nel simularlo (poi la simulazione può essere banale o estremamente difficile, ma questa è un’altra storia).
Questo problema non ha nulla di simulabile. Il primo hint che hai dato è alla meglio poco utile, e alla peggio misleading. L’uso della parola “ovviamente” nel secondo hint è molto infelice, perché per uno alle prime armi il fatto che in un problema del genere convenga sortare non è per nulla ovvio. Del terzo hint (soluzione?) non si capisce una cippa, so cosa stai dicendo solo perché conosco la soluzione.
Voglio enfatizzare che aiutare una persona che si sta avvicinando ora alle olimpiadi/CP è molto diverso dall’aiutare una persona experienced. Quest’ultima può capire hint criptici e non si demoralizza se gli/le viene detto che qualcosa a cui non aveva pensato è ovvio. Nel primo caso, questo è falso.
La roba tipo “duh” e “ovviamente” erano meant to be a joke, enfatizzato dall’uso di [spoiler].
Mi sembrava di aver fatto una risposta half joke perche’ qualcuno aveva gia risposto con una risposta seria, ma non vedo altre risposte quindi either l’hanno cancellata o ho avuto un brainfart.
In ogni caso quando l’ho risolto e ancora adesso mi sembra una simulazione.
Il problema mi dice che ogni tizio va in vacanza nel tempo A_i e torna nel tempo B_i e vuole sapere quando c’e’ il massimo numero di tizi.
Quello che faccio io e’: creo due eventi per ognuno: quello che va in vacanza e quello che torna, sorto e scorro, tenendo un contatore di quanti non sono in vacanza.
Greedy ho abbastanza un idea di cosa sia, per simulazione non ho mai letto una definizione rigorosa, ma a intuito questa soluzione mi sembra la cosa piu “simulazione” che ci sia.
Mmh, okay I guess, anche se non capsico il tuo British humour.
Sisi so qual è la tua interpretazione e la tua soluzione. Sono d’accordo che l’approccio abbia un che di vagamente simulativo, ma dare come hint “basta simularlo” confonde e basta.
Ma no mica c’è una definizione, è un termine ombrello e quando si usa ci vuole un po’ di buonsenso. Tecnicamente puoi dire che questa è una simulazione, ma tecnicamente puoi anche dire che Dijkstra è una programmazione dinamica. Puoi argomentare che non è sbagliato, ma è anche molto poco illuminante.
1 Mi Piace