[Vari] Contest 16: Intervalli

[rеpne scasb]

■

[^TiGeRShArK^]

oh finalmente due uguali

[gugoXX]

Ieee, ci siamo allora, e' il risultato.
Lo do 2 su 5 almeno

[rеpne scasb]

■

[^TiGeRShArK^]

uff...
sistemato pure io....
avevo fatto il banalissimo errore di mettere l'assegnazione dopo l'if esterno..

string[] content = File.ReadAllLines("RealLine.txt");
Stopwatch watch = Stopwatch.StartNew();
char[] separator = new char[] { ' ' };
var orderedIntervals = (from c in content
                        let tokens = c.Split(separator, StringSplitOptions.RemoveEmptyEntries)
                        let first = double.Parse(tokens[0])
                        let second = double.Parse(tokens[1])
                        select new double[] { 
                              first <= second ? first : second, 
                              first <= second ? second : first 
                        }).OrderBy(e => e[0]).ToArray();

double previousRight = double.NegativeInfinity;
double total = 0.0;
foreach (var interval in orderedIntervals)
{
    double left = interval[0];
    double right = interval[1];
    if (previousRight <= right) {
        if (left > previousRight)
        {
            total += right - left;
        }
        else
        {
            total += right - previousRight;
        }
        previousRight = right;
    }
}
watch.Stop();
Console.WriteLine("Il totale è {0}, calcolato in {1}ms", total, watch.ElapsedMilliseconds);
Console.ReadLine();

L'algoritmo che ho usato dovrebbe essere abbastanza self-explanatory
l'output è:

Il totale è 380404,063114734, calcolato in 41ms

sul solito windows xp virtualizzato tramite parallels su un macbook pro a 2.4 ghz

[Vincenzo1968]

17 pure a me

Per il momento ritiro il mio codice perché mi sono accorto che c'è un bug e il risultato, sul file grosso, non è corretto

[^TiGeRShArK^]

Originariamente inviato da rеpne scasb

Come algoritmo ho utilizzato un OR logico su numeri float, basandomi sul concetto che se ABS(A[i]-B[i])>K allora e' possibile quantizzare A[i] e B[i] con 'n' stati di lunghezza K. Di fatto ho trasformato dei float in interi, e ne ho fatto l'OR.

Tu che algoritmo hai utilizzato?

ehmm..
dopo aver sostituito CLK_TCK con CLOCKS_PER_SEC, che altrimenti mi dava errore in compilazione, il tuo codice mi va in segmentation fault..
Lo sto usando su Mac Os X Leopard 10.5.7 compilato con XCode....

[rеpne scasb]

■

[gugoXX]

Originariamente inviato da rеpne scasb

Come algoritmo ho utilizzato un OR logico su numeri float, basandomi sul concetto che se ABS(A[i]-B[i])>K allora e' possibile quantizzare A[i] e B[i] con 'n' stati di lunghezza K. Di fatto ho trasformato dei float in interi, e ne ho fatto l'OR.

Tu che algoritmo hai utilizzato?

Ho mantenuto una lista di intervalli non sovrapposti, e ogni volta che devo valutare un nuovo intervallo cerco tutti i sovrapponibili, li estraggo, li fondo e inserisco il nuovo intervallo nella lista.
Per velocizzare la ricerca dei sovrapposti ho mantenuto 2 Indici, e con un paio di filtri e operazioni insiemistiche riduco l'insieme dei controlli.
Tra il dire e il fare c'e' di mezzo l'Italiano, dato che l'algoritmo in realta' sono una dozzina di righe abbastanza semplici.

[Vincenzo1968]

A me il codice di repne funziona perfettamente:



La macchina è questa:

AMD Athlon(tm) 64 X2
Dual Core Processor 4800+
2.50 GHz
896 MB di RAM

Microsoft Windows XP Professional (32 bit)
Service Pack 3

[^TiGeRShArK^]

Originariamente inviato da rеpne scasb

Tutto puo' essere. Ho scritto il codice in pochi minuti, e ci saranno sicuramente dei bachi. Allego l'eseguibile per Win32 che funziona sul mio PC, se interessa.

ok, questo va..
mi sa che il problema è che avevo cambiato i punti in virgole nel file originale perchè mi scaramellavo ad utilizzare il CultureInfo

ci mette 250ms circa sul mio....

[^TiGeRShArK^]

Originariamente inviato da Vincenzo1968

A me il codice di repne funziona perfettamente:



La macchina è questa:

mmm...
strano che sul mio xp virtualizzato sia così lento quello di repne....
puoi fare girare il mio codice sulla tua macchina per vedere quanto ci mette?

[gugoXX]

Originariamente inviato da Vincenzo1968

A me il codice di repne funziona perfettamente:



La macchina è questa:

Ma il tuo com'e'? L'hai aggiustato?

[Vincenzo1968]

Originariamente inviato da gugoXX

Ma il tuo com'e'? L'hai aggiustato?

No, non l'ho ancora aggiustato. Sui due esempi piccoli il risultato è corretto; sul file grosso no. Evidentemente l'algoritmo non è corretto.

[Vincenzo1968]

