Marathoncode

Flávio Josephus foi um historiador judeu famoso do primeiro século, no momento da destruição do Segundo Templo. Durante a guerra judaico-romana, ele ficou preso em uma caverna com um grupo de 40 soldados cercados pelos romanos. A lenda diz que eles preferia o suicídio do que serem capturados então os judeus decidiram formar um círculo e, procedendo à sua volta, para matar cada terceira pessoa restante até que ninguém foi deixado. Josephus, não queria de morrer, rapidamente encontrou o local seguro no círculo e assim permaneceu vivo.

Você pode tentar repetir o feito de Flávio no seguinte jogo:

http://www.cut-the-knot.org/recurrence/flavius.shtml

Uma maneira simples de resolver este problema é utilizar a estrutura de dados fila e realizar uma simulação para descobrir qual é a posição do último a morrer no círculo formado.

Resultado

input:

10 3

output:

morreu 3
morreu 6
morreu 9
morreu 2
morreu 7
morreu 1
morreu 8
morreu 5
morreu 10
Sobrevivente 4

Outra maneira é definir a estrutura recursiva do problema:
f(n,k) = sobrevivente em um círculo com n pessoas e salto k começando na pessoa 1.

f(n,k) = ( k-1 + f(n-1,k)) %n + 1
f(1,k) = 1

O valor k-1 é adicionado ao valor de f(n-1,k) justamente para ajustar o círculo na posição k-1, lembrando que f(n-1,k) devolve a posição com relação primeiro, e o valor +1 é para ajustar corretamente na posição k.

segunda-feira, 15 de julho de 2013

Dojo Operações com Árvore Binária de Busca

Operações implementadas:
Altura da árvore
Imprimir em ordem crescente
Inserir elemento na árvore
Menor elemento da árvore
Imprimir a árvore
Remover elemento da árvore
Juntar duas subárvores
Testar se a árvore está balanceada

Saída

0
1
2
3
4
5
6
(4 (2 (1 (0 NULO NULO) NULO) (3 NULO NULO)) (5 NULO (6 NULO NULO)))
(5 (2 (1 (0 NULO NULO) NULO) (3 NULO NULO)) (6 NULO NULO))

sexta-feira, 21 de junho de 2013

Dojo Python Lista Encadeada

No dia 21/06/2013, fizemos um dojo na linguagem Python. O desafio foi implementar uma lista encadeada usando a linguagem Python.
Código fonte

Teste Unitário

sexta-feira, 14 de junho de 2013

Frações contínuas II

Seja um fração contínua x = $[a_1;a_2,a_3,\ldots,a_n]$, chamamos de convergentes ou frações parciais a sequência de números racionais $c_0, c_1, c_2, \ldots$ dados por:

$c_0 = a_0, c_1 = a_0+\frac{1}{a_1}, c_2 = a_0 + \frac{1}{a_1+\frac{1}{a_2}}, \cdots, c_n = a_0 + \frac{1}{a_1+\frac{1}{\cdots +\frac{1}{a_n}}}, \cdots$ ,

ou seja, $c_0 = [a_0], c_1 = [a_0; a_1], c_2 = [a_0; a_1, a_2], \cdots, c_n = [a_0; a_1, a_2, \cdots, a_n], \cdots$

Retirado: http://pt.wikipedia.org/wiki/Fra%C3%A7%C3%A3o_cont%C3%ADnua

Vamos denotar cada $c_i por \dfrac{p_i}{q_i}$

$c_0$ = $a_0$. Logo, $p_0 = a_0$ e $q_0 = 1$

$c_1$ = $a_0 + \dfrac{1}{a_1}$ = $\dfrac{a_0a_1 + 1}{a_1}$. Logo, $p_1 = a_0a_1 + 1$ e $q_1 = a_1$

$c_2$ = $a_0 + \cfrac{1}{ a_1 + \cfrac{1}{a_2}}$ = $\displaystyle \dfrac{a_0a_1a_2 + a_2 + a_0}{a_1a_2 + 1}$ =
$\dfrac{a_2(a_0a_1 + 1) + a_0}{a_1a_2 + 1}$ = $\dfrac{a_2p_1 + p_0}{q_1a_2 + q_0}$

