The present document can't read!
Please download to view
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
...

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

by alexandre-duarte

on

Report

Category:

Sports

Download: 0

Comment: 0

3,352

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   [email protected]
  • 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