Tutorial TopCoder

O Topcoder merece uma página especial porque o formato dele é muito diferente da maratona.

Registration

Se vocês não tem uma conta, comecem por aí – entrem em: http://community.topcoder.com/tc (e não topcoder.com, porque essa página é direcionada para outras coisas), "Register Now" e, bom, não sei se vocês vão querer participar no TopCoder Studio (não sei o que é), mas certamente, se vocês vieram para essa página, querem competir no Topcoder.

Preencham seus dados and all that jazz e vocês vão ter um TopCoder handle, que vai seguir vocês para o resto de toda a vida maratonística de vocês (choose well, vocês não podem mudar depois, a não ser que vocês façam outra conta!).

Treinando no TopCoder

Antes de participar de QUALQUER competição do site, sugiro que vocês treinem ao menos uma vez para entender o esquema da coisa. Entrem no site do topcoder (o que está acima), no menu da esquerda tem "competitions" – aí tem vários tipos de competição diferentes e, claro que eu encorajo vocês a fuçarem, mas a mais parecida com maratona é a de Algorithm, e aí tem dois tipos, o Single Round Match (que ninguém chama assim, as pessoas chamam de SRM) e o Marathon Match. Os dois são interessantes, mas o Marathon, como é mais longo, tem problemas bem mais fodas. De qualquer forma, vale a pena ler e pensar sobre.
O SRM é a competição tradicional dos maratonistas (não o Marathon - oh, the irony), então vamos começar por ele: abram o submenu e cliquem em "Launch Arena". Aqui começam as diferenças do topcoder: você tem que baixar e abrir esse applet Java para ler ou submeter qualquer problema, e participar em qualquer competição. Feito isso, vai ter uma tela de login, entre com seu handle e, se você estiver conectando do GRAD, use "Connection: HTTP Tunnel A" - lembre-se que o grad bloqueia todas as portas a não ser por HTTP e HTTPS, então o applet vai dar falha de conexão se vocês não fizerem isso…

Para treinar, vocês querem abrir o Practice Rooms, aí tem vários tipos de competição, vamos escolher os SRM – note que, para cada número de SRM, tem dois itens: SRMXXX Div 1 e SRMXXX Div 2. Isso tem a ver com o sistema de ranking do Topcoder – pessoas com pontuação maior que 1200 são Div. 1, o resto é Div. 2, mas isso só vale para competições rankeadas, no practice vocês podem treinar em SRMs Div. 1 (só tenham em mente que eles vão ser mais difíceis).
Cada SRM tem 3 problemas, independente da div, o fácil (geralmente 250), o médio (geralmente 500) e o difícil (geralmente 1000). Sugiro vocês começarem pelo fácil, para entender a lógica – eu escolhi o SRM 451 Div. 2 para esse exemplo, mas tanto faz. No menu escrito "Select One", escolha o primeiro (no meu caso, 250).
A janela do problema é dividida em partes:
1. Problem Statement, que é a descrição do problema em si;
2. Definition, aqui que é a parte diferente, a parte do Class, method, etc. Já explico isso
3. Constraints: os limites de cada variável no enunciado (vocês vão ficar surpresos como o TopCoder é rigoroso com isso!)
4. Examples, que é equivalente aos samples de maratona

Diferentemente da maratona, o TopCoder não pede para você ler do stdin e imprimir para o out – em vez, ele cria uma instância de uma classe definida por você, chama uma função específica e testa se o retorno daquela função está correto – por isso tem a parte definition, porque você deve garantir que o nome da classe, do método, parâmetros e etc, estão corretos - e é basicamente isso que vocês vão precisar saber de orientação a objeto para o TopCoder. Tá, então passo-a-passo:

1.1. Definição de uma classe (C++)

class nomeDaClasse {
   //aqui dentro vai o código relativo à essa classe
}; //não esqueçam essa droga desse ponto e vírgula! Isso é uma declaração (todas as declarações precisam de ponto-e-vírgula em C)!