Teorema: Seja $c_i = \dfrac{p_i}{q_i}$ a i-ésima fração parcial da fração contínua $[a_0,a_1,\ldots,a_n]$. Então o numerador $p_i$ e o denominador $q_i$ de $c_i$ satisfazem as seguintes relações: $p_i = a_ip_{i-1} + p_{i-2}$, $q_i = a_iq_{i-1} + q_{i-2}$, para i=2,3,$\ldots$,n sendo que $p_0 = a_0$, $q_0=1$, $p_1 = a_0a_1 + 1$ e $q_1 = a_1$

1/1
1.000000000000000000
3/2
1.500000000000000000
7/5
1.399999999999999911
17/12
1.416666666666666741
41/29
1.413793103448275801
99/70
1.414285714285714368
239/169
1.414201183431952558
577/408
1.414215686274509887
1393/985
1.414213197969543145
3363/2378
1.414213624894869570
8119/5741
1.414213551646054778
19601/13860
1.414213564213564256
47321/33461
1.414213562057320406
114243/80782
1.414213562427273363
275807/195025
1.414213562363799470
665857/470832
1.414213562374689870
1607521/1136689
1.414213562372821364
3880899/2744210
1.414213562373141997
9369319/6625109
1.414213562373086930
22619537/15994428
1.414213562373096478
54608393/38613965
1.414213562373094701
131836323/93222358
1.414213562373095145
318281039/225058681
1.414213562373095145
768398401/543339720
1.414213562373095145
1855077841/1311738121
1.414213562373095145
4478554083/3166815962
1.414213562373095145
10812186007/7645370045
1.414213562373095145
26102926097/18457556052
1.414213562373095145
63018038201/44560482149
1.414213562373095145
152139002499/107578520350
1.414213562373095145
367296043199/259717522849
1.414213562373095145
886731088897/627013566048
1.414213562373095145
2140758220993/1513744654945
1.414213562373095145
5168247530883/3654502875938
1.414213562373095145
12477253282759/8822750406821
1.414213562373095145
30122754096401/21300003689580
1.414213562373095145
72722761475561/51422757785981
1.414213562373095145
175568277047523/124145519261542
1.414213562373095145
423859315570607/299713796309065
1.414213562373095145
1023286908188737/723573111879672
1.414213562373095145
2470433131948081/1746860020068409
1.414213562373095145
5964153172084899/4217293152016490
1.414213562373095145
14398739476117879/10181446324101389
1.414213562373095145
34761632124320657/24580185800219268
1.414213562373095145
83922003724759193/59341817924539925
1.414213562373095145
202605639573839043/143263821649299118
1.414213562373095145
489133282872437279/345869461223138161
1.414213562373095145
1180872205318713601/835002744095575440
1.414213562373095145
2850877693509864481/2015874949414289041
1.414213562373095145
6882627592338442563/4866752642924153522
1.414213562373095145

quinta-feira, 6 de junho de 2013

Frações contínuas

Uma fração contínua é uma expressão obtida a partir de um processo iterativo para representação de um número como a soma de sua parte inteira mais o inverso da sua parte fracionária. O processo termina quando o número não tem uma parte fracionária. Note que este processo pode ser utilizado para representação dos números racionais e irracionais.

Considere o seguinte exemplo:
$\dfrac{415}{93}$ = 4 + $\dfrac{43}{93}$ = 4 + $\dfrac{1}{\frac{93}{43}}$
$\dfrac{93}{43}$ = 2 + $\dfrac{7}{43}$ = 2 + $\dfrac{1}{\frac{43}{7}}$
$\dfrac{43}{7}$ = 6 + $\dfrac{1}{7}$ = 6 + $\dfrac{1}{\frac{7}{1}}$
$\dfrac{7}{1}$ = 7 + 0

Este processo produz a seguinte expressão:
$4+\cfrac{1}{2+\cfrac{1}{6+\cfrac{1}{7}}}$

Esta expressão pode ser abreviada usando a seguinte notação
[4;2,6,7]

Saída

[4;[2;[6;[7;]]]]

A representação usando frações contínuas tem várias propriedades desejáveis:

1. A representação usando frações contínuas para um número racional é finita e somente os números racionais tem representação finita. Usando a representação decimal, alguns números tem representação finita e outros são representados por dízimas periódicas. Por exemplo,
Representação decimal
$\dfrac{4}{27} $ = 0.148148148148….
Representação usando frações contínuas:
$\dfrac{4}{27} $ = [0;6,1,3]

