Arquivo da tag: computação

Como copiar textos da Folha e outros sites que não deixam

Alguns sites começaram a abusar de um recurso super interessante do JavaScript para acabar com uma das características mais importantes da Internet: a capacidade de copiar/colar.

O tratamento dos clipboard events (oncut, oncopy e onpaste) deveria servir para permitir que os programadores façam coisas legais quando você copia/cola um texto (por exemplo, um processador de textos online pode inserir/remover formatação), mas tenho visto cada vez mais ele ser usado para adicionar uma mensagem de copyright no final de um texto copiado, impedir usuários leigos de copiarem textos na web e evitar que se cole coisas que você copiou em formulários.

O que mais me incomoda (e que me levou a escrever esta postagem) é que, hoje, quem copia um trecho de uma reportagem da Folha (para guardar, compartilhar numa rede social ou o que quer que seja) acaba colando:

Para compartilhar esse conteúdo, por favor utilize o link http://www1.folha.uol.com.br/fsp/bla-bla-bla ou as ferramentas oferecidas na página. Textos, fotos, artes e vídeos da Folha estão protegidos pela legislação brasileira sobre direito autoral. Não reproduza o conteúdo do jornal em qualquer meio de comunicação, eletrônico ou impresso, sem autorização da Folhapress (pesquisa@folhapress.com.br). As regras têm como objetivo proteger o investimento que a Folha faz na qualidade de seu jornalismo. Se precisa copiar trecho de texto da Folha para uso privado, por favor logue-se como assinante ou cadastrado.

Não é incrível (e sintomático) que o grupo que gerencia o portal mais importante da Internet no Brasil (UOL) tenha uma concepção tão atrasada da rede? Ok, não dá nem pra dizer que isso nos surpreende depois da censura da Falha e do paywall.

Sem mais delongas: isso merece ser hackeado. Neste post, proponho algumas soluções simples para você poder voltar a copiar e colar no seu navegador como sempre fez. Minha preferida, como sempre, é a última.

Solução trivial para quem usa Linux

Antes de sugerir soluções de verdade, convém observar que quem usa Linux (X11) pode copiar selecionando um texto (sem apertar Ctrl+C ou qualquer outra combinação esdrúxula de teclas) e colar apertando o botão do meio do mouse. Quando se copia/cola dessa forma, o navegador não emite os temidos eventos oncopy/onpaste (ou seja, tudo funciona normalmente).

Rodolfo Mohr também observou que você pode copiar um texto selecionando-o, clicando com a tecla direita na seleção e em “Pesquisar no Google”. Uma aba vai abrir com a pesquisa no Google e você pode copiar o texto lá. É um hack válido, embora incômodo.

Somente Firefox: usando about:config

Se você usa Firefox, pode desabilitar os clipboard events digitando, na barra de endereços, em about:config. Talvez ele diga que é perigoso e peça para você clicar num botão dizendo que sabe o que está fazendo. Pode confiar. Em seguida, procure a chave dom.event.clipboardevents.enabled e clique duas vezes nela para mudar seu valor para false. Reiniciando o navegador, o recurso copiar/colar estará funcionando normalmente (ou talvez nem precise reiniciá-lo).

Extensões (para Firefox, Chrome e Opera)

Não tem o que explicar. Simplesmente clique no nome do seu navegador e instale: Firefox, Chrome, Opera.

Editado em 01/04/2014, 22:30: A extensão que eu havia colocado para Chrome só desabilita o tratamento de eventos onpaste em formulários. Se você conhecer alguma extensão similar a do Firefox ou a do Opera, me avise pelos comentários.

Desabilitando sob demanda via JavaScript

É muito importante ter em mente que aplicações web como processadores de texto podem usar os eventos oncut/oncopy/onpaste para coisas úteis. Por isso, é desejável desabilitar esses eventos somente em sites específicos.

Não encontrei nenhuma extensão que faça isso, mas um código simples em JavaScript para recuperar o comportamento padrão dos eventos em um determinado site (testei no Firefox e no Chrome) é:

all = document.querySelectorAll("*");
fn = function(e) {
    e.stopPropagation();
    return true;
}
for (var i = 0; i < all.length; i++) {
    all[i].oncut = fn;
    all[i].oncopy = fn;
    all[i].onpaste = fn;
}

Se digitarmos isso no console (Shift+Ctrl+J), as funções copiar/colar devem voltar a funcionar.

Userscript

A solução anterior nos permite criar um userscript para desabilitar o tratamento dos eventos apenas no site da Folha:

// ==UserScript==
// @name Permite copiar textos da Folha
// @include http://*.folha.uol.com.br/*
// ==/UserScript==
 
window.onload = function() {
    all = document.querySelectorAll("*");
    fn = function(e) {
        e.stopPropagation();
        return true;
    }
    for (var i = 0; i < all.length; i++) {
        all[i].oncut = fn;
        all[i].oncopy = fn;
        all[i].onpaste = fn;
    }
}

Portanto, se você quiser copiar do site da Folha sem preocupações (e sem desabilitar os eventos em outros sites), pode instalar as extensões GreaseMonkey (Firefox) ou TamperMonkey (Chrome), e então esse userscript clicando neste link: falha.user.js.

Bookmarlet

Acho o método acima (do userscript) o melhor para copiar da Folha. No entanto, é conveniente ter um método mais genérico. Por isso, criei um bookmarklet, isso é, um pequeno script que podemos executar clicando num botão na barra de favoritos (neste caso, para restaurar o comportamento padrão das funções copiar/colar).

Aqui está ele: Restaurar copiar/colar

Para instalar, arraste esse link para sua barra de favoritos. Para usar, clique sempre que precisar copiar um texto e então copie normalmente.

Viva a Internet!

Como ler documentos do Scribd

Depois de ouvir esse improviso do André Mehmari sobre Odeon e Choro pro Zé, fiquei com vontade de encontrar a partitura desse belo choro do Guinga. Porém, descobri que infelizmente é extremamente difícil encontrar o songbook “A música de Guinga”.

Procurando na rede, encontrei um torrent com um PDF com qualidade ruim e um documento do Scribd com qualidade boa. O problema é que o Scribd tem um paywall para não deixar as pessoas baixarem ou lerem os documentos que seus usuários colocam lá:

free-preview

Percebi que ele passa todas as imagens corretamente para o navegador e só no lado do cliente muda a opacidade das páginas para elas ficarem semitransparentes. Então escrevi um userscript bem simples (usando jQuery por comodidade) para o Greasemonkey (uma dessas extensões indispensáveis do Firefox) para recuperar a opacidade das páginas do texto e, se necessário, remover essa mensagem “You’re reading a free preview”.

// ==UserScript==
// @name Suppress Scribd Paywall
// @include http://*.scribd.com/doc/*
// @require http://code.jquery.com/jquery-2.0.3.min.js
// ==/UserScript==
 
