USACO - Milking Cows

[polska]

Boas pessoal, estive a resolver um problema da USACO, e esta-me a falhar num caso de teste...

O problema é o seguinte:

Three farmers rise at 5 am each morning and head for the barn to milk three cows. The first farmer begins milking his cow at time 300 (measured in seconds after 5 am) and ends at time 1000. The second farmer begins at time 700 and ends at time 1200. The third farmer begins at time 1500 and ends at time 2100. The longest continuous time during which at least one farmer was milking a cow was 900 seconds (from 300 to 1200). The longest time no milking was done, between the beginning and the ending of all milking, was 300 seconds (1500 minus 1200).

Your job is to write a program that will examine a list of beginning and ending times for N (1 <= N <= 5000) farmers milking N cows and compute (in seconds):

• The longest time interval at least one cow was milked.
  
• The longest time interval (after milking starts) during which no cows were being milked.
  

O meu cod:

/*
ID: bruninh1
LANG: C++
TASK: milk2
*/
#include <stdio.h>
int main()
{
FILE *in, *out;
in = fopen( "milk2.in", "r" );
out = fopen( "milk2.out", "w" );
int N, list1[5000], list2[5000],tmp;

int output1, output2;
//output 1 representa o resultado do primeiro output
//output 2 representa o resultado do segundo output

//get N
fscanf( in, "%d", &N );

//get times
for( int i=0; i<N; i++ )
{
 fscanf( in, "%d %d", &list1[i], &list2[i] );
}

//sort lists -> bubble sort
for( int i=0; i<N; i++ )
{
 for ( int j=i+1; j<N; j++ )
 {
  if( list1[i]>list1[j] )
  {
//list1
tmp=list1[i];
list1[i]=list1[j];
list1[j]=tmp;
//list2
tmp=list2[i];
list2[i]=list2[j];
list2[j]=tmp;
  }
 }
}

output1=list2[0]-list1[0]; //valor default
output2=0; //valor default

//get results -> complete search technique
for( int i=1; i<N; i++ )
{
 //output 1
 if( ( list1[i]<list2[i-1] ) && ( list2[i]>list2[i-1] ) )
  if( list2[i]-list1[i-1]>output1 )
output1=list2[i]-list1[i-1];
 //output 2
 if( list1[i]>list2[i-1] )
  if( list1[i]-list2[i-1]>output2 )
output2=list1[i]-list2[i-1];
}

//results
fprintf( out, "%d %d\n", output1, output2 );

//close
fclose( in );
fclose( out );

return 0;
}

A solução da Usaco para o caso de teste é 19_0 ( _ = espaço) , e o meu prog dá 19_1 ... Mas não percebo porque é 0 em vez de 1 ...

TESTE:

10

2 3

4 5

6 7

8 9

10 11

12 13

14 15

16 17

18 19

1 20

Line 1: The single integer

Lines 2..N+1: Two non-negative integers less than 1000000, the starting and ending time in seconds after 0500

Edited June 26, 2012 at 08:12 PM by polska

[mogers]

O último farmer trabalha de 1 a 20, logo está sempre activo. Por isso a 2ª resposta tem de ser 0.

btw, seria bom começares a usar um sort mais eficiente. O sort da stl do c++ é muito fácil de usar...

[polska]

O último farmer trabalha de 1 a 20, logo está sempre activo. Por isso a 2ª resposta tem de ser 0.

btw, seria bom começares a usar um sort mais eficiente. O sort da stl do c++ é muito fácil de usar...

kkkk, eu pensava que os intervalos eram sempre crescentes, logo não percebia aquele 1... xD

Mas sendo assim não vale a pena fazer o sort.. vamos ver que se resolvo desta ves ;D

Eu sei, mas a USACO vai abordar essas técninas mais eficientes, só estou a espera de chegar até lá 🙂

Obrigado

Edited June 26, 2012 at 08:29 PM by polska

[pmg]

/*
ID: bruninh1
LANG: C++
TASK: milk2
*/

Quadro errado?

Porque e que nao usas os streams do C++ em vez do fopen(), fscanf(), fclose()?

[polska]

Quadro errado?

Porque e que nao usas os streams do C++ em vez do fopen(), fscanf(), fclose()?

Eu tinha C no comentário, mas quando enviava a solução, dava-me uma série de erros esquisitos que eu não consegui resolver, então mudei para C++ e modifiquei apenas o void main(), e inclui os returns claro... E os erros nunca mais apareceram, eu sei que não é uma prática muito bonita mas eu ainda não sei as funções de streams do C++, estou agora a ver as classes mas neste livro não fala das streams ..

