El cuervo sediento -- java campo con programming-challenge camp codereview Relacionados El problema

The Thirsty Crow


5
vote

problema

Español

Declaración de problemas

Hay n ollas. Cada olla tiene un poco de agua en ella. Pueden ser parcialmente
llenado. Así que hay un número de desbordamiento o asociado con cada olla que dice cuántas piezas de piedra mínimas requieren para esa olla para desbordarse. Así que si para una olla o-valor es 5 significa mínimo 5 Las piezas de piedra deben ponerse en esa olla para que se desborde.

Inicialmente, un cuervo observó esas ollas y al ver el nivel del agua. anticipado o-valor correctamente para cada olla (es decir, él sabía O1 para Sobre). Pero cuando volvió por la noche, descubrió que cada olla es pintado desde afuera y no puede saber qué olla tiene lo que O-valor. El cuervo quiere que algunas ollas se desborden para que pueda servir. su hijo apropiadamente. Para desbordar las macetas que necesita para buscar. Para las piedras en el bosque (asume que cada piedra tiene el mismo tamaño).

Quiere usar un número mínimo de piedras para desbordar las ollas K. Pero Él no sabe ahora que la olla tiene lo que vale. Así que la tarea es encontrar El número mínimo de piedras que el cuervo requiere hacer el k. Los macetas se desbordan en el peor de los casos.

Especificación de entrada:

  1. una matriz O correspondiente a O-valor de N Pots {O1, O2, ......., ON}
  2. Número de ollas
  3. k -value (número de macetas que el cuervo quiere desbordarse)

Especificación de salida:

Número mínimo de piedras requeridas para hacer desbordar K Pots en el peor de los casos Caso o -1 si la entrada no es válida.

Ejemplo:

Digamos que hay dos ollas:

  1. la olla 1 tiene un valor de 5, O1 = 5
  2. la olla 2 tiene un valor de 58, O2 = 58

Digamos que el Cuervo quiere hacerlo uno de los ollas desbordamiento. Si él sabe qué olla tiene lo que o-valor, simplemente buscaría 5 piedras y póngalos en olla 1 para que se desborde. Pero en un caso real. no sabe qué olla tiene lo que o-valor para que solo 5 piedras no pueden siempre trabajo. Sin embargo, él sabe que una olla tiene o-valor 5 y otros tiene 58. Entonces, incluso en el peor de los casos, puede hacer uno del desbordamiento de la olla. solo usando 10 piedras. Pondría 5 piedras en una olla si no se desborda, intentaría los 5 restantes en la otra olla que definitivamente se desbordaría porque uno de los ollas tiene o-valor de 5. así que La respuesta para la pregunta anterior es Mínimo 10 piedras incluso en el peor de los peores caso .