(function($) {
    $(document).ready(function() {
        window.setInterval(function(){$(".absimg").css("opacity", "1")}, 1000);
        $(".autogen_class_views_read_show_page_blur_promo").on("click", function(e) { $(this).hide(); });
    });
})(jQuery);

Para usar, é só instalar o Greasemonkey no Firefox e depois baixar o userscript scribd.user.js. Resultado:

choro-pro-ze

Como a criptografia é uma arma fundamental na luta contra os estados do império

O que começou como um meio de manter a liberdade individual pode agora ser usado por estados menores para afastar as ambições dos maiores.

Julian Assange, The Guardian (tradução: Tiago Madeira)

Os cypherpunks originais eram em maioria libertários californianos. Eu era de uma tradição diferente, mas nós todos procurávamos proteger a liberdade individual da tirania do estado. Criptografia era nossa arma secreta. Foi esquecido quão subversivo isso era. A criptografia era então propriedade exclusiva dos estados, para utilização nas suas várias guerras. Escrevendo nosso próprio software e disseminando-o por toda parte nós libertamos a criptografia, a democratizamos e a espalhamos através das fronteiras da nova internet.

A repressão resultante, sob várias leis de “tráfico de armas”, falhou. A criptografia se tornou padronizada nos navegadores e em outros programas que as pessoas agora usam cotidianamente. Criptografia forte é uma ferramenta vital na luta contra a opressão do estado. Essa é a mensagem no meu livro, Cypherpunks. Mas o movimento pela disponibilidade universal da criptografia forte deve ser feito para fazer mais que isso. Nosso futuro não depende da liberdade de indivíduos sozinhos.

Nosso trabalho no WikiLeaks dá uma profunda compreensão da dinâmica da ordem internacional e da lógica do império. Durante a ascensão do WikiLeaks, vimos evidências de pequenos países intimidados e dominados por maiores ou infiltrados por empresas estrangeiras e influenciados para agirem contra eles mesmos. Vimos expressões da vontade popular negada, eleições compradas e vendidas, e as riquezas de países como a Quênia sendo roubadas e leiloadas a plutocratas em Londres e Nova Iorque.

A luta pela autodeterminação latinoamericana é importante para muito mais pessoas do que as que vivem na América Latina, porque ela mostra ao resto do mundo que isso pode ser feito. Mas a independência da América Latina ainda está engatinhando. Tentativas de subversão de democracia latinoamericana ainda estão acontecendo, incluindo mais recentemente Honduras, Haiti, Equador e Venezuela.

Por isso a mensagem dos cypherpunks é de especial importância para audiências latinoamericanas. A vigilância em massa não é uma questão somente para a democracia e a governabilidade — é uma questão geopolítica. A vigilância de uma população inteira por uma potência estrangeira naturalmente ameaça a soberania. Intervenção após intervenção nos assuntos da democracia latinoamericana nos ensinaram a sermos realistas. Nós sabemos que as velhas potências ainda vão explorar qualquer vantagem para atrasar ou suprimir a eclosão da independência da América Latina.

Considere geografia simples. Todo mundo sabe que os recursos do petróleo dirigem a geopolítica global. O fluxo de petróleo determina quem é dominante, quem é invadido e quem está condenado ao ostracismo por parte da comunidade global. Controle físico mesmo sobre um segmento de um oleoduto produz uma grande potência geopolítica. Governos nessa posição podem extrair enormes concessões. Numa tacada, o Kremlin pode sentenciar a Europa oriental e a Alemanha a um inverno sem aquecimento. E mesmo a perspectiva do Tehran controlar um oleoduto ao leste para Índia e China é um pretexto para a lógica bélica de Washington.

Porém, o novo grande jogo não é a guerra por tubulações de petróleo. É a guerra por tubulações de informação: o controle sobre os caminhos de cabos de fibra óptica que se espalham por via submarina e terrestre. O novo tesouro global é o controle sobre os fluxos de dados gigantes que conectam continentes e civilizações inteiras, ligando as comunicações de bilhões de pessoas e organizações.

Não é segredo que, na internet e no telefone, todas as estradas que saem e chegam na América Latina passam pelos Estados Unidos. A infraestrutura da Internet direciona 99% do tráfego para e da América do Sul sobre cabos de fibra óptica que atravessam fisicamente as fronteiras dos EUA. O governo dos EUA não mostrou nenhum escrúpulo sobre quebrar a sua própria lei ao explorar esses cabos e espionar seus próprios cidadãos. Não existem tais leis contra espionar cidadãos estrangeiros. Todos os dias, centenas de milhões de mensagens de todo o continente latinoamericano são devoradas por agências de espionagem estadounidenses, e guardadas para sempre em galpões do tamanho de pequenas cidades. Os fatos geopolíticos sobre a infraestrutura da internet, logo, tem consequências para a independência e para a soberania da América Latina.

O problema também transcende a geografia. Muitos governos e militares latinoamericanos protegem seus segredos com hardware criptográfico. Isso são caixas e programas que embaralham as mensagens e então desembaralham-as na outra extremidade. Os governos as compram para manter seus segredos em segredo — frequentemente com grandes despesas para o povo — porque eles estão corretamente preocupados com a interceptação das suas comunicações.

Mas as empresas que vendem esses dispositivos caros desfrutam de laços estreitos com a comunidade da inteligência dos EUA. Seus presidentes e altos funcionários são frequentemente matemáticos e engenheiros da NSA (Agência de Segurança Nacional dos EUA) capitalizando nas invenções que eles criaram para o estado de vigilância. Seus dispositivos são muitas vezes deliberadamente quebrados: quebrados com um propósito. Não importa quem está usando ou como eles são usados — agências dos EUA ainda podem desembaralhar o sinal e ler as mensagens.

Esses dispositivos são vendidos para os países da América Latina e de outros lugares como uma forma de proteger seus segredos, mas são na verdade uma forma de roubar seus segredos.

Enquanto isso, os Estados Unidos estão acelerando a próxima grande corrida armamentista. As descobertas do vírus Stuxnet — e então dos vírus Duqu e Flame — anunciam uma nova era de armas-programas altamente complexas feitas por estados poderosos para atacar estados mais fracos. Seu primeiro ataque agressivo contra o Irã está determinado a minar os esforços iranianos de soberania nacional, um prospecto que é um anátema para os interesses dos Estados Unidos e de Israel na região.

Houve um tempo que o uso de vírus de computador como armas ofensivas era enredo de romances de ficção científica. Agora se tornou uma realidade global estimulado pelo comportamento irresponsável do governo de Barack Obama em violação ao direito internacional. Outros estados vão agora seguir o mesmo caminho, aumentando as suas capacidades ofensivas para se recuperarem.

Os Estados Unidos não são os únicos culpados. Nos últimos anos, a infraestrutura da internet de países como Uganda foi enriquecida por investimento direto chinês. Empréstimos pesados são distribuídos em troca de contratos africanos para as empresas chinesas construírem a infraestrutura de backbones de internet ligando escolas, ministérios do governo e comunidades no sistema global de fibra óptica.