[pmg]

Possivelmente o teu compilador é para C99 e o da USACO é para C89.

Uma diferenca que pode ser a causa dos erros é a declaracao de variaveis "fora do sitio"

int main(void) {
   int ok = 0;
   ok++; /* ok is 1 */
   int onlyc99 = 2; /* erro em C89 */
   return 0;
}

Outra diferenca é a declaracao de variaveis na inicializacao do for

for (int c99only = 0; c99only < 100; c99only++) { /* ... */ }

Eu nao sei C++, acho que os streams nessa linguagem se usam com << e >>

inputstream >> variavel;
outputstream << variavel;

[polska]

Possivelmente o teu compilador é para C99 e o da USACO é para C89.

Uma diferenca que pode ser a causa dos erros é a declaracao de variaveis "fora do sitio"

int main(void) {
int ok = 0;
ok++; /* ok is 1 */
int onlyc99 = 2; /* erro em C89 */
return 0;
}

Outra diferenca é a declaracao de variaveis na inicializacao do for

for (int c99only = 0; c99only < 100; c99only++) { /* ... */ }

Eu nao sei C++, acho que os streams nessa linguagem se usam com << e >>

inputstream >> variavel;
outputstream << variavel;

Esse erro de declarar nos ciclos for eu sabia, tive que corrigir uma vez no Mingw ...

Eu vou experimentar submeter em C e tentar corrigir de novo, pode ser que ajude 😄 .

Eu também já me habituei a fazer assim nos concursos e depois para mudar é complicado xDD, mas eu vou acabar de estudar c++ e depois deixo o c

[mogers]

kkkk, eu pensava que os intervalos eram sempre crescentes, logo não percebia aquele 1... xD

Mas sendo assim não vale a pena fazer o sort.. vamos ver que se resolvo desta ves ;D

Eu sei, mas a USACO vai abordar essas técninas mais eficientes, só estou a espera de chegar até lá 🙂

A minha solução usa o sort, mas o tratamento dos intervalos tem de ser feito de outra forma.

A usaco não fala sobre algoritmos de ordenação. Esse ponto tens de aprender por fora.

Já agora o sort da <algorithm> é muito mais eficiente do que o qsort (ao ponto de já ter tido TLE simplesmente por usar o qsort e ao trocá-lo tive AC).

Quanto a aprender C++ e deixar o C, é uma opção tua mas eu prefiro muito mais misturar os 2. Isto é, usar a STL do C++ e a programação orientada por objectos sempre que seja útil, mas usar scanf/printf e outras ferramentas do C pois são (tipicamente) muito mais eficientes do que cin/cout e equivalentes.

e.g. Se tiveres de ler uns milhões de chars, a diferença de usar fgets/scanf e getline/cin é tremenda.

[polska]

A minha solução usa o sort, mas o tratamento dos intervalos tem de ser feito de outra forma.

A usaco não fala sobre algoritmos de ordenação. Esse ponto tens de aprender por fora.

Já agora o sort da <algorithm> é muito mais eficiente do que o qsort (ao ponto de já ter tido TLE simplesmente por usar o qsort e ao trocá-lo tive AC).

Quanto a aprender C++ e deixar o C, é uma opção tua mas eu prefiro muito mais misturar os 2. Isto é, usar a STL do C++ e a programação orientada por objectos sempre que seja útil, mas usar scanf/printf e outras ferramentas do C pois são (tipicamente) muito mais eficientes do que cin/cout e equivalentes.

e.g. Se tiveres de ler uns milhões de chars, a diferença de usar fgets/scanf e getline/cin é tremenda.

Pensei que falava, por abordar também a DP e assim..

Eu iniciei a aprendizagem a c++ mesmo porcausa da OOP, mas também já tinha visto no c plus plus esse sort do <algorithm> , mas ainda não aprendi..

Não conheço essas diferenças do scanf e cout e assim... Mas nunca é demais sabe-lo 😄

btw, eu voltei a incluir o sort porque depois pensei noutra maneira de resolver o problema.. Mas agora falha-me no test 6, penso que é o último, que é este:

6

100 200

200 400

400 800

800 1600

50 100

1700 3200

