Jump to content
mogers

Problema: Eko

Recommended Posts

mogers

Resolvi este problema no SPOJ. Parece-me um desafio simples e interessante.

Restrições: o programa deve correr em menos de 1 segundo para qualquer input que respeita os limites do enunciado.

Enunciado:

Lumberjack Mirko needs to chop down M metres of wood. It is an easy job for him since he has a nifty

new woodcutting machine that can take down forests like wildfire. However, Mirko is only allowed to

cut a single row of trees.

Mirko‟s machine works as follows: Mirko sets a height parameter H (in metres), and the machine raises

a giant sawblade to that height and cuts off all tree parts higher than H (of course, trees not higher than

H meters remain intact). Mirko then takes the parts that were cut off. For example, if the tree row

contains trees with heights of 20, 15, 10, and 17 metres, and Mirko raises his sawblade to 15 metres, the

remaining tree heights after cutting will be 15, 15, 10, and 15 metres, respectively, while Mirko will take

5 metres off the first tree and 2 metres off the fourth tree (7 metres of wood in total).

Mirko is ecologically minded, so he doesn‟t want to cut off more wood than necessary. That‟s why he

wants to set his sawblade as high as possible. Help Mirko find the maximum integer height of the

sawblade that still allows him to cut off at least M metres of wood.

Input

The first line of input contains two space-separated positive integers, N (the number of trees, 1 ≤ N

1 000 000) and M (Mirko‟s required wood amount, 1 ≤ M ≤ 2 000 000 000).

The second line of input contains N space-separated positive integers less than 1 000 000 000, the

heights of each tree (in metres). The sum of all heights will exceed M, thus Mirko will always be able to

obtain the required amount of wood.

Output

The first and only line of output must contain the required height setting.

Example

Input:

4 7

20 15 10 17

Output:

15

Explicação:Colocando a serra a altura 15, cortam-se 5 (20-15) + 2 (17-15) = 7 unidades de madeira o que satisfaz M.

Input:

5 20

4 42 40 26 46

Output:

36

Explicação:Colocando a serra a altura 36, cortam-se 6 (42-36) + 4 (40-36) + 10 (46-36) = 20 unidades de madeira o que satisfaz M.

Nota: fazer um simples ciclo na altura pretendida é demasiado lento. Como as alturas vão até 10^9 é necessária uma solução melhor.

  • Vote 1

"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
Warrior

Por acaso é um problema bem interessante.

Existe uma solução simples, mas a primeira coisa que me lembrei foi O(N*logN + logM*logN). Acho que nunca tinha feito nada com esta complexidade algorítmica.

Share this post


Link to post
Share on other sites
mogers

Também pensei nessa abordagem, mas a que eu submeti no spoj foi a abordagem mais simples :x


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
Rui Carlos

A primeira (e a única :D ) solução que me bem à cabeça passa por ordenar as árvores por altura. Assim à primeira vista, a complexidade da solução será a complexidade da ordenação.


#include <iostream>
#include <vector>

using namespace std;

int height(vector<int> heights, int ntrees, int quantity) {
   int i, max, current, diff, tdiff, result;
   sort(heights.begin(), heights.end(), greater<int>());
   max = heights[0];
   tdiff = 0;
   result = -1;
   for(i = 1; i < ntrees && result < 0; i++) {
       diff = max - heights[i];
       current = i * diff - tdiff;
       if(current > quantity) result = max - (current - quantity) / i;
       else tdiff += diff;
   }
   return result;
}

int main() {
   int quantity, ntrees, i, max, current, diff, tdiff;
   cin >> ntrees;
   cin >> quantity;
   vector<int> heights(ntrees);
   for(i = 0; i < ntrees; i++) {
       cin >> heights[i];
   }
   cout << height(heights, ntrees, quantity) << endl;
   return 0;
}

Share this post


Link to post
Share on other sites
mjamado

Estou aqui a pensar numa solução, que deverá ser semelhante à do Rui Carlos, com uma complexidade de O(n log n + n) (uma ordenação e uma iteração).

Existe alguma coisa mais simples?


"Para desenhar um website, não tenho que saber distinguir server-side de client-side" - um membro do fórum que se auto-intitula webdesigner. Temo pelo futuro da web.

Share this post


Link to post
Share on other sites
Warrior

Sem ordenar, O(N log M) é extremamente fácil de implementar.

Mudaram alguma coisa no problema, porque tinha accepted e passei a ter TLE. :o

EDIT: Acho que estragaram o problema ao obrigar fast input/output. Só mudei o código de leitura, spoiler em baixo..


#define SIZE 10001000


char s[size];