A África está ficando online, mas com hardware fornecido por um aspirante a potência estrangeira. Será que vai ser a internet o meio pelo qual a África vai continuar subjulgada no século XXI? A África será novamente o espaço de confronto entre potências mundiais?

Essas são apenas algumas das formas importantes pelas quais a mensagem dos cypherpunks vai além da luta por liberdade individual. A criptografia pode proteger não somente as liberdades civis e direitos dos indivíduos, mas a soberania e independência de países inteiros, solidariedade entre grupos com causas comuns e projetos de emancipação global. Pode ser usada para lutar não apenas contra a tirania do estado sobre o indivíduo mas a tirania do império sobre estados menores.

Os cypherpunks ainda têm que fazer seu maior trabalho. Junte-se a nós.

43 anos de Internet

ATENÇÃO: Este conteúdo foi publicado há 5 anos. Eu talvez nem concorde mais com ele. Se é um post sobre tecnologia, talvez não faça mais sentido. Mantenho neste blog o que escrevo desde os 14 anos por motivos históricos. Leia levando isso em conta.

Há exatos 43 anos foi escrito o primeiro RFC (Request for Comments), motivo pelo qual muitos comemoramos no dia 7 de abril o nascimento da Internet. Imagino que poucas pessoas já leram ou sabem o que são RFCs fora do meio nerd: em resumo, são simples documentos de texto com não mais de 80 caracteres de largura que regulamentam os protocolos usados na Internet e são fundamentais para o desenvolvimento dos programas que você usa diariamente, inclusive o que você está usando para abrir o meu blog (seja no seu computador, no seu celular, ou no seu óculos).

Traduzi para o português (meio correndo e talvez porcamente; me corrijam se acharem alguma coisa muito errada) e recomendo a leitura do texto abaixo, escrito pelo cara que fez o primeiro RFC e publicado pelo The New York Times há três anos (para o aniversário de 40 anos da Internet). Além do valor histórico, acho que é um texto que tem muito a ver com o debate sobre as possibilidades que a internet do Wikileaks e do Mega Upload nos abre hoje e sobre os valores democráticos da rede, que têm sido duramente combatidos pelo conservadorismo do governo dos Estados Unidos e por iniciativas como a SOPA nos EUA e a Lei Azeredo no Brasil.

Como a Internet obteve suas regras

* Stephen Crocker

Hoje é uma data importante na história da Internet: é o aniversário de 40 anos dos chamados RFCs (Request for Comments). Fora da comunidade técnica, poucos sabem o que são RFCs, mas esses simples documentos moldaram o funcionamento interno da Internet e têm desempenhado um papel significativo no seu sucesso.

Quando os RFCs nasceram, não havia a World Wide Web. Mesmo no final de 1969, havia apenas uma rede rudimentar ligando quatro computadores em quatro centros de pesquisa: a UC Los Angeles, o Stanford Research Institute, a UC Santa Barbara e a Universy of Utah em Salt Lake City. O governo financiou a rede e os cem ou menos cientistas da computação que a utilizaram. Era uma comunidade tão pequena que todo mundo se conhecia.

Muito planejamento e muitas deliberações tinham sido feitos sobre a base da tecnologia da rede, mas ninguém tinha pensado muito no que fazer com ela. Então, em agosto de 1968, um punhado de estudantes e funcionários dos quatro locais começaram a se reunir intermitentemente pessoalmente para tentarem descobrir. (Fui sortudo o suficiente para ser um dos estudantes da UCLA incluídos nessas grandes discussões.) Só na primavera seguinte nós percebemos que deveríamos começar a escrever nossos pensamentos. Pensamos que talvez devêssemos juntar memorandos temporários e informais sobre os protocolos da rede, as regras pelas quais os computadores trocam informação. Me ofereci para organizar nossas primeiras notas.

O que deveria ser uma tarefa simples acabou se tornando um projeto desesperador. Nossa intenção era apenas encorajar outras pessoas a dialogarem, mas fiquei preocupado que soasse como se estivéssemos tomando decisões oficiais ou afirmando autoridade. Na minha cabeça, eu estava incitando a ira de algum professor de prestígio em algum estabelecimento da Costa Leste. Eu estava realmente perdendo o sono com a coisa toda e quando finalmente decidi escrever meu primeiro memorando, que lidava com a comunicação básica entre dois computadores, era madrugada. Tive que trabalhar no banheiro para não incomodar os amigos com quem eu estava hospedado, que estavam todos dormindo.

Ainda com medo de soar presunçoso, rotulei a nota “Request for Comments” (Pedido de Comentários). O RFC 1, escrito 40 anos atrás, deixou muitas perguntas sem resposta e logo se tornou obsoleto. Porém, os RFCs se enraizaram e floresceram. Eles se tornaram o método formal de publicar padrões do protocolo da Internet, e hoje são mais de 5000, todos disponíveis online.

Começamos a escrever essas notas antes que nós tivéssemos e-mail e mesmo antes que a rede estivesse realmente funcionando, então nós escrevíamos nossas visões para o futuro no papel e mandávamos pelo correio. Enviávamos uma impressão para cada grupo de pesquisa e eles tinham que tirar suas cópias.

Os primeiros RFCs variavam de grandes visões para detalhes mundanos, embora o segundo rapidamente tenha se tornado o mais comum. Menos importante do que o conteúdo desses primeiros documentos era o fato de que eles eram disponíveis de forma gratuita e qualquer um poderia escrever um. Em vez de um modelo de tomada de decisão baseado em autoridade, nós confiamos num processo que chamamos de “consenso básico e código em execução”. Todo mundo era bem-vindo a propôr ideias e, se pessoas suficientes gostassem e usassem, o projeto se tornava um padrão.

No fim, todos entendiam que havia uma utilidade prática em escolher fazer a mesma tarefa da mesma forma. Por exemplo, se quiséssemos mover um arquivo de uma máquina para a outra, se você projetasse o processo de uma forma e eu projetasse de outra, então qualquer pessoa que quisesse falar com nós dois teria que usar duas formas diferentes para fazer a mesma coisa. Então houve muita pressão natural para evitar tais inconvenientes. Provavelmente ajudou que naqueles dias nós evitávamos patentes e outras restrições; sem incentivo financeiro para controlar os protocolos, era muito mais fácil chegar a acordos.

Isso foi o melhor para a abertura dos projetos técnicos, e a cultura dos processos abertos foi essencial para permitir que a internet crescesse e evoluísse da forma tão espetacular como fez. Na verdade, nós provavelmente não teríamos a web sem eles. Quando os físicos do CERN quiseram publicar um monte de informações numa forma que as pessoas pudessem facilmente pegá-las e adicionarem às mesmas, eles simplesmente construíram e testaram suas ideias. Por causa do fundamento que colocamos no RFC, eles não tiveram que pedir permissão, ou fazerem quaisquer mudanças nas operações básicas da Internet. Outros logo copiaram-os — centenas de milhares de usuários de computador, então centenas de milhões, criando e compartilhando conteúdo e tecnologia. Isso é a Web.