Sobre os problemas da representação decimal leia:
0,999... OU “COMO COLOCAR UM BLOCO QUADRADO EM UM BURACO REDONDO”

O mesmo problema acontece na representação de números reais na base 2:
http://marathoncode.blogspot.com.br/2013/01/representacao-do-ponto-flutuante-em.html

2. A representação usando frações contínuas reduzidas, ou seja, com todos os numeradores iguais a 1, é sempre única.
3. A representação usando frações contínuas de números irracionais é única.
4. A representação usando frações contínuas de alguns números irracionais parece ser menos randômica que a representação decimal. Por exemplo,

Representação decimal $\sqrt{2}$ = 1,4142135623730950488016887242097...
Representação usando frações contínuas $\sqrt{2}$ = [1;2,2,2,…]

5. A representação usando frações contínuas pode ser usada para obter aproximações bastando interromper o processo a qualquer momento.

Considere o seguinte exemplo:

Note que as seguintes propriedades são válidas:
$(\sqrt{2}+1)(\sqrt{2}-1)=1$
$(\sqrt{2}+1) = \dfrac{1}{(\sqrt{2}-1)}$

A fração contínua de $\sqrt{2}$:

$\sqrt{2}$ = 1 + ($\sqrt{2}$-1) = 1 + $\dfrac{1}{\sqrt{2}-1}$
$(\sqrt{2}+1)$ = 2 + ($\sqrt{2}$-1) = 2 + $\dfrac{1}{\sqrt{2}-1}$

O processo repete-se indefinidamente. Logo,

$\sqrt{2}$ = [1;2,2,...]

Podemos usar essa ideia para encontrar uma aproximação para $\sqrt{2}$

Saída:

1.000000000000000000
1.500000000000000000
1.399999999999999911
1.416666666666666741
1.413793103448275801
1.414285714285714368
1.414201183431952558
1.414215686274509887
1.414213197969543145
1.414213624894869570
1.414213551646054778
1.414213564213564256
1.414213562057320406
1.414213562427273363
1.414213562363799470
1.414213562374689870
1.414213562372821364
1.414213562373141997
1.414213562373086930
1.414213562373096478
1.414213562373094923
1.414213562373095145
Numero de iteracoes: 21

Alguns exemplos de representação de números irracionais usando frações contínuas:

$\sqrt{19} = [4;2,1,3,1,2,8,2,1,3,1,2,8,…]$. O padrão repete-se com período 6.
e = [2;1,2,1,1,4,1,1,6,1,1,8,…]
$\pi$ = [3;7,15,1,292,1,1,1,2,1,3,1,…].

Fonte:
http://en.wikipedia.org/wiki/Continued_fraction
http://pt.wikipedia.org/wiki/Fra%C3%A7%C3%A3o_cont%C3%ADnua

Leia também:
O uso das Frações Contínuas como tema articulador no Ensino Médio

Quem quiser se aprofundar:
http://www.sbm.org.br/docs/coloquios/SE-1.06.pdf

Você gostou da postagem? Deixe seu comentário!!

quinta-feira, 9 de maio de 2013

Torneio de Boxe

Um torneio eliminatório de boxe foi organizada. Temos 114 participantes e por isso temos 57 partidas na primeira rodada do torneio. Na segunda rodada, os 57 lutadores restantes foram emparelhado, resultando em 28 jogos, um lutador ganhou por WO (isto é, não tem que lutar nessa rodada). Os 29 lutadores restantes foram então emparelhado, e assim por diante.

(a) Quantos jogos ao todo foram necessários para determinar um vencedor do torneio?

(b) Quantos jogos seria necessário se n pessoas participaram no torneio (onde n representa um inteiro fixo, mas não especificado número)?

Vamos definir uma função F(n) que devolve o número de lutas necessárias para descobrir o vencedor do torneio com n participantes:

F(n) : número de lutas necessárias para descobrir o vencedor do torneio com n participantes.

Observe que quando o n é par então podemos realizar n/2 lutas e restaram n/2 lutadores. Quando n é impar, então podemos realizar n/2 lutas e restaram n/2 + 1 lutadores. Logo, podemos obter a seguinte recursão:

$$F(1) = 0$$
$$F(n) =
\begin{cases}
F(\frac{n}{2}) + \frac{n}{2} & \mbox{se n é par}\\
F(\frac{n}{2}+1) + \frac{n}{2} & \mbox{se n é ímpar}\\
\end{cases}
$$

