Técnicas de resolução da situação de Time Limit Exceeded de questões da maratona de programação

Abstract

RESUMO: A programação é a essência da computação. Um dos eventos que tem como cerne este conceito é a Maratona de Programação. O estudante de computação que participa do evento põe em prática importantes conceitos da computação, além de aguçar sua criatividade na resolução de problemas, e a capacidade de resolvê-los sob pressão. O objetivo não é apenas solucionar o problema, mas também solucionar de forma que passe na bateria de testes no tempo limite estabelecido. Quando o tempo limite é ultrapassado o juiz online responde TLE (Time Limit Exceeded). Este trabalho tem como objetivo apresentar soluções para evitar TLE. Problemas de nível fácil geralmente não requerem uma técnica avançada para que a solução passe na bateria de testes abaixo do tempo limite, porém problemas de nível médio e difícil, requer uma atenção na escolha do algoritmo a ser utilizado. Para testar as soluções apresentadas foi utilizado o beecrowd, um online judge, que é um site que possui os problemas de maratonas de programação anteriores e é possível submeter código/solução e verificar se a solução está correta ou não. Assim, é possível se estudar técnicas para evitar TLE, e uma melhor capacidade em pensar soluções rápidas e eficientes diante de desafios em programação.

ABSTRACT: Programming is the essence of computing. One competition with this concept as its core is the Programming Marathon. The computing student who participates in the event puts into practice important computing concepts, sharpening their creativity in problem-solving, and the ability to solve them under pressure. The goal is not only to solve the problem but also to solve it in a way that passes the battery of tests within the established time limit. When the time limit is exceeded the online judge responds TLE (Time Limit Exceeded). This work aims to present solutions to avoid TLE. Easy-level problems generally do not require an advanced technique for the answer to pass the battery of tests under the time limit, but medium and hard-level problems require attention in choosing the algorithm to be used. To test the presented solutions, beecrowd was used, an online judge, which is a site that has the problems of previous programming marathons and it is possible to submit code/solution and verify if the answer is correct or not. Thus, it is possible to study techniques to avoid TLE, and a better ability to think of fast and efficient solutions in the face of programming challenges.