Posto de outra forma, nós sempre tentamos projetar cada novo protocolo para ser útil tanto para seu próprio fim como para serem um bloco de construção disponível para outros. Nós não pensamos nos protocolos como produtos acabados, mas deliberadamente expusemos suas arquiteturas internas para fazer fácil que os outros os aproveitassem. Isso era a antítese da atitude das velhas redes de telefonia, que desencorajavam fortemente quaisquer acréscimos ou utilizações que elas não haviam sancionado.

É claro que o processo para publicar ideias e escolher padrões eventualmente se tornou mais formal. Nossas reuniões soltas e anônimas cresceram e se semi-organizaram no que chamamos de Network Working Group (Grupo de Trabalho da Rede). Nas quatro décadas desde lá, esse grupo evoluiu, se transformou algumas vezes e hoje é a Internet Engineering Task Force (Força de Tarefa da Engenharia da Internet). Ela tem alguma hierarquia e formalidade, mas não muita, e continua a ser gratuita e acessível a qualquer um.

Os RFCs cresceram também. Eles não são mais realmente pedidos de comentários, porque eles são publicados somente depois de muita examinação. Mas a cultura que foi construída no início continuou a desempenhar um papel importante em manter as coisas mais abertas do que elas poderiam ter sido. Ideias são aceitas e classificadas pelos seus méritos, com tantas ideias rejeitadas como aceitas.

A medida que reconstruirmos nossa economia, espero que tenhamos em mente o valor da transparência, especialmente em indústrias que raramente a tiveram. Seja na reforma do sistema de saúde ou na inovação da energia, as maiores recompensas virão não do que o pacote de incentivo paga diretamente, mas das perspectivas que abrimos para os outros explorarem.

Me lembrei do poder e da vitalidade dos RFCs quando eu fiz a minha primeira viagem para Bangalore, India, há 15 anos atrás. Fui convidado a dar uma palestra no Indian Institute of Science e durante a visita fui apresentado a um estudante que construiu um sistema de software bastante complexo. Impressionado, perguntei onde ele havia aprendido a fazer tudo aquilo. Ele respondeu simplesmente: “Eu baixei os RFCs e li.”

* Stephen D. Crocker escreveu o primeiro RFC há exatos 43 anos.

Combatendo a censura com algoritmos

ATENÇÃO: Este conteúdo foi publicado há 6 anos. Eu talvez nem concorde mais com ele. Se é um post sobre tecnologia, talvez não faça mais sentido. Mantenho neste blog o que escrevo desde os 14 anos por motivos históricos. Leia levando isso em conta.

Mohammad Mahdian* (tradução: Tiago Madeira)

Os levantes recentes no Oriente Médio demonstraram a eficácia da internet em ajudar ativistas políticos e sociais a organizarem protestos, disseminarem informações para o público e enviarem notícias de prisões e repressões ao restante do mundo. Ameaçados por esse paradigma, regimes totalitários tentaram controlar e monitorar o acesso de seus cidadãos à web, desenvolvendo ou adquirindo tecnologias de censura e de vigilância da internet. Ao mesmo tempo, uma variedade de ferramentas de violação desses filtros foi desenvolvida para ajudar os usuários a contornarem o filtro da internet acessando sites bloqueados através de intermediários não-bloqueados (os chamados proxies). O artigo de Dan Boneh (Recent Ideas for Circumventing Internet Filtering) dá um ótimo resumo sobre novas e velhas técnicas para construir essas ferramentas.

No coração de todos os métodos de violação existe o seguinte dilema: Para fazer a ferramenta disponível ao público, os endereços de proxy precisam ser comunicados para os usuários. Isso, no entanto, permite que as autoridades obtenham esses endereços (fingindo serem usuários legítimos) e aí bloqueiem todo o tráfego nesses endereços específicos. Ter vários proxies de curta duração alivia o problema, mas a questão permanece: Existe algum método algorítmico esperto para distribuir proxies que diminua o número de proxies necessários para fornecer acesso à internet sem filtro?

O problema de distribuição de proxy

Vamos começar definindo um modelo teórico simples para este problema. Nós gostaríamos de distribuir um conjunto de m proxies para uma população de n usuários: k deles são adversários (agentes da censura) e o restante (n-k) são usuários legítimos. Nós não sabemos as identidades dos adversários, mas podemos assumir que k << n. Na verdade, para simplicidade, pense em k como uma constante, enquanto n cresce ao infinito.

Se um proxy é dado a um adversário, ele pode comprometer o proxy, tornando-o inutilizável para os outros usuários. Uma vez que um proxy é comprometido, nós ficamos sabendo e podemos distribuir outros proxies para os usuários afetados. Nossa meta é garantir que todo usuário legítimo tenha pelo menos um proxy não-comprometido. A questão é: qual é o menor m com o qual conseguimos fornecer essa garantia?

Claramente, o problema pode ser resolvido com n proxies dando pra cada usuário um proxy diferente. Na verdade, podemos fazer muito melhor usando um algoritmo de busca binária: Comece dividindo os usuários em duas caixas e dê pra cada caixa o seu proxy. Uma vez que um proxy é comprometido, divida sua caixa correspondente pela metade e dê para cada uma das metades um proxy. Continue fazendo isso enquanto existe apenas um usuário na caixa. É fácil ver que esse método usa no máximo O(log(n)) proxies. Uma divisão cuidadosa dos usuários em caixas rende uma solução com no máximo k(1+log_2(n/k)) proxies.

Podemos resolver o problema com menos de O(log(n)) proxies? Talvez surpreendentemente, nós podemos fazer um pouco melhor. Há um algoritmo randomizado de distribuição de proxies que usa no máximo O(log(n)/loglog(n)) proxies. Um argumento simples de entropia mostra que isso é assintoticamente ótimo para um k constante.

Distribuição de proxies via redes de confiança

Uma forma comum de construir uma base de usuários num país sob censura é através de relações pessoais de confiança. O sistema começa com poucos usuários confiáveis e então cada usuário confiável pode convidar novos usuários em quem ele confia para o sistema. Dessa forma, o conjunto de usuários cresce como uma rede de confiança: uma árvore enraizada na qual o conjunto de usuários confiáveis inicial é filho da raiz e arestas indicam relações de confiança.

Usar uma rede de confiança dificulta que um adversário se infiltre na base de usuários. No entanto, o problema é que uma vez que a rede é infiltrada, o adversário pode convidar novos adversários para a rede. Para levar isso em conta, nós modificamos a formulação do problema como segue: em vez de exigir que um pequeno número de usuários seja adversário, nós assumimos que um pequeno número de usuários e todos os seus descendentes na rede são adversários. Uma forma alternativa de formular esse problema é considerar redes de confiança capacitadas e assumir que o menor corte da raiz para todos os adversários é no máximo um pequeno número k.