O output deles dá 1550_100 e o meu dá 1500_100 , os meus 1500 é (3200-1700) e os 100 é (1700-1600) , não entendo aquele 1550, a única maneira de se fazer ali é 1600-50.. Mas não entendo o porquê de se fazer isso .. 😞

[mogers]

Tás a olhar sem olhos de ver 😛

50 - 100, 100 - 200, 200 - 400, 400 - 800, 800 - 1600 : dá 1550

edit: sobre os algoritmos de ordenação, é um tópico relativamente simples e standard que até na wikipedia deve explicar +- bem. Daí que não seja tão necessário a Usaco ter focado isso. Tens nos tutoriais do topcoder um super resumo de alguns algoritmos de ordenação.

O sort da algorithm é fácil de usar, mas convém aprender POO, overloading de operadores e tal. Tanto funciona com containers como a classe vector como com arrays[] de C.

#include <algorithm>
using namespace std;
struct Tipo {
int val;
bool operator < (const Tipo & t ) const {
	 return val < t.val;
}
} vec[20];
//
sort( vec , vec + numElementos );
// ...

Edited June 28, 2012 at 03:29 PM by mogers

[polska]

Tás a olhar sem olhos de ver 😛

50 - 100, 100 - 200, 200 - 400, 400 - 800, 800 - 1600 : dá 1550

ah?? xD

isso dá -1550 se fizer o somatório das subtracções dos intervalos... Mas como é que isso é suposto estar certo no problema..

Já agora, deixo o meu cod para veres como estou a tratar dos intervalos:

//get max and min
maximo = list2[0];
minimo = list1[0];

for( int i=1; i<N ;i++ )
{
   //max
   if( list2[i]>maximo )
   maximo=list2[i];

   //min
   if( list1[i]<minimo )
   minimo=list1[i];
}


//sort lists -> bubble sort
for( int i=0; i<N; i++ )
{
   for( int j=i+1; j<N; j++ )
   {
       if( list1[i]>list1[j] )
       {
           tmp = list1[i];
           list1[i] = list1[j];
           list1[j] = tmp;
           tmp = list2[i];
           list2[i] = list2[j];
           list2[j] = tmp;
       }
   }
}

output1=list2[0]-list1[0]; //valor default
output2=0; //valor default


//get results -> complete search technique
for( int i=0; i<N; i++ )
{

   //output 1
   if( list1[i] == minimo && list2[i] == maximo )
   {
       output1 = list2[i]-list1[i];
       output2 = 0;
       break;
   }

   if( list2[i]-list1[i]>output1 )
       output1 = list2[i]-list1[i];
   if( ( i!=0 ) && ( list1[i]>list1[i-1] ) && ( list1[i]<list2[i-1] ) && list2[i]>list2[i-1] )
       if( list2[i]-list1[i-1]>output1)
           output1 = list2[i]-list1[i-1];

   //output 2
   if( ( list1[i]>list2[i-1] ) && ( i!=0 ) )
       if( list1[i]-list2[i-1]>output2 )
           output2 = list1[i]-list2[i-1];
}

Edited June 28, 2012 at 07:12 PM by pmg
indentacao adicinada (usando o editor basico)

[mogers]

Código sem indentação 😕

Deves ter percebido mal o problema. Quer-se saber o maior periodo de tempo seguido em que pelo menos uma vaca está a ser ordenhada. Os intervalos que referi são todos consecutivos, sem espaço entre eles. Assim é o mesmo que ter um intervalo 50 - 1600

[polska]

Código sem indentação 😕

Deves ter percebido mal o problema. Quer-se saber o maior periodo de tempo seguido em que pelo menos uma vaca está a ser ordenhada. Os intervalos que referi são todos consecutivos, sem espaço entre eles. Assim é o mesmo que ter um intervalo 50 - 1600

Tem identação, o problema é que ao copiar para aqui fica tudo junto 😕 ...

Pois percebi mal, eu pensei que era o maior período de tempo em que uma vaca foi ordenhada... xD

Mas penso que no output 2 estou correcto, é o maior período de tempo em que não se fez leite, ou melhor, em que nenhuma vaca foi ordenhada.. certo?

EDIT : Pronto, cheguei até ao ultimo teste, que são 1000 intervalos, agora é que eu não sei como descobrir onde falhei, eu penso que estou a tratar bem os intervalos..

Eu testo se existe um intervalo que englobe todos, ou seja, um intervalo que comece no principio e acabe depois de todos os outros, ai eu sei logo o resultado..