1.2. Definição de uma classe (Java):
(alguém quer contribuir?)
1.3. Definição de uma classe (C#):
(alguém quer contribuir?)
1.4. Definição de uma classe (VB):
(alguém quer contribuir?)

2.1. Método de uma classe (C++)

class nomeDaClasse {
   int metodo1(float par1, char par2) {
      //aqui vai o código desse método, geralmente o que vocês vão fazer no topcoder
   }
   //ou, também é válido
   void metodo2(int par1);
};

void nomeDaClasse::metodo2(int par1) {
    //aqui vai o código do metodo2
}

Se vocês colocarem algum dos dois protótipos de método, ainda vai dar errado (há!), porque o default de classes é que métodos são private, ou seja, só podem ser chamados por métodos da própria classe; para um método ser chamável (haha, essa palavra nem existe, mas vocês entenderam) de fora da classe, ele deve ser public, o que significa, em código:
class nomeDaClasse {
   public: //tudo a partir daqui é public, a não ser que você diga o contrário, o que faz metodo1 e metodo2 serem public
   int metodo1(float par1, char par2) {
   }
   void metodo2(int par1);
};

void nomeDaClasse::metodo2(int par1) {
}

Se vocês querem saber mais de orientação a objeto em C++ (ou C++ em geral), por favor olhem o EXCELENTE site: http://www.learncpp.com; nunca tive uma dúvida em C++ que esse carinha não resolveu

2.2. Método de uma classe (Java):
(alguém quer contribuir?)
2.3. Método de uma classe (C#):
(alguém quer contribuir?)
2.4. Método de uma classe (VB):
(alguém quer contribuir?)

3.1. Strings e vetores (C++)

A partir daí, vocês sabem o suficiente para codar o problema 250 do SRM que eu escolhi (no Coding Area). Mas vocês não sabem o suficiente para codar todos, ainda, porque algumas vezes o TopCoder vai te passar string e vector de C++. O acesso a elementos desses objetos é idêntico ao seus amigos de C:

#include <string> //sem .h, é a classe string de C++
std::string a = "qualquer coisa";
a[i]='c'; //muda o i-ésimo caractere da string pra 'c' (exatamente como em strings de C)

Você pode comparar objetos da classe string com ==, ou seja, funciona como strcmp. Muito mais documentação pode ser encontrada aqui: http://en.cppreference.com/w/cpp/string/basic_string
std::vector<int> a; //cria um vector de inteiros
std::vector<float> v; //cria um vector de floats
std::vector<tipoQueVoceQuiser> b; //voces entenderam a ideia
//A unica coisa que vocês têm que tomar cuidado é vector de vector, porque >> é um operator em C++, então você TEM QUE dar o espaço:
std::vector<vector<int> > g;

O acesso é igual: a[i] é o i-ésimo elemento de a.
Mais doc: http://en.cppreference.com/w/cpp/container/vector

Nota importante 1: para ordenar uma string ou um vector, você tem que passar os iterators na função sort da algorithm, então fica mais ou menos assim:

#include <algorithm>
//codigo in-between

std::sort(a.begin(), a.end()); //nao vou explicar muito mais de iterators, se vocês quiserem, posso fazer um artigo só pra isso depois

Nota importante 2: para evitar todos os std::, vocês podem escrever antes do código de vocês "using namespace std" – isso geralmente é feito depois dos includes

#include <vector>
#include <stdio.h>
#include <math.h>
#include <string>
#include <algorithm>
using namespace std;

//aí podemos tirar todos os std::
string a = "qualquer coisa";
sort(a.begin(), a.end());
//etc...

3.2. Strings e vetores (Java):
3.3. Strings e vetores (C#):
3.4. Strings e vetores (VB):

4. Compilando e testando

O TopCoder tem um compilador próprio no applet, que está acessível por "Compile" no canto inferior direito; para testar em algum dos samples, clique em Test e o dropdown "Select Example…" tem todos os samples pré-digitados para você. Quando você tiver certeza que seu código está OK (ou seja, você testou ele nos samples e achou que está bom o suficiente), clique em Submit. Você vai ver sua pontuação para o problema, que é resultado de uma função de quantos pontos o problema tinha inicialmente com quanto tempo você demorou pra codar e submeter sua solução. Mesmo que mostre sua pontuação, o código ainda não foi testado (só você que testou, se você testou)!
Mais uma vez o TopCoder se diferencia da Maratona – no TopCoder, a bateria grande de testes só é rodada no final da competição (como vai ser descrito na parte de SRM), então para rodar seu código na bateria grande de testes, você precisa fechar a janela do problema (não se preocupe, uma vez que você submeteu, seu código está salvo), ir no menu superior, em Practice Options > Run System Test. Lá ele vai rodar o System Test (systest é mais comum entre os competidores) pros seus problemas daquele SRM - se ficar verdinho, o score do problema, o problema passou; vermelho é sinal que deu algum problema: ou seu código estourou o limite de tempo (muito bem definido como 2s sempre), deu resposta errada em algum caso ou deu runtime.
Se deu errado, você pode voltar, corrigir seu código e resubmeter o problema, mas lembre-se que isso tem um custo de 10% de penalidade (só vale pra competição, mas ele vai te avisar mesmo assim)

5. Olhando o código dos outros

Quando você está na sala de um SRM, você pode olhar o código de qualquer pessoa que submeteu aquele problema clicando em Summary e na pontuação do problema daquele cara (por exemplo, eu posso abrir o código do 250 do AxiomOfChoice clicando no 248.85 que alinha com o nome dele). Isso é legal para você ver as ideias e truques de outras pessoas para aquele problema; ainda, se você descobrir um caso de teste que quebra aquela solução, você pode tentar dar um Challenge, clicando no botão do canto inferior direito e digitando o caso de teste que você acha que vai dar errado.
Ah, e se você está se perguntando sobre o código de cores da tela de Summary, ele é referente à linguagem que aquele cara usou para resolver o problema – amarelo pálido é C++, verde é Java, azul é C# e eu nunca vi VB (haha).

6. Não sei resolver nada, e agora?

Se você não tem A MENOR IDÉIA de como resolver uma das questões, não se desespere, o TopCoder tem algo super legal – para cada competição, eles publicam, depois de um tempo, um editorial detalhado com a solução daquela questão e porque funciona, além de uma seleção de um código que implementa essa ideia particularmente bem. Esses editoriais estão no menu da esquerda em:
Algorithm > Single Round Match > Statistics > Match Editorials
Ou vocês podem abrir direto por aqui (haha): http://apps.topcoder.com/wiki/display/tc/Algorithm+Problem+Set+Analysis

SRM

Agora que você já conhece o esquema do TopCoder, já submeteu alguns problemas, passou metade deles, etc, você já está pronto para competir valendo! Primeiro de tudo, pra você não se assustar com o "valendo", me sinto na obrigação de te convencer que participar de SRMs rankeados é bacana pra você e pro seu treino:
1. Ao contrário da Maratona, é você com você mesmo, então te obriga a pensar em todos os problemas sozinho!
2. Como é rankeado, a preguiça de codar fica para segundo plano
3. Te acostuma mais com a pressão de durante a prova
4. Te dá questões fresquinhas pra pensar duas vezes por mês, de temas variados (o que é importante, pra quem está focando em conteúdos específicos)

Registration

Para cada SRM, você tem que se registrar até 10 minutos antes da competição, então abra o Arena com antecedência, procure o SRM que você quer se inscrever e clique em Register. Aí, só esperar o contest começar.

Coding Phase

Nessa parte, você tem 1h 15 para resolver os três problemas propostos, no mesmo esquema que foi falado na parte de treino, mas agora você só pode ver o código dos outros depois, então foque nas suas soluções, crie casos de teste, preste atenção nos limites e you're good to go. A pontuação continua funcionando da mesma forma que no Practice e lembre-se que seu código só vai ser testado no final (não existe Run System Test agora)!

Challenge Phase

Aqui você tem 15 minutos que você pode olhar o código dos outros e criar casos de teste que furam a solução dele – pense bem antes de fazê-lo, porque challenges errados de custam 25 pontos, mas se você está convicto, vá em frente, porque challenges certos te dão 50 pontos! Caso um competidor te dê um challenge, você perde todos os pontos referentes àquele problema.

System Test Phase

Essa é a parte do nervosismo, onde você espera a máquina testar seus códigos - não há muito o que fazer, só esperar e ver quão bem você ficou colocado na sua Div. Dependendo de como ficou o placar, você ganha ou perde pontos, o que faz você mudar de rating e ocasionalmente, de cor – são elas:
- Branco (Div 2): not rated
- Cinza (Div 2): [0,900)
- Verde (Div 2): [900,1200)
- Azul (Div 1): [1200, 1500)
- Amarelo (Div 1): [1500, 2200)
- Vermelho (Div 1): [2200, inf+)
No caso dos vermelhos, se você tiver pontuação igual ou superior a 3000, você vira target, que é um alvinho.

Tutoriais

O TopCoder paga para a galera escrever artigos sobre diversos temas, então eles têm uma coleção muito bacana de material em Tutorials. Os de algoritmo tem uns que são referência, como o de "Binary Indexed Tree" e o de "Range Minimum Query and Lowest Common Ancestor", mas vale a pena dar uma lida em todos que vocês tiverem interesse:
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=alg_index

Plugins

Você acha o editor de texto do topcoder uma bosta? Detesta ficar clicando nas coisas? Acha o compilador terrível? Muita gente é que nem você, por isso o TopCoder permite o uso de plugins para editores de texto – existem muitos, mas que eu lembro agora são dois:

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License