Testando alguns casos da recursão acima, podemos notar que F(n) = n-1, uma vez que, cada luta elimina um lutador e precisamos eliminar n-1 lutadores para encontrar o vencedor do torneio.

Podemos provar este fato resolvendo a recorrência acima:

Suponha n = $2^k$. Logo, podemos escrever a recorrência da seguinte maneira: $$F(2^0) = 0$$
$$F(2^k) = F(2^{k-1}) + 2^{k-1}$$
Utilizando o método da substituição: $$ F(2^k) = F(2^{k-1}) + 2^{k-1} \\ F(2^{k-1}) = F(2^{k-2}) + 2^{k-2} \\ F(2^{k-2}) = F(2^{k-3}) + 2^{k-3} \\ \vdots \\ F(2^{1}) = F(2^{0}) + 2^{0} \\ $$ Somando tudo temos: $$ F(2^k) = F(2^{0}) + 2^{0} + 2^{1} + 2^{2} + \ldots + 2^{k-1} \\ F(2^k) = 2^{k} - 1\\ $$ Desfazendo a substituição, temos: $$ F(n) = n - 1\\ $$

quarta-feira, 8 de maio de 2013

Desafio Semanal

Professor Ricardo tem n chips supostamente idênticos que, em princípio, são capazes de testar uns aos outros. Um testador do professor acomoda dois chips ao mesmo tempo. Quando os chips são carregados, cada chip testa o outro e relata se é bom ou ruim. Um bom chip de sempre relata com precisão se o outro chip é bom ou ruim, mas a resposta de um mau chip não pode ser confiável. Assim, os quatro possíveis resultados de um teste são como se segue:

Chip A	Chip B	Conclusão
B é bom	A é bom	ambos são bons, ou ambos são ruins
B é bom	A é ruim	pelo menos um é ruim
B é ruim	A é bom	pelo menos um é ruim
B é ruim	A é ruim	pelo menos um é ruim

a. Mostre que, se mais de n / 2 chips são ruins, o professor pode não determina necessariamente quem são os bons chips usando qualquer estratégia com base neste tipo de teste emparelhado. Suponha que os maus chips podem conspirar para enganar o professor.

b. Considere o problema de encontrar um único chip de bom entre n chips, supondo que o mais que n / 2 dos chips são bons. Mostre que ⎣ n / 2 ⎦ testes de pares são suficientes para reduzir o problema para aproximadamente a metade do tamanho.

c. Mostre que os bons chips podem ser identificados com Θ (n) testes emparelhados, assumindo que mais que n / 2 dos chips são bons. Dê e resolva a recorrência que descreve o número de testes.

segunda-feira, 29 de abril de 2013

Problemas legais resolvidos usando recursão

Not so mobile

http://uva.onlinejudge.org/external/8/839.html

Chocolate

http://uva.onlinejudge.org/external/109/10970.html

Investimento em ações

http://br.spoj.com/problems/ACOES1MG/

Coconut

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=557%7C

Brick Wall Patterns

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=841

Cola

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2091

Tri Triling

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1859

The Coco-Cola Store

http://uva.onlinejudge.org/index.php?option=onlinejudge&Itemid=8&category=226&page=show_problem&problem=2999

Moliu Number Generator

http://uva.onlinejudge.org/external/115/11567.html

segunda-feira, 22 de abril de 2013

Funções recursivas

O entendimento e a utilização de funções recursivas é uma grande arma para resolver vários tipos de problemas. Entre os problemas que são mais fáceis serem resolvidos usando métodos recursivos estão os problemas de contagem. Em alguns casos, o próprio processo que precisamos contar é descrito de maneira recursiva.

Em geral, os algoritmos recursivos são mais fáceis de serem entendidos e mais fáceis de provar a corretude dos mesmos.

Considere o seguinte problema Cola:

A cada três garrafas devolvidas vazias de Choco Cola, ganhe um nova garrafa de Choco Cola.

Se você comprar N garrafas de Choco Cola na loja, quantos refrigerantes você vai conseguir realizando todas as trocas possíveis?

Seja T(n) o número de refrigerante que você pode conseguir realizando todas as trocas possíveis.

Recorrência dada pelo professor Fábio Carlos.

$$T(n) = \begin{cases}n & n < 3 \\ 3 + T(n-3+1) & \text{caso contrário,} \end{cases}$$

