Estudo de algoritmos

Assuntos Gerais
#41

[quote=juliocbq][quote=mochuara][quote=juliocbq]
a questão é como.
E dito no problema, você não tem gasolina.
E mais, imagine essa lista com milhões de possibilidades(Uma árvore, para falar a verdade).[/quote]

É um bom dever de casa, mas pra mim se não vem acompanhado de um modelo de receita não é um problema que vale a pena perder meu tempo. rsrs
[/quote]
Então fique sabendo que te pagariam $1.000.000, se fizesse um software que resolvesse esse problema em tempo real.
Com certeza você não é um engenheiro, nem cientista da computação. Essa é a diferença entre eles e os analistas.[/quote]

Se voce analisar, esse valor é pouco.

#42

[quote=mochuara][quote=juliocbq][quote=mochuara][quote=juliocbq]
a questão é como.
E dito no problema, você não tem gasolina.
E mais, imagine essa lista com milhões de possibilidades(Uma árvore, para falar a verdade).[/quote]

É um bom dever de casa, mas pra mim se não vem acompanhado de um modelo de receita não é um problema que vale a pena perder meu tempo. rsrs
[/quote]
Então fique sabendo que te pagariam $1.000.000, se fizesse um software que resolvesse esse problema em tempo real.
Com certeza você não é um engenheiro, nem cientista da computação. Essa é a diferença entre eles e os analistas.[/quote]

Se voce analisar, esse valor é pouco.[/quote]

eu estaria feliz com 1 milhão de dólares, por um problema. fora trabalho na nasa ou outra instituição como essa.
Sem querer ofender, mas vc ganha mais que isso?

#43

[quote=mochuara]
Certa vez eu trabalhei num projeto que estava custando muito grana porque tinha um programador que queria de toda maneira resolver o problema utilizando um algoritmo de grafos que ele havia aprendido na faculdade recentemente. Como não foi dada uma solução mais simples para o problema eu tive que chamar a responsa e usei meu conhecimento da Java Collections Framework que resolveu o problema. Essa empresa também era uma grande multinacional.[/quote]
Você deu um exemplo de um cara que já viu os algoritmos mas não entendeu a teoria.

#44

Esse valor mal da pra comprar uma quota do orkut. :lol:

#45

tá certo. rs.

#46

Fala aí galera, estou lendo o livro Programming Chanllenge, tentei submiter os codigos e ta dando resposta errada em um site e em outro erro em tempo de execução, mas acredito que não esteja, alguem sabe como submiter?
Estou achando que o segredo é descobrir como submiter ao inves de resolver o algoritmo rsrs.

Tentei nesses dois sites http://www.programming-challenges.com ou http://online-judge.uva.es

Achei meio estranho a forma de ler os inputs, não se se está certo, segui um exemplo que tem no site.

vlw!!!

#47

Só alguns comentários. Muitas soluções excelentes não poderão ser usadas em challenges como o Google Code Jam nesses eventos também existem severas limitações sobre o tamanho do binário, tempo para o desenvolvimento, etc.

Acho que os algoritmos desenvolvidos lá podem ser considerados um exemplo de técnica, mas não necessariamente um exemplo de boas práticas. Na vida real, você acaba tendo que abrir mão da enxutes e performances absolutas em prol de manutenção, encapsulamento, facilidade de uso, etc.

Além do mais, é bom lembrar que algoritmos são só parte da solução do problema. Decisões arquiteturais são outra parte. Usar os algoritmos certos com uma arquitetura errada pode ser tão prejudicial quanto usar os algoritmos errados numa arquitetura correta.

O bom desenvolvedor deve saber balancear os dois.

#48

Opa VinyGodoy, valeu pela dica! Tava lendo mesmo a respeito disso no livro, ele da varias dicas de como programar em challenges, o que usar o que não usar. Mas a solução que fiz não usei nada de mais, apenas uma recursividade. Estranho esses dois sites, não tem nada explicando o procedimento.

vlw!

#49

[quote=Veneno]Fala aí galera, estou lendo o livro Programming Chanllenge, tentei submiter os codigos e ta dando resposta errada em um site e em outro erro em tempo de execução, mas acredito que não esteja, alguem sabe como submiter?
Estou achando que o segredo é descobrir como submiter ao inves de resolver o algoritmo rsrs.

Tentei nesses dois sites http://www.programming-challenges.com ou http://online-judge.uva.es

Achei meio estranho a forma de ler os inputs, não se se está certo, segui um exemplo que tem no site.

vlw!!![/quote]
Qual o código ou o link do seu problema? Você fez em Java?

#50

é 110101 no Programming Challenge e 100 no UVa.

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=29&page=show_problem&problem=36
http://www.programming-challenges.com/pg.php?page=downloadproblem&probid=110101&format=html

fiz em Java.

#51

