Julio,
O problema de o Java ser considerado lento na maratona não tem a ver com a entrada? No TopCoder, por exemplo, nunca tive problemas com Java, enquanto que na Maratona (seja SPOJ ou UVa) não me dava muito bem com Java.
No TopCoder é um método. Então, na descrição do problema, ele dá a assinatura do método, não implicando em problemas de leitura de entradas muito grandes.
[quote=Andre Brito]Julio,
O problema de o Java ser considerado lento na maratona não tem a ver com a entrada? No TopCoder, por exemplo, nunca tive problemas com Java, enquanto que na Maratona (seja SPOJ ou UVa) não me dava muito bem com Java.
No TopCoder é um método. Então, na descrição do problema, ele dá a assinatura do método, não implicando em problemas de leitura de entradas muito grandes.[/quote]
entendi.
[quote=juliocbq][quote=Andre Brito]Julio,
O problema de o Java ser considerado lento na maratona não tem a ver com a entrada? No TopCoder, por exemplo, nunca tive problemas com Java, enquanto que na Maratona (seja SPOJ ou UVa) não me dava muito bem com Java.
No TopCoder é um método. Então, na descrição do problema, ele dá a assinatura do método, não implicando em problemas de leitura de entradas muito grandes.[/quote]
entendi.[/quote]
Podem existir problemas que a solução requer muito processamento. Daí pode não ser possível submeter em Java, mesmo com a algoritmo válido e feito da melhor forma possível, porque passa o tempo limite.
Tem alguns desses problemas que as respostas podem ser pré-calculadas e feito um código que seleciona uma dessas respostas para cada entrada… mas são poucos.
Uma dúvida: peguei a prova do ano passado e não vi nas questões a definição de um tempo limite, porém nas regras consta que se exceder o tempo limite o exercicio não é aprovado. Esse tempo limite é o mesmo para todas as questões? Ou então como fico sabendo o tempo limite de processamento de cada questão?
[quote=Adelar][quote=juliocbq][quote=Andre Brito]Julio,
O problema de o Java ser considerado lento na maratona não tem a ver com a entrada? No TopCoder, por exemplo, nunca tive problemas com Java, enquanto que na Maratona (seja SPOJ ou UVa) não me dava muito bem com Java.
No TopCoder é um método. Então, na descrição do problema, ele dá a assinatura do método, não implicando em problemas de leitura de entradas muito grandes.[/quote]
entendi.[/quote]
Podem existir problemas que a solução requer muito processamento. Daí pode não ser possível submeter em Java, mesmo com a algoritmo válido e feito da melhor forma possível, porque passa o tempo limite.
Tem alguns desses problemas que as respostas podem ser pré-calculadas e feito um código que seleciona uma dessas respostas para cada entrada… mas são poucos.[/quote]
Sim, mas esse lance de processamento não tem nada a ver. O que eu estou tentando passar é que java como uma “ferramenta” é 3x ou mais vezes robusto que um compilador de linguagem c porque inclui muitos recursos que o segundo não possui(não contando questões de linguagem). Novamente o hotspot torna a competição “desleal” entende?
para você ter uma idéia, o exemplo que dei acima sobre séries harmônicas levou 3 dias para eu conseguir otimizar(em c++) para competir com o mesmo java, e mesmo assim só chegou perto, não consegui bater.
Tenho experiência de 10 anos em c++ e linguagem c, e em Maratonas e Olimpíadas imagino que seja injusto comparar um código c com um java em questões de desempenho e em simples resolução de problemas(quem usa java tem o código otimizado automaticamente, não por mérito do programador). Porque?
Por causa do hotspot e por java ser uma linguagem de alto nível. Java e C são linguagens que alvejam pontos completamente diferentes.
Eu também acho injusto. Até porque o Garbage Collector é um excelente memory manager. E ele tem parte ativa no problema, cria gerações de objeto, faz processos em runtime.
É bem diferente do C, onde o malloc aloca memória e o free desaloca, sem qualquer tipo de checagem de runtime.
Não acho que seria justo comparar porque não se tratam de linguagens diferentes, mas sim, de plataformas diferentes.
[quote=ViniGodoy]Eu também acho injusto. Até porque o Garbage Collector é um excelente memory manager. E ele tem parte ativa no problema, cria gerações de objeto, faz processos em runtime.
É bem diferente do C, onde o malloc aloca memória e o free desaloca, sem qualquer tipo de checagem de runtime.
Não acho que seria justo comparar porque não se tratam de linguagens diferentes, mas sim, de plataformas diferentes.[/quote]
Sim, isso mesmo.
Algumas provas não tem. Outras tem. Me lembro que no SPOJ diz o tempo limite. Em geral, você não sabe. Tem que praticar o suficiente pra conseguir identificar trechos que comem tempo. A quantidade de “Time Limit Exceed”, vulgo TLE, já me deixou chateado muitas vezes. O algoritmo tem que estar correto e ser rápido (eliminar for, em alguns casos, for dentro de for é caixão).
[quote=Adelar][quote=juliocbq][quote=Andre Brito]Julio,
O problema de o Java ser considerado lento na maratona não tem a ver com a entrada? No TopCoder, por exemplo, nunca tive problemas com Java, enquanto que na Maratona (seja SPOJ ou UVa) não me dava muito bem com Java.
No TopCoder é um método. Então, na descrição do problema, ele dá a assinatura do método, não implicando em problemas de leitura de entradas muito grandes.[/quote]
entendi.[/quote]
Podem existir problemas que a solução requer muito processamento. Daí pode não ser possível submeter em Java, mesmo com a algoritmo válido e feito da melhor forma possível, porque passa o tempo limite.
Tem alguns desses problemas que as respostas podem ser pré-calculadas e feito um código que seleciona uma dessas respostas para cada entrada… mas são poucos.[/quote]
Pois é, mas como explicar o que acontece no TopCoder?
Acredito eu que seja mais problema na leitura das entradas do que no processamento em si. Ou algum problema de memória que pode estourar a memória alocada no servidor pro problema.
Memória é um problema sério para o Java. O Garbage Collector é rápido, mas também consome muito mais memória do que se pode fazer em C.
Algumas provas não tem. Outras tem. Me lembro que no SPOJ diz o tempo limite. Em geral, você não sabe. Tem que praticar o suficiente pra conseguir identificar trechos que comem tempo. A quantidade de “Time Limit Exceed”, vulgo TLE, já me deixou chateado muitas vezes. O algoritmo tem que estar correto e ser rápido (eliminar for, em alguns casos, for dentro de for é caixão).[/quote]
Nesse caso específico da Maratona de Programação ACM. Nas regras diz o seguinte:
“Para cada submissão o time recebe uma resposta, que pode ser satisfatória (e o problema está resolvido pelo time) ou indica algum erro ocorrido, como: resposta errada, tempo de execução excedido, erro de execução, erro de compilação, etc.”
Então, se eu participar da competição tenho que fazer o algortimo e mandar para a coordenação, ai ele vai me dizer se está no tempo de execução correto ou não? não tenho como prever isso durante a criação?
E depois que ele falar que o tempo excedeu, não ficarei sabendo quanto é esse tempo? É isso?
Algumas provas não tem. Outras tem. Me lembro que no SPOJ diz o tempo limite. Em geral, você não sabe. Tem que praticar o suficiente pra conseguir identificar trechos que comem tempo. A quantidade de “Time Limit Exceed”, vulgo TLE, já me deixou chateado muitas vezes. O algoritmo tem que estar correto e ser rápido (eliminar for, em alguns casos, for dentro de for é caixão).[/quote]
Nesse caso específico da Maratona de Programação ACM. Nas regras diz o seguinte:
“Para cada submissão o time recebe uma resposta, que pode ser satisfatória (e o problema está resolvido pelo time) ou indica algum erro ocorrido, como: resposta errada, tempo de execução excedido, erro de execução, erro de compilação, etc.”
Então, se eu participar da competição tenho que fazer o algortimo e mandar para a coordenação, ai ele vai me dizer se está no tempo de execução correto ou não? não tenho como prever isso durante a criação?
E depois que ele falar que o tempo excedeu, não ficarei sabendo quanto é esse tempo? É isso?[/quote]
Você manda e cada entrada é avaliada. Então é assim:
A partir daí, a resposta já volta pra você, como errada. Quando eu participava, não vinha nem a entrada que tinha estourado o tempo. O que eu conseguia ver era em quanto tempo o algoritmo era executado. Se desse TLE (Time Limit Exceed), mostrava quantos segundos havia levado. A única maneira de passar em TLE é resolvendo o problema da maneira correta e limpa. Resolver por resolver, qualquer um resolve. Mas resolver pra passar no tempo estipulado, aí é outra história. Por isso que um ponto principal nessas competições é Complexidade e Otimização, principalmente quando envolve Programação Dinâmica e Grafos, por exemplo.
Um exemplo, bem simples: fatorial. Voce tem que armazenar num array o que já foi calculado. Portanto, se a entrada for 10 e a próxima for 15, você não faz 15 * 14 * … * 3 * 2 * 1. Você faz 15 * 14 * 13 * 12 * 11 * o fatorial de 10 já guardado no array.
Outro exemplo bem básico: calcular números primos. Sem Crivo de Erastótenes não passa (vai dar TLE).
Para empolgar mais, recentemente dois ex-maratonistas do Centro de Informática da UFPE foram contratados pela Google, vide http://www2.cin.ufpe.br/site/lerNoticia.php?s=1&c=94&id=349 e http://www2.cin.ufpe.br/site/lerNoticia.php?s=1&c=94&id=352
C, C++ e Java.
Sim, porque todos os times possuem acesso às mesmas linguagens e APIs. Cabe a cada time escolher qual a linguagem utilizará no momento da submissão de cada problema, podendo alterar a linguagem a cada nova submissão se achar necessário.
É permitido levar quaisquer materiais impressos, por exemplo, livros, apostilas e trechos de códigos, porém não podem acessar Internet nem levar material magnético (pen drive e CD-ROM). Todo time que se preze possui um bom notebook (cadernos com rotinas prontas). Geralmente, utiliza-se C ou C++ por questão de cultura (da mesma forma que desenvolvedor ágil deveria utilizar Ruby e R. on Rails) e comodidade porque já há muito material escrito nestas linguagens.
A linguagem de programação termina sendo é irrelevante para os tipos de problema da maratona. A solução de um problema com um algoritmo ruim não será aceito, nem que o sujeito escreva o código em Assembly.
É a mesma: compara-se a saída gerada pela solução submetida com a solução esperada. Se as respostas forem iguais, a solução é aceita, senão rejeitada.
A informação está errada, porque o conjunto de testes é o mesmo, independente da linguagem de programação utilizada.
[quote=juliocbq][quote=Adelar]A questão por escolher Java ou C quando participávamos na maioria das vezes se encaixava em um dos critérios: se a necessidade fosse por velocidade era C ou se fosse por estruturas de dados complexas, era Java. O C++ seria mais ou menos um meio termo entre as duas.
[]'s[/quote]
C++ tem o mesmo nível da Java.
Mesmo assim não é tão justo não. O hotspot tem o jit para otimizar o código. Ou seja, pode ser 3 programadores x 1 programador se contar desempenho. Não estou criticando o evento não, é que sempre tive curiosidade de entender por que a competição não usa linguagens do mesmo nível. Ex:
C++ vs Java;
Java vs C#;
Java vs ObjectPascal;
python x ruby;
…
Digo isso porque já participei de algumas (á alguns bons anos) e ninguém da coordenação conseguiu me explicar isso.[/quote]
A linguagem de programação é irrelevante, porque é uma competição de projeto de algoritmos. Se você não utilizar um algoritmo que execute abaixo do limite de complexidade de tempo e memória máximo, não conseguirá ter sua solução aceita.
Escovar bits ou trocar a linguagem de programação não fará a complexidade de seu algoritmo sair de O(n!) para O(log n).
[quote=juliocbq][quote=Marky.Vasconcelos]
@topic
Eu sou elegivel para participar e ainda estou na faculdade, só falta um time para isso. =/[/quote]
Eu encararia uma olimpíada dessas mas já passei de ser elegível faz tem rsrsrsrs…
[/quote]
Sugiro as competições do TopCoder para você. Veja o site http://www.topcoder.com/tc.
[quote=Marky.Vasconcelos]
Chegar lá com uns algoritmos de busca inteligentes na ponta do dedo te dá uma grande chance de boa pontuação.[/quote]
Não é o suficiente. É preciso entender o problema, modelar a solução adequada e implementá-la, porque os problemas não são aplicações diretas de algoritmos clássicos na grande maioria dos casos. A parte mais fácil é a implementação em si.
[quote=Loiane]Para a maratona, aconselho altamente usar C ou C++.
Java só para usar para problemas com BigDecimal, BigNumber, etc.
Na maratona, Java perde muito em relação à performance e memória, por conta da orientação a objetos. E nesse tipo de contest, vai ser muuuuito raro precisar usar uma instância de uma classe criada. Programação “procedural” dá conta do recado numa boa.
Já teve caso de quando participei fazer o programa em java, não passar (resposta errada), aí tentamos em C (o mesmo algoritmo) e passou.
Bem, em todo caso, não custa ir sabendo C/C++. Se não der certo com um, tenta com outro! 
[/quote]
Deve ter sido lentidão com entrada e saída apenas.
[quote=juliocbq][quote=Loiane]Para a maratona, aconselho altamente usar C ou C++.
Java só para usar para problemas com BigDecimal, BigNumber, etc.
Na maratona, Java perde muito em relação à performance e memória, por conta da orientação a objetos. E nesse tipo de contest, vai ser muuuuito raro precisar usar uma instância de uma classe criada. Programação “procedural” dá conta do recado numa boa.
Já teve caso de quando participei fazer o programa em java, não passar (resposta errada), aí tentamos em C (o mesmo algoritmo) e passou.
Bem, em todo caso, não custa ir sabendo C/C++. Se não der certo com um, tenta com outro! [/quote]
A questão dos números de grande precisão podem ser resolvidos como o Andre falou (long long).
[/quote]
Tenta resolver estes dois problemas com long long 
É trivial e você ainda pode levar rotinas normalmente utilizadas por escrito.
Na Maratona, não fica sabendo O indicativo do limite de tempo pode sugerir o tamanho dos casos de teste e, principalmente, a complexidade da solução desejada.
De 2008 pra cá, posso afirmar que o tempo é o mesmo para todas as linguagens de programação. Muito provavelmente, sempre foi assim.