Observe que a cada três refrigerantes, ele ganha um novo refrigerante. Teste

Podemos acelerar a recorrência acima da seguinte maneira:

$$T(n) = \begin{cases}n & n < 3 \\ 3* \lfloor n/3 \rfloor + T(n - 3 \lfloor n/3 \rfloor + \lfloor n/3 \rfloor) & \text{caso contrário,} \end{cases}$$

Esta solução é equivalente a solução dada pelo aluno Alexsandro Oliveira.

$$T(n) = \begin{cases}n & n < 3 \\ n - n \text{ mod } 3 + T(n \text{ mod } 3 + \lfloor n/3 \rfloor ) & \text{caso contrário,} \end{cases}$$

Esta outra recorrência também resolve o mesmo problema:

$$T(n,m) = \begin{cases}n & n+m < 3 \\ n + T( \lfloor (n+m)/3 \rfloor , (n+m) \text{ mod } 3 ) & \text{caso contrário,} \end{cases}$$

segunda-feira, 1 de abril de 2013

GEMP Quixadá

O grupo de estudos da Maratona de Quixadá (GEMP-UFC Quixadá) que foi criado em 2009 pelo professor Wladimir Araújo Tavares.

Atualmente, o grupo conta com uma página:
http://lia.ufc.br/~wladimir/gemp/index.html

Além dessa página, o grupo mantém um site com um boa quantidade de material de apoio:
https://sites.google.com/site/quixadamaratona/

O grupo também desenvolve uma ferramenta para classificar os problemas do spoj:
http://classificadorspoj.appspot.com/

Acesse também o wiki do GEMP - UFC Fortaleza
http://lia.ufc.br/~gemp/Main/HomePage

Na seção Problemas do wiki do GEMP - UFC Fortaleza, você poderá encontrar dicas de como resolver alguns problemas resolvidos pelos membros do GEMP-UFC Fortaleza.
http://lia.ufc.br/~gemp/Problemas/Problemas

terça-feira, 26 de março de 2013

Usando a Busca Binária - Ensinando a pescar

Considere o seguinte problema retirado sessão de prática da Internacional Olympiad in Informatics 2007 em Zagreb na Croácia.

O problema a seguir é um ótimo exemplo da aplicação da busca binária.

PEIXES

Em um pequeno país costeiro, todas as cidades estão situadas em uma longa faixa costeira (que vai ser modelada como uma linha reta). Uma estrada longa corre ao longo da costa, que liga as cidades. A posição de cada cidade pode ser descrita por um número inteiro não negativo único representando a distância (em km) a partir do início da estrada. A maioria dos cidadãos são pescadores, e eles pegam grandes quantidades de peixe. Após a temporada de pesca terminar e antes da alta temporada começar, os peixes podem ser transportados entre diferentes cidades. Uma cidade pode acomodar X turistas se tem toneladas de peixes X disponíveis. O objetivo é para acomodar o maior número possível de turistas igualmente em cada cidade. Em outras palavras, queremos encontrar o maior número inteiro Y para o qual é possível distribuir os peixes de modo a que cada cidade pode acomodar, pelo menos, Y turistas. Em uma transferência, um número inteiro de toneladas de peixes é enviado de uma cidade para outra. Durante o transporte, uma tonelada de peixe por quilômetro percorrido é perdido para saqueadores famintos que descem das montanhas. Mais formalmente, se a navios cidade F toneladas de peixe para outra cidade que é D quilômetros de distância, em seguida, toneladas FD vai chegar o destino, se F é inferior a D, então, toda a carga é perdida. É possível arbitrariamente reembalar e combinar envios em cidades intermediárias. Por exemplo, podemos enviar embarques de cidades A e B para a cidade C, combinar a metade do peixe restante de ambos os embarques com os peixes originários em C e enviá-lo em uma única remessa grande de cidade C para a cidade D.

TAREFA

Escreva um programa que, dadas as posições de todas as cidades e da quantidade de peixe de cada cidade produz, determina o maior número de turistas que podem ser acomodados em cada cidade depois que o peixe foi distribuído.

A primeira linha da entrada contém um inteiro N, 1 ≤ N ≤ 100 000, o número de cidades.

ENTRADA

Cada uma das N linhas seguintes contém dois inteiros P e F, 0 ≤ P, F ≤ 1012, a posição de uma cidade (em km) e da quantidade de peixe que produz (em toneladas). As cidades serão classificadas em ordem crescente de posição.