Acho que o propósito desse problema e ‘pegar’ os iniciantes. Ele parece ser bem inocente mas, na verdade, não é. Se você não usar uma técnica chamada parecida com outra chamada Memoization, ele não passa (passar passa, mas é difícil). Essa técnica de Memoization é bem simples: memorize o que você já fez. Por exemplo, pra calcular o fatorial de 2, o computador resolve bem rápido. 2 * 1 = 2. De 3, também: 3 * 2 * 1. De 10, já parece demorar um pouco mais. Agora imagine de 10000. Demora bastante se você não usar Memoization.

Nesses problemas eles geralmente dizem o maior valor que será entrado De posse disso, você pode criar uma estrutura de dados pra armazenar o resultado dos valores já entrado, não precisando ‘percorrer todo o caminho’. Ainda, no fatorial, se pedissem pra calcular o fatorial de um número gigantesco depois de calcular o fatorial de diversos outros números menores, você pode tirar vantagem disso.

Supondo que n seja a entrada, e 100 (cem) seja o maior valor entrado (geralmente é muito maior, mas dependendo da quantidade de dígitos do resultado você deve usar outras técnicas, como Big Num, mas isso é mais tarde). Você pode criar um vetor de Long (em Java) ou long long em C++. Long porque int não consegue ‘aguentar’ o tranco, ou seja, não consegue suportar a quantidade de dígitos do resultado (alguns chegam a 10, 15 dígitos).
Certo. Criamos o vetor de Long. E agora? Agora, inicializamos as duas primeiras posições dele:
vetor[0] = 1;
vetor[1] = 1;

Agora, basta armazenar o resultado das entradas:
Entrou 2.
vetor[2] = 2 * vetor[1];
vetor[2] = 2;

Entrou 3.
vetor[3] = 3 * vetor[2];
vetor[3] = 6;

Entrou 5:
se vetor[4] for nulo (ou nil, ou 0), pegamos o vetor[3] e fazemos o mesmo procedimento.

Pra entradas pequenas parece ser muito inútil. Mas imagine que você tenha calculado o fatorial de 10 e seja pedido o de 11. Em vez de você fazer 11!, você faz 11 * fatorial de 10. Isso dá MUITA diferença no tempo com que o resultado final é impresso. Acho que mais confundi que expliquei :frowning:

Tem muito desse tipo de problema. Quando é simples, como o 3n + 1 ou esse do fatorial, é tranquilo de ver que é necessário usar uma estrutura pra memorizar os resultados.

Acho que eu tenho esse problema resolvido (não veja se quiser tentar por si próprio, que é o melhor) num repositório pra códigos no Google Code criado pela minha pessoa. A proposta do repositório era manter a nossa equipe da maratona de programação atualizada, mas ninguém se interessou. Se você andar mais pra trás nos diretórios vai ver que tem alguns problemas resolvidos no SPOJ (na verdade, tem bem pouco no uva). Hoje em dia ando meio sem tempo de resolver, mas quando puder coloco alguns novos lá.

Aliás, outro forum ótimo pra comentar sobre esses problemas é o do spoj. Tem o do uva e o do spoj polonês (que é tudo em inglês) também.

Sobre usar Java, nunca consegui resolver um direito :\ Tanto que aprendi o que sei de C++ pra usar na maratona (e é bem pouca coisa).

Abraço.

#52

Opa André, uia não sabia que tinha que usar as tecnicas certas pra resolver. Entendi o que você falou, realmente faz bastante diferença mesmo, nunca tinha pensado em usar, é simple e bem util né? Vou mudar aqui pra ver se funciona. O duro desse site é que não tem como saber o que aconteceu, se é a sua lógica ou se falta usar alguma tecnica. O bom do GCJ é que ele disponibiliza o input, aí ja da pra ver se é problema de performance pelo menos hehe.
Legal em , voce tem uma equipe pra participar dessas maratonas?

vlw Abraço…

#53

Eu tinha. Hoje ou eles estão muito ocupados ou se desinteressaram. Tem um colega que ainda participa do TopCoder. Acho que ano que vem eu volto a participar deste último.

Alguns sites falam o tipo do erro. Alguns exemplos de erro (tem outros no livro): se o formato da saída está incorreto (tinha que pular uma linha entre cada resposta, por exemplo), se excedeu o tempo limite (TLE - Time Limit Exceed - geralmente precisa de uma ou outra otimização pra diminuir o tempo). Tem alguns erros mais ‘cabreiros’. O SPOJ apresenta também se o erro foi por falha de segmentação (o segfault, que muita gente já se deparou em C e C++).

#54

Na universidade tínhamos uma disciplina complementar que era Maratona de Programação. A gente aprendia todo o embasamento teórico por trás dos problemas - grafos, programação dinâmica, backtracking, etc - e simulávamos maratonas dividindo a turma em equipes de 3 programadores. Foi uma das disciplinas mais proveitosas que cursei.

#55

Inclusive, esse tópico aqui tem links pra sites - alguns já citados aqui - com problemas de computação:
http://www.guj.com.br/posts/list/80031.java

#56

Tínhamos tmb, e posso dizer que não somente essa maratona, como a iniciação científica, são essenciais no curso.