int main() {
 scanf("%d %d\n", &n, &k);

 int next = 0;
 fread(s, 1, SIZE, stdin);
 int acc = 0;
 for (size_t i = 0; s[i]!='\n'; i++) {
   if (s[i] == ' ') {
     v[next] = acc; 
     acc = 0;
   }
   else
     acc = acc*10 + s[i]-'0';
 }
 v[next] = acc;       

Edited by Warrior
  • Vote 1

Share this post


Link to post
Share on other sites
mogers

Puseram o limite em 2 segundos há pouco, já se pode usar o scanf novamente.

Rui, eu não resolvi dessa forma, mas penso que a ideia base funciona. No entanto tens alguns erros. O código falha sempre que N = 1 e também falha noutros casos, exemplo:

2 8

10 20

A resposta é 12, mas o programa devolve 18. Não tenho a certeza, mas penso também que será necessário usar long longs em alguns sitios.

Eu também fiz o O(N log M) que o Warrior referiu. A ideia base é: para uma altura X, se cortarmos as árvores a essa altura e obtivermos uma quantidade de madeira igual ou superior a M, então qualquer altura inferior a X também seria uma possível solução.

Edited by mogers

"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
Rui Carlos

Estava a fazer mal uma das contas... Curioso é que mesmo assim deu o resultado correcto nos casos de teste apresentados.

No cálculo do current é possível que um int não seja suficiente.

E também parece que com cin não vai lá, por isso troquei por scanf.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int height(vector<int> heights, int ntrees, int quantity) {
   long long int i, max, current, diff, tdiff, result;
   sort(heights.begin(), heights.end(), greater<int>());
   max = heights[0];
   tdiff = 0;
   result = -1;
   if(ntrees == 1) {
       result = max - quantity;
   }
   else {
       for(i = 1; i < ntrees && result < 0; i++) {
           diff = max - heights[i];
           current = i * diff - tdiff;
           if(current > quantity) result = max - diff + (current - quantity) / i;
           else tdiff += diff;
       }
   }
   return result;
}

int main() {
   int quantity, ntrees, i, max, current, diff, tdiff;
   scanf("%d %d", &ntrees, &quantity);
   vector<int> heights(ntrees);
   for(i = 0; i < ntrees; i++) {
       scanf(" %d", &heights[i]);
   }
   cout << height(heights, ntrees, quantity) << endl;
   return 0;
}

Share this post


Link to post
Share on other sites
Rui Carlos

E pronto, isto acabou de me fazer lembrar a razão pela qual não gosto deste tipo de problemas/concursos (não do problema em si, que me parece bastante interessante, mas da forma como são avaliados)...

Com o cin não passava no tempo, com o scanf dava um tempo de 4.xx, e usando o método do Warrior passa para um tempo de 1.49. Resumindo, o processamento do input leva muito mais tempo do que o algoritmo em si.

EDIT: Warrior, penso que te falta incrementar o next no teu código.

Share this post


Link to post
Share on other sites
mogers

Essas questões dos inputs acontecem mais nestes online judges. Em concursos mais a sério como as Olimpiadas de Informática, competições ACM, TopCoder (nem há I/O), Codejam e afins, as soluções do juri são aceites 99% das vezes mesmo usando cin. As poucas excepções que me lembro são normalmente relativas a grandes quantidades de texto como input onde é aconselhavel usar o fgets ou o getline.

A título de curiosidade deixo aqui 2 soluções. A que submeti primeiro O(N log M) e a outra que fiz à pouco O(N log N + log M * log N) que usa as rotinas de fast input que costumo usar. Qualquer sugestão é bem-vinda - o meu "fast input" não costuma estar ao nível dos mais rápidos.

#include <stdio.h>
unsigned h[1000010], N, M;
int main() {
 unsigned i, j, left(1), right, mid, res(0);
 scanf("%u %u", &N, &M);
 for (i = 0 ; i < N ; i++) {
	  scanf("%u", h+i);
	  if (h[i] > right)
		   right = h[i];
 }
 while (left <= right) {		   // pesquisa binária na solução O(N log M)
	  mid = (left+right) >> 1;
	  j = 0;
	  for (i = 0 ; i < N && j < M ; i++) // corte a altura 'mid'
		   if (h[i] > mid)
				j += h[i]-mid;
	  if ( j >= M ) {
		   res = mid;
		   left = mid+1;
	  }
	  else
		   right = mid-1;
 }
 printf("%u\n", res);
 return 0;
}

#include <stdio.h> /* a ideia é a mesma mas melhorando o cálculo da qt de madeira cortada */
#include <algorithm>
using namespace std;
#define MAX		  1000010
#define BUF_SIZE	   11000000
char buffer[bUF_SIZE];
int bindex;
#define readint(num)   while ( buffer[bindex] < '0' ) bindex++; \
                  for ( num = 0 ; buffer[bindex] >= '0' ; )	   num = num * 10 + buffer[bindex++]-'0';
unsigned h[MAX], N, M;
long long sum[MAX], s;

int main() {
 unsigned i, j, left(0), right, mid, res(0);
 fread( buffer , 1 , BUF_SIZE , stdin );
 readint(N);
 readint(M);
 ++N;
 for (i = 1 ; i < N ; i++) {
	  readint(h[i]);
 }
 sort(h+1, h+N);
 right = h[N-1];
 for (i = 1 ; i <= N ; i++)
	  sum[i] = sum[i-1] + h[i];

 while (left <= right) { // pesquisa binaria O(log M)
	  mid = (left+right) >> 1;
	  i = lower_bound(h, h+N, mid) - h;	   // * O(log N) para saber a
	  j = N-i;                          // partir de onde se pode cortar.
	  s = sum[N]-sum[i-1] - (long long)j*mid; // s=madeira se cortar ao nível 'mid'
	  if ( s >= M ) {
		   res = mid;
		   left = mid+1;
	  }
	  else
		   right = mid-1;
 }
 printf("%u\n", res);
 return 0;
}

PS: porque é que ao copiar o código, os tabs são eliminados? Tive de indentar à mão -.-'

Edited by mogers

"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
thoga31

PS: porque é que ao copiar o código, os tabs são eliminados? Tive de indentar à mão -.-'

Se utilizares o editor "bonito", acho que isso acontece. Se, como eu, utilizares o editor BBcode isso não acontece - passa tudo certinho. ;)

  • Vote 1

Knowledge is free!

Share this post


Link to post
Share on other sites
mogers

Se utilizares o editor "bonito", acho que isso acontece. Se, como eu, utilizares o editor BBcode isso não acontece - passa tudo certinho. ;)

Obrigado, é isso mesmo :)


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.