As posições de todas as cidades sejam distintas.

SAÍDA

A primeira linha de saída e apenas deve conter a maior quantidade de turistas Y a partir da descrição de tarefas.

Entrada

1 0

2 21

4 0

Saída

input

5 70

15 100

1200 20

output

input

20 300

40 400

340 700

360 600

output

415

Primeiramente, precisamos fazer algumas observações

Um algoritmo guloso pode ser usado para descobrir se é possível acomodar X turistas em cada cidade. Podemos considerar as cidades da esquerda para a direita. Se uma cidade tem mais X unidades de peixes, então ela pode enviar o excedente para a cidade da direita. Se a cidade tem menos que X unidades, ela deve receber o que falta da cidade da esquerda.

1. Se um valor de turista X é possível então X-1 também é um valor possível. Por outro lado, se X não é possível então X+1 também não é possível. Logo, podemos usar uma busca binária para encontrar o maior valor X possível. A complexidade do algoritmo será O(N LG MAX), onde MAX é um limite superior para a solução do problema. Um bom limite superior seria a soma de toda produção de peixes divididos pelo número de cidades.

quarta-feira, 20 de março de 2013

Escalonamento de intervalos com pesos

Cada tarefa j tem um início $s_j$ e um fim $f_j$ e tem um peso ou valor $v_j$.
Duas tarefas são compatíveis se elas não se sobrepõem
Meta: encontrar o subconjunto de tarefas mutuamente compatíveis com maior peso.

Figura retirada dos slides http://www.cs.washington.edu/education/courses/cse417/08wi/notes/11-dp-sched-complete.pdf

O algoritmo guloso funciona para esse problema quando todas as tarefas tem o mesmo peso.

1. Ordene as tarefas em ordem crescente de tempo final.

2. Adicione um tarefa no subconjunto construído se ela é compatível quando as tarefas previamente escolhidas. Note que para executar este passo basta comparar o início da tarefa com o final da última tarefa escolhida.

Note que esta estratégia não funciona quando os pesos não são iguais.

O algoritmo guloso falha quando ordenamos por tempo final ou ordenamos por peso.

Contra-exemplo 1: ordenando por tempo final

Contra-exemplo 2: ordenando por peso

Programação Dinâmica

Ordene as tarefas pode ordem de tempo final: $f_1$,$f_2$,$f_3$,....

Defina p(j) = maior indíce i < j tal que a tarefa i é compatível com a tarefa j.

typedef struct{
  int s,f,w;
} tarefa;

tarefa t[MAXN];
int p[MAXN];

int order_by_finish(const void *a, const void *b){
  tarefa pa,pb;

  pa = *(tarefa *)a;
  pb = *(tarefa *)b;

  return pa.f - pb.f;
}

Agora, vamos decompor o problema definindo uma estrutura recursiva. A forma de decompor será chamada de escolha binária. A escolha binária também é utilizada no problema da mochila.

OPT(j) = valor da solução ótima do problema consistindo das tarefas 1,2,..,j.

Note que temos que avaliar dois casos:

• Se a tarefa j é escolhida então não podemos usar nenhuma tarefa que incompatível com j. Logo, p(j) entra em acão. As tarefas {p(j)+1,...,j-1} serão descartadas, o problema fica:

OPT(j) = OPT(p(j)) + v(j)

• Se a tarefa j não é escolhida então o problema é reduzido para

OPT(j) = OPT(j-1).

Logo, a solução é dada por

OPT(j) = max(OPT(p(j)) + v(j), OPT(j-1)).

Main


t[0].s = 0;
t[0].f = 0;
t[0].w = 0;

for(i=1;i<=n;i++)
   scanf("%d %d %d",&t[i].s,&t[i].f,&t[i].w);

qsort(t,n+1,sizeof(tarefa), order_by_finish);

for(i=1;i<=n;i++){
   p[i] = 0;
   for(j=i-1;j>=1;j--){
      if(t[j].f <= t[i].s){
          p[i] = j;
          break;
      }
   }
}

opt[0] = 0;
for(j=1;j<=n;j++){
  opt[j] = max(opt[j-1], opt[ p[j]] + t[j].w);     
}
printf("%d\n",opt[n]);

SPOJ:

http://www.spoj.com/problems/RENT/

