Jugo's blog

By Jugo, history, 6 days ago, translation, In English

Hello, Codeforces!

At Jan/13/2021 17:35 (Moscow time) will start Belarusian round #2: Simran, Muskan, Divyansh, Pranjal and their problems (Div. 3).

This is my first IOI round, I hope you like it) 15 minutes before the end table will be frozen.

UPD: tasks are not sorted by difficulty!

You will be given 6 tasks and 2 hours to solve.

For creating English statements I want to give thanks: MatesV13, Radhe_Loves_To_Eat and ahmedfouadnew.

Tasks were tested by: Radhe_Loves_To_Eat, ahmedfouadnew, MatesV13, Gareton, Xennon, cirieena, Asgio and Artem___.

Thanks MikeMirzayanov for Polygon and Codeforces!

Good luck! I wish you only Perfect results!)

To register:

https://codeforces.com/contestInvitation/19e1d6bcd351edb57df326e05cce16c73715d02c

If you are registered:

https://codeforces.com/contests/305369

 
 
 
 
  • Vote: I like it
  • +60
  • Vote: I do not like it

»
3 days ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

What is the main idea behind the solution C?

  • »
    »
    3 days ago, # ^ |
    Rev. 2   Vote: I like it +6 Vote: I do not like it

    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