O problema de distribuição de proxy em redes de confiança está ainda sem solução em geral. Temos resultados parciais para pequenos k e no caso capacitado. Os algoritmos são não-triviais e precisam olhar para a estrutura da rede de confiança.

Conclusão

O objetivo desse exercício era convencer o leitor de que existe um problema teórico interessante e desafiante no âmago das tecnologias de violação de censura. Modelos e algoritmos para esse problema estão muito próximos dos que são usados na prática e, logo, há potencial para pesquisa nessa área que pode ter um impacto real nas vidas de milhões de pessoas vivendo sob opressão.


* Mohammad Mahdian é um pesquisador senior do Yahoo Research Lab em Santa Clara, CA. É bacharel em Engenharia da Computação pela Universidade de Tecnologia de Sharif, mestre em Ciência da Computação pela Universidade de Toronto e PhD em Matemática pelo MIT. Seus interesses de pesquisa atuais incluem projeto de algoritmos, economia algorítmica e aplicações em publicidade online e redes sociais.

Este texto foi publicado em inglês na última edição da XRDS (revista da ACM para estudantes), cujo tema é Ciência da Computação a serviço da democracia. No site do autor, há o artigo “Fighting censorship with algorithms” completo em PDF disponível para download gratuito. Ainda não li, mas parece interessante.

Boa nova

ATENÇÃO: Este conteúdo foi publicado há 7 anos. Eu talvez nem concorde mais com ele. Se é um post sobre tecnologia, talvez não faça mais sentido. Mantenho neste blog o que escrevo desde os 14 anos por motivos históricos. Leia levando isso em conta.

Resolvi fazer Ciência da Computação há muito tempo. Faz tanto tempo que eu não lembro quando foi, mas acho que eu tinha uns oito anos. Minha única certeza é que eu não fazia ideia do que era o curso (mas isso não importa — hoje acho que escolhi estudar uma das coisas mais legais que existem).

O tempo passou e cogitei fazer outras faculdades, mas nunca seriamente. Começou o 3º ano do Ensino Médio e comparei os currículos de UFSC, UNICAMP, ICMC-USP e IME-USP pra decidir que curso escolher. Ordenei-os (por motivos teóricos) da seguinte forma:

  1. IME-USP
  2. ICMC-USP
  3. IC-UNICAMP (engenharia)
  4. UFSC

Desde lá minha meta foi entrar no lugar onde hoje, felizmente, estou. Mas não foi fácil.

Passei o último ano do Ensino Médio namorando estudando, li os resumos dos livros exigidos e quando chegou novembro… não passei na primeira fase do vestibular da Fuvest.

(Felizmente passei na UFSC e vivi um ano sensacional. Morava do lado da Universidade, fiz grandes amigos, conheci professores do mais alto nível, me classifiquei pra final mundial da Maratona de Programação e aprendi mais Matemática do que em toda a vida. Mas nem todos têm a mesma sorte.)

O vestibular da USP usa um terrível sistema baseado em carreiras.

Def. Carreiras são conjuntos disjuntos não-vazios de cursos universitários que em geral tem algo em comum (e.g., uma carreira pode ter Engenharia de Produção e Ciência da Computação porque ambos são cursos pra seres humanos — não sei se poderia haver alguma outra razão mais específica, sem ser através da Lei dos Cinco, mas creio que não).

No sistema da USP o candidato escolhe uma carreira, cursos que gostaria de fazer nessa carreira e sua ordem de preferência.

Passam pra segunda fase do vestibular três vezes o número de vagas disponíveis na carreira. Depois da segunda fase, os candidatos são ordenados de acordo com a nota da segunda fase e roda-se um algoritmo assim:

1
2
3
4
5
6
7
8
for (int pos = 0; tem_vagas_sobrando() && pos < n; pos++) {
    for (int opcao = 0; opcao < 4; opcao++) {
        if (tem_vagas_no_curso(pessoa[pos].opcao[opcao])) {
            da_vaga(pessoa[pos], pessoa[pos].opcao[opcao]);
            break;
        }  
    }  
}

Estava com sono e dificuldade de pensar quando postei. Outra hora tento passar pra uma língua menos nerd.

São os institutos que decidem em que carreira seus cursos vão entrar e o negócio fica uma bagunça. A maioria das carreiras têm cursos iguais com diferença apenas de período (diurno e noturno), mas há carreiras de institutos inteiros (a FEA, por exemplo, tem apenas uma carreira onde coloca Economia [diurno e noturno], Administração [diurno e noturno], Ciências contábeis [diurno e noturno] e Bacharelado em Ciências Atuariais), de cursos iguais em diferentes campi (na carreira de Direito, por exemplo, o candidato pode escolher entre o Largo São Francisco e Ribeirão Preto) e, por fim, carreiras como a minha: Engenharia na Escola Politécnica e Computação, que oferece (versão Fuvest 2010):

  • Engenharia Civil e Engenharia Ambiental (poli)
  • Engenharia Elétrica (ênfases: Automação e controle, energia e automação elétricas, sistemas eletrônicos, telecomunicações) (poli)
  • Engenharia Mecânica e Engenharia Naval (poli)
  • Engenharia Química, Engenharia Metalúrgica, Engenharia de Materiais, Engenharia de Minas e Engenharia de Petróleo (poli)
  • Engenharia de Computação e Engenharia Elétrica (ênfase Computação) (poli)
  • Engenharia Mecânica – Automação e Sistemas (Mecatrônica) (poli)
  • Engenharia de Produção (poli)
  • Bacharelado em Ciência da Computação (IME!)

Reza a lenda que essa era uma carreira que tinha todos os cursos que classificam como Exatas (uma classificação ridícula, na minha opinião) e todos eles foram saindo, até que no meu ano sobraram só as engenharias da Poli e o BCC.

(E eu prefiro acreditar nisso porque me doeria acreditar o contrário — aceitar que em certo momento da História algum idiota professor decidiu que Ciência da Computação tem mais a ver com Engenharia Ambiental do que com Matemática.)

Agora veja o problema: Em um ano aqui, aprendi que trabalhar em bancos está na moda em São Paulo. Como se formar em engenharia na Escola Politécnica é garantia desse nobre emprego, fazem um monte de cursinhos (e turmas especiais neles) voltados a destruir o cérebro das ensinar crianças (o link é bom; clique!) pra jihad passar na Fuvest. O resultado é que um catarinense que quer entrar no Bacharelado em Ciência da Computação não consegue nem passar da primeira fase do concurso. Se passa pra segunda fase, ainda assim precisa competir com estudantes que colocaram o BCC na quarta opção para não decepcionar os pais e seu ego caso não passem nas três engenharias que desejam.

E não para por aí.

