gildot

Topo
Sobre
FAQ
Tópicos
Autores
Preferências
Artigos
Sondagens
Propor artigo


8/3
gildicas
9/30
jobs
10/9
perguntas
10/25
press

 
SWERC'2002 - Concurso Internacional de Programação
Contribuído por js em 19-11-02 19:08
do departamento E-o-vencedor-é...
News Realizou-se este fim de semana (e pelo segundo ano consecutivo) na Universidade do Porto a eliminatória do sudoeste da Europa do concurso de programação do ACM - SWERC 2002.
Os vencedores terão acesso à final a realizar na California, USA. A China e os países de leste têm ganho consistentemente a prova a nível mundial ao longo dos anos. Será que a língua é a única barreira a impedir o aparecimento de software oriundo destes lados?
Em relação às equipas lusitanas, a equipa de Ciências da UP ficou em 1º, seguida de Aveiro e o IST.

[js: Nenhum dos duendes de serviço publicou a notícia do evento, que nos foi simpaticamente enviada no passado dia 15. Agora já vai tarde mas, à laia de pedido de desculpas, aqui fica ela. E já agora não passem sem ver uns problemas para resolver!]

WhiteShadow escreveu: "

É já nos próximos dias 16 e 17 de Novembro que se realiza na Universidade do Porto um concurso internacional de programaçao para alunos universitários, SWERC'2002 (Southwestern Europe ACM Regional Programming Contest) de qualificaçao para as finais mundiais que terão lugar em Março de 2003 em Beverly-Hills, Califórnia.

O SWERC consiste numa prova em que o objectivo é resolver o maior número de problemas no menor tempo possível, usando C, C++, java ou Pascal. Habitualmente, sao propostos 9 problemas para serem resolvidos em 5 horas por equipas com no máximo 3 elementos. A prova destina-se a alunos de cursos de licenciatura e visa estimular nos alunos o gosto e a criatividade na resoluçao, rápida e eficiente, de problemas, o desenvolvimento de capacidades de trabalho em equipa, assim como promover o convívio entre jovens de vários países com interesses científicos e profissionais próximos.

Ao todo, estarão no Porto 54 equipas de 6 países: 18 portuguesas, 13 espanholas, 10 alemãs, 7 francesas, 4 italianas e 2 suíças. De Portugal vêm equipas das principais escolas de informática: Universidade do Minho, Universidade do Porto (Faculdade de Ciências e Faculdade de Engenharia), Instituto Superior de Engenharia do Porto, Universidade de Aveiro, Universidade de Coimbra, Instituto Superior de Engenharia de Coimbra, Instituto Superior Técnico, Universidade de Évora e a Universidade Nova de Lisboa.

Mais informação sobre a prova poderá ser consultada no site oficial do swerc'2002.

A prova real será no dia 17, das 10:00 às 15:00, e será possível participar na prova pública, que decorrerá ao mesmo tempo, com os mesmos problemas. Experimentem participar !

De notar que em Outubro se tinha realizado o MIUP'2002 (Maratona Inter-Inoversitária de Programação), na FCUL, o "equivalente" nacional ao SWERC, com a participação de 33 equipas. Os vencedores foram a equipa Virtuais, da Faculdade de Ciências da Univ. Porto, que também já tinham vencido o MIUP'2001. De notar que esta equipa também foi a responsável pela melhor classificação de sempre de uma equipa portuguesa num SWERC, nomeadamente o 2ºlugar no SWERC'2000 (que na altura não chegou para passar à final). "

Formação Linux - Lisboa | O Super Bug  >

 

gildot Login
Login:

Password:

