Tarefa 1: Linguagem e abordagem

Tarefa 1: Linguagem e abordagem

by Carlos Duarte do Nascimento -
Number of replies: 7
Professor/Monitor,

  Seguem duas dúvidas sobre a Tarefa 1:
  1. A página de envio de soluções do UVa Judge Online oferece quatro opções de linguagem: C, C++, Pascal e Java. Alguma delas é obrigatória / recomendada / discriminada / proibida, ou fica a critério do aluno?

  2. A forma com que o problema é apresentado sugere, a princípio, uma implementação "inocente": executar uma variação da rotina exibida (que meça o tamanho do ciclo) para cada inteiro entre i e j, guardando o maior valor.

    No entanto, há espaço para otimizações. Por exemplo: observando que qualquer número entre i e j que ocorra durante um ciclo não precisa ter seu próprio ciclo verificado (já que este é menor que o ciclo atual) podemos reduzir significativamente o número de ciclos a percorrer (à custa de espaço adicional para monitorar quais ciclos já foram descartados).

    A pergunta é: devemos nos preocupar com este tipo de otimização, ou basta um programa que execute a tarefa em tempo finito, seja aprovado pelo sistema e atenda aos critérios de legibilidade mencionados no enunciado?
Obrigado!
In reply to Carlos Duarte do Nascimento

Re: Tarefa 1: Linguagem e abordagem

by Rafael Schouery -
Não sou monitor, mas segue algumas considerações:

1. Não sei se o professor vai restringir linguagem, mas cuidado com Java. O Site não usa o sun-jdk, usa o gcj que é, até onde eu sei, o compilador gnu para java. Ouvir boatos sobre você ter que usar java até 1.1 apenas e existem outras restrições, imagino que principalmente sobre imports.

2. O UVa analisa também o tempo que seu algoritmo demora. Para esse exercício é no máximo 10 segundos. Ou seja, guloso normalmente não passa.

A moral da história é que não bastar dar a resposta. Existe um limite de tempo e memória para o programa. Cuidado também com suposições sobre a entrada e o formato da saída.

Espero ter ajudado.
In reply to Carlos Duarte do Nascimento

Re: Tarefa 1: Linguagem e abordagem

by Rafael Cosentino -
1. Não há restrições quanto a linguagem de programação. Porém quem quiser ser "legal" com o monitor pode fazer preferencialmente em Java ou C. Mas estejam a vontade para usar qualquer linguagem permitida pelo juiz. Realmente há algumas restrições no uso da linguagem Java, você não pode usar toda API do Java por exemplo (mesmo porque se pudesse ficava bem mais fácil resolver os problemas e não é exatamente isso que a gente quer... smile). Procurem as restrições no site do juiz.


2. Realmente o objetivo da tarefa 1 é que vcs aprendam a submeter para o juiz. Desde que o código seja legível, não tem problema se vcs fizerem uma implementação não tão trivial e mais otimizada para esta primeira tarefa.  Para as proximas tarefas, as soluções precisam ser otimizadas. Mesmo porque implementações ruins demais não passam pelo juiz.
In reply to Rafael Cosentino

Re: Tarefa 1: Linguagem e abordagem

by Sérgio Lopes -
Caramba, que encrencado fazer esse juiz aceitar Java hein! Os caras usam gcj MUITO velho (o último gcj consegue rodar até o Eclipse!).

Bom, o meu tá dando "Restricted Function". Devo estar usando algum método não permitido, mas ele não fala qual! Existe algum modo de saber o que é e o que não é permitido?

Eu estou usando as classes BufferedReader, InputStreamReader, InputStream, String, Integer... só. Alguma dessas não pode?!?

E os métodos: Integer.parseInt, String.substring, BufferedReader.readLine

Valeu!
In reply to Sérgio Lopes

Re: Tarefa 1: Linguagem e abordagem

by Rafael Cosentino -

Tem algumas informações sobre submeter código Java nestes links:

http://acm.uva.es/problemset/java.html

http://online-judge.uva.es/board/viewtopic.php?t=7429

Dá pra configurar o seu profile para que o juiz mande informações por email (mensagens de erro do compilador por exemplo). Não testei muito qual é o nível de informação que ele manda por email mas talvez ele informe qual as classes que estão sendo usadas que não são permitidas (precisa testar isso!).

http://acm.uva.es/problemset/editProfile.php

In reply to Rafael Cosentino

Re: Tarefa 1: Linguagem e abordagem

by Sérgio Lopes -
Eu já tinha visto esses links (esses são aqueles dois que tem no menu). Faltava um lugar que dissesse exatamente o que não está disponível sad

E eu já tinha pedido o envio de emails pelo juiz. Ele me mandou um email pouco explicativo. Não fala o que eu fiz de errado!

"Dear S:

Your program has tried to use a non allowed function (such as fopen(), system(),...). Remember that you only need to read from the standard input, to process and to write into the standard output (Note: all programs submited are logged in this system wink.

If you still are sure that you are using only standard functions, please contact the administrator."

In reply to Sérgio Lopes

Re: Tarefa 1: Linguagem e abordagem

by Carlos Duarte do Nascimento -
Sérgio,

  Eu abri mão do Java (era minha escolha preferencial, mas as possíveis diferenças - considerando o assunto estudado - são quase irrelevantes, e o par C/C++ parece ser o cidadão de primeira classe no UVa smile).

  Em C o programa deve usar apenas stdin/stdout. Meu palpite é que, em Java, isso se traduz em restringir apenas a System.in e System.out. Imagino que encadear um BufferedReader e um InputStreamReader no System.in para ler linhas da entrada, por exemplo, deva ser legal (mas aí vai do temperamento do juiz, e você já irritou ele não usando C wink).

  É difícil saber sem ver a mensagem mesmo (e esse tipo de coisa reforça a minha opção de abandonar o Java). De qualquer forma, se conseguir ver o erro, compartilhe conosco, e boa sorte!
In reply to Carlos Duarte do Nascimento

Re: Tarefa 1: Linguagem e abordagem

by Sérgio Lopes -
Eu submeti um programa que fazia só new BufferedReader() e ele recusou. O Juiz não aceita class auxiliares de I/O.

Agora ler a entrada com System.in.read() é suicídio. Isso aí devolve um byte (que, em Java, não é nem um char ainda!).

To pensando em fazer em C mesmo...

Aliás, achei uma outra universidade que tem um Juiz que aceita o mesmo problema: http://acm.pku.edu.cn/JudgeOnline/problem?id=1207
A interface é melhor, é mais rápido e eles rodam Java 5.