O BCC abre 50 vagas por ano e neste ano matricularam-se 31 calouros. Os alunos da turma (para a qual dou monitoria da disciplina Introdução à Computação) me contaram que tem 26 pessoas indo assistir as aulas. Enquanto há jovens no Brasil inteiro querendo entrar neste curso, que considero um dos melhores (se não o melhor) do país, a sala da turma de 2010 está com metade de sua capacidade porque gente que queria fazer engenharia marcou a opção do BCC e não fez a matrícula.

A solução imediata é óbvia: tirar o Bacharelado em Ciência da Computação da carreira da Escola Politécnica.

Felizmente, não sou o único que penso isso. Então, após todo esse preâmbulo, informo em primeira mão: a Congregação do Instituto de Matemática e Estatística, em sessão ordinária realizada hoje (29/04) da qual tive o enorme prazer de participar, aprovou por unanimidade essa decisão, que já havia sido aprovada (também por unanimidade) dentro do Departamento de Computação.

Será criada nesse ano na Fuvest uma carreira chamada “Bacharelado em Ciência da Computação”, que a princípio terá 50 vagas, mas para a qual será convidado o Bacharelado em Ciência da Computação do ICMC-USP (São Carlos).

A decisão é fantástica e será fundamental pra vida de diversos futuros estudantes desta faculdade. Já estou ansioso pelo ano que vem…

Coordenadas homogêneas

ATENÇÃO: Este conteúdo foi publicado há 7 anos. Eu talvez nem concorde mais com ele. Se é um post sobre tecnologia, talvez não faça mais sentido. Mantenho neste blog o que escrevo desde os 14 anos por motivos históricos. Leia levando isso em conta.

Conheci as coordenadas homogêneas por acaso. Era 2004, ganhei a modalidade iniciação da Olimpíada Brasileira de Informática e passei o inverno estudando C, acho que por dois motivos: interesse pelos problemas da modalidade programação e desejo de aproveitar bem o curso que os medalhistas fazem na UNICAMP; ou talvez fosse apenas falta do que fazer ou curiosidade mesmo. Não importa.

Confundo os cursos de 2004, 2005 e 2006, mas lembro que no primeiro aprendi com um monitor sobre recursão, representação de grafos e busca em profundidade. Lembro também que foi em 2004 que conheci o CLRS (livro que comprei alguns meses depois e tenho na cabeceira até hoje). Esse post, porém, é sobre um acontecimento mais aleatório relacionado a esse curso e, ouso afirmar, digno de figurar n’O Andar do Bêbado do Mlodinow.

O pessoal da modalidade programação ia tirar cópias de um livro do Stolfi e do Rezende, chamado “Fundamentos de Geometria Computacional” (dá pra baixar aqui). Nem sabia do que estavam tirando xerox, mas vi que era barato e que todos os mais velhos estavam querendo, então também pedi.

Folheei o livro, não entendi nada, deixei num canto e voltei a abrir alguns anos depois, não lembro exatamente quando. E foi aí que fez-se a luz. A primeira parte é sobre coordenadas homogêneas.

Coordenadas homogêneas? A ideia parece simples (até demais) pra ser poderosa. Basicamente você representa uma coordenada em (X, Y) \in \mathbb{R}^2 com uma tripla ordenada [w, x, y] tal que x = \frac{X}{w} e y = \frac{Y}{w}. A reta tem a mesma representação.

1
2
3
4
5
struct ponto {
	int w, x, y;
};
 
typedef ponto reta;

E o que isso tem demais? Você deixa de precisar de pontos flutuantes pra maioria das operações geométricas; ganha pontos no infinito (eles são a interseção entre retas paralelas!) que permitem fazer fórmulas sem preocupação com casos especiais, usar a mesma fórmula pra determinar uma reta gerada por dois pontos ou por um ponto e um vetor etc.; tem representações iguais (e dualidade) entre pontos e retas (e.g. interseção entre retas p e q = reta determinada por pontos p e q); e mais um monte de outras coisas.

Uau! Como eu não ouvi falar disso antes? Eu não sei a razão, mas, embora tenham várias vantagens, as coordenadas homogêneas não são muito populares na universidade, nem entre os maratonistas. No entanto, são usadas em projetos grandes que usam muita geometria (e.g. OpenGL).

Quero código! Vou mostrar como resolvi o problema Symmetry (2002 TopCoder Inv Round 4 – Division I, Level Three).

O enunciado é simples: Dados n (2 \leq n \leq 200) pontos inteiros (com coordenadas de -10000 a 10000) determinar quantas linhas de simetria existem entre eles.

Dá pra fazer em O(n^3) com a seguinte ideia:

  1. Crie uma árvore binária balanceada indexada por retas. (em C++, map <reta,int>)
  2. Para cada par de pontos, determine a reta de simetria entre eles e adicione 2 a essa reta na árvore binária. (O(n^2 log n))
  3. Para cada reta na árvore binária, adicione 1 para cada ponto que pertence a essa reta. (O(n^3))
  4. É fácil ver que a reta é uma reta de simetria do conjunto de pontos se e somente se seu valor na árvore binária for n.

O problema geométrico está no segundo passo: determinar a reta de simetria entre dois pontos. Sejam esses pontos p e q. É preciso:

  1. Determinar o ponto médio entre p e q.
  2. Determinar a reta que passa por p e q (o enunciado garante que p != q).
  3. Determinar uma reta (ou um vetor) perpendicular à reta do passo acima.
  4. Determinar a reta que passa pelo ponto médio e tem a direção do vetor perpendicular do passo 3.

Determinar o ponto médio sem usar ponto flutuante seria trivial de qualquer forma (basta multiplicar todas as coordenadas por dois), mas com coordenadas homogêneas isso é desnecessário. É fácil ver que o ponto médio m entre p = [w_0, x_0, y_0] e q = [w_1, x_1, y_1] é:

m = [ 2 w_0 w_1 , w_1 x_0 + w_0 x_1 , w_1 y_0 + w_0 q_1 ]

1
2
3
ponto ponto_medio(ponto p, ponto q) {
	return (ponto) { 2*p.w*q.w, q.w*p.x+q.x*p.w, q.w*p.y+q.y*p.w };
}

Três pontos [w_0, x_0, y_0], [w_1, x_1, y_1], [w_2, x_2, y_2] são colineares se

 \left| \begin{array}{ccc} w_0 & x_0 & y_0 \\ w_1 & x_1 & y_1 \\ w_2 & x_2 & y_2 \end{array} \right| = 0 ,

o que nos permite concluir que a reta r = \langle W, X, Y \rangle que passa por p = [ w_0, x_0, y_0 ] e q = [ w_1, x_1, y_1 ] é:

r = \langle +x_0 y_1 - y_0 x_1, -w_0 y_1 + w_1 y_0, w_0 x_1 - w_1 x_0\rangle.

1
2
3
ponto reta_determinada_por(ponto p, ponto q) {
	return (reta) { +p.x*q.y-q.x*p.y, -p.w*q.y+q.w*p.y, +p.w*q.x-q.w*p.x };
}

