Vou ver se depois da minha época de exames, ou talvez um bocadinho ao fim da tarde ou à noite nestes dias, começo a tentar resolver os da USACO, mas eles parecem-me mesmo dificieis...
ETA: Tharis, já que sou um bocado newbie no que toca à USACO, podemos submeter o nosso solution file em Python?
O USACO é engraçado, não é difícil, bom para aprender mas torna-se um pouco aborrecido...
Spoj tem problemas muito engraçados mas também tem muitos ridículos, é uma questão de seleccionar
Embora já me esteja a desligar um pouco das provas da ACM, em termos de algoritmia aconselho a aprender as bases ao mesmo tempo no USACO e no Introduction to Algorithms. Depois pode-se ir ao SPOJ resolver os problemas das provas regionais da ACM. Esses já dão para pensar mas com eles é que se aprende verdadeiramente, a ir consultar e estudar para ir resolvendo.
Quanto às questões de velocidade, não são tão "inacreditáveis" como vocês dizem Naturalmente há linguagens mais rápidas mas o mais relevante é mesmo o algoritmo. Como curiosidade, vejam as optimizações do gcc ou do g++ e depois pensem se afinal o código que corre é mesmo o vosso
Por vezes é melhor escrever o código o mais simples possível e deixar as optimizações para o compilador (que assim compreende melhor o que deve fazer sem ter de cair para estados de menor optimização por causa de expressões complexas) do que tentar optimizar.
Bem, sobre compiladores muito se pode dizer, até que acabam por não respeitar a "vontade" do programador. Linguagens interpretadas não podem ter muitas dessas optimizações, c'est la vie
Ivo_Timóteo Escreveu:O USACO é engraçado, não é difícil, bom para aprender mas torna-se um pouco aborrecido...
Não concordo quando dizes que é difícil nem quando dizes que torna-se aborrecido. É difícil para quem tá a aprender, sem dúvida. E não se torna aborrecido, o nível de problemas que te colocam é que aumenta de uma maneira um pouco abrupta que podes ficar parado numa secção durante meses e noutras passares num dia.
@Bruno Oliveira, não. O USACO só aceita Pascal, C, Cpp, Java.
Ivo_Timóteo Escreveu:O USACO é engraçado, não é difícil, bom para aprender mas torna-se um pouco aborrecido...
Não concordo quando dizes que é difícil nem quando dizes que torna-se aborrecido. É difícil para quem tá a aprender, sem dúvida. E não se torna aborrecido, o nível de problemas que te colocam é que aumenta de uma maneira um pouco abrupta que podes ficar parado numa secção durante meses e noutras passares num dia.
@Bruno Oliveira, não. O USACO só aceita Pascal, C, Cpp, Java.
Eu disse que não era muito difícil mas, para mim, a certa altura torna-se aborrecido Mas o pior problema mesmo é já não estar no secundário com muito tempo E o facto de, a certa altura, amortizar NP's ter muito mais piada
Eu disse que não era muito difícil mas, para mim, a certa altura torna-se aborrecido Mas o pior problema mesmo é já não estar no secundário com muito tempo E o facto de, a certa altura, amortizar NP's ter muito mais piada
Oh, the good old days...
Um grande abraço, Ivo!
José António Paixão Departamento de Física da FCTUC
Prof, peço desculpa por reabrir este tópico, mas sempre podia dar umas dicas sobre como fazer um algoritmo para resolver este problema que corra em menos de 1 minuto?
De facto, fiquei curioso sobre este problema e gostaria de o conseguir resolver ou pelo menos perceber como se resolve
Bruno Oliveira Escreveu:Prof, peço desculpa por reabrir este tópico, mas sempre podia dar umas dicas sobre como fazer um algoritmo para resolver este problema que corra em menos de 1 minuto?
De facto, fiquei curioso sobre este problema e gostaria de o conseguir resolver ou pelo menos perceber como se resolve
Eu não sei qual é o algoritmo rápido (não pensei mais sobre o assunto) mas sei que ele existe!
Any clues da comunidade quarkiana?
José António Paixão Departamento de Física da FCTUC
Finalmente acabei de escrever uma solução decente. Primeiro, este é um problema de teoria dos números. Vou primeiro dar indicações para perceber como funciona o programa e depois vou dar uma solução que corre instantaneamente.
RN = Reversible Number
Este é um problema em que devemos usar uma approach Divide and Conquer. Neste caso podemos dividir o problema em 2 partes: calcular o número de RN com comprimento par e com comprimento ímpar.
COMPRIMENTO PAR
Convém notar um propriedade muito importante: NÃO EXISTE CARRY. Deixo a prova em SPOILER para não ocupar espaço (espero que alguém a leia porque deu um bocadinho de trabalho ).
Prova
Lema: Não existe carry na soma reversível de números de comprimento par. Prova: Seja N = abcdef, então, a soma com o reverso será: abcdef + fedcba = [a+f][b+e][c+d][d+c][e+b][f+a]
[f+a] terá de ser ímpar, uma vez que a sua paridade só depende de si próprio (não pode ser alterado por carry algum).
Será necessário apenas analisar a metade esquerda de N, uma vez que, por simetria, não pode ocorrer carry apenas na metade direita.
Analisemos dois casos: um que ocorre carry devido a [f+a], ou seja, na ponta e outro em que o carry ocorre "dentro" do número.
Para o primeiro caso, podemos verificar que [e+b] terá de ser par para que com o carry se torne ímpar. E se [e+b] é par, então [b+e] também o é e consequentemente, para que N seja um RN, [b+e] terá de receber carry de [c+d]. Para que [c+d] forneça carry, este terá de ser maior que 10 (não poderá ser 9 e a receber carry porque somaria 10 que é par). Se [c+d] >= 10, então [d+c] também o é e consequentemente também fornecerá carry ao algarismo seguinte. O algarismo seguinte é [c+d] e recebe carry, implicando que [c+d] seja par. E se [c+d] é par, [d+c] também o é implicando que também terá de receber carry de [e+b]. Se [e+b] fornece carry, então [e+b] >= 10 e portanto [b+e] também >= 10 e [a+f] receberá carry deixando de ser ímpar para passar a ser par, implicando que N não seja um RN.
Apesar de ter utilizado N com comprimento seis, isto ocorre para qualquer comprimento par, uma vez que se pode "inserir" pares de algarismos à volta dos algarismos centrais de N e o resultado será igual, uma vez que os algarismos mais "exteriores" requerão carry dos algarismos contíguos interiores até se chegar aos algarismos centrais.
O segundo caso (carry ocorre "dentro" de N) pode ser reduzido ao primeiro, uma vez que se pode "cortar" N de modo que o local onde ocorreu o carry fique como primeiro algarismo, uma vez que para a direita nunca ocorreu carry.
Conclui-se que não existe carry na soma reversível de números de comprimento par.
Este pormenor tem duas grandes implicações (uma delas é ele próprio): a soma de cada par de algarismos terá de ser menor que 10 e ímpar. Terá de ser ímpar, porque se for par, vai necessitar de um carry para se tornar ímpar e tal não acontece numa soma reversível. Para a soma ser ímpar, um deles terá de ser par e o outro ímpar.
Portanto basta pegar em todos os pares (i,j) de números menores que 10, verificar quais aqueles em que (i+j) < 10 e (i+j) % 2 == 0 e ir construíndo o nosso número reversível de dentro para fora ou de fora para dentro, tanto faz, com especial atenção que o par exterior não poderá conter qualquer 0.
COMPRIMENTO ÍMPAR
Nos de comprimento ímpar, a propriedade do carry já não se verifica. Podemos ser erradamente levados a pensar que não existem RNs com comprimento ímpar porque o algarismo do meio irá ser somado consigo próprio e 2k é sempre par para qualquer k natural. No entanto podemos encontrar rapidamente um contra-exemplo como 318 (318+813 = 1131). O que acontece é que o algarismo central recebe carry mas não fornece.
Vou resumir esta parte e apresentar a solução sem prova. Só existem RNs de comprimento ímpar quando duas condições se verificam:
O comprimento é da forma 3+4k (3,7,11,...) A sequência de pares de algarismos tem a forma (ip)u(pi), em que i é um par cuja soma é ímpar e maior que 10, p um par cuja soma é par e menor que 10 e u um número inteiro tal que 0 <= u <= 4
É relativamente fácil ver a olho porquê se "brincarem" com os números. A prova será na linha da que apresentei nos comprimentos pares.
Agora que já passámos as matematiquices, vamos ao código.
Basicamente usa-se um dfs (Depth First-Search) para gerar todos os números. Começa-se com comprimento 0 e escolhe-se um par de algarismos. Avança-se para o comprimento 2 e escolhe-se outro par de algarismos. Fazemos isto até comprimneto = d e voltamos para trás e escolhemos outro par, etc. Quem não perceber bem, veja aqui.
def make(n): " Função que forma um inteiro a partir da lista de algarismos " if n.count(None) != d: return int(''.join(map(str,filter(lambda x: x!=None, n)))) return ''
def odd_length(n, p): global t, d, l, odd_greater, even_less
# Já adicionámos d algarismos if p == d/2: return
# Forma (ip)u(pi) if p%2 == 0: algs = odd_greater else: algs = even_less
for k in algs: # Colocar o par no meio i,j = k; n[p] = i; n[-p-1] = j
# Comprimento ((p+1)*2+1 - 3) da forma 3+4k if not ((p+1)*2 - 2)%4: # > Necessário apenas para gerar os números for a in range(5): n[p+1] = a l.append(make(n)) # Encontrámos mais 5 (algarismo central 0..4) t += 5 n[p+1] = None
# Iterar por todos os pares de soma ímpar < 10 for k in odd_less[s:]: i,j = k; n[p] = i; n[-p-1] = j
t += 1; l.append(make(n))
# Próximo comprimento even_length(n, p+1)
n[p] = None; n[-p-1] = None
# Pares de soma ímpar maior que 10 odd_greater = [(i,j) for i in range(10) for j in range(10) if (i+j)%2 == 1 and (i+j)>10] # Pares de soma par menor que 10 even_less = [(i,j) for i in range(10) for j in range(10) if (i+j)%2 == 0 and (i+j)<10] # Pares de soma ímpar menor que 10 odd_less = [(i,0) for i in range(1,10,2)] + [(i,j) for i in range(10) for j in range(1,10) if (i+j)%2 == 1 and (i+j)<10]
O melhor é que eles só nos pedem o número de RNs e não os RNs em si, por isso, existe uma maneira mais fácil e rápida de calcular para qualquer comprimento.
Se considerarmos o comprimento máximo d, então o número de RNs é dado pela soma de RNs de comprimento par e de comprimento ímpar.
Podemos chegar facilmente a uma fórmula para cada usando combinatória simples.
Par:
Ímpar:
Os indicam a função floor, basicamente vai fazer o trabalho da divisão inteira.
P.S.: Não sei bem o formalismo de uma proof, algum matemático que queira corrigir está à vontade. P.S.2: Acho que existe uma forma mais simples e limpa para as fórmulas, mas não sei bem.
Sem dúvida uma solução épica!! Uma das melhores que alguma vez já li.
Vou imprimir este post, e tentar percebe-lo mesmo bem, mas achei que a solução estava absolutamente genial.
Parabéns!!
E claro, um grande obrigado por partilhares aqui a solução, porque assim, aos poucos e poucos vou aprendendo (grão a grão enche a galinha o papo não é verdade?)
projecto Quark! ~ Escola de Física para Jovens
por Bruno Oliveira em Segunda Jun 07, 2010 6:49 am 
).![20 \sum_{i=2}^{d} \left [ 30^{ \left \lfloor \frac{i-2}{2} \right \rfloor } \times (1-i \mod 2) \right ]](/phpBB3/latexrender/pictures/19671de7ad0bbe57f247ae8773d65abc.gif "20 \sum_{i=2}^{d} \left [ 30^{ \left \lfloor \frac{i-2}{2} \right \rfloor } \times (1-i \mod 2) \right ]")
![5 \sum_{i=2}^{d} \left [ 20^{ \left \lfloor \frac{i}{4} + (1-i \mod 2) \right \rfloor } \times 25^{\frac{i}{4}} \times (1 - ((i-3) \mod 4)) \right ]](/phpBB3/latexrender/pictures/7e7b7def9e25810f59bde997431f5b5e.gif "5 \sum_{i=2}^{d} \left [ 20^{ \left \lfloor \frac{i}{4} + (1-i \mod 2) \right \rfloor } \times 25^{\frac{i}{4}} \times (1 - ((i-3) \mod 4)) \right ]")
indicam a função floor, basicamente vai fazer o trabalho da divisão inteira.
