System is processing data
Please download to view
...

Olimpiadas Programação: O que, Por que e Como?

by alexandre-duarte

on

Report

Category:

Sports

Download: 0

Comment: 0

3,354

views

Comments

Description

Download Olimpiadas Programação: O que, Por que e Como?

Transcript

  • 1. Olimpíadas  de  Programação:   O  que,  Por  que  e  Como? Alexandre  Duarte   aalexandrend@gmail.com
  • 2. Agenda • O  que  é  uma  Olimpíada  de  Programação? • Por  que  parAcipar  ? • Como  parAcipar  ?– Regras– Preparação– Tipos  de  Problemas– Resolvendo  um  Problema
  • 3. O  que  é  uma  Olimpíada  de  Programação? 3
  • 4. O  que  é  uma  Olimpíada  de  Programação? • CompeAção  individual  ou  por  equipes – Um  único  computador  em  ambos  os  casos• ParAcipantes  recebem  um  conjunto  de  problemas   para  resolver  em  um  tempo  limitado• Vence  quem  resolve  o  maior  número  de  problemas   no  menor  tempo – Resolver  significa  apenas  produzir  a  saída  correta  para   um  determinado  conjunto  de  entradas!
  • 5. O  que  é  uma  Olimpíada  de  Programação?• É  um  exercício  de  criaAvidade  e  habilidade  para   trabalhar  sob  pressão• É  uma  compeAção!• É  uma  brincadeira!• É  uma  vitrine  para  você!
  • 6. Exemplo  de  Problema:  Alarme  de  Maria • Dados  a  hora  e  minuto  em  que  Maria  dormiu  e   a  hora  e  minuto  em  que  o  despertador  dela  vai   tocar,  calcule  a  quanAdade  de  minutos  de  sono   que  Maria  terá.EntradaSaída 1  5  3  5 12023  59  0  34 35 21  33  21  101417
  • 7. “Circuito  Mundial”  de  Olimpíadas  de  Programação • Olimpíadas  locais  para  escolher  equipes  para   as  regionais • Olimpíadas  regionais  para  escolher  equipes   para  as  nacionais • Olimpíadas  nacionais  para  escolher  equipes   para  a  final  mundial • Final  mundial... • Google,  Microso=,  Yahoo,  IBM,  Oracle,  etc.
  • 8. Situação  no  Brasil  em  2009• 46  sedes  regionais • 411  equipes  inscritas • 52  equipes  classificadas  para  a  Nacional– Incluindo  uma  equipe  da  UFCG • 5  equipes  se  classificarão  depois  de  amanhã   para  a  final  Mundial  na  China  – hbp://maratona.ime.usp.br/final09.html
  • 9. Regional  de  2009  (sede  UFCG)
  • 10. Regional  de  2009  (sede  UFCG)
  • 11. Regional  de  2009  (sede  UFCG)
  • 12. Regional  de  2009  (sede  UFCG)
  • 13. Situação  no  Mundo  em  2008•88  países   •1838  insAtuições •cerca  de  7100  equipes •100  equipes  classificadas  para  a  final  Mundial  
  • 14. Final  Mundial  de  2008  em   Estocolmo  -­‐  Suécia
  • 15. Final  Mundial  de  2008  em   Estocolmo  -­‐  Suécia
  • 16. Final  Mundial  de  2008  em   Estocolmo  -­‐  Suécia
  • 17. Final  Mundial  de  2008  em   Estocolmo  -­‐  Suécia
  • 18. I  Olimpíada  de  Programação  do  Litoral  Norte • CompeAção  individual  para  moAvar  os  alunos   a  formarem  Ames  para  treinar  e  representar  o   CCAE/UFPB  nas  regionais  de  2010 • 4  horas  de  duração • Prova  com  vários  (8  ou  mais)  problemas  de   diferentes  níveis  de  dificuldade • Pode-­‐se  uAlizar  qualquer  material  impresso – Livros,  algoritmos,  anotações,  etc...
  • 19. I  Olimpíada  de  Programação  do  Litoral  Norte • Duas  categorias– Iniciante  (apenas  para  alunos  matriculados  em  sua  primeira  disciplina  de  programação)– Avançado  (demais  alunos) • Premiação  para  os  três  primeiros  colocados  de   cada  categoria • Todos  os  parAcipantes  serão  convidados  a   parAcipar  de  um  treinamento  para  parAcipar  de   outras  olimpíadas  de  programação
  • 20. Por  que  devo  parAcipar  de  uma  Olimpíada  de  Programação?
  • 21. Por  que  devo  parAcipar  de  Olimpíadas  de  Programação? • É  diverAdo! • É  desafiador! • Empresas  (e  os  professores)  estão  sempre  de   olho  nos  alunos  que  parJcipam  deste  Jpo  de   compeJção!• Cuidado:  Pode  causar  dependência!
  • 22. ParAcipando  de  Olimpíadas  de  Programação  você  vai... • Viajar – conhecer  lugares  novos – conhecer  gente  nova • Se  relacionar  com  alunos  e  professores  de   outras  universidades – Networking • Aprender  algoritmos  e  técnicas  de  programação   que  provavelmente  não  veria  na  sala  de  aula
  • 23. Exemplo:  ACM  Interna+onal   Collegiate  Programming  Contest • Concurso  Internacional  de  Programação  para   Estudantes  Universitários– Olimpíadas  Regionais  e  Nacionais  Brasileiras  são  seleAvas  para  este  evento.– 5  Ames  do  Brasil  se  classificam  para  a  mundial • Patrocinado  pela  IBM • Finalistas  geralmente  são  contratados  por   empresas  como  Google,  Microsom,  Oracle,  IBM,   etc.
  • 24. Exemplo:  Google  Code  Jam• Concurso  de  programação  via  web  promovido   pela  Google • No  próprio  formulário  de  inscrição  eles  já   perguntam  se  você  teria  interesse  em  trabalhar   na  Google  e  em  qual  sede  gostaria  de  ficar • Finalistas  vão  para  Mountain  View– Prêmios  em  dinheiro  até  o  25o  lugar– 1o  Lugar  leva  U$5000,00
  • 25. Exemplo:  TopCoder • Site  com  concursos  periódicos  de  programação   patrocinados  por  diversas  empresas  (Google,   Yahoo,  etc) • Distribui  prêmios  em  dinheiro  para  os   parAcipantes • Várias  empresas  procuram  talentos  nos   rankings  do  TopCoder
  • 26. Como  ParAcipar?26
  • 27. Pré-­‐Requisitos • Gostar  de  Programar • Gostar  de  Programar • Saber  programar  em  alguma  linguagem• Para  OPLN:  Pascal,  C/C++  ou  Java• Gostar  de  Programar • Gostar  de  Programar27
  • 28. Regras • O  parAcipante  recebe  um  caderno  com  as  questões  da   prova • O  objeAvo  é  resolver  o  maior  número  de  questões  no   menor  tempo  possível • O  parAcipante  escolhe  um  dos  problemas  que  ainda   não  resolveu,  preferencialmente  o  mais  fácil,  e  escreve   um  programa  que  produz  a  saída  especificada  no   enunciado  do  problema • É  preciso  obedecer  ao  pé  da  letra  os  formatos  de   entrada  e  saída  especificados  no  problema28
  • 29. Exemplo:    Alarme  de  MariaEntrada: 1  5  3  523  59  0  3421  33  21  10 Saída: Saída: Saída: Saída:12  35  1417 Minutos  =    12 12.0 12Minutos  =  35   35.0   35Minutos  =  1417 1417.0 1417 29
  • 30. Entrada  e  Saída • Os  dados  de  entrada  são  sempre  lidos  do  teclado  (entrada   padrão)– Pascal:  read,  readln,  etc– C:  scanf,  getchar,  etc– C++:  cin,  scanf,  getchar,  etc– Java:  java.uAl.Scanner    -­‐  Não  usar  JOpJonPane! • Os  dados  de  saída  são  sempre  impressos  na  tela  (saída  padrão)– Pascal:  write,  writeln– C:  prinv– C++:  cout,  prinv– Java:  System.out.print,  System.out.println30
  • 31. Correção • Quando  o  parAcipante  achar  que  resolveu  o   problema  ele  submete  a  solução  para  correção   por  um  juiz • O  juiz  corrige  a  solução  e  retorna   imediatamente  uma  resposta • A  correção  é  feita  de  forma  automáJca  – A  saída  precisar  seguir  a  especificação  do  problema– Os  limites  do  problema  serão  testados31
  • 32. Respostas  do  Juíz • Correto • Incorreto • Erro  de  execução • Erro  de  compilação • Limite  de  tempo  excedido32
  • 33. Pontuação • Duas  métricas:– Número  de  problemas  resolvidos  (P)– Tempo  em  minutos  gastos  para  resolver  os  problemas  (T) • Quando  o  parAcipante  resolve  um  problema:– P  =  P  +  1– T  =  T  +  tempo  desde  o  início  da  prova  +  Penalidade– Penalidade  =  x  *  20,  onde  x  é  o  número  de  tentaAvas  incorretas  para  resolver  este  problema!33
  • 34. Pontuação • Todo  problema  tem  uma  entrada  e  uma  saída  de  exemplo– Não  se  iluda,  o  juiz  vai  testar  sua  solução  com  muitas   outras  entradas; • Evite  enviar  a  solução  precipitadamente.  – 5  minutos  testando  sua  solução  é  melhor  do  que  20   minutos  de  penalidade; • A  maioria  dos  problemas  possuem  cascas  de  bananas– É  preciso  testar  a  solução  antes  de  submeter– Testar  os  limites  descritos  no  problema 34
  • 35. Preparação:  Treinar  para  que  se  eu  já  sei  o  que  fazer? 35
  • 36. Preparação:  O  segredo  é  treinar!36
  • 37. Como  Treinar?• PraJcar  com  problemas  de  outras  olimpíadas • Juízes  online– SPOJ:  br.spoj.pl– Programming  Challenges:  programming-­‐challenges.com– Universidade  de  Valladolid:  uva.onlinejudge.org 37
  • 38. Como  Treinar?• ParJcipar  de  fóruns  e  grupos  de  discussão • Todo  site  de  juiz  online  têm  um  fórum  onde  os  parAcipantes   discutem  como  resolver  os  problemas  propostos • É  legal  primeiro  tentar  resolver  o  problema  e  só  recorrer  ao   fórum  ao  chegar  num  beco  sem  saída • Opções  em  Português– hbps://br.spoj.pl/forum/– hbp://groups.google.com/group/algoritmos-­‐ccae38
  • 39. Preparação• Livros  são  importantes!– Programming  Challenges  (Steven  S.  Skiena  e  Miguel  A.  Revilla)– IntroducAon  to  Algorithms  (Thomas  H.  Cormen,  Charles  E.  Leiserson,  Ronald  L.  Rivest)– The  Art  of  Computer  Programming,  Volume  1:  Fundamental  Algorithms  (Donald  E.  Knuth)– The  Art  of  Computer  Programming,  Volume  3:  SorAng  and  Searching  (Donald  E.  Knuth) 39
  • 40. Tipos  de  Problemas • Triviais:    ordenação,  fórmulas  matemáAcas,  números   primos,  fibonacci,  strings,  ... • Geometria:  Interseção,  distância,  polígonos,  pontos,  ... • Grafos:  busca  em  largura  e  profundidade,   conecAvidade,  menor  caminho,  cobertura,  fluxo   máximo  e  mínimo,  ... • OAmização:  mochila  binária,maior  subsequência   comum,  ... • Ad-­‐hoc:  Simulação  de  jogos,  ...40
  • 41. Exemplos  de  Problemas:  Triviais • Ordenação  por  NotaExemplo  de  Entrada Exemplo  de  Saída5 1  -­‐  JoãoPedro  8.3 2  -­‐  MarcusMarcus  9.1 3  -­‐  LeonardoJoão  10.0 4  -­‐  PedroAlysson  5.0 5  -­‐  AlyssonLeonardo  8.5 41
  • 42. Exemplos  de  Problemas:  Triviais • Quantos  números  primos  existem  em  um   intervalo? Exemplo  de  Entrada Exemplo  de  Saída 2  9 48  1737  11242
  • 43. Exemplos  de  Problemas:  Ad  Hoc • Mutant  Flatword  Explorers Exemplo  de  EntradaExemplo  de  Saída5311ERFRFRFRF11E32N 3 3 N LOSTFRRFLLFFRRFLL 23S03WLLFFFLFLFL43
  • 44. Exemplos  de  Problemas:  Grafos • Dado um conjunto de cidades e um conjunto de rodovias onde cada rodovia liga duas cidades, crie um programa que compute o menor caminho entre duas cidades. Exemplo  de  Entrada Exemplo  de  Saída2Patos CampinaGrande 170 290CampinaGrande JoaoPessoa 1201Patos JoaoPessoa44
  • 45. Exemplos  de  Problemas:  Geometria • Interseção de retângulosExemplo  de  EntradaExemplo  de  Saída 1336 2334 2 1 11 445
  • 46. Resolvendo  um  Problema  de   Olimpíada • Feynman: http://br.spoj.pl/problems/FEYNMAN/46
  • Fly UP