(um ponto [w, x, y] pertence a r se Ww + Xx + Yy = 0)

1
2
3
int ponto_na_reta(ponto p, reta r) {
	return p.w*r.w + p.x*r.x + p.y*r.y == 0;
}

Agora a parte mais legal: a fórmula para determinar uma reta que passa por dois pontos funciona com pontos no infinito (pensemos em pontos no infinito como vetores, porque eles tem direção mas tem w = 0): o resultado é a reta determinada por um ponto e uma direção. O vetor perpendicular à reta \langle W, X, Y \rangle é [ 0, X, Y ].

1
2
3
ponto ponto_infinito_na_reta_perpendicular(reta r) {
	return (reta) { 0, r.x, r.y };
}

E isso é tudo. Agora basta criar uma representação única da reta pra guardar na árvore binária.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
reta reformata_reta(reta r) {
	if (r.w < 0) {
		r.w = -r.w;
		r.x = -r.x;
		r.y = -r.y;
	} else if (r.w == 0) {
		if (r.x < 0) {
			r.x = -r.x;
			r.y = -r.y;
		} else if (r.x == 0 && r.y < 0) {
			r.y = -r.y;
		}
	}
	int d = gcd(r.w, gcd(abs(r.x), abs(r.y)));
	return (reta) { r.w/d, r.x/d, r.y/d };
}

Usando essas funções, primeiro e segundo passos da solução são:

map <reta,int> M;
for (int i = 0; i < n; i++) {
	for (int j = i+1; j < n; j++) {
		reta s = reformata_reta(reta_determinada_por(P[i], P[j]));
		ponto pm = ponto_medio(P[i], P[j]);
		ponto dir = ponto_infinito_na_reta_perpendicular(s);
		reta r = reformata_reta(reta_determinada_por(pm, dir));
		if (M.find(s) == M.end())
			M[s] = 0;
		if (M.find(r) == M.end())
			M[r] = 0;
		M[r]+= 2;
	}
}

Terceiro e o quarto são:

1
2
3
4
5
6
7
8
int output = 0;
for (map <reta,int>::iterator i = M.begin(); i != M.end(); i++) {
	for (int j = 0; j < n; j++)
		if (ponto_na_reta(P[j], i->first))
			i->second++;
	if (i->second == n)
		output++;
}

O código completo ficou com umas 90 linhas com comentários e linhas em branco e foi aceito na primeira submissão (ok, na verdade na segunda, mas não foi devido à geometria muito menos à precisão): symmetry.cpp. Não é lindo?

Vergonha

ATENÇÃO: Este conteúdo foi publicado há 8 anos. Eu talvez nem concorde mais com ele. Se é um post sobre tecnologia, talvez não faça mais sentido. Mantenho neste blog o que escrevo desde os 14 anos por motivos históricos. Leia levando isso em conta.

O disciplina é “Princípios de Desenvolvimento de Algoritmos” e ela está sendo ministrada neste semestre pelo Prof. Dr. Carlos Eduardo Ferreira, participante do grupo de otimização combinatória, diretor nacional da Maratona de Programação e orientador da minha iniciação científica.

A turma é do Bacharelado em Ciência da Computação no IME-USP.

Acabei de receber a seguinte mensagem de um dos monitores:

Screenshot

Preciso dizer mais alguma coisa?

Bacharelado em Ciência da Computação

ATENÇÃO: Este conteúdo foi publicado há 8 anos. Eu talvez nem concorde mais com ele. Se é um post sobre tecnologia, talvez não faça mais sentido. Mantenho neste blog o que escrevo desde os 14 anos por motivos históricos. Leia levando isso em conta.

Em primeiro lugar quero afirmar aos desavisados que o curso de Ciência da Computação hoje é, na maioria dos lugares, não mais do que o estereótipo indica: um curso de viciados em jogos. Até aí tudo bem; afinal cada um faz o que bem entende nos seus momentos de lazer.

Porém, eu acho que esse fato colaborou para esse bacharelado se transformar num reduto de usuários de computador, pessoas que leram “Computação” no nome e pensaram: “Eu gosto de mexer no computador, acho que este é o meu curso”.

Our new mobile lab
Creative Commons License photo credit: Christy Tvarok Green

Se já sabemos que funciona, pra que provar?

A realidade que percebo nas turmas, tanto na UFSC quanto no IME-USP, é decepcionante. Quando um professor dá um curso mais forte e teórico, vários alunos se espantam e reclamam que o curso não está formando para a prática. Pior: em muitas universidades o curso está mudando de cara pra satisfazer estes estudantes e não o contrário, como deveria ser. O IME-USP ainda tem um curso excelente, mas advinhe o que os alunos da minha turma aprenderam na primeira matéria do curso (chamada de Introdução à Computação)? Java e programação orientada a objetos. Eles aprendem classes e métodos antes de aprenderem operadores lógicos e laços. Na única aula que fui da disciplina, o professor falava bem do Java porque as classes e métodos podem ter acentos!!!

A situação é tão desanimadora que às vezes penso que o nome do meu curso deveria mudar para não pegar desavisados que não procuram o que é antes de entrar. Deveria ser algo como Bacharelado em Ciência dos Algoritmos, Bacharelado em Matemática Discreta, que tal? Não sei. Mas é obviamente uma besteira: o que precisa mudar são as pessoas. Tanto as que entram no curso, quanto as pessoas em geral, que pedem favores pra cientistas da computação pensando que eles são técnicos de informática. As pessoas precisam entender o que é o curso antes de entrar nele, precisam saber que Ciência da Computação é um ramo da matemática que existe desde muito antes da criação dos computadores digitais.

O primeiro parágrafo do texto da Wikipedia em português sobre Ciência da computação diz (e juro que não fui eu que editei!):

Ciência da computação é o estudo dos algoritmos e suas aplicações, bem como das estruturas matemáticas indispensáveis à formulação precisa dos conceitos fundamentais da teoria da computabilidade e da computação aplicada. Desempenha por isso um papel importante na área de ciência da computação a formalização matemática de algoritmos, como forma de representar problemas decidíveis, i.e., os que são suscetíveis de redução a operações elementares básicas, capazes de serem reproduzidas através de um qualquer dispositivo mecânico/eletrônico capaz de armazenar e manipular dados. Um destes dispositivos é o computador digital, de uso generalizado, nos dias de hoje, pelo custo reduzido dos componentes eletrônicos que formam o seu hardware.

Se o Java já tem um heap implementado para que reinventar a roda?

Edsger Dijkstra, um dos grandes cientistas da computação de nossa história, disse certa vez:

Ciência da Computação está tão relacionada aos computadores quanto a Astronomia aos telescópios, Biologia aos microscópios, ou Química aos tubos de ensaio. A Ciência não estuda ferramentas. Ela estuda como nós as utilizamos, e o que descobrimos com elas.

Precision knob?
Creative Commons License photo credit: gogoninja

