Codeforces 811C, WA nel test 12

Altre gare
1

Testo dell’esercizio:
http://codeforces.com/problemset/problem/811/C

La mia soluzione consiste nel calcolare la bellezza di ogni possibile segmento (lo faccio in N^2) salvando il primo e ultimo numero per ogni città che incontro.
Calcolo anche l’inizio minimo per i segmenti che contengono un numero V[i] sapendo che è il minimo fra tutti gli inizi dei numeri che sono contenuti all’interno.

Dopo linearmente calcolo quali conviene prendere con la programmazione dinamica (parto dall’ultimo elemento) ritornando il massimo fra: [non prendo il segmento e salto questo numero, lo prendo e vado direttamente all’inizio minimo aggiungendo pure la bellezza].

Però sul sito ottengo wrong answer nel test 12, e non so cosa sbaglio :confused:

Questo è il mio codice: https://pastebin.com/3GJTARYC

Personalmente credo che il problema sia nel calcolare l’inizio_massimo, però non so.

Grazie.

2

sei la seconda persona che mi chiede aiuto per l’811 di Codeforces :wink:
innanzitutto non hai considerato che non tutti gli N^2 segmenti sono validi: ad esempio un segmento S non è valido se esistono due indici i,j : V_i=V_j \land V_i \in S \land V_j \notin S.
Pensa ad un altra strada, fai congetture, cerca controesempi o cerca di dimostrarle.
Se vuoi qualche hint, io sono qua. Buona fortuna!

3

Avevo dimenticato di saltare alcuni intervalli (quando avevo saltato un numero ma questo faceva parte dell’intervallo scelto).

Questo è il codice funzionante: https://pastebin.com/sq6M28UR

4

Accepted?
-in ogni caso quando linki codice da Codeforces, metti pure il link alla submission-

5

Si, accepted:
http://codeforces.com/contest/811/submission/27472848

Tu come l’hai risolto? Sarei curioso di vedere il tuo codice

6

http://codeforces.com/contest/811/submission/27424065