Blog

Mais sobre a Índia

Então, mais alguns fatos curiosos:

– As pessoas realmente comem com a mão aqui… é meio esquisito. E depois eles lavam e tal, mas sem sabão. Nem tem talheres, só uma colher. Guardanapos então… nem sinal.
– Eles têm um hábito de virar a cabeça meio esquisito… não é um “sim” nem um “não”. No começo achei que fosse um sinal de impaciência, mas depois percebi que é assim mesmo que eles conversam uns com os outros.
– Os vasos sanitários são mais altos que o normal…
– A empresa é de TI mas não tem internet sem fio em lugar algum!
– Tive três refeições hoje. Nas três saí com os olhos lacrimejando de tanta pimenta o.O (inclusive o café da manhã)

No mais, a empresa é bem legal. Tem duas academias super bem equipadas e aulas de yoga e alongamento. Tem um monte de praça de alimentação com restaurantes diferentes, um mercadinho, loja de celular, banco e tudo mais. Tem quadra de basquete, campo de golfe e piscina =D

Sobre a Índia – primeiras impressões

Bom, estou no país a aproximadamente 2 horas e acho que já posso dizer que uma característica geral aqui é a falta de orgazinação (o que vai ser um problema enorme pra mim). Começando pela fila da imigração, que eles fizeram um esquema que pra mim não fez o menor sentido… Colocaram todo mundo (todo mundo mesmo, imigrante, indiano, idosos, mulheres com crianças de colo) numa fila gigante. E lá na frente tinha entre 5 e dez guichês funcionando. Ao invés de cada guichê chamar o primeiro da fila única, essa fila foi dividida em uma fila individual pra cada guichê. Na frente de todo mundo tinha uma mulherzinha que decidia pra qual fila de qual guichê vc ia baseando, aparentemente, no tamanho da fila ¬¬ Não era dividido por fila de família, de crianças, de indianos ou entrangeiros. Ela redistribuia as pessoas ao seu bel-prazer… Vai entender.

Bom, aí o cara me pegou de taxi e tal (tava com meu nome lá no papelzinho e tudo, olha que chic!) e gentilmente deixou eu levar minhas malas sozinha até o estacionamento do aeroporto. Minha malinha básica de 32 kgs que veio com uma etiqueta amarela da companhia aérea escrito “HEAVY”. Enfim, durante o passeio de taxi (que demorou +- 1 hr) deu pra entender como funciona o trânsito aqui. Algumas coisas cusiosas:

– Aqui é mão inglesa. O contrário da gente.
– A buzina é o que tem de mais importante no seu carro. Seta? Retrovisor? A maioria dos carros nem tem o retrovisor esquerdo. Mas a buzina é imprescindível. É utilizada pra avisar que tá passando, avisar que vai mudar de pista, avisar que tá indo e nao vai frear pro cara da frente, avisar pro outro cara que não vai deixar ele entrar na sua pista, enfim, pra quase tudo. E quem buzinar por mais tempo ganha a preferência (se não ganhar a gente invade a contra-mão). E por causa disso os motoristas ficam treinando a buzina mesmo quando não tem absolutamente ninguém perto do carro.
– O conceito de faixa simplesmente não existe. Três faixas viram cinco ou até seis. O que couber.
– Se apertar cabe mais gente. Os carros passam super colados uns nos outros, e ninguém pára, só no último segundo antes de bater.
– Vc pode virar em praticamente qualquer rua que quiser, de qualquer local que vc estiver. Se a rua der mão, é só atravessar a avenida de 5 pistas.

Pelo menos eu cheguei aqui na empresa e parece ser diferente. Tinham meu quarto reservado, já tenho crachá com foto e tudo mais. Igual gente grande.

Agora to morta… Vou ver se tomo um banho pra não dormir. São 5 da manhã no Brasil e eu passei uma noite dormindo no avião =/

Sobre o módulo da divisão de números grandes

Motivado pelo seguinte problema: https://br.spoj.pl/problems/DIOFANTO/

Então, eu li esse problema e bolei uma solução toda bonitinha pra ele usando combinatória. Só tava faltando implementar e eu mal sabia que era isso que ia me causar toda a dor de cabeça.

Eu estou implementando um algoritmo e em certo ponto preciso fazer a seguinte conta:

(a!/b!) mod p

Em que a e b são números cujo fatorial não cabe em uma variável, p é um primo e p é maior que a e b. Como proceder?

Obviamente não posso calcular o fatorial antes, fazer a divisão e depois tirar o módulo. Mesmo um algoritmo que tenta ir simplificando a fração à medida que o fatorial é calculado não funciona. E o módulo do quociente não é o quociente dos módulos (Não acredita? Teste com p = 7, a = 5 e b = 3).

O que fazer então? Bom, as seguintes propriedades vão ajudar:

