try_kuhn's blog

Belarusian round #2: Simran, Muskan, Divyansh, Pranjal and their problems
By try_kuhn, history, 4 years ago, translation, In English

Hello, Codeforces!

At [contest_time:305369] 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, Irpacci and Artem___.

Thanks MikeMirzayanov for Polygon and Codeforces!

Good luck! I wish you only Perfect results!)

To register:

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

If you are registered:

https://codeforces.net/contests/305369

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

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

What is the main idea behind the solution C?

→ Reply
  • »
    »
    4 years 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

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Does this contest have some editorial?

→ Reply