TOPIC

C++: TLE. Como optimizar?

Daniel Koga asked 4 months ago

Primeiro eu tentei do modo óbvio, tomei as duas dimensões A e B da placa e as duas dimensões A e B do projeto e fiz as comparações:

Question solved. Code removed.

As duas duplas de teste são necessárias, pois o problema não explicita a orientação da placa e dos projetos. Num primeiro passo de optimização, é possível eliminar uma das duplas de teste se forçarmos a orientação. Dei uma pesquisada sobre e achei essa página com métodos para se calcular o mínimo e o máximo entre dois números sem usar testes:

https://www.geeksforgeeks.org/compute-the-minimum-or-maximum-max-of-two-integers-without-branching/

Usando ele, o código fica:

Question solved. Code removed.

Escrevi essa cadeia de variáveis ao invés de usar somente uma linha para evitar recálculos, afinal dXY é calculado 4 vezes e dXYSigned, duas.

Por fim, resolvi eliminar mais um teste fazendo algo simples. Ao invés de testar cada dimensão ordenada separadamente, testei as duas ao mesmo tempo, concatenando elas. Por exemplo, se as dimensões da placa são 4 e 12, as dimensões concatenadas (na base 10) seriam 1204. No meu código, fiz a concatenação em base binária e considerando que 64 = 2^6:

Question solved. Code removed.

E ainda continuo tomando TLE. Fiz uns testes usando o header chrono e uma entrada gigante de umas 10000 linhas e os resultados foram todos semelhantes, antes e depois de tudo isso e mesmo não usando nenhuma flag de optimização.

Alguém pode dar uma dica sobre o que posso explorar para realmente optimizar esse código?

This topic was solved and cannot recieve new replies.

  • feodorv replied 4 months ago

    Seems your TLE is due to the incorrect input reading.

  • Daniel Koga replied 4 months ago

    On point, Feodorv. Thank you!

    It seens the int I declared wasn't enough for 10^5 projects. Also, I redid the test (there were cases it couldn't handle correctly) and now I got it.