Mark hai qualche idea per risolvere vasi2?
1 Mi Piace
vediamo se ho capito: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.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).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 chiaroLawliet
mark03
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
1 Mi Piace
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?
Io sìP.S: ci sarete tutti e due alle OII a settembre?mark03
1 Mi Piace
yes (y)Io sìP.S: ci sarete tutti e due alle OII a settembre?mark03
Lawliet
1 Mi Piace
Qualche guru che possa illuminarmi nella risoluzione di vasi2?
1 Mi Piace
Allora perchè la ricerca dovrebbe avere complessità O(N/M) + O(M) ??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.simone.pri
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).Allora perchè la ricerca dovrebbe avere complessità O(N/M) + O(M) ??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.simone.pri
wil93
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 
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 :)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)UPD: Anzi no, probabilmente nell'altro metodo sono uguali... quindi direi che il vostro è migliore :)wil93
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?
1 Mi Piace
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.
1 Mi Piace
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…
1 Mi Piace
Ma mi sembra strano che non te lo faccia perché comunque l’algoritmo è quello
1 Mi Piace
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…
1 Mi Piace
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
1 Mi Piace
Forse segment tree?
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)
1 Mi Piace
Noi comunque aspettiamo l’illuminazione di qualche guru
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è?
#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;
}
1 Mi Piace