Por favor, hágamelo saber las correcciones que necesito para hacer mejor el código.

  public class ThirstyCrow {      public ThirstyCrow() {         super();     }     private static final int INVALID_INPUT=-1;      public int getMinimumNumberOfStonesRequiredToOverflowThePots(int[] overflowValues,int numberOfPotsPresent,             int numberOfPotsToOverFlow){         List<Pot> pots = null;         if(overflowValues.length>numberOfPotsPresent)return INVALID_INPUT;         if(numberOfPotsPresent<numberOfPotsToOverFlow) return INVALID_INPUT;         try {             pots = Pot.createPotsFromOverFlowLimits(overflowValues, numberOfPotsPresent);         } catch (InvalidInputException e) {             return INVALID_INPUT;         }         return getTotalNumberOfStonesUsedForOverflowing(pots, numberOfPotsPresent, numberOfPotsToOverFlow);     }      private int getTotalNumberOfStonesUsedForOverflowing(List<Pot> pots,int numberOfPotsPresent,             int numberOfPotsToOverFlow){         int numberOfPotsOverFlown=0;         int totalNumberOfStonesUsedForOverflowing = 0;         while(numberOfPotsOverFlown!=numberOfPotsToOverFlow){             int minimumOverFlowValue = getMinimumOverFlowValue(pots) ;             addTheStonesToAllPots(pots, minimumOverFlowValue);             numberOfPotsOverFlown++;             totalNumberOfStonesUsedForOverflowing+=(minimumOverFlowValue*pots.size());             removeOverflowingPotFromTheList(pots);         }         return totalNumberOfStonesUsedForOverflowing;      }      private int getMinimumOverFlowValue(List<Pot> pots){         if(pots.isEmpty())return 0;         Collections.sort(pots);         return pots.get(0).numberOfStoneRequiredForOverFlow();     }      private void removeOverflowingPotFromTheList(List<Pot> pots){         if(pots==null) return;         Iterator<Pot> potsListIterator = pots.iterator();         while(potsListIterator.hasNext()){             Pot pot = potsListIterator.next();           if(pot.numberOfStoneRequiredForOverFlow()==0) potsListIterator.remove();         }     }      private void addTheStonesToAllPots(List<Pot> pots,int numberOfStonesToAdd){         if(pots==null) return;         for (Pot pot : pots) {             pot.addStonesToThePot(numberOfStonesToAdd);         }     }   }  class Pot implements Comparable<Pot>{     private int overflowValue;     private int numberOfStonesPresent=0;      public Pot(int overflowValue) throws InvalidInputException{         if(overflowValue<0) throw new InvalidInputException("Invalid Input Provided!!");         this.overflowValue=overflowValue;     }      public Integer getOverFlowValue(){         return overflowValue;     }      public Integer getNumberOfStonesPresent() {         return numberOfStonesPresent;     }      public void addStonesToThePot(int numberOfStones){         if(numberOfStonesPresent>=overflowValue) return; //If the Pot is Already overflowing         numberOfStonesPresent+=numberOfStones;     }      public Integer numberOfStoneRequiredForOverFlow(){         return overflowValue-numberOfStonesPresent;     }      @Override     public int compareTo(Pot pot) {         return this.numberOfStoneRequiredForOverFlow().compareTo(pot.numberOfStoneRequiredForOverFlow());     }      public static List<Pot> createPotsFromOverFlowLimits(int [] overFlowLimits,int numberOfPots) throws InvalidInputException{         List<Pot> pots = new ArrayList<>();         if(overFlowLimits==null || overFlowLimits.length==0) return pots;         for (int i = 0; i < numberOfPots; i++) {             pots.add(new Pot(overFlowLimits[i]));         }         return pots;     }  }  class InvalidInputException extends Exception{      private String message;     private static final long serialVersionUID = 8332397639526918252L;      public InvalidInputException(String message){         this.message=message;     }      public String getMessage() {         return message;     }  }   
Original en ingles

Problem Statement

There are N pots. Every pot has some water in it. They may be partially
filled. So there is a Overflow Number O associated with every pot which tell how many minimum stone pieces are require for that pot to overflow. So if for a pot O-value is 5 it means minimum 5 stone pieces should be put in that pot to make it overflow.

Initially a crow watched those pots and by seeing the water level he anticipated O-value correctly for every pot (that is he knew O1 to On). But when he came back in evening he found that every pot is painted from outside and he is not able to know which pot has what O-value. The Crow wants some K pots to overflow so that he can serve his child appropriately. For overflowing the pots he needs to search for the stones in forest (assume that every stone has same size).

He wants to use minimum number of stones to overflow the K pots. But he doesn't know now which pot has what O-value. So the task is to find out the minimum number of stones that the crow requires to make the K pots overflow in the worst case.

Input Specification:

  1. A array O corresponding to O-value of N pots {O1, O2, ....... , On}
  2. Number of pots
  3. K -value ( number of pots which the crow wants to overflow)

Output Specification:

Minimum number of stones required to make K pots overflow in worst case or -1 if input is invalid.

Example:

Let's say there are two pots:

  1. Pot 1 has O value of 5 , O1= 5
  2. Pot 2 has O value of 58, O2= 58

Let's say the crow wants to make one of the pots overflow. If he knows which pot has what O-value he would simply search for 5 stones and put them in pot 1 to make it overflow. But in a real case he doesn't know which pot has what O-value so just 5 stones may not always work. However he does know that one pot has O-value 5 and other has 58. So even in the worst case he can make one of the pot overflow just by using 10 stones. He would put 5 stones in one pot if it doesn't overflow he would try the remaining 5 in the other pot which would definitely overflow because one of the pot has O-value of 5. So the answer for above question is minimum 10 stones even in worst case.

Please let me know the corrections that I need to make the code better.

public class ThirstyCrow {      public ThirstyCrow() {         super();     }     private static final int INVALID_INPUT=-1;      public int getMinimumNumberOfStonesRequiredToOverflowThePots(int[] overflowValues,int numberOfPotsPresent,             int numberOfPotsToOverFlow){         List<Pot> pots = null;         if(overflowValues.length>numberOfPotsPresent)return INVALID_INPUT;         if(numberOfPotsPresent<numberOfPotsToOverFlow) return INVALID_INPUT;         try {             pots = Pot.createPotsFromOverFlowLimits(overflowValues, numberOfPotsPresent);         } catch (InvalidInputException e) {             return INVALID_INPUT;         }         return getTotalNumberOfStonesUsedForOverflowing(pots, numberOfPotsPresent, numberOfPotsToOverFlow);     }      private int getTotalNumberOfStonesUsedForOverflowing(List<Pot> pots,int numberOfPotsPresent,             int numberOfPotsToOverFlow){         int numberOfPotsOverFlown=0;         int totalNumberOfStonesUsedForOverflowing = 0;         while(numberOfPotsOverFlown!=numberOfPotsToOverFlow){             int minimumOverFlowValue = getMinimumOverFlowValue(pots) ;             addTheStonesToAllPots(pots, minimumOverFlowValue);             numberOfPotsOverFlown++;             totalNumberOfStonesUsedForOverflowing+=(minimumOverFlowValue*pots.size());             removeOverflowingPotFromTheList(pots);         }         return totalNumberOfStonesUsedForOverflowing;      }      private int getMinimumOverFlowValue(List<Pot> pots){         if(pots.isEmpty())return 0;         Collections.sort(pots);         return pots.get(0).numberOfStoneRequiredForOverFlow();     }      private void removeOverflowingPotFromTheList(List<Pot> pots){         if(pots==null) return;         Iterator<Pot> potsListIterator = pots.iterator();         while(potsListIterator.hasNext()){             Pot pot = potsListIterator.next();           if(pot.numberOfStoneRequiredForOverFlow()==0) potsListIterator.remove();         }     }      private void addTheStonesToAllPots(List<Pot> pots,int numberOfStonesToAdd){         if(pots==null) return;         for (Pot pot : pots) {             pot.addStonesToThePot(numberOfStonesToAdd);         }     }   }  class Pot implements Comparable<Pot>{     private int overflowValue;     private int numberOfStonesPresent=0;      public Pot(int overflowValue) throws InvalidInputException{         if(overflowValue<0) throw new InvalidInputException("Invalid Input Provided!!");         this.overflowValue=overflowValue;     }      public Integer getOverFlowValue(){         return overflowValue;     }      public Integer getNumberOfStonesPresent() {         return numberOfStonesPresent;     }      public void addStonesToThePot(int numberOfStones){         if(numberOfStonesPresent>=overflowValue) return; //If the Pot is Already overflowing         numberOfStonesPresent+=numberOfStones;     }      public Integer numberOfStoneRequiredForOverFlow(){         return overflowValue-numberOfStonesPresent;     }      @Override     public int compareTo(Pot pot) {         return this.numberOfStoneRequiredForOverFlow().compareTo(pot.numberOfStoneRequiredForOverFlow());     }      public static List<Pot> createPotsFromOverFlowLimits(int [] overFlowLimits,int numberOfPots) throws InvalidInputException{         List<Pot> pots = new ArrayList<>();         if(overFlowLimits==null || overFlowLimits.length==0) return pots;         for (int i = 0; i < numberOfPots; i++) {             pots.add(new Pot(overFlowLimits[i]));         }         return pots;     }  }  class InvalidInputException extends Exception{      private String message;     private static final long serialVersionUID = 8332397639526918252L;      public InvalidInputException(String message){         this.message=message;     }      public String getMessage() {         return message;     }  } 
     
         
         

Lista de respuestas

4
 
vote
vote
La mejor respuesta
 

no funciona en todos los casos

Considere un caso de prueba con 2 potes: 99887776655443322 y $colors: null; // private, don't touch $themes: ( blog: ( base: red , light: lighten(red, 20%) ) , portfolio: ( base: orange , light: lighten(orange, 20%) ) , profile: ( base: green , light: lighten(green, 20%) ) , impressum: ( base: blue , light: lighten(blue, 20%) ) ); @mixin themify { @each $theme, $c in $themes { .page--#{$theme} { $colors: $c !global; @content; } } } @function theme($color: base) { @return map-get($colors, $color); } @include themify { .foo, .bar { background-color: theme(base); color: theme(light); } } 3 . Su programa devolverá 10, pensando que el cuervo debe llenar ambas ollas con 5 piedras. Pero en realidad el cuervo debería llenar una olla con 7 piedras, haciendo la respuesta 7.

Algoritmos alternativos

Creo que hay dos estrategias para eliminar una sola olla:

  1. Llene una olla con suficientes piedras para llenar la olla más grande.

  2. Rellena todas las macetas con suficientes piedras para llenar la olla más pequeña. Esto garantiza que se llenará la olla más pequeña.

Ahora, para llenar $ K $ POTS, no puede simplemente hacer la estrategia codiciosa de "para la próxima olla, elija las piedras mínimas para el caso # 1 y el caso # 2". Esto se debe a que el caso # 1 solo elimina una olla de la contienda, pero el caso # 2 también llena todas las otras ollas con algunas piedras, lo que podría tener beneficios para futuras iteraciones.

Puedo imaginar una solución de fuerza bruta que recursivamente intenta ambas estrategias en cada paso, pero eso tomaría un tiempo de $ $ (2 ^ k). Es muy probable que sea una mejor manera de hacer esto. Tal vez una solución de tiempo lineal sería:

Para cada $colors: null; // private, don't touch $themes: ( blog: ( base: red , light: lighten(red, 20%) ) , portfolio: ( base: orange , light: lighten(orange, 20%) ) , profile: ( base: green , light: lighten(green, 20%) ) , impressum: ( base: blue , light: lighten(blue, 20%) ) ); @mixin themify { @each $theme, $c in $themes { .page--#{$theme} { $colors: $c !global; @content; } } } @function theme($color: base) { @return map-get($colors, $color); } @include themify { .foo, .bar { background-color: theme(base); color: theme(light); } } 4 en $colors: null; // private, don't touch $themes: ( blog: ( base: red , light: lighten(red, 20%) ) , portfolio: ( base: orange , light: lighten(orange, 20%) ) , profile: ( base: green , light: lighten(green, 20%) ) , impressum: ( base: blue , light: lighten(blue, 20%) ) ); @mixin themify { @each $theme, $c in $themes { .page--#{$theme} { $colors: $c !global; @content; } } } @function theme($color: base) { @return map-get($colors, $color); } @include themify { .foo, .bar { background-color: theme(base); color: theme(light); } } 5 : intente llenar $colors: null; // private, don't touch $themes: ( blog: ( base: red , light: lighten(red, 20%) ) , portfolio: ( base: orange , light: lighten(orange, 20%) ) , profile: ( base: green , light: lighten(green, 20%) ) , impressum: ( base: blue , light: lighten(blue, 20%) ) ); @mixin themify { @each $theme, $c in $themes { .page--#{$theme} { $colors: $c !global; @content; } } } @function theme($color: base) { @return map-get($colors, $color); } @include themify { .foo, .bar { background-color: theme(base); color: theme(light); } } 6 Potes más grandes con la estrategia # 1, y el $colors: null; // private, don't touch $themes: ( blog: ( base: red , light: lighten(red, 20%) ) , portfolio: ( base: orange , light: lighten(orange, 20%) ) , profile: ( base: green , light: lighten(green, 20%) ) , impressum: ( base: blue , light: lighten(blue, 20%) ) ); @mixin themify { @each $theme, $c in $themes { .page--#{$theme} { $colors: $c !global; @content; } } } @function theme($color: base) { @return map-get($colors, $color); } @include themify { .foo, .bar { background-color: theme(base); color: theme(light); } } 7 Potes más pequeños con la estrategia # 2. Luego, elija el $colors: null; // private, don't touch $themes: ( blog: ( base: red , light: lighten(red, 20%) ) , portfolio: ( base: orange , light: lighten(orange, 20%) ) , profile: ( base: green , light: lighten(green, 20%) ) , impressum: ( base: blue , light: lighten(blue, 20%) ) ); @mixin themify { @each $theme, $c in $themes { .page--#{$theme} { $colors: $c !global; @content; } } } @function theme($color: base) { @return map-get($colors, $color); } @include themify { .foo, .bar { background-color: theme(base); color: theme(light); } } 8 que requirieron las menos piedras y esa es la respuesta.

No he pensado lo suficiente sobre el problema de saber si el algoritmo anterior en realidad produce la respuesta correcta.

Otra consideración

Considere un caso de prueba con 3 ollas: $colors: null; // private, don't touch $themes: ( blog: ( base: red , light: lighten(red, 20%) ) , portfolio: ( base: orange , light: lighten(orange, 20%) ) , profile: ( base: green , light: lighten(green, 20%) ) , impressum: ( base: blue , light: lighten(blue, 20%) ) ); @mixin themify { @each $theme, $c in $themes { .page--#{$theme} { $colors: $c !global; @content; } } } @function theme($color: base) { @return map-get($colors, $color); } @include themify { .foo, .bar { background-color: theme(base); color: theme(light); } } 9 y /* line 42, ../sass/test.scss */ .page--blog .foo, .page--blog .bar { background-color: red; color: #ff6666; } /* line 42, ../sass/test.scss */ .page--portfolio .foo, .page--portfolio .bar { background-color: orange; color: #ffc966; } /* line 42, ../sass/test.scss */ .page--profile .foo, .page--profile .bar { background-color: green; color: #00e600; } /* line 42, ../sass/test.scss */ .page--impressum .foo, .page--impressum .bar { background-color: blue; color: #6666ff; } 0 . En este caso, la respuesta debe ser 10 y no 15, ya que después de llenar dos ollas con 5 piedras, se le garantiza haber llenado una de las ollas de tamaño 5. Por lo que se debe considerar al usar la estrategia # 2 anterior.

 

Doesn't work on all cases

Consider a test case with 2 pots: 5, 7 and k=1. Your program will return 10, thinking that the crow must fill both pots with 5 stones. But actually the crow should just fill one pot with 7 stones, making the answer 7.

Alternative algorithms

I think that there are two strategies for eliminating a single pot:

  1. Fill one pot with enough stones to fill the biggest pot.

  2. Fill all pots each with enough stones to fill the smallest pot. This guarantees that the smallest pot will be filled.

Now, to fill \$k\$ pots, you can't just do the greedy strategy of "for the next pot, pick the minimum stones for case #1 and case #2". That is because case #1 only eliminates one pot from contention, but case #2 also fills all the other pots with some stones, which could have benefits for future iterations.

I can imagine a brute force solution that recursively tries both strategies at each step, but that would take \$O(2^k)\$ time. There is most likely a better way of doing this. Perhaps a linear time solution would be:

For each i in 0..k: Try filling i largest pots with strategy #1, and the k-i smallest pots with strategy #2. Then pick the i that required the least stones and that is the answer.

I haven't thought enough about the problem to know if the above algorithm actually produces the correct answer.

Another consideration

Consider a test case with 3 pots: 5, 5, 20 and k=1. In this case, the answer should be 10 and not 15, because after filling two pots with 5 stones, it is guaranteed to have filled one of the pots of size 5. So this should be considered when using strategy #2 above.

 
 
   
   

Relacionados problema

1  Codificación de Google Jam: Tienda Credit Java Solution  ( Google code jam store credit java solution ) 
Sería genial si pudiera obtener este código revisado. Me encantaría consejos sobre cómo podría mejorar mi código. problema Recibirá un crédito C en una...

6  Proyecto EULER # 7: 10001ST PRIME  ( Project euler 7 10001st prime ) 
Esta es mi implementación de Project Euler # 7 . ¿Lo he exagerado de nuevo? ¿Hay algo más que debería o no debo hacer? Se ejecuta en 9 milisegundos en mi com...

4  Encuentre el número de subcadenas de una cadena numérica mayor que una cadena numérica dada  ( Find the number of substrings of a numerical string greater than a given num str ) 
Pregunta: http://qa.geeksforgeeks.org/9744/vinay-queried-interesting -Problem-optimización Entrada La primera línea contiene n que denota la longitud...

56  Proyecto Euler Problema 1 en Python - Múltiples de 3 y 5  ( Project euler problem 1 in python multiples of 3 and 5 ) 
Me gustaría sugerencias para optimizar esta solución de fuerza bruta a problema 1 . El algoritmo actualmente comprueba cada entero entre 3 y 1000. Me gustarí...

6  Solución de codewars a "ascensor simple"  ( Codewars solution to simple elevator ) 
Soy nuevo en la programación (menos de un año), y me gustaría mejorar. Resolví un problema en las claquinas y copié tanto mi solución como la solución venci...

6  Encontrar el siguiente palíndromo de una cadena de números  ( Finding the next palindrome of a number string ) 
Aquí está el problema: Un entero positivo se llama palíndromo si su representación en el El sistema decimal es el mismo cuando se lee de izquierda a dere...

5  Proyecto EULER NO. 17: contando letras para escribir los números de 1 a 1000  ( Project euler no 17 counting letters to write the numbers from 1 to 1000 ) 
Soy muy nuevo en la programación y, cierto, estoy avergonzado de compartir mi código para la crítica. Este código funciona y produce la respuesta correcta a l...

61  Uso de funciones separadas para Project Euler 1  ( Using separate functions for project euler 1 ) 
Comencé a programar con Java y C ++, así que estoy acostumbrado a tener una función "principal" que llama a otras funciones que realizan el trabajo real. En l...

6  Las vocales en una cadena están en orden alfabético  ( Vowels in a string are in alphabetical order ) 
Tarea Escriba una implementación que devuelva si un 99887776655544330 tiene vocales (idioma inglés) en orden alfabético (A-Z) o no. Feedback es mi v...

5  Cuatro cuatro para obtener cualquier número  ( Four fours to get any number ) 
Decidí resolver un problema de Código Golf llamado los cuatro cuatro . Descripción del problema: El Puzzle Four Fours es un popular rompecabezas matemát...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos