Primeira fase da Maratona de Programação 2018

No último fim de semana aconteceu a primeira fase da Maratona de Programação (a fase sub-regional da ACM-ICPC) no Brasil. Essa prova é feita em várias sedes no país e serve como classificatória para a fase nacional, que esse ano acontece em Salvador.

Participaram mais de 700 equipes, e cerca de 70 se classificam para a fase seguinte de acordo com múltiplas regras como a colocação no Brasil e a colocação na sede. Esse ano, participei com a equipe do ITA (CalopsITA) junto com o Lucas França e o Lucas Soares, todos no nosso último ano de participação, e conseguimos o quarto lugar no Brasil!

Programação Dinâmica com dígitos [Pt 3]: Editorial

Vamos aqui abordar dois problemas que são bons exemplos de PD com dígitos e não são fáceis:

Spoj NUMTSN: 369 Numbers (link para o problema)
Codeforces 2015-2016 Petrozavodsk Winter Training Camp: Maximum Product (link para o problema)

Programação Dinâmica com dígitos [Pt 2]

Na parte 1, vimos como resolver o problema de quantos números existem entre 0 e B com uma propriedade, e dissemos que para computar de A a B basta fazer de 0 a B menos de 0 a A-1. O problema é que nem sempre dá certo. Por exemplo, se quisessemos o número entre A e B com maior soma de dígitos, essa estratégia não funcionaria!

Vamos agora ver como resolver de outra forma então, mais genérica, mas que pode ser mais lenta.

Como exemplo, vamos usar o problema: quantos números menores que X e maiores que Y existem tal que a soma dos dígitos é exatamente 20.

Programação Dinâmica com dígitos [Pt 1]

Programação dinâmica (PD) em dígitos é uma subclasse dos problemas de PD. Existem muitas variações, nessa parte falamos da forma: Dado um intervalo A e B, quantos números x, A <= x <= B, tem uma propriedade específica.

No nosso caso, vamos usar o problema: quantos números menores que X existem tal que a soma dos dígitos é exatamente 20. Existem várias formas de resolver, e irei mostrar uma.

Cultivando strings (Growing Strings): dois caminhos

Mais um problema interessante, da ACM/ICPC South America, do contest de 2010! O problema é Cultivando Strings (ou Growing Strings, em inglês), e vou (tentar :) ) resolver por duas formas diferentes: o algoritmo de Aho-Corasick e Suffix Arrays.

URI 1141 - Cultivando Strings / Growing Strings (link)

(A partir daqui, vou supor que você conhece os métodos. Se não for o caso, google it! Se algum dia eu escrever alguma coisa sobre um dos dois, edito o link aqui).

Jogo no servidor e cliente

O servidor e o cliente do nosso jogo funcionam em cima de uma mesma estrutura básica, mas há diferenças grandes entre eles.

Para começar, nosso servidor deve ser anti-cheating. O player pode alterar sua posição de um jeito "ilegal" e mandar para o servidor e... Opa, devemos tratar isso. E se ele quiser roubar uns pontos de vida? Para evitar isso, usamos um servidor autoritário: o cliente envia inputs para o servidor e desenha na tela, além de atualizar localmente o que recebe remotamente, enquanto nós processamos tudo.

Trabalhando com JavaScript Object Notation (JSON)

Algumas propriedades de um jogo devem ser definidas de maneira que seja fácil trocar posteriormente. Por exemplo, a massa de um corpo no qual age uma força, coeficientes de atrito entre outras propriedades físicas. Isso porque não existe um valor "ideal" para tais características. E só há um jeito de descobrir a melhor massa, ou força, ou qualquer propriedade: testando.

Geralmente essas propriedades são utilizadas em vários lugares, então o ideal é armazená-las em um arquivo de configuração, de forma que até quem não viu o código (ou mesmo quem não entende de programação) possa alterá-las.