Referências
  • problemas para resolver
  • WhiteShadow
  • site oficial do swerc'2002
  • prova pública
  • MIUP'2002
  • SWERC 2002
  • vencedores
  • final
  • longo dos anos
  • Ciências da UP
  • Aveiro
  • IST
  • Mais acerca News
  • Também por js
  • Esta discussão foi arquivada. Não se pode acrescentar nenhum comentário.
    China. (Pontos:2)
    por leitao em 19-11-02 21:26 GMT (#1)
    (Utilizador Info) http://scaletrix.com/nuno/
    Será que a língua é a única barreira a impedir o aparecimento de software oriundo destes lados?

    Nao -- tem mais a ver com uma falta geral de "entrepreneurship" e condicoes sociais/economicas.


    "Monogamy is for guys that can't get pussy." --Steve-O.

    Criatividade!! (Pontos:2)
    por GdoL em 20-11-02 10:51 GMT (#2)
    (Utilizador Info) http://www.gazetadolinux.com
    "A prova (...) visa estimular nos alunos o gosto e a criatividade na resolução, rápida e eficiente, de problemas, o desenvolvimento de capacidades de trabalho em equipa, (...) "
    Nesta frase está resumido o porque dos concorrentes lusitanos em geral nunca ficarem muito bem qualificados. O ensino nas faculdades ainda está muito virado para a não descoberta e repetição "ad nauseam" dos mesmos esquemas de raciocínio.

    eBoX:email

    Leiam a Linux Gazette

    Não é bem assim... (Pontos:2)
    por CrLf em 20-11-02 16:24 GMT (#4)
    (Utilizador Info) http://crodrigues.webhop.net
    É verdade que o ensino nas faculdades em geral não potencia a liberdade de raciocínio mas não foi por isso que os portugueses não ficaram bem classificados. Nestas provas (a nivel internacional) os portugueses ainda têm pouca experiência pelo menos quando comparados com por exemplo a equipa que ganhou onde um dos seus elementos é o primeiro do ranking da Univ. de Valladolid com 865 problemas feitos em apenas um ano (não me parece que tenha vida própria...). A este gajo é dificil apresentar um problema que não seja idêntico a algum que ele já tenha feito.

    Por outro lado os problemas destes concursos beneficiam mais o conhecimento de alguns algoritmos do que a engenharia da resolução de problemas, até porque muitas vezes quem fica melhor classificado foi quem resolveu os problemas com métodos ingénuos de força bruta (não estou a dizer que não tenham mérito, é verdade).

    -- Carlos Rodrigues
    Re:Não é bem assim... (Pontos:2)
    por CrLf em 20-11-02 18:38 GMT (#14)
    (Utilizador Info) http://crodrigues.webhop.net
    Não será bem assim, já que de um conjunto de 9 problemas a equipa vencedora "apenas" (é o normal) resolveu 4.

    Essa mesma equipa participou no parte pública do MIUP e resolveu 8 dos 9 problemas (ok que tinham a prossibilidade de usar mais recursos -- mais máquinas, documentação -- do que os participantes locais). 4 problemas não é normal na equipa que venceu.

    Também não corresponde à verdade já que os programas têm um tempo limitado para apresentar a solução... e sim, os organizadores sabem fazer problemas que pela força bruta não se vai lá... ;-)

    Óbviamente que alguns problemas não podem ser resolvidos à força bruta mas acredita que muitos sim (tipo fazer comparações sucessivas num array de char* em vez de usar um hash_map da STL -- que até se faz com menos linhas de código). Neste tipo de concursos muitas vezes compensa arriscar ir por uma solução estúpida do ponto de vista da elegância e ineficiente mas simples de imaginar porque muitos testes têm um tempo limite suficiente para isso.

    Dou como exemplo o problema de entrada do repositório de Valladolid. Não é incomum para quem tenha alguns conhecimentos de programação e goste de fazer as coisas como deve ser resolver este problema recorrendo a alguma técnica (que até nem é nada complicada) que guarde os cálculos já efectuados para acelerar o processo. Na realidade este problema pode ser resolvido com força bruta pura e nem sequer chega próximo do limite de tempo imposto.

    Mas atenção, como disse no post anterior não estou a dizer que as soluções de força bruta nestes casos sejam menos válidas do que qualquer outras (se fosse para resolver problemas do mundo real já não seria bem assim).

    -- Carlos Rodrigues
    Dificeis!! (Pontos:2)
    por cgd em 20-11-02 12:59 GMT (#3)
    (Utilizador Info)

    É pena não ter havido disto no meu tempo (acho que não havia...)

    Dei uma olhadela a dois problemas apenas: o dos intervalos e o das familias (de monstros).

    O dos intervalos nao percebi bem no inicio (será da velhice?!), e depois de perceber, não o consegui resolver (definitivamente é velhice!). Vou pensar melhor nesse.

    O das familias era +/- facil.


    struct r { int p1,p2; };
    struct r r[300];

    float rel(int a,int b)
    {
      if (a==b) return 1;

      if (r[a].p1 == -1 && r[a].p2 == -1) { /* a is parent */
        int c=a; a=b; b=c;
        if (r[a].p1 == -1 && r[a].p2 == -1) /* both are parents */
          return 0;
      }

      float rl=0.0;
      if (r[a].p1 == b)
        rl += 0.5;
      else if (r[a].p1 >= 0 && r[a].p1 != a)
        rl += rel(r[a].p1, b) / 2;

      if (r[a].p2 == b)
        rl += 0.5;
      else if (r[a].p2 >= 0 && r[a].p2 != a)
        rl += rel(r[a].p2, b) / 2;

      return rl;
    }

    #define R() if (scanf("%d", &x)==0) {printf("bad input"); return 1;} else
    main()
    {
      int i,x,k,n,m;

      for (i=0;i<300;i++)
        r[i].p1 = r[i].p2 = -1;

      R(); n=x;
      R(); k=x;
      for (i=0;i<k;i++) {
        int ix=0;
        R(); ix=x-1;
        R(); r[ix].p1 = x-1;
        R(); r[ix].p2 = x-1;
      }
      R(); m=x;
      for (i=0;i<m;i++) {
        int a,b;
        R(); a=x-1;
        R(); b=x-1;
        printf("%g%%\n", 100*rel(a,b));
      }
    }

    Vou ver se dou uma olhadela nos outros com + tempo...


    -- carlos

    Errrmm... (Pontos:2)
    por CrLf em 20-11-02 16:42 GMT (#5)
    (Utilizador Info) http://crodrigues.webhop.net
    É pena não ter havido disto no meu tempo (acho que não havia...)

    Em Portugal não sei mas os concursos da ACM existem desde 1970.

    O dos intervalos nao percebi bem no inicio (será da velhice?!), e depois de perceber, não o consegui resolver (definitivamente é velhice!). Vou pensar melhor nesse.

    Não é da velhice, depois de falar com outros participantes chegámos todos à conclusão que era um bocado estranho.

    O das familias era +/- facil.

    Quando não se tem 9 problemas para fazer em 5 horas parecem mais fáceis é verdade... Mas agora resta saber se passaria nos testes deles (talvez o possas testar quando for colocado no online judge da Univ. de Valladolid).

    O maior problema destes concursos é quando se resolvem problemas que dão resultados certos para todos os testes que lhes atiramos e depois quando se submetem o Mooshak retorna Wrong Answer sem dar absolutamente razão nenhuma (porque é mesmo assim). A minha equipa teve alguns nessa situação... ainda estou para perceber porquê...

    Quanto à dificuldade dos problemas foi consensual que eram mais manhosos do que os do ano passado (onde não participei) e do que os da MIUP. Ainda houve alguns problemas como por exemplo um erro no output do problema H que despistou toda a gente e que obrigou a prolongar o prazo da prova por mais meia hora (seja como for estas coisas acontecem e não é por isso que a organização não deixa de estar de parabéns).

    -- Carlos Rodrigues
    Re:Errrmm... (Pontos:2)
    por cgd em 20-11-02 17:12 GMT (#6)
    (Utilizador Info)

    Quando não se tem 9 problemas para fazer em 5 horas parecem mais fáceis é verdade...

    Pelo que eu li, eram equipas de 3 elementos. Dá tres problemas a cada um (se forem feitos individualmente) o que dá cerca de 1h40 por cada problema. Eu resolvi o das familias em cerca de 10 minutos, pensei cerca de 15 no outro e desisti (por ora!). Portanto, nao é uma questao de parecer facil...


    -- carlos

    Context matters (Pontos:2)
    por CrLf em 20-11-02 17:45 GMT (#7)
    (Utilizador Info) http://crodrigues.webhop.net
    Sim, mas só há um computador por equipa, e quando se está relaxado em casa a resolver problemas consegue-se resolver problemas mais difíceis em menos tempo (trust me on this) pois não se tem limite de tempo nem o burburinho de uma data de gente em background e nem sequer se é penalizado por cada submissão que não funcione. Por outro lado, e como referi, muitas vezes as soluções aparentam estar correctas e são rejeitadas pelo sistema (pormenores nem sempre óbvios que escapam) ou demoram mais tempo que o permitido, ou usam mais memória que o permitido. Outra coisa importante é a tendência para estar a pensar em vários problemas em simultâneo o que não ajuda.

    De fora parece fácil mas lá no local existem muito mais variáveis que influenciam o desempenho do que a simples dificuldade dos problemas.
    Por isso é que me referi aos problemas deste ano como mais manhosos e não como difíceis.

    Resumindo é mais ou menos como quando se sai de um exame e se analisam as perguntas que nos pareciam complicadas e pensamos "ishhh... que burro que sou, isto era tão fácil...".

    -- Carlos Rodrigues
    Re:Context matters (Pontos:2)
    por CrLf em 20-11-02 17:56 GMT (#8)
    (Utilizador Info) http://crodrigues.webhop.net
    Já agora só para que fique claro (just in case), os problemas têm que passar a 100% nos testes do sistema (quer na validade da solução como em não exceder a memória ou tempo limite), caso contrário são rejeitados e adicionam uma penalização de 20 minutos por rejeição, não há pontuação intermédia como por exemplo penso que existe nas olimpíadas de informática. Isto tem a ver com o que disse acima na medida em que muitas vezes se perde tempo a verificar que o problema está realmente bem resolvido e que não há possibilidade de apanhar com algum caso especial nos testes do sistema, já para não dizer que cada wrong answer que se apanha em problemas que estamos convencidos que estão a funcionar na perfeição não ajudam nada ao moral das tropas :).

    -- Carlos Rodrigues
    Re:Context matters (Pontos:2)
    por cgd em 20-11-02 18:28 GMT (#12)
    (Utilizador Info)

    ah! pareceu-me simplesmente que estavas a deitar abaixo.

    o factor silencio é importante, embora (shame on me) resolvi isto no trabalho que (infelizmente) não é propriamente sossegado.

    claro pá, sob pressão as coisas sao mais complicadas, alias, parecem. simplesmente tinha dito que aquele problema nao parecia complicado em relacao ao outro. eu só vi mesmo o enunciado de dois (nao quero estragar a surpresa :) e o dos intervalos parecia bem puxadinho-- a coisa que me ocorreu era marcar num array todas as posicoes dos intervalos em que ci == bi-ai+1 (ou seja todos os elementos desse intervalo vao ter que estar presentes) e com os restantes intervalos, encontrar recursivamente a solucao minima em bi-ai+1 - ci + 1 combinacoes! mas isso pode demoraaaaaaaaaaaaar e parece-me haver aqui uma dupla recursao... face a isto, um varrimento de uma arvore binaria parece simples :)

    got it?


    -- carlos

    Re:Context matters (Pontos:2)
    por CrLf em 20-11-02 18:45 GMT (#16)
    (Utilizador Info) http://crodrigues.webhop.net
    ah! pareceu-me simplesmente que estavas a deitar abaixo.

    Não estava a deitar abaixo estava simplesmente a falar da minha experiência pessoal.

    -- Carlos Rodrigues
    Re:Errrmm...10 minutos ??? (Pontos:1)
    por LostStar em 20-11-02 21:27 GMT (#19)
    (Utilizador Info)
    Eu olhei para ele varios 10 minutos em todas as 5 horas e sempre me pareceu chines autentico...
    Tambem escolheste os mais estranhos para tentar fazer...
    E' claro que pode ser por me trazer velhos traumas de redes de bayes (ou qq coisa parecida).
    Vou ver se entendo o teu codigo , pode ser que consiga ver a luz :)



    ------------------------------------------
    "You got to make it right this time, 'cause this time is all you have."
    prot , in K-PAX
    Re:Errrmm...10 minutos ??? (Pontos:2)
    por cgd em 21-11-02 11:12 GMT (#20)
    (Utilizador Info)

    eheh

    Bom, por acaso escolhi-os apenas pelo nome.

    O dos intervalos parecia facil no inicio: corrias os extremos (maximos e minimos) com o c somado/subtraido a cada um. Essa solucao funciona a nivel dos extremos (eu fiz o boneco), mas o proprio exemplo nao funcionava. O problema é que o conjunto pedido era o minimo, e pode-se minimizar esse conjunto com alguns buracos no meio... como se descobrem esses buracos é que é o caraças: ou se constroem varios sets recursivamente, ou constroi-se um e tentam-se pôr buracos de satisfacao recursivamente (?).

    Mas nao voltei a pensar muito nesse. Ontem à noite resolvi os tres primeiros (comecei por ordem).


    -- carlos

    Re:Errrmm... (Pontos:2)
    por CrLf em 20-11-02 18:41 GMT (#15)
    (Utilizador Info) http://crodrigues.webhop.net
    E apresentava os resultados correctos com os dados de exemplo que eles dão?

    Sim, caso contrário estaria óbviamente errado e não subtilmente errado ;). Apenas referi isso para mostrar que não recebemos ajuda nenhuma por parte do sistema acerca do que possa estar errado ou acerca do que falhou nos testes.

    -- Carlos Rodrigues
    Re:Dificeis!! (Pontos:1)
    por WhiteShadow em 20-11-02 18:11 GMT (#9)
    (Utilizador Info) http://www.dcc.fc.up.pt/~pribeiro/

    > O das familias era +/- facil

    Bem, quanto a isso só tenho de te dizer que TU achas que o teu código está certo. Mais de 80% das submissões não foram aceites, e não acredito que as equipas submetam sem acharem que têm a solução correcta (e sem resolver o caso exemplo).

    Por isso digamos que tens uma hipótese de resolução que pode ou não estar correcta (não estou a dizer que não está !)

     
    --------------- "Truth suffers from too much analysis." - Ancient Fremen Saying ---------------

    Re:Dificeis!! (Pontos:2)
    por cgd em 20-11-02 18:36 GMT (#13)
    (Utilizador Info)

    Bom, na realidade EU NEM sequer acho que o meu código esteja certo. Let's face it: fiz isto em cerca de 10 minutos, testei com o exemplo do enunciado e a rel() nem me parece totalmente logica... e se calhar até é capaz de estar certo :-)

    Mas so what? Eu fiz um comentário e inclui algum codigo. Nao consigo perceber tanta animosidade por causa disto...


    -- carlos

    Re:Dificeis!! (Pontos:2)
    por CrLf em 20-11-02 18:47 GMT (#17)
    (Utilizador Info) http://crodrigues.webhop.net
    Nao consigo perceber tanta animosidade por causa disto...

    Não me parece que haja aqui animosidade (pelo menos não no sentido de malhar na cabeça) são só comentários (pelo menos da minha parte).

    -- Carlos Rodrigues
    Já agora... (Pontos:2)
    por CrLf em 20-11-02 18:51 GMT (#18)
    (Utilizador Info) http://crodrigues.webhop.net
    Para quem estiver nessa onda e não tiver nada de mais excitante para fazer e/ou quiser exercitar as suas capacidades programativas (quase que aposto que a palavra não existe) vai haver um concurso online dentro de dois dias aqui.

    -- Carlos Rodrigues
    Resoluções (hipoteses de...) (Pontos:2)
    por cgd em 21-11-02 11:26 GMT (#21)
    (Utilizador Info)

    Fiz resoluções dos problemas A, B e C (ontem à noite) e já tinha o E (ontem de manha).
    Se alguem quiser ver o meu codigo/solucoes, envie mail para carlos.gameiro@corp.vodafone.pt (bom, basicamente porque nao tenho pagina web :)
    nota: por razões de ordem técnica (cof cof) a partir de hoje à tarde até segunda não tenho acesso a mail/internet. até à hora de almoço estou por cá ...


    -- carlos

     

     

    [ Topo | Sugerir artigo | Artigos anteriores | Sondagens passadas | FAQ | Editores | Preferências | Contacto ]