| Esta discussão foi arquivada. Não se pode acrescentar nenhum comentário. |
| | | 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.
|
| |
| | "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 |
| |
| |
| | É 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
|
| |
| | 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
|
| |
| | | É 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 |
| |
| |
| | É 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
|
| |
| | | 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 |
| |
| | 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
|
| |
| | 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
|
| |
| | | 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 |
| |
| | 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
|
| |
| | 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 |
| |
| | | 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
|
| |
| | 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
|
| |
| | | > 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 --------------- |
| |
| | | 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 |
| |
| | 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
|
| |
| | 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
|
| |
| | | 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
|
| |
