O problema do apostador - Uma aplicação

Como foi introduzido no post passado, hoje vamos falar de uma aplicação prática do problema do apostador. O puzzle do Facebook para o famoso hackathon anual (https://www.facebook.com/events/828648753872660/) finalmente foi encerrado e podemos divulgar ideias e métodos. A questão era a seguinte:

Temos um vetor "arr" com n inteiros, sendo cada elemento 1 ou 0. Queremos achar as posições L e R tal que, invertendo todos os elementos de índice L a R, inclusive, temos o maior número possível de uns. A resposta para o problema deve ser um inteiro, o número de uns total do vetor depois dos elementos entre L e R serem invertidos.

Lembrando que "inverter" um inteiro nesse vetor significa transformar zeros em uns, e uns em zeros.

Para resolver esse problema, voltamos às técnicas do post anterior. Podemos variar L e R para todos os valores possíveis e armazenar o número de uns antes de L e depois de R, e o número de zeros entre L e R, somando os dois. Depois vemos para que valores de L e R temos a soma máxima e, pronto, temos nossa resposta!

Infelizmente esse método é extremamente ineficiente, e portanto nem vou botar a ideia em código. Fica muito evidente os problemas de tempo quando se fala em vetores com um número grande de elementos.

Portanto, vamos ao segundo método. Foi minha primeira ideia para resolver o puzzle: Criar uma lista encadeada de ilhas e unir os elementos que valem a pena. Segue o código que fiz, comentado.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

import java.util.ArrayList; import java.util.Scanner; public class island { int start; //indice do começo da ilha int finish; //indice do fim da ilha int size; //lucro da ilha, quantos zeros tem a mais que 1 int type; //0 ou 1 public static ArrayList<island> verifyWorth(ArrayList<island> list) { boolean done = false; while(!done) //quando nenhuma modificacao for feita, encerramos { done = true; for(int i=0; i<list.size()-2; i++) { if(list.get(i).type == 0 && list.get(i+2).size > list.get(i+1).size) { done = false; list.get(i).finish = list.get(i+2).finish; list.get(i).size += (list.get(i+2).size - list.get(i+1).size); list.get(i).mixed = true; list.remove(i+1); list.remove(i+1); i--; //como estamos modificando os elementos da lista, precisamos modificar o i adequadamente } } } return list; } public static ArrayList<island> buildList(int[] raw) //constroi a lista a partir do vetor dado { ArrayList<island> list = new ArrayList<island>(); island temp = new island(); int start; start = 0; for(int i=0; i<raw.length-1; i++) { if(raw[i]!=(raw[i+1])) { temp.start = start; temp.finish = i; temp.type = raw[start]; start = i+1; temp.size = 1 + temp.finish - temp.start; list.add(temp); temp = new island(); //precisamos reiniciar essa ilha para ela não modificar um elemento já adicionado } } temp.start = start; //por causa das restrições do for, o último elemento tem que ser tratado separadamente temp.finish = raw.length-1; temp.type = raw[start]; temp.size = 1 + temp.finish - temp.start; list.add(temp); temp = new island(); return list; } public static island findMax(ArrayList<island> list) //retorna o máximo da lista já reduzida { island max; if(list.get(0).type == 0) max = list.get(0); else max = list.get(1); for(int i=0; i<list.size(); i++) { if(list.get(i).type == 0 && max.size < list.get(i).size) max = list.get(i); } return max; } public static int Result(int[] raw) { ArrayList<island> list = new ArrayList<island>(); island max; int counter=0; list = buildList(raw); //constrói o ArrayList list = verifyWorth(list); //Reduz max = findMax(list); //Retorna a ilha máxima for(int i=0; i<raw.length(); i++) //conta quantos uns temos { if((i<max.start || i>max.finish) && raw[i] == '1') counter++; else if((i>=max.start && i<=max.finish) && raw[i] == '0') counter++; } return counter; } }

Esse código é funcional, porém bastante longo e complexo. Também não é muito eficiente em questão de tempo de execução. Podemos fazer melhor.

Chegamos então, finalmente, na última ideia. Segue o código, comentado.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

public static void Solution(int[] arr) { int ones=0; //quantos uns tem na string, ao todo, sem inversão int score=0; //lucro do elemento sendo analisado int maxscore=0; //lucro maximo encontrado ate o momento for(int i=0; i<arr.length;i++) //percorremos o vetor { if(arr[i]==0) //se o dia tiver lucro { score++; //incremente o lucro atual if(score>maxscore) //se maior que o lucro máximo, temos um novo máximo maxscore = score; } if(arr[i]==1) //se for prejuízo { score--; //decremente o lucro atual ones++; //conte quantos uns existem no vetor if(score<0) //se o lucro for negativo, nao compensa começar o dia até hoje score = 0; //L se torna esse } } System.out.println(ones+maxscore); //maxscore sao todos os zeros trocados MENOS os uns trocados. Entao //para a resposta temos o numero de uns total, mais o numero de zeros entre L e R, MENOS o numero de uns entre L e R. return; }

E pronto! Temos a resposta em pouquíssimas linhas, em uma única função e em ordem n, não sendo problemática para vetores grandes.

Quaisquer dúvidas, estou à disposição.

Até depois!