É por tudo isso que abandono a sala ao ouvir que hoje em dia classes são mais importantes do que laços e nomear corretamente funções é mais importante do que conhecer algoritmos. (Sim, já ouvi isso de um professor dentro da universidade.)

Declaro-me a favor de um curso de Ciência da Computação onde os computadores sejam tratados apenas como ferramentas. Há outros cursos (técnicos) para quem não pensa assim e entra na universidade buscando uma formação sobre desenvolvimento ágil e produtividade. Não estou criticando quem busca isto. Porém, na minha opinião, estes definitivamente não deveriam entrar num curso chamado Bacharelado em Ciência da Computação.

Escada perfeita (OBI2006)

ATENÇÃO: Este conteúdo foi publicado há 10 anos. Eu talvez nem concorde mais com ele. Se é um post sobre tecnologia, talvez não faça mais sentido. Mantenho neste blog o que escrevo desde os 14 anos por motivos históricos. Leia levando isso em conta.

Depois de meses sem postar, resolvi que a partir de agora darei mais atenção pra este blog. Muita gente me manda e-mail e comentários com dúvidas e gostaria de deixar bem claro que eu não faço trabalhos de faculdade pra ninguém, mas que se você tiver uma dúvida real onde eu possa ajudar eu ajudarei de bom grado.

Pensei muito sobre o que postar aqui, tenho rascunhos sobre buscas em grafos e sobre resoluções de problemas de grafos, mas resolvi quebrar toda a ordem e, a partir de um scrap de orkut, acabei me lembrando do problema Escada perfeita, da OBI 2006, e me deu vontade de resolvê-lo aqui.

Por que o problema Escada Perfeita?

A programação deste problema é extremamente simples, mas a sua lógica (matemática pura) é muito inteligente. Tente resolver o problema antes de ver minha solução e, caso não consiga, depois veja como a solução é bonita.

Vamos ao enunciado…

Uma construtora, durante a criação de um parque temático, encontrou no terreno um conjunto de várias pilhas de cubos de pedra. Ao invés de pagar pela remoção dos cubos de pedras, um dos arquitetos da empresa achou interessante utilizar as pedras para decoração do parque, determinando que as pedras fossem rearranjadas no formato de “escada”. para isso, os funcionários deveriam mover alguns cubos para formar os degraus das escadas. Só que o arquiteto decidiu que, entre uma pilha e outra de pedras deveria haver exatamente uma pedra de diferença, formando o que ele chamou de escada perfeita. O exemplo abaixo mostra um conjunto de cinco pilhas de pedras encontradas e as cinco pilhas como ficaram após a arrumação em escada perfeita.

Tarefa

Dada uma seqüência de pilhas de cubos de pedras com suas respectivas alturas, você deve determinar o número mínimo de pedras que precisam ser movidas para formar uma escada perfeita com exatamente o mesmo número de pilhas de pedras encontrado inicialmente (ou seja, não devem ser criadas ou eliminadas pilhas de pedras). O degrau mais baixo da escada deve sempre estar do lado esquerdo.

Entrada

A entrada contém um único conjunto de testes, que deve ser lido do dispositivo de entrada padrão (normalmente o teclado). A primeira linha contém um inteiro n que indica o número de pilhas de pedras. A segunda linha contém N números inteiros que indicam a quantidade de cubos de pedras em cada uma das pilhas, da esquerda para a direita.

Saída

Seu programa deve imprimir, na saída padrão, uma única linha, contendo um inteiro: o número mínimo de cubos de pedras que devem ser movidos para transformar o conjunto de pilhas em uma escada perfeita, conforme calculado pelo seu programa. Caso não seja possível efetuar a transformação em escada perfeita, imprima como resultado o valor -1.

Exemplos

Exemplo 1

Entrada
5
5 4 5 4 2

Saída
5

Exemplo 2

Entrada
6
9 8 7 6 5 4

Saída
9

Exemplo 3

Entrada
2
1 5

Saída
-1

OK. Estão prontos?

Depois de pensar um pouco, conclui-se que:

  1. A escada perfeita é uma PA de razão 1 (aumenta de um em um). Você lembra disso do seu primeiro ano do Ensino Médio? Senão, é bom dar uma relembrada. As fórmulas (simples e facilmente deduzíveis) da PA são:

    Termo geral da PA

    a_{n} = a_{1} + (n-1).r

    Soma de PA

    \displaystyle S_{n} = (a_{1}+a_{n}).\frac{n}{2}

  2. Sabemos quanto vale n (o número de pilhas, número de elementos da PA) e conseguimos calcular a soma de todos os elementos (podemos fazer isso até durante o loop da entrada, certo?)
  3. Sabemos quanto vale a razão (r=1).
  4. Substituindo o que sabemos nas fórmulas conseguimos formar um sistema de equações básico e desta forma torna-se fácil descobrir o valor do primeiro e do último termo da PA (a_{1} e a_{n}). Resumindo um pouco os cálculos, depois de alguma manipulação algébrica você chega a: \displaystyle a_{n} = \frac{\frac{2.S_{n}}{n}+n-1}{2}

    \displaystyle a_{1} = 1 + a_{n} - n

  5. Agora que já sabemos onde começa e onde termina a escada basta fazer um loop em cada fila de blocos e adicionar à uma variável movimentos a quantidade de quadradinhos que estão sobrando nesta fileira (por exemplo, na primeira fileira da figura do enunciado está sobrando três quadradinhos para chegar ao a_{1}=2). Ao mesmo tempo, adicionamos à outra variável (moves) a quantidade de quadradinhos que devem ser retirados ou colocados na fileira (porque depois se esta variável não for igual a 0 imprimimos -1). Ficou claro?

Implementação

Variáveis

  • n: número de degraus (fileiras de blocos)
  • a: a_{1}, número de blocos do primeiro degrau.
  • b: a_{n}, número de blocos do último degrau.
  • soma: S_{n}, soma da PA.
  • pilha[]: vetor de degraus.
  • movimentos e moves: explicados no quinto passo da solução.
  • i e j: variáveis auxiliares para fazer os loops.

Codeado em C

#include <stdio.h>
#define PMAX 10001
 
int main() {
    int i, j;
    int n;
    int soma=0;
    int a, b;
    int pilha[PMAX];
    int moves=0;
    int movimentos=0;
 
    scanf("%d", &n);
    for (i=0; i<n; i++) {
        scanf("%d", &pilha[i]);
        soma+=pilha[i];
    }
 
    b=(((2*soma)/n)+(n-1))/2;
    a=1+b-n;
 
    for (i=0; i<n; i++) {
        moves+=(pilha[i]-(i+a));
        if (pilha[i]>i+a) {
            movimentos+=(pilha[i]-(i+a));
        }
    }
 
    if (moves!=0) {
        printf("-1n");
    } else {
        printf("%dn", movimentos);
    }
 
    return 0;
}

Prontinho! Qualquer dúvida escrevam seus comentários.