Aiutino per Vasi


#21

Mark hai qualche idea per risolvere vasi2?


#22
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


#23

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
 quindi ora
deck[0]={0,1,3} e deck[1]={4,2}

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

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

mark03

Io sì

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

mark03

Io sì

Lawliet

yes (y)

#26

Qualche guru che possa illuminarmi nella risoluzione di vasi2?


#27
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.

#28
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).

#29

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 :slight_smile:


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

#30
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)

#31

Nemmeno io riesco a risolverlo…

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

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

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

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?


#32

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.


#33

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…

#34

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


#35

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

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

#36
A quanto pare per risolvere vasi2 servono un'update e una ricerca  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

#37

Forse segment tree?


#38

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)


#39

Noi comunque aspettiamo l’illuminazione di qualche guru


#40

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
#include <stdio.h>
#include <iostream>
#include <deque>
#include <math.h>
#include <algorithm>
#include <stdlib.h>
using namespace std;
int a,b;


int main()
{
  FILEfr;
  FILEfw;
  fr=fopen(“input.txt”,“r”);
  fw=fopen(“output.txt”,“w”);
   
  int N,M;
  
  fscanf(fr,"%d%d",&N,&M);
  
  int rad=(int)sqrt(N);
  
  deque <int> V[N];
  
  for(a=0;a<N;a++)V[a/rad].push_back(a);
  
  char op;
  for(a=0;a<M;a++)
  {
    fscanf(fr,"%c%c",&op,&op);
    if(op==‘s’)
    {
  int prev,now;
  fscanf(fr,"%d%d",&prev,&now);
  int prad=prev/rad;
  int pd=prev%rad;
  int nrad=now/rad;
  
  int change=V[prad][pd];
  if(prev<now)
  {
         
V[prad].erase(V[prad].begin()+pd);
         
         for(b=prad;b<nrad;b++)
         {
      V[b].push_back(V[b+1].front());
      V[b+1].pop_front();
}
V[nrad].insert(V[nrad].begin()+now%rad,change);
  }   
  else  //prev<now
  {
    V[prad].erase(V[prad].begin()+pd);
    
    for(b=prad;b>nrad;b–)
    {
      V[b].push_front(V[b-1].back());
      V[b-1].pop_back();
}
V[nrad].insert(V[nrad].begin()+now%rad,change);
  }
    }
    else
    {
 int pos;
 fscanf(fr,"%d",&pos);
 fprintf(fw,"%d ",V[pos/rad][pos%rad]);
}
 
  }
  return 0;
}