Привет, Codeforces!
В [contest_time:305369] состоится Belarusian round #2: помогите Даш... детям справиться с проблемами! (Div. 3).
Это первый мой раунд по стандартам IOI. Вам будет дано 6 задач на 2 часа. Надеюсь, что задачи вам понравятся) За 15 минут до конца таблица будет заморожена.
UPD: задачи не сортированы по сложности!
За создание условий на английском языке хочу выразить благодарность: MatesV13, Radhe_Loves_To_Eat и ahmedfouadnew.
Задачи вместе со мной тестировали Radhe_Loves_To_Eat, ahmedfouadnew, MatesV13, Gareton, Xennon, cirieena, Irpacci и Artem___.
Также большое спасибо MikeMirzayanov за системы Polygon и Codeforces!
Удачи в раунде! Успешных решений!
Для регистрации:
https://codeforces.com/contestInvitation/19e1d6bcd351edb57df326e05cce16c73715d02c
Если вы зарегистрировались:
How to solve c?
https://pastebin.com/vGBAk24W
What is the main idea behind the solution C?
Disclaimer — haven't coded it, might not work.
If there's an even number of negative numbers then the answer is product of whole array.
If there's an odd number of negative numbers, one subarray will have negative product, so obviosuly we want to minimise this and maximise the other one.
It's easy to notice that subarray will be a prefix till the first negative number, or suffix till the first negative number.
Those numbers will be huge, so instead of comparing them directly we can use the trick to compare sum of logarithms instead of products e.g.
a * b < c * d => log (a * b) < log (c * d) => log a + log b < log c + log d
Does this contest have some editorial?
Sory, I'm too late. Only russian in my blog