Editorial for CCC '17 S3 - Nailed It! - Olympiads Online Judge

Editorial for CCC '17 S3 - Nailed It!

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Authors: Phoenix1369, Kirito

For up to $9$ $9$ out of the $15$ $15$ available marks $(N \le 1000)$ $(N \leq 1000)$ , a simple algorithm which iterates over each pair of the pieces of wood in the input suffices.

Time Complexity: $\mathcal O(N^2)$ $O (N^{2})$

For the full $15$ $15$ marks, we make the observation $1 \le L_i \le 2000$ $1 \leq L_{i} \leq 2000$ . This means we can iterate over every (unordered) pair of lengths of pieces of wood available and add it to the corresponding total for a length of board made. Since each length of wood can be uniquely paired up with another length of wood to create a corresponding length of board, no pairs are over-counted this way. Finally, we can iterate over every possible board length to determine the length of the longest fence and the heights of all fences which have that length.

Time Complexity: $\mathcal O(N + {L_i}^2)$ $O (N + {L_{i}}^{2})$

Comments

There are no comments at the moment.