a.b (mod p) = (a mod p)(b mod p) mod p
a / b = a.b-1

a-1 (mod p) existe se mmc(a, p) = 1

Agora a gente pode usar essas coisas pra fazer o seguinte:

(a/b) mod p = ab-1 mod p = (a mod p)(b-1 mod p) mod p

Por sorte (?) b e p são primos entre si, já que p é primo e b é menor que p, e podemos calcular o módulo do seu inverso. Pra fazer isso, tem que desenvolver a equação (eu quero encontrar o x):

b-1 = x (mod p)
b-1b = xb (mod p)
xb = 1 (mod p)
xb – 1= qp
xb – qp = 1 
Então tudo se resume a encontrar o x e q que resolvem a última expressão. Isso pode ser feito com o algoritmo estendido de Euclides.
Acho que já escrevi demais… vou tentar implementar isso agora.

Método dos mínimos quadrados

Ainda sobre a prova de 2004 da seletiva da USP, agora no problema F: Estimando a Produção.

Se eu soubesse o que era o método dos mínimos quadrados antes de ler o problema eu ia ver isso e pensar “óbvio!”. Fazendo uma analogia, seria como um problema que possa ser resolvido com Dijkstra ser descrito por um grafo e pedindo o menor caminho a partir de um vértice para todos. Enfim… faltaram algumas aulas de matemática aí.

O problema é descaradamente a aplicação do método dos mínimos quadrados. Eu li isso, entendi a modelagem e tal, mas como resolver isso computacionalmente?? Não é trivial =/
Nesse link tem alguns métodos numéricos que mostram como fazer, mas sem pseudo-código nem nada… e pra mim que não conheço esses algoritmos fica difícil.

Em algum outro lugar vi que podia ser resolvido com o método de Newton ou algoritmo de Gauss-Newton, mas não olhei os detalhes deles ainda.

Largest Empty Circle

Sobre o problema I, da prova de 2004 da seletiva interna para a maratona de programação da USP, chamado Centro de Convenções.

Esse problema é um caso especial do “largest empty circle”, descrito aqui. Para resolver esse problema acho que tem que ser feito o seguinte:

Primeiro vc tem que gerar o diagrama de Voronoi do seu plano. Suponha que seu plano seja formado por um conjunto de n pontos: p1, p2, …, pn. Esse diagrama é uma divisão do plano em regiões de maneira que as arestas dessas regiões são formadas por pontos equidistantes de pi e pj. Cada vértice da região é um ponto equidistante de três ou mais pontos. Portanto, em cada região só existe um ponto pi, e aquela região contém todos os pontos que são mais próximos de pi do que de qualquer outro do plano.

Um diagrama de Voronoi pode ser construído com o algoritmo de Fortune (não achei trivial, por isso não implementei esse algoritmo =/ ).

Dado que a região foi construída, a maior circunferência que não contém nenhum pi terá o centro localizado em um dos vértices desse diagrama. Logo, basta percorrer a lista de vértices e verificar qual é a distância para os três (ou mais) pontos que definiram esse vértice.

A construção do diagrama é feita em O(n log n), o que é maior que o custo linear de percorrer os vértices para encontrar o centro do círculo procurado, logo, essa é a complexidade do algoritmo.

Texto

No meio da avalanche de mensagens sentimentais que eu recebo pela internet, algumas valem a pena… E essa é uma delas. Procurei pela autora e o blog dela é esse aqui. Não olhei muito bem o que tem por lá ainda, esse texto com certeza não foi publicado nesse blog. Mas enfim, com autoria certa ou não, a mensagem é bacana, e é o jeito que eu quero viver minha vida (talvez exceto pelo vinho do porto =P ).

Da minha precoce nostalgia
Maria Sanz Martins

Quando eu for bem velhinha, espero receber a graça de, num dia de domingo, me sentar na poltrona da biblioteca e, bebendo um cálice de vinho do Porto, dizer a minha neta:
– Querida, venha cá. Feche a porta com cuidado e sente-se aqui ao meu lado. Tenho umas coisas pra te contar.
E assim, dizer apontando o indicador para o alto:
– O nome disso não é conselho, isso se chama corroboração!
Eu vivi, ensinei, aprendi, caí, levantei e cheguei a algumas conclusões. E agora, do alto dos meus 82 anos, com os ossos frágeis, a pele mole e os cabelos brancos, minha alma é o que me resta saudável e forte. Por isso, vou colocar mais ou menos assim:
É preciso coragem para ser feliz. Seja valente. Siga sempre seu coração. Para onde ele for, seu sangue, suas veias e seus olhos também irão. E satisfaça seus desejos. Esse é seu direito e obrigação. Entenda que o tempo é um paciente professor que irá te fazer crescer, mas a escolha entre ser uma grande menina ou uma menina grande, vai depender só de você. Tenha poucos e bons amigos. Tenha filhos. Tenha um jardim. Aproveite sua casa, mas viaje, vá a Fernando de Noronha, Rio de Janeiro, a Barcelona e a Austrália. Cuide bem dos seus dentes. Experimente, mude, corte os cabelos. Ame. Ame pra valer, mesmo que ele seja o carteiro. Não corra o risco de envelhecer dizendo “ah, se eu tivesse feito…” Tenha uma vida rica de vida. Vai que o carteiro ganhe na loteria – tudo é possível, e o futuro é imprevisível.
Viva romances de cinema, contos de fada e casos de novela. Faça sexo, mas não sinta vergonha de preferir fazer amor.

