# Aiutino per Vasi

**URL:** <https://forum.olinfo.it/t/aiutino-per-vasi/3800>\
**Category:** Aiuto\
**Created:** [29 Aprile 2014, 10:04am UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800 "2014-04-29T10:04:58Z")\
**Posts on this page:** 20\
**Page:** 2

<div class="post-metadata">

**Author:** ![Lawliet](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lawliet/32/28_2.png) [@Lawliet](https://forum.olinfo.it/u/Lawliet)\
**Post date:** [9 Agosto 2014, 2:08pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/21 "2014-08-09T14:08:14Z")

</div>

Mark hai qualche idea per risolvere vasi2?

---

<div class="post-metadata">

**Author:** ![simone.pri](https://forum.olinfo.it/user_avatar/forum.olinfo.it/simone.pri/32/18_2.png) [@simone.pri](https://forum.olinfo.it/u/simone.pri)\
**Post date:** [9 Agosto 2014, 2:12pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/22 "2014-08-09T14:12:08Z")

</div>

> > Sostanzialmente non dovresti usare remove e search ma le funzioni per aggiungere e togliere valori dalla fine è dll'inizio della lista (push\_back(), push\_front(), pop\_back(), pop\_front()) per tutte le liste "centrali" tra i due indici coinvolti nell'update. Per i segmenti che invece contengono questi due indici devi usare remove e insert. Il problema è che le liste sono lente, quindi ti conviene usare varie deque.
> > La complessità migliora perché tu fai solo 2 operazioni per ogni segmento, diventando quindi O(2\*sqrt(N))=O(sqrt(N)).
> > 
> > Non so se sono stato chiaro
> > 
> > Lawliet
> 
> Esatto, dato che pop/push\_back e pop/push\_front hanno coplessità costante (O(1)). Quindi ti fai un vettore di sqrt(N) deque, ognuna con sqrt(N) elementi (o meno, nel caso dell'ultima, dato che sqrt(N) non è sempre un intero).
> 
> mark03

vediamo se ho capito:  
Esempio:  
deck[0] = {0, 1, 2}  
deck[1] = {3, 4}  
  
Per eseguire  
s 2 4  
  
faccio:  
  
deck[1].push\_back(deck[0].back());  
deck[0].pop\_back();  
  
deck[0].push\_back(deck[1].front());  
deck[1].pop\_front();  
  
E nel caso fosse  
  
s 1 3  
  
come farei?  
dovrei levare il 2 poi l'1, poi rimettere il 2, levare il 4 inserire l' 1 e rimettere il 4

---

<div class="post-metadata">

**Author:** ![mark03](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/439d5e/32.png) [@mark03](https://forum.olinfo.it/u/mark03)\
**Post date:** [9 Agosto 2014, 2:35pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/23 "2014-08-09T14:35:40Z")

</div>

deck[0] = {0, 1, 2}  
deck[1] = {3, 4}

  

```
int temp=deck[0][2]; //salvo il valore;  
deck[0].erase(deck[0].begin()+2); // lo tolgo  
deck[0].push\_back(deck[1].front()); //sposto il valore  
deck[1].pop\_front(); // lo rimuovo  
deck[1].insert(deck[1].begin()+1,temp); // lo reinserisco
```

&nbsp;quindi ora

deck[0]={0,1,3} e deck[1]={4,2}

  

P.S: ci sarete tutti e due alle OII a settembre?

---

<div class="post-metadata">

**Author:** ![Lawliet](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lawliet/32/28_2.png) [@Lawliet](https://forum.olinfo.it/u/Lawliet)\
**Post date:** [9 Agosto 2014, 2:45pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/24 "2014-08-09T14:45:03Z")

</div>

> P.S: ci sarete tutti e due alle OII a settembre?
> 
> mark03

Io sì

---

<div class="post-metadata">

**Author:** ![simone.pri](https://forum.olinfo.it/user_avatar/forum.olinfo.it/simone.pri/32/18_2.png) [@simone.pri](https://forum.olinfo.it/u/simone.pri)\
**Post date:** [9 Agosto 2014, 2:48pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/25 "2014-08-09T14:48:46Z")

</div>

> > P.S: ci sarete tutti e due alle OII a settembre?
> > 
> > mark03
> 
> Io sì
> 
> Lawliet

yes (y)

---

<div class="post-metadata">

**Author:** ![Lawliet](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lawliet/32/28_2.png) [@Lawliet](https://forum.olinfo.it/u/Lawliet)\
**Post date:** [9 Agosto 2014, 3:07pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/26 "2014-08-09T15:07:50Z")

</div>

Qualche guru che possa illuminarmi nella risoluzione di vasi2?

---

<div class="post-metadata">

**Author:** ![wil93](https://forum.olinfo.it/user_avatar/forum.olinfo.it/wil93/32/2862_2.png) [@wil93](https://forum.olinfo.it/u/wil93)\
**Post date:** [9 Agosto 2014, 3:28pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/27 "2014-08-09T15:28:00Z")

</div>

> Allora perchè la ricerca dovrebbe avere complessità O(N/M) + O(M) ??
> 
> simone.pri

Io intendevo "è facile trovare un modo di farlo in in O(N/M) + O(M)", il vostro metodo (che usa la divisione per M e il modulo per M) chiaramente impiega O(1). Però assume che gli array (a parte l'ultimo) siano tutti lunghi esattamente M. Il problema però è quando si va a fare l'update questa assunzione potrebbe smettere di essere vera.

---

<div class="post-metadata">

**Author:** ![mark03](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/439d5e/32.png) [@mark03](https://forum.olinfo.it/u/mark03)\
**Post date:** [9 Agosto 2014, 3:45pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/28 "2014-08-09T15:45:35Z")

</div>

> > Allora perchè la ricerca dovrebbe avere complessità O(N/M) + O(M) ??
> > 
> > simone.pri
> 
> Io intendevo "è facile trovare un modo di farlo in in O(N/M) + O(M)", il vostro metodo (che usa la divisione per M e il modulo per M) chiaramente impiega O(1). Però assume che gli array (a parte l'ultimo) siano tutti lunghi esattamente M. Il problema però è quando si va a fare l'update questa assunzione potrebbe smettere di essere vera.
> 
> wil93

L'assunzione non smette di essere vera, però, se si spostano anche tutti gli intervalli intermedi (mettendo il primo del successivo alla fine del precedente, o viceversa nel caso in cui lo spostamento sia al "contrario", ovvero da una posizione più grande a una più piccola).

---

<div class="post-metadata">

**Author:** ![wil93](https://forum.olinfo.it/user_avatar/forum.olinfo.it/wil93/32/2862_2.png) [@wil93](https://forum.olinfo.it/u/wil93)\
**Post date:** [9 Agosto 2014, 3:49pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/29 "2014-08-09T15:49:22Z")

</div>

Sì, “potrebbe” cioè dipende da come si decide di implementare l’update. Col vostro metodo il “find” è più veloce dell’update, c’è un’altra soluzione in cui è l’opposto… ma vabbé, funzionano entrambe 🙂

  

UPD: Anzi no, probabilmente nell’altro metodo sono uguali… quindi direi che il vostro è migliore 🙂

---

<div class="post-metadata">

**Author:** ![mark03](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/439d5e/32.png) [@mark03](https://forum.olinfo.it/u/mark03)\
**Post date:** [9 Agosto 2014, 3:53pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/30 "2014-08-09T15:53:04Z")

</div>

> Sì, "potrebbe" cioè dipende da come si decide di implementare l'update. Col vostro metodo il "find" è più veloce dell'update, c'è un'altra soluzione in cui è l'opposto... ma vabbé, funzionano entrambe :)
>   
> 
> UPD: Anzi no, probabilmente nell'altro metodo sono uguali... quindi direi che il vostro è migliore :)
> 
> wil93

Io l'ho risolto (vasi1) con update in O(sqrt(N)) e find in O(1). Ma ci sono soluzioni molto più veloci (o meglio ottimizzate ahaha)

---

<div class="post-metadata">

**Author:** ![Delfad0r](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/d/22d042/32.png) [@Delfad0r](https://forum.olinfo.it/u/Delfad0r)\
**Post date:** [9 Agosto 2014, 6:57pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/31 "2014-08-09T18:57:58Z")

</div>

Nemmeno io riesco a risolverlo…

Come suggerito in questo topic, ho creato un array lungo&nbsp;√N&nbsp;di deque, ciascuna con&nbsp;√N elementi. La ricerca è semplicemente

```
return blocks[i / sqrtN][i % sqrtN]
```

dove blocks è l’array di deque. L’update invece è&nbsp;

```
if(i == j) return;
int v_i = query(i);
int b = i / sqrtN;
blocks[b].erase(blocks[b].begin() + (i % sqrtN));
if(i < j) {
while(b < j / sqrtN) {
blocks[b].push_back(blocks[b + 1].front());
blocks[++b].pop_front();
}
blocks[b].insert(blocks[b].begin() + (j % sqrtN), v_i);
}
```

e analogamente se i \> j.

Mi sembra tutto corretto, eppure va in Time Limit in un paio di testcase. Cosa sto sbagliando?

---

<div class="post-metadata">

**Author:** ![Lawliet](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lawliet/32/28_2.png) [@Lawliet](https://forum.olinfo.it/u/Lawliet)\
**Post date:** [9 Agosto 2014, 7:08pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/32 "2014-08-09T19:08:27Z")

</div>

L’algoritmo è corretto. Magari prova a mettere il risultato di j/sqrtN in una variabile. Poi prova a rimandare semplicemente la soluzione. Spesso fa così se il server in quel momento era occupato.

---

<div class="post-metadata">

**Author:** ![Delfad0r](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/d/22d042/32.png) [@Delfad0r](https://forum.olinfo.it/u/Delfad0r)\
**Post date:** [9 Agosto 2014, 7:28pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/33 "2014-08-09T19:28:42Z")

</div>

Niente da fare, va ancora in Time Limit Exceeded. Proverò a risottometterlo occasionalmente. Grazie comunque per l’aiuto!

  

EDIT: ovviamente con fast I/O totalizza 100/100, ma così è un po’ come barare ^^. Mi piacerebbe trovare un modo per stare nel tempo limite anche senza getchar\_unlocked() e simili…

---

<div class="post-metadata">

**Author:** ![Lawliet](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lawliet/32/28_2.png) [@Lawliet](https://forum.olinfo.it/u/Lawliet)\
**Post date:** [9 Agosto 2014, 7:37pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/34 "2014-08-09T19:37:52Z")

</div>

Ma mi sembra strano che non te lo faccia perché comunque l’algoritmo è quello 🙂

---

<div class="post-metadata">

**Author:** ![EmanueleRossi](https://forum.olinfo.it/user_avatar/forum.olinfo.it/emanuelerossi/32/42_2.png) [@EmanueleRossi](https://forum.olinfo.it/u/EmanueleRossi)\
**Post date:** [9 Agosto 2014, 8:02pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/35 "2014-08-09T20:02:33Z")

</div>

A quanto pare per risolvere vasi2 servono un’update e una ricerca &nbsp;in tempo logaritmico.

Questo mi fa subito pensare ai segment oi fenwick, per dubito sia cosi banale…

---

<div class="post-metadata">

**Author:** ![Lawliet](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lawliet/32/28_2.png) [@Lawliet](https://forum.olinfo.it/u/Lawliet)\
**Post date:** [9 Agosto 2014, 8:23pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/36 "2014-08-09T20:23:13Z")

</div>

> A quanto pare per risolvere vasi2 servono un'update e una ricerca &nbsp;in tempo logaritmico.
> Questo mi fa subito pensare ai segment oi fenwick, per dubito sia cosi banale..
> 
> EmanueleRossi

  

  

Anche secondo me dev'essere logaritmica. Dobbiamo peggiorare la ricerca per migliorare l'update e credo che la soluzione ottimale sia O(logN). Nonostante questo non credo sia con i fenwick, ma potrei anche sbagliarmi

---

<div class="post-metadata">

**Author:** ![mark03](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/439d5e/32.png) [@mark03](https://forum.olinfo.it/u/mark03)\
**Post date:** [9 Agosto 2014, 8:36pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/37 "2014-08-09T20:36:33Z")

</div>

Forse segment tree?

---

<div class="post-metadata">

**Author:** ![Lawliet](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lawliet/32/28_2.png) [@Lawliet](https://forum.olinfo.it/u/Lawliet)\
**Post date:** [9 Agosto 2014, 8:49pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/38 "2014-08-09T20:49:21Z")

</div>

Appena ho il tempo butto giù un algoritmo perché forse ho in mente qualcosa con un segment tree con complessità di update e di ricerca entrambe O(logN)

---

<div class="post-metadata">

**Author:** ![mark03](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/439d5e/32.png) [@mark03](https://forum.olinfo.it/u/mark03)\
**Post date:** [9 Agosto 2014, 11:08pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/39 "2014-08-09T23:08:01Z")

</div>

Noi comunque aspettiamo l’illuminazione di qualche guru

---

<div class="post-metadata">

**Author:** ![E.rocchi1955](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/e/e19b73/32.png) [@E.rocchi1955](https://forum.olinfo.it/u/E.rocchi1955)\
**Post date:** [16 Agosto 2014, 7:04am UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/40 "2014-08-16T07:04:38Z")

</div>

Ho anch’io un problemino con vasi. Mi sembra che il mio algoritmo coincida con quello che dite qui ma va in timeout in 3 casi dell’ultima subtask di circa mezzo secondo.Secondo voi,perchè?

  

[//vasi.cpp](https://vasi.cpp)

#include \<stdio.h\>

#include \<iostream\>

#include \<deque\>

#include \<math.h\>

#include \<algorithm\>

#include \<stdlib.h\>

using namespace std;

int a,b;

  

  

int main()

{

&nbsp; FILE_fr;_

&nbsp; FILEfw;

&nbsp; fr=fopen(“input.txt”,“r”);

&nbsp; fw=fopen(“output.txt”,“w”);

&nbsp;&nbsp;&nbsp;

&nbsp; int N,M;

&nbsp;&nbsp;

&nbsp; fscanf(fr,"%d%d",&N,&M);

&nbsp;&nbsp;

&nbsp; int rad=(int)sqrt(N);

&nbsp;&nbsp;

&nbsp; deque \<int\> V[N];

&nbsp;&nbsp;

&nbsp; for(a=0;a\<N;a++)V[a/rad].push\_back(a);

&nbsp;&nbsp;

&nbsp; char op;

&nbsp; for(a=0;a\<M;a++)

&nbsp; {

&nbsp; &nbsp; fscanf(fr,"%c%c",&op,&op);

&nbsp; &nbsp; if(op==‘s’)

&nbsp; &nbsp; {

 &nbsp; int prev,now;

 &nbsp; fscanf(fr,"%d%d",&prev,&now);

 &nbsp; int prad=prev/rad;

 &nbsp; int pd=prev%rad;

 &nbsp; int nrad=now/rad;

 &nbsp;&nbsp;

 &nbsp; int change=V[prad][pd];

 &nbsp; if(prev\<now)

 &nbsp; {

&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;

 V[prad].erase(V[prad].begin()+pd);

&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;

&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;for(b=prad;b\<nrad;b++)

&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;{

 &nbsp; &nbsp; &nbsp; V[b].push\_back(V[b+1].front());

 &nbsp; &nbsp; &nbsp; V[b+1].pop\_front();

 }

 V[nrad].insert(V[nrad].begin()+now%rad,change);

 &nbsp; } &nbsp;&nbsp;

 &nbsp; else &nbsp;//prev\<now

 &nbsp; {

 &nbsp; &nbsp; V[prad].erase(V[prad].begin()+pd);

 &nbsp; &nbsp;&nbsp;

 &nbsp; &nbsp; for(b=prad;b\>nrad;b–)

 &nbsp; &nbsp; {

 &nbsp; &nbsp; &nbsp; V[b].push\_front(V[b-1].back());

 &nbsp; &nbsp; &nbsp; V[b-1].pop\_back();

 }

 V[nrad].insert(V[nrad].begin()+now%rad,change);

 &nbsp; }

&nbsp; &nbsp; }

&nbsp; &nbsp; else

&nbsp; &nbsp; {

 &nbsp;int pos;

 &nbsp;fscanf(fr,"%d",&pos);

 &nbsp;fprintf(fw,"%d ",V[pos/rad][pos%rad]);

}

 &nbsp;

&nbsp; }

&nbsp;&nbsp;return 0;

}

[Pagina precedente](https://forum.olinfo.it/t/aiutino-per-vasi/3800.md?page=1)

[Pagina seguente](https://forum.olinfo.it/t/aiutino-per-vasi/3800.md?page=3)