TOPIC

PROBLEM 1712 - URI Fórum 1.0

URI Online Judge asked 6 years ago

URI Online Judge Fórum 1.0

MOD

This topic was solved and cannot recieve new replies.

  • Altamir Gomes Bispo Junior replied 6 years ago

    A simulação por força bruta é cabível. Uma maneira de cortar processamento inútil é calcular a média de todos os quadrados e passar batido por aqueles cujo valor é menor do que ela. Repare que a média dos quadrados da melhor solução é sempre igual a ou maior do que a média de todos os quadrados, o que por sua vez significa que a solução necessariamente possui pelo menos um quadrado com valor igual a ou maior do que a média, mas não necessariamente quadrados com valores menores do que a mesma.

    O registro de todos os padrões de formas não surpreendentemente também pode ser feito através de força bruta. Sem cortes de processamento, a complexidade de espaço se torna fatorial no valor de M, inviabilizando o processo. Mas se informação redundante a respeito dos registros já gravados for eliminada, o processo se torna eficiente.

  • Im Olek replied 6 years ago

    I could not pass .. I tried implementing a BFS for all possibilities. A thorough search briefly, give me TLE.

    Some who went told me that the idea was as follows: -> Generate and store all the M. size shapes patterns (https://oeis.org/A001168) (M=10 |36,446 shapes). -> Then simulate to all square (N * N). all shapes and see what's the largest amount.

    I do not know how to implement and does not tried this way. But it's an idea, rs.

  • Felipe Godoy replied 6 years ago

    Alguma dica para esse problema?