E tome conta sempre da sua reputação, ela é um bem inestimável. Porque sim, as pessoas comentam, reparam, e se você der chance elas inventam também detalhes desnecessários.
Se for se casar, faça por amor. Não faça por segurança, carinho ou status.
A sabedoria convencional recomenda que você se case com alguém parecido com você, mas isso pode ser um saco! Prefira a recomendação da natureza, que com a justificativa de aperfeiçoar os genes na reprodução, sugere que você procure alguém diferente de você. Mas para ter sucesso nessa questão, acredite no olfato e desconfie da visão. É o seu nariz quem diz a verdade quando o assunto é paixão.
Faça do fogão, do pente, da caneta, do papel e do armário, seus instrumentos de criação. Leia. Pinte, desenhe, escreva. E por favor, dance, dance, dance até o fim, se não por você, faça-o por mim.
Compreenda seus pais. Eles te amam para além da sua imaginação, sempre fizeram o melhor que puderam, e sempre farão.
Cultive os amigos. Eles são a natureza a nosso favor e uma das formas mais raras de amor.
Não cultive as mágoas – porque se tem uma coisa que eu aprendi nessa vida é que um único pontinho preto num oceano branco deixa tudo cinza.
Era só isso minha querida. Agora é a sua vez. Por favor, encha mais uma vez minha taça e me conte: como vai você?

Sobre equações diofantinas

Motivado pelo seguinte problema: http://ipsc.ksp.sk/contests/ipsc2010/real/problems/d.php

A minha modelagem pra esse problema chegou em uma quatro equações do tipo:
ax + by = c

No final das contas eu tinha que saber se essa equação tinha solução pra decidir quem ganhava a luta: o príncipe ou o dragão. E então? Como eu sei se uma equação dessa tem soluções inteiras?
Acontece que essa é uma equação diofantina linear, e ela só tem solução se c é o mdc(a, b) ou múltiplo do mdc(a, b). Bom resultado pra se lembrar.

Sobre grafos bipartidos

Uma rede de computadores pode ser facilmente representada por um grafo, no qual cada máquina representa um vértice e arestas são conexões entre essas máquinas. Nesse grafo, cada vértice possui um label que seria o endereço da máquina na rede. Mas esses labels podem ser mais que endereços, eles podem refletir diretamente a distância entre os vértices (máquinas). Em uma rede cujo endereçamento segue essa regra, o roteamento de pacotes pode ser feito de maneira ótima analisando somente informações locais (incrível, hein?? =P ). Basta fazer o seguinte: um pacote sabe sempre seu endereço de destino, quando ele alcança um vértice ele compara esse endereço com os vizinhos desse vértice e vai para o que está mais próximo do seu objetivo. Simples.

Um grafo que obviamente satisfaz essa propriedade é n-cubo. Nele, a distância entre os vértices é exatamente a distância Hamming (ou distância de edição) entre as sequências de bits atribuídas a cada vértice. Para construir uma rede dessa maneira (na qual os pacotes percorrem sempre o caminho ótimo) devemos saber que tipo de grafo pode ter seus vértices endereçados com strings de bits de modo que a distância de Hamming corresponda à distância entre os vértices no grafo.

Teorema (Djokovic – 1973):
Existe um esquema de endereçamento usando strings de binárias para os vértices de um grafo simples G tal que a distância Hamming das strings coincide com a distância dos vértices no grafo se, e somente se:
    (i) G é bipartido.
    (ii) G(a,b) é um conjunto fechado para toda aresta (a,b) em A(G).

OBS: G(a,b) = {x em V(G) | d(x,a) = d(x,b)-1}
         Um subconjunto de vértices U de V(G) é dito fechado se para todo par a,b em U: x em V(G) e d(a,x) + d(b,x) = d(a,b) então x está em U.

[1] Bipartite Graphs and their Applications (Cambridge Tracts in Mathematics) – Armen S. Asratian

Captchas

Quando eles começaram a fazer algoritmos tão bons pra decifrar os captchas?? Agora essas letrinhas estão tão complicadas que nem eu consigo acertar mais o que tá escrito =/