# ZigZag

**URL:** <https://forum.olinfo.it/t/zigzag/3798>\
**Category:** Aiuto\
**Created:** [27 Aprile 2014, 4:28pm UTC](https://forum.olinfo.it/t/zigzag/3798 "2014-04-27T16:28:34Z")\
**Posts on this page:** 16\
**Page:** 1

<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:** [27 Aprile 2014, 4:28pm UTC](https://forum.olinfo.it/t/zigzag/3798/1 "2014-04-27T16:28:34Z")

</div>

Ciao a tutti, chi mi sa dare un aiuto per risolvere l'ultimo subtask del problema ZigZag?&nbsp;  
Il mio codice è:

```
#include <fstream>
#include <cstdlib>
#include <algorithm>
#define MAXN 100001
using namespace std;
ifstream fin ("input.txt");
ofstream fout("output.txt");
int N;
int sequenza[MAXN],soluzioni[MAXN][2];
int massimo,temp;
int main()
{
fin>>N;
  
for(int i=0;i<N;i++)
{
fin>>sequenza[i];
//soluzioni[i][0]=soluzioni[i][1]=1;
}
for(int i=0;i<N-1;i++)
for(int j=i+1;j<N;j++)
{
temp=sequenza[i]-sequenza[j];
if(temp>0 && soluzioni[i][1]+1>soluzioni[j][0])
soluzioni[j][0]=soluzioni[i][1]+1;
else if(temp<0 && soluzioni[i][0]+1>soluzioni[j][1])
soluzioni[j][1]=soluzioni[i][0]+1;
}
  
for(int i=0;i<N;i++)
{
if(soluzioni[i][0]>massimo)
massimo=soluzioni[i][0];
if(soluzioni[i][1]>massimo)
massimo=soluzioni[i][1];
}
  
fout<<massimo+1;
}
```

Praticamente lo risolvo utilizzando la programmazione dinamica: nel vettore sequenza tengo la sequenza di numeri, nella matrice soluzioni tengo le soluzioni nel caso in cui la somma sia positiva (colonna 0) o negativa (colonna 1). Alla fine ricerco il massimo e lo stampo. La soluzione è corretta, ma con l'ultimo subtask vado fuori tempo limite. Come posso risolvere?  
  
Grazie a tutti :)

---

<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:** [27 Aprile 2014, 5:04pm UTC](https://forum.olinfo.it/t/zigzag/3798/2 "2014-04-27T17:04:52Z")

</div>

Ma perché allegare il programma se tanto non ha bug? 😛  
Volendo, il post si potrebbe “accorciare” in «Come si risolve ZigZag in meno di O(n²)?» 🙂

---

<div class="post-metadata">

**Author:** ![Mirko](https://forum.olinfo.it/user_avatar/forum.olinfo.it/mirko/32/34_2.png) [@Mirko](https://forum.olinfo.it/u/Mirko)\
**Post date:** [1 Maggio 2014, 10:36pm UTC](https://forum.olinfo.it/t/zigzag/3798/3 "2014-05-01T22:36:46Z")

</div>

Questo problema può essere risolto il tempo lineare tramite un approccio greedy!

---

<div class="post-metadata">

**Author:** ![Gaspare](https://forum.olinfo.it/user_avatar/forum.olinfo.it/gaspare/32/86_2.png) [@Gaspare](https://forum.olinfo.it/u/Gaspare)\
**Post date:** [2 Maggio 2014, 7:03am UTC](https://forum.olinfo.it/t/zigzag/3798/4 "2014-05-02T07:03:01Z")

</div>

Io ho una soluzione in O(N log N) che utilizza due range tree,

ottiene 100/100 con tempo max di 0.17s contro i 0.03-0.01s,

quindi esiste ovviamente una soluzione greedy lineare ( che non ho ancora trovato 😛 )

---

<div class="post-metadata">

**Author:** ![Gaspare](https://forum.olinfo.it/user_avatar/forum.olinfo.it/gaspare/32/86_2.png) [@Gaspare](https://forum.olinfo.it/u/Gaspare)\
**Post date:** [2 Maggio 2014, 7:30am UTC](https://forum.olinfo.it/t/zigzag/3798/5 "2014-05-02T07:30:00Z")

</div>

Ok ho trovato la lineare greedy con tempo max 0.00s 😛

Consiglio: guarda i segni della differenza tra due valori continui…

---

<div class="post-metadata">

**Author:** ![VashTheStampede](https://forum.olinfo.it/user_avatar/forum.olinfo.it/vashthestampede/32/10_2.png) [@VashTheStampede](https://forum.olinfo.it/u/VashTheStampede)\
**Post date:** [2 Maggio 2014, 5:55pm UTC](https://forum.olinfo.it/t/zigzag/3798/6 "2014-05-02T17:55:25Z")

</div>

Gaspare mica ti vieni a fare un giro alle OII sto anno? Mi piacerebbe conoscerti: fra te e Milizia (di cui conosco solo le leggende _-_) non so a chi fare la statua :0 Siete irraggiungibili ç\_\_ç

Coooomunque io con la Greedy lo faccio in 0.01, che cavolo mi manca per farlo in 0 :0

---

<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:** [2 Maggio 2014, 9:24pm UTC](https://forum.olinfo.it/t/zigzag/3798/7 "2014-05-02T21:24:04Z")

</div>

Se non sbaglio Gaspare usa il C, proprio per questi motivi di tempo. Gaspare correggimi se sbaglio.

  

OT  

Concordo sull’irraggiungibili! Ricordo l’anno scorso che Gaspare era scontento di essere arrivato decimo, mentre io avevo fatto appena 15 punti ahahah

---

<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:** [2 Maggio 2014, 10:20pm UTC](https://forum.olinfo.it/t/zigzag/3798/8 "2014-05-02T22:20:19Z")

</div>

Non c’è motivo di credere che il C++ sia in generale più lento del C.  
  
La cosa che prende gran parte del tempo (nei problemi in cui va fatto) è spesso l’I/O (anche per questo motivo si sta passando ai grader).  
  
Per fare 0.00s in genere basta scrivere una funzione che legge/scrive interi velocemente 🙂  
(ad esempio, leggendo carattere per carattere con **getchar\_unlocked()**).

---

<div class="post-metadata">

**Author:** ![Gaspare](https://forum.olinfo.it/user_avatar/forum.olinfo.it/gaspare/32/86_2.png) [@Gaspare](https://forum.olinfo.it/u/Gaspare)\
**Post date:** [3 Maggio 2014, 7:47am UTC](https://forum.olinfo.it/t/zigzag/3798/9 "2014-05-03T07:47:56Z")

</div>

VashTheStampede: si quest’anno vengo alle OII&nbsp;

Lawliet: no uso C++, ma conosco molti trucchi per ottimizzare i tempi,&nbsp;

uno tra i quali

  

p.s. Chi siete, che non ho associato i nomi ai nick 😃

p.p.s ottavo non decimo ☹ anche se ero scontento perchè ho perso l’oro per un banalissimo

return -1 ;(

---

<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:** [3 Maggio 2014, 3:31pm UTC](https://forum.olinfo.it/t/zigzag/3798/10 "2014-05-03T15:31:17Z")

</div>

Chiedo venia, ma mi pare che l’I/O del C fosse più veloce di quello del C++, ma forse ricordo male (o comunque, a quanto pare, ho erroneamente esteso il discorso ad ogni parte dei due linguaggi).

Gaspare non ci siamo conosciuti l’anno scorso, io sono Roberto Stagi (scontentissimo per i miei 15 punti dell’anno scorso, pronto per riscattarmi quest’anno).

---

<div class="post-metadata">

**Author:** ![Gaspare](https://forum.olinfo.it/user_avatar/forum.olinfo.it/gaspare/32/86_2.png) [@Gaspare](https://forum.olinfo.it/u/Gaspare)\
**Post date:** [3 Maggio 2014, 3:42pm UTC](https://forum.olinfo.it/t/zigzag/3798/11 "2014-05-03T15:42:39Z")

</div>

Io uso le librerie del c++ però uso le funzione di I/O del c,

proprio perchè sono più veloci.

O ancora meglio come ha detto william scriversi un parser di interi con&nbsp;

la lettura carattere per carattere!

  

p.s. ho nuovamente confuso OII con IOI xD&nbsp;
mi sa che non ci vediamo con vash

---

<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:** [8 Maggio 2014, 8:44pm UTC](https://forum.olinfo.it/t/zigzag/3798/12 "2014-05-08T20:44:52Z")

</div>

> Ok ho trovato la lineare greedy con tempo max 0.00s :P
> Consiglio: guarda i segni della differenza tra due valori continui...
> 
> Gaspare

Ho trovato una soluzione che confronta i segni delle differenze, ma inspiegabilmente funziona solo sui primi 12 testcase :/

---

<div class="post-metadata">

**Author:** ![Gaspare](https://forum.olinfo.it/user_avatar/forum.olinfo.it/gaspare/32/86_2.png) [@Gaspare](https://forum.olinfo.it/u/Gaspare)\
**Post date:** [8 Maggio 2014, 10:53pm UTC](https://forum.olinfo.it/t/zigzag/3798/13 "2014-05-08T22:53:18Z")

</div>

posta il codice…

---

<div class="post-metadata">

**Author:** ![marcoBeretta](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/ed655f/32.png) [@marcoBeretta](https://forum.olinfo.it/u/marcoBeretta)\
**Post date:** [3 Agosto 2014, 4:07pm UTC](https://forum.olinfo.it/t/zigzag/3798/14 "2014-08-03T16:07:50Z")

</div>

Per Gaspare in particolare, ma per chiunque abbia una risposta :)  
Con questo codice faccio giusti i primi 4 subtask in 0.000 secondi, ma per l'ultimo mi da output non corretto... mi sfugge qualcosa?  
Grazie!

// array con i numeri letti  
int array[n];

// array con le differenze (l'elemento diff[i] contiene 1 se&nbsp;array[i]-array[i+1] \> 0; -1 altrimenti)  
int diff[n-1];  
for(i=0; i\<n-1; i++)  
&nbsp; &nbsp; if(array[i]-array[i+1] \> 0)  
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;diff[i] = 1;  
&nbsp; &nbsp; else  
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;diff[i] = -1;

int count;  
int last;  
  
// count è la lunghezza sequenza  
count = 1;

// last vale 1 se l'ultima differenza era positiva; -1 altrimenti  
last = 1;

// per ogni differenza, se è diversa dall'ultima incremento la lunghezza della stringa e aggiorno il segno dell'ultima differenza (last)  
for(i=0; i\<n-1; i++)  
&nbsp; &nbsp; if(diff[i] != last){  
&nbsp; &nbsp; &nbsp; &nbsp; last = diff[i];  
&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;count++;  
&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;}  
  
int max = count;  
  
// ripeto tutto, ma partendo con il segno della prima differenza diverso da quello di prima  
count = 1;  
last = -1;

for(i=0; i\<n-1; i++)  
&nbsp; &nbsp; if(diff[i] != last){  
&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;last = diff[i];  
&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;count++;  
&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;}  
  
// aggiorno max se necessario  
&nbsp; &nbsp; &nbsp;if(count \> max)  
&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;max = count;  
  
// stampo max su file

---

<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:** [3 Agosto 2014, 4:56pm UTC](https://forum.olinfo.it/t/zigzag/3798/15 "2014-08-03T16:56:40Z")

</div>

Devi anche considerare il caso in cui ci siano due elementi consecutivi uguali! Ad esempio, con l’input {5, 5, 4, 4, 3, 3} il tuo programma restituisce 6 (in quanto considera la differenza tra due numeri uguali negativa), mentre il risultato corretto è 2!

---

<div class="post-metadata">

**Author:** ![marcoBeretta](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/ed655f/32.png) [@marcoBeretta](https://forum.olinfo.it/u/marcoBeretta)\
**Post date:** [5 Agosto 2014, 8:20am UTC](https://forum.olinfo.it/t/zigzag/3798/16 "2014-08-05T08:20:06Z")

</div>

Risolto, perfetto!

Grazie mille!