Se não houver, testo se os intervalos começam uns a seguir aos outros, e vou aumentado ao resultado...

Isto para o output 1 , para o 2 , se não houver um intervalo global também vou apontando o resultado á medida que comparo os intervalos...

Edited June 28, 2012 at 07:06 PM by polska

[mogers]

Mas penso que no output 2 estou correcto, é o maior período de tempo em que não se fez leite, ou melhor, em que nenhuma vaca foi ordenhada

Sim, certo.

[polska]

@mogers posso comparar o teu prog com o meu?

No ultimo teste da Usaco são 1000 intervalos, eu tive os meus dois outputs mal mas já corrigi e tenho o maior numero de tempo sem ordenhar correto, mas com 1000 casos não consigo descobrir porque tenho o primeiro output mal, no entanto deixo aqui o meu código, faço sort e depois testo 3 condições.

//default values
minimo = list1[0];
maximo = list2[0];
output1 = list2[0] - list1[0];
output2 = 0;

//get results -> complete search technique
for( int i=1; i<N; i++ )
{
//output1
if( list1[i] < maximo )
continue;
else if( list1[i] == maximo )
maximo = list2[i];
else
{
if( maximo-minimo > output1)
output1 = maximo - minimo;
minimo = list1[i];
maximo = list2[i];
//output2
if( list1[i]-list2[i-1] > output2 )
output2 = list1[i]-list2[i-1];
}
}

Edited June 28, 2012 at 07:55 PM by polska

[mogers]

Não me parece que esse seja o último teste. Visto que N <= 5000, o último teste deve ter 5000.

Não sou fã de dar o código. Repara que podes terminar o ciclo com um maximo e minimo actual que ainda não comparaste com o resultado.

Mas isso não me parece muito bem. Se tiveres [1,10] e [5,20] , como o 5 < 10 fazes continue, mas devias actualizar o máximo.

if (list1[i] <= maximo) {
     maximo = max( maximo , list2[i] );
}

[polska]

Mas isso não me parece muito bem. Se tiveres [1,10] e [5,20] , como o 5 < 10 fazes continue, mas devias actualizar o máximo.

[/code]

Tinhas razão, por 2 vezes xD

Faltava-me esta condição que falaste, por vezes não tenho de actualizar o máximo, mas neste caso tinha, e agora esta correcto..

E sim agora é o último caso, 5000 números xD , e só para não variar, voltou a falhar, mas eu vou descobrir, porra!

[polska]

Sucess ! 😄

Foram precisas 16 vezes para acertar o raio do problema, mas era mesmo simples xD, enquanto nos seguintes precisei de apenas 2 vezes ahah.

Fica aqui o code:

/*
ID: bruninh1
LANG: C++
TASK: milk2
*/

#include <stdio.h>

int main()
{
FILE *in, *out;
in = fopen( "milk2.in", "r" );
out = fopen( "milk2.out", "w" );
i
nt N, list1[5000], list2[5000];
int tmp, int_inicial, int_final;
int output1, output2;

// recebe N
fscanf( in, "%d", &N );

// recebe intervalos
for( int i=0; i<N; i++ )
{
 fscanf( in, "%d %d", &list1[i], &list2[i] );
}

// sort dos intervalos -> Bubble sort
for( int i=0; i<N; i++ )
{
 for( int j=i+1; j<N; j++ )
 {
  if( list1[i] > list1[j] )
  {
   //sort list1
   tmp = list1[i];
   list1[i] = list1[j];
   list1[j] = tmp;
   //sort list2
   tmp = list2[i];
   list2[i] = list2[j];
   list2[j] = tmp;
  }
 }
}

//atribui valores primários
// int_ = intervalo inicial e final
output1 = list2[0]-list1[0];
output2 = 0;
int_inicial = list1[0];
int_final = list2[0];

// produz resultados
for( int i=1; i<N; i++ )
{
 if( list1[i] < int_inicial || list2[i] > int_final )
 {
  if( list1[i] <= int_final && list2[i] >= int_final )
   int_final = list2[i];
  else
  {
   if( int_final-int_inicial > output1 )
 output1 = int_final-int_inicial;
   if( list1[i] > int_final && list1[i]-int_final > output2 )
 output2 = list1[i]-int_final;
   int_inicial = list1[i];
   int_final = list2[i];
  }
 }
}
if( int_final-int_inicial > output1 )
 output1 = int_final-int_inicial;

fprintf( out, "%d %d\n", output1, output2 );

return 0;
}