#57

[quote=Veneno]é 110101 no Programming Challenge e 100 no UVa.

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=29&page=show_problem&problem=36
http://www.programming-challenges.com/pg.php?page=downloadproblem&probid=110101&format=html

fiz em Java.[/quote]

Uma resposta possível para esse problema (descontando o fato que este programa não lê um arquivo) é:

import java.util.*;
class The3n1problem {
    int max;
    public The3n1problem (int max) {
        this.max = max;
        cl = new long [max + 1];
        cl [1] = 1;
    }

    public int cycleLength (int num) {
        long next = num;
        int count = 0;
        while (next >= max || cl[(int) next] == 0) {
            count++;
            next = next % 2 == 0 ? (next / 2) : (3 * next + 1);
        }
        int ret = (int) (count + cl [(int) next]);
        cl [num] = ret;
        return ret;
    }

    public int maxCycleLength (int a, int b) {
        int max = -1;
        for (int i = a; i <= b; ++i) {
            int x = cycleLength (i);
            if (max < x) { 
                max = x;
            }
        }
        return max;
    }
    private long[] cl;

    public static void main(String[] args) {
        The3n1problem t = new The3n1problem (1000000);
        System.out.println (t.cycleLength (1)); // 1
        System.out.println (t.cycleLength (10)); //
        System.out.println (t.cycleLength (22)); // 16
        System.out.println (t.maxCycleLength (1, 10)); // 20
        System.out.println (t.maxCycleLength (100, 200)); // 125
        System.out.println (t.maxCycleLength (201, 210)); // 89
        System.out.println (t.maxCycleLength (900, 1000)); // 174
        System.out.println (t.maxCycleLength (1, 1000000)); // 525
    }
}

Obviamente o pior caso é quando i = 1 e j = 1000000.

#58

Legal pra caramba galera, na minha faculdade infelizmente não tive isso =/. Tenho que aprender agora.

Fiz da seguinte forma, mas ainda não funcionou lá no site, vou desistir desse site hehe…

Map<Long, Long> ciclosRealizados = new HashMap<Long, Long>();

	public void run() {

		ciclosRealizados.put(1L, 1L);

		// segundo numero do intervalo
		long ultimoNumero = 0;
		// primeiro numero do intervalo
		long primeiroNumero = 0;
		long tamanhoMaximo = 0;

		String linha = null;
		while ((linha = Main.ReadLn(50)) != null && linha.trim().length() > 0) {

			linha = linha.trim();
			String[] entrada = linha.split(" ");

			primeiroNumero = Long.parseLong(entrada[0]);
			ultimoNumero = Long.parseLong(entrada[1]);

			if (ultimoNumero < primeiroNumero) {
				long temp = primeiroNumero;
				primeiroNumero = ultimoNumero;
				ultimoNumero = temp;
			}


			for (long i = ultimoNumero; i >= primeiroNumero; i--) {

				long qtdCiclos = calcula(i);

				// recupera o maior ciclo da sequencia
				if (tamanhoMaximo < qtdCiclos)
					tamanhoMaximo = qtdCiclos;
			}

			System.out.println(Long.parseLong(entrada[0]) + " "
					+ Long.parseLong(entrada[1]) + " " + tamanhoMaximo);

			ultimoNumero = 0;
			primeiroNumero = 0;
			tamanhoMaximo = 0;

		}
	}

	long calcula(long numeroAtual) {
		Long numeroOriginal = numeroAtual;
		if (!ciclosRealizados.containsKey(numeroAtual)) {
			if (numeroAtual % 2 == 0) {
				numeroAtual /= 2;
			} else {
				numeroAtual = (numeroAtual * 3) + 1;
			}
			ciclosRealizados.put(numeroOriginal, 1 + calcula(numeroAtual));
		}
		return ciclosRealizados.get(numeroOriginal);
	}

vlw!!

#59

Seu Veneno, o seu programa não vai passar no site porque provavelmente eles usam a entrada (1, 1000000). O seu programa tem problemas de recursividade para um determinado número (que não lembro mais qual é), mas que excede os limites do Java.
Experimente rodá-lo. (É por isso que meu programa não usa recursividade. A primeira versão do meu programa era praticamente igual à sua, até que descobri essa pegadinha de que o Java não aceita muitos níveis de recursividade e esse problema precisa de muitos níveis (talvez mais de 600), ou seja, não pode ser feito de maneira recursiva para uma linguagem que não aceita um número indefinido de níveis de recursividade.

#60

Outra ‘boa prática de testes de maratona de programação’ é criar um arquivo txt com as entradas que você acha que pode ter. Geralmente, se a entrada menor é m e a maior é n, coloca essas duas. Depois executa o algoritmo com base nesse arquivo. Em C++ era assim

./programa < arquivoDeEntrada.txt

No Java deve ser a mesma coisa:

[code]java programa < arquivoDeEntrada.txt[code]
Mas acho que não funciona da mesma maneira.