Where can i find an editiorial for this problem?
Vojnici-regional
well, i can tell you my idea...
it is obvious you need to sort something...
( maybe it isn't :), and maybe you don't need )
i sorted my soldiers.
next for every my soldier you need to find best choice:
and it is soldier with max( get[ i ] + los[ i ] ).
why max( get[ i ] + los[ i ] ) ? well...
let's assume you chose a soldier p .
now if there is another soldier q and
get[ p ] - los[ q ] < get[ q ] - los[ p ]
then soldier q is better choice.
// try to think about this for 2 min, and you will understand why is that :)
so you don't need to change soldier if
get[ p ] - los[ q ] > get[ q ] - los[ p ]
get[ p ] + los[ p ] > get[ q ] + los[ q ]
which means get[ p ] + los[ p ] is max. :)
i hope you understood me :)
it is obvious you need to sort something...
( maybe it isn't :), and maybe you don't need )
i sorted my soldiers.
next for every my soldier you need to find best choice:
and it is soldier with max( get[ i ] + los[ i ] ).
why max( get[ i ] + los[ i ] ) ? well...
let's assume you chose a soldier p .
now if there is another soldier q and
get[ p ] - los[ q ] < get[ q ] - los[ p ]
then soldier q is better choice.
// try to think about this for 2 min, and you will understand why is that :)
so you don't need to change soldier if
get[ p ] - los[ q ] > get[ q ] - los[ p ]
get[ p ] + los[ p ] > get[ q ] + los[ q ]
which means get[ p ] + los[ p ] is max. :)
i hope you understood me :)
hehe not so complicated:D ... i hoped for DP or something:D but its still nice:D not disappointed anyway. Thnx
i have DP in O( N^2 )