Google Codejam 2022 - Round 1A

preview_player
Показать описание

I couldn't figure out the last problem
Рекомендации по теме
Комментарии
Автор

thanks for the explanations here!
For the equal sum problem, at first, I skipped over the test set constraints and thought N could be variable, I spent over a day only to realise that it's 100 ALWAYS! 😂, and then everything felt under control. key ideas to solve this problem were,
1> if we can have all the powers of 2 up to the gap that we want to fill, it's always possible to fill the gap! moreover, it will also split into two equal sum subsets.
2> judges output numbers always are distinct and also distinct from the one that we choose. so that means no extra powers of 2 if we choose them all.
3> and as there are only two subsets, we know if it can't go into the first subset, it always goes to the other one because we know both subsets can only take up to the target(sum/2) value.

correct me if there are any missing pieces here.

tusharsnn
join shbcf.ru