Referência:

http://www.cs.washington.edu/education/courses/cse417/08wi/notes/11-dp-sched-complete.pdf

Problema da Maioria

Como determinar se algum candidato recebeu mais de 50% dos votos em tempo linear. Esse problema é conhecido como problema da maioria. Formalmente,

Dada uma sequência de n elementos onde cada elemento é um inteiro x $\in$ [1..k] devolva o elemento majoritário, ou seja, o elemento que aparece mais do que $\frac{n}{2}$ ou zero se nenhum elemento é encontrado.

Algoritmo baseado em contagem

int MajorityCount(int v[], int n, int k){
  int c[k];
  int i;
  for(i=0;i<k;i++) c[i] = 0;
  for(i=0;i<n;i++) c[v[i]]++;
  for(i=0;i<k;i++)
    if(c[i] > n/2 ) return i;
  return 0;
}

Complexidade de tempo O(n+k)
Complexidade de espaço extra O(k)

Algoritmo baseado em comparações

Força Bruta

int MajorityBrute(int v[], int n)
{
  int i;
  for(i=0; i< n; i++)
  {
    int count = 1;
    int item = v[i];
    int j;
    for(j=i+1; j <= n; j++)
    {
      if (v[j] == item) count++; }
      if (count > n/2) return item;
    }
    return 0;
}

Complexidade de tempo O($n^2$)
Complexidade de espaço extra O(1)

Divisão e Conquista

int Count(int v[], int lo, int hi, int x){
  int k;
  int cont = 0;
  for(k=lo;k<=hi;k++)
    if(v[k]==x) cont++;
  return cont;
}

int MajorityDivideConquer(int v[], int lo, int hi)
{
  if (lo > hi) return 0; // empty sequence case
  else if (lo == hi) return v[lo]; // one-element sequence case
  else // general case
  {
    int mid = lo + (hi-lo)/2; // integer division
    int x = MajorityDivideConquer(v,lo,mid);
    int y = MajorityDivideConquer(v,mid+1,hi);
    if (x==y) return x; // x and y are both zero or both majority
    if (x > 0) // x is a majority in 1st half
    if ( Count(v,lo, hi,x) > (hi-lo+1)/2 ) return x;
    if (y > 0) // y is a majority in 2nd half
    if ( Count(v,lo, hi,y) > (hi-lo+1)/2 ) return y;
    return 0;
  }
}

Complexidade de tempo

C(n) = C(n/2) + C(n−n/2) + 2n
C(0) = C(1) = 0

Simplificando para C(n)=2C(n/2)+2n

Complexidade de tempo O(n lg n)

Moore’s Voting Algorithm

int MajorityLinearMoore(int v[], int n){
     int maj_index = 0;
     int count = 1;
     int i;
     for (i = 1; i < n; i++ ){
      if (v[maj_index] == v[i]) count++;
      else count--;
      if (count == 0){
        maj_index = i;
        count = 1;
      }
     }
    if( Count(v, 0, n-1, v[maj_index]) > n/2 )
      return v[maj_index];
    else
      return 0;
}

A corretude deste algoritmo é baseado nas seguintes observações:

se v[1..n] tem um valor majoritário e se A[n-1] $\neq$ A[n] então A[1..n-2] também tem um valor majoritário. A mesma observação vale para quaisquer dois elementos do vetor: se A[i] $\neq$ A[j] e A tem um valor majoritário então o vetor que se obtém pela eliminação das posições i e j também tem um valor majoritário. Observe que quando o valor count == 0, o algoritmo recomeça. Isso quer dizer que todos os valores anteriores podem ser eliminados.
Para qualquer k $\in$ [1..n], se x é majoritário de A[1..n] se somente se x é majoritário em A[1..k-1] ou A[k..n] ou em ambos.

Complexidade de tempo O(n)

Problema SPOJ
http://www.spoj.com/problems/MAJORITY/
http://www.spoj.com/problems/MAJOR/

Referências:
Majority Element : http://www.geeksforgeeks.org/majority-element/
Minicurso de Análise de Algoritmos http://www.ime.usp.br/~pf/livrinho-AA/

segunda-feira, 26 de agosto de 2013

17 equations that changed the course of humanity http://www.thejournal.ie/equations-changed-course-of-humanity-764429-Jan2013/?utm_source=shortlink

segunda-feira, 5 de agosto de 2013