Po_pietre troppe domande

Sono riuscito a trovare una soluzione O(2log^2(N)) tuttavia faccio soltanto 60 punti causa troppe domande :confused:

Tuttavia non dovrebbe funzionare (effettuando circa 800 domande nel peggiore dei casi)?

In pratica faccio una ricerca binaria nelle prime [1, N] scatole e con un’altra ricerca binaria vedo quante scatole [N+1, 2N] sono maggiori della scatola scelta.
Se vedo che sono poche vado in una scatola iniziale più a destra, altrimenti a sinistra.
Se non sono riuscito a trovare la soluzione faccio la stessa cosa per le scatole [N+1, 2N] cercando quante ce n’è più piccole nella prima parte…

Qualche aiuto?

La complessità che puoi ambire è O(\log G). Riponiamo il problema come segue:
trovare il G-esimo minore dati due array preordinati di dimensione uguale a N (in realtà quest’ultimo aspetto non ha importanza).

[spoiler]Propongo un algoritmo divide et impera , e per farlo osserviamo un dato cruciale:

Osservazione: siano i e j due indici del primo e del secondo vettore (banalmente j è nella forma j = N + j', quindi WLOG tratteremo i due array separatamente). Se A[i]<B[j] \implies A[k] < B[j], \quad k = 0,1,\dots,i e analogamente \implies A[i] < B[l], \quad l = j, j+1,\dots, |B|-1 . Ciò significa che, se i non è l’indice adatto, devo cercarlo o tra i succcessori di A[i] (A[i] escluso), o tra i predecessori di B[j] (incluso). Considerazioni opposte se vale il confronto opposto.

L’idea è: supponiamo di prendere inizialmente due valori di i e j pari a G/2. In questo modo gestiremo due subarray che complessivamente avranno G/2 elementi. Se A[i] < B[j], vorrà dire che l’elemento G potrebbe trovarsi o dopo A[i] o prima di B[j]. A questo punto, osserviamo che gli elementi prima di A[i] (A[i] incluso) saranno “tolti”, di conseguenza vanno anch’essi tolti da G.

Quindi, se avessi una funzione findG^{th}(A, B, sz_A, sz_B, G) la dovrei richiamare, dopo il confronto, con questi valori: findG^{th}(A + i, B, sz_A - i + 1, sz_B - j, G - j).
Considerazione analoghe se il confronto è opposto.

Un caso base è quando G = 1, infatti devi soltanto capire qual è il minimo tra i due array, ovvero tra i loro primi elementi. Un altro caso base è quando un array è vuoto, in tal caso devi prendere il G-esimo elemento dell’altro vettore.[/spoiler]

Lascio a te il compito di sistemare gli altri dettagli implementativi, e anche la rogna degli array 0-based o 1-based (che mi ha dato personalmente parecchi grattacapi). Comunuque, è ovvio il perché l’algoritmo proposto funziona e ha complessità O(\log k)

Pashmoom kir pashmoom

1 Mi Piace

l’idea di doublechar mi sembra comunque corretta,
puoi postare il codice?

Eccoti: https://pastebin.com/kSAJtXLz

1 Mi Piace

In che linguaggio è? :smile:

1 Mi Piace

L’osservazione mi è chiara, però non l’idea :confused:

N=3, G=4
2 4 6
1 3 5

Il vettore completo sarebbe: 2 4 6 1 3 5
Assumendo che i valori di i e j siano G/2 sarebbero rispettivamente 2 e 5 (indici 1-based).
La funzione Confronta(i, j) ritornerà 1 perché la scatola con peso 4 non è più leggera della scatola con peso 3.
Questo vuol dire che la soluzione potrebbe essere tra [1, i] e [j+1, 2N]?
Inoltre cosa intendi che gli elementi prima di A[i] vanno tolti da G?
Scusa, però l’idea della ricerca binaria su un unico vettore diviso in due mi confonde parecchio.

1 Mi Piace

Farsi, la lingua che si parla in Iran

@doublechar14 Leggi attentamente la parte in cui viene descritta l’assegnazione del punteggio. Da quello che ho capito nel subtask 6 non serve a niente il valore di D, ma al suo posto viene utilizzato un valore Q che è il numero minimo di domade che la giuria ha ritenuto sufficienti per risolvere il test in questione e se il numero di domande supera 4Q, allora il punteggio in quel subtask sarà zero. Dato che il valore di Q sarà all’incirca log(K), la tua soluzione con complessità O(2log^2(N)) ottiene 0 punti in quel subtask ottenendo il verdetto “troppe domande”.

4 Mi Piace

Ok, mi rispiego meglio.

Prendiamo proprio il caso d’esempio:
N=3, G=4
2 4 6
1 3 5

Dunque, sappiamo di per certo che il numero cercato potrebbe trovarsi tra [1, 2] e tra [N+1, N+2].

In particolare, supponiamo di scegliere i = G/2, j = G/2, entrambi pari a 2. Confrontiamo di conseguenza i secondi elementi, e avremo 4 > 3, di conseguenza possiamo riconsiderare i sottovettori [2, 4] e [5], grazie all’osservazione so che non sto perdendo il mio G-esimo elemento.
Ora, se ho scartato 2 elementi del vettore [1, 3, 5] significa che gli elementi inferiori non erano candidati minimi, tuttavia essendo più piccoli di G devono necessariamente essere tolti. Ergo, G \leftarrow G - i (o G - j, dipende dal confronto): quindi, dobbiamo trovare il secondo minimo di:

[5]
[2, 4]

Ok, continuiamo: i \leftarrow G/2 = 1 e j \leftarrow G/2 = 1. Quindi, confrontiamo 5 e 2, e quindi rimarranno 5 e 4, con G diminuito e che ora vale 1. A questo punto, sai che fare.

Ci sarebbe un invariante da rispettare (ed sto rispettando in questo momento), che non ho citato prima e non citerò neanche stavolta perché vorrei ci arrivassi da te.