Originariamente inviato da ^TiGeRShArK^

mmm...
strano che sul mio xp virtualizzato sia così lento quello di repne....

Boh Può dipendere dalle ottimizzazioni del compilatore(utilizzo Visual Studio 2008)?

Originariamente inviato da ^TiGeRShArK^

puoi fare girare il mio codice sulla tua macchina per vedere quanto ci mette?

Mi dà errore:



EDIT: Riguardando il tuo codice m'è venuto un dubbio atroce: si tratta, per caso, di C# e io sto tentando di eseguirlo con l'interprete Ruby?

EDIT 2: Si, è C# Il risultato(sostituendo, nel file, i punti con le virgole) è questo:

[rеpne scasb]

■

[PGI-Bis]

Che strano. 17 e 13.5 si, il grosso no. Può essere un errore teorico?

Ho usato un albero BSP. I nodi contengono segmenti. L'idea è quella di prendere i segmenti in entrata e costruire un albero che abbia come valori segmenti che non si sovrappongono. Quando un segmento si sovrappone ad un altro:

------------------
              ++++++++++++++++

Genero tre segmenti non sovrapposti:

----------oooooooo+++++++++

il segmento centrale viene assegnato al nodo corrente, il segmento sinistro finisce nel sottoalbero sinistro, il segmento destro finisce nel sottoalbero destro.

Se il segmento inserito non si sovrappone a quello del nodo corrente allora il segmento finisce nel sottoalbero destro o sinistro, a seconda che il punto medio del nuovo segmento sia minore o maggiore del punto medio del segmento corrente.

Poichè i nodi dell'albero così costruito contengono segmenti disgiunti il risultato cercato è la somma delle estensioni dei segmenti contenuti in tutti i nodi.

Mi da 13.5, mi da 17 ma non mi da 380404,063114734. Mi perde per strada qualche segmento durante la lettura o è la parte teorica che non quaglia?

[^TiGeRShArK^]

Originariamente inviato da Vincenzo1968

Boh Può dipendere dalle ottimizzazioni del compilatore(utilizzo Visual Studio 2008)?



Mi dà errore:



EDIT: Riguardando il tuo codice m'è venuto un dubbio atroce: si tratta, per caso, di C# e io sto tentando di eseguirlo con l'interprete Ruby?

EDIT 2: Si, è C# Il risultato(sostituendo, nel file, i punti con le virgole) è questo:

boh... io ho usato l'eseguibile che ha postato repne..
prova pure tu ad usare quello casomai e vedi se ci sono differenze.....

Si cmq era C#, anche se in effetti avrei dovuto specificarlo dato che nei contest ne uso uno a caso tra C#, python e ruby
Ad onor del vero questo avevo iniziato a farlo in F#, ma mi sono rotto subito perchè ancora non lo so usare per bene

[wingman87]

Originariamente inviato da PGI-Bis

Che strano. 17 e 13.5 si, il grosso no. Può essere un errore teorico?

Ho usato un albero BSP. I nodi contengono segmenti. L'idea è quella di prendere i segmenti in entrata e costruire un albero che abbia come valori segmenti che non si sovrappongono. Quando un segmento si sovrappone ad un altro:

------------------
              ++++++++++++++++

Genero tre segmenti non sovrapposti:

----------oooooooo+++++++++

il segmento centrale viene assegnato al nodo corrente, il segmento sinistro finisce nel sottoalbero sinistro, il segmento destro finisce nel sottoalbero destro.

Se il segmento inserito non si sovrappone a quello del nodo corrente allora il segmento finisce nel sottoalbero destro o sinistro, a seconda che il punto medio del nuovo segmento sia minore o maggiore del punto medio del segmento corrente.

Poichè i nodi dell'albero così costruito contengono segmenti disgiunti il risultato cercato è la somma delle estensioni dei segmenti contenuti in tutti i nodi.

Mi da 13.5, mi da 17 ma non mi da 380404,063114734. Mi perde per strada qualche segmento durante la lettura o è la parte teorica che non quaglia?

Il ragionamento mi sembra corretto, siccome ti viene un valore più grande del risultato l'errore potrebbe essere o nella parte che controlla se due segmenti sono sovrapposti (perché se non rileva una sovrapposizione sommerà la stessa parte più di una volta) oppure nella somma degli intervalli (può essere un errore di distrazione).

[gugoXX]

Originariamente inviato da ^TiGeRShArK^

uff...
sistemato pure io....
avevo fatto il banalissimo errore di mettere l'assegnazione dopo l'if esterno..

string[] content = File.ReadAllLines("RealLine.txt");
Stopwatch watch = Stopwatch.StartNew();
char[] separator = new char[] { ' ' };
var orderedIntervals = (from c in content
                        let tokens = c.Split(separator, StringSplitOptions.RemoveEmptyEntries)
                        let first = double.Parse(tokens[0])
                        let second = double.Parse(tokens[1])
                        select new double[] { 
                              first <= second ? first : second, 
                              first <= second ? second : first 
                        }).OrderBy(e => e[0]).ToArray();

Eheh. Mi fa piacere.
Ho creato un mostro...