Codeforces Round #892 (Div. 2) Editorial

Revision en15, by induk_v_tsiane, 2023-08-12 20:31:40

We hope you liked the problems.

Task A was invented and prepared by induk_v_tsiane.

Task B was invented by induk_v_tsiane, and prepared by i_love_penguins.

Task C was invented and prepared by induk_v_tsiane.

Task D was invented by i_love_penguins and efimovpaul, and prepared by i_love_penguins.

Task E was invented by induk_v_tsiane and kristevalex, and prepared by induk_v_tsiane.

Task F was invented by induk_v_tsiane and Artyom123, and prepared by induk_v_tsiane.

1859A - United We Stand

Hints
Tutorial
Author's code

1859B - Olya and Game with Arrays

Hints
Tutorial
Author's code

1859C - Another Permutation Problem

Hints
Tutorial
Author's code

1859D - Andrey and Escape from Capygrad

Hints
Tutorial
Author's code

1859E - Maximum Monogonosity

Hints
Tutorial
Author's code

1859F - Teleportation in Byteland

Hints
Tutorial
Author's code

Some notes/challenges:

  • We know about the $$$O(N^2)$$$ solution in C, but we did not find a good suitable proof for it (and, using the method, we could achieve faster solutions).

  • You can solve $$$D$$$ without the constraint that the segments are contained, but that is harder. It is solvable in $$$(ONlogN)$$$.

  • Thank you all for participating! If you have any complaints/suggestions/advice for future rounds, feel free to share in the comments!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en15 English induk_v_tsiane 2023-08-12 20:31:40 1099
en14 English induk_v_tsiane 2023-08-12 20:22:32 0 (published)
en13 English induk_v_tsiane 2023-08-12 20:21:56 10 Tiny change: 'an use binlifts, and for ' -> 'an use binary lifting, and for '
en12 English induk_v_tsiane 2023-08-12 20:20:50 7878 Tiny change: ' - h2[LCA]. If $v1$ ' -> ' - h2[LCA]$. If $v1$ ' (saved to drafts)
en11 English induk_v_tsiane 2023-08-12 19:54:26 45 Tiny change: 'blems.\n\n[prob' -> 'blems.\n\nTutorial for F will be added a bit later.\n\n[prob'
en10 English induk_v_tsiane 2023-08-12 19:54:06 0 (published)
en9 English induk_v_tsiane 2023-08-12 19:53:39 1 Tiny change: 'utorial">\\nStatemen' -> 'utorial">\nStatemen'
en8 English induk_v_tsiane 2023-08-12 19:52:59 125
en7 English induk_v_tsiane 2023-08-12 19:50:53 745
en6 English induk_v_tsiane 2023-08-12 19:32:14 2148
en5 English induk_v_tsiane 2023-08-12 19:20:14 1868
en4 English induk_v_tsiane 2023-08-12 19:12:24 2
en3 English induk_v_tsiane 2023-08-12 19:11:41 1
en2 English induk_v_tsiane 2023-08-12 19:11:09 4057
en1 English induk_v_tsiane 2023-08-12 19:06:10 6576 Initial revision for English translation (saved to drafts)
ru3 Russian induk_v_tsiane 2023-08-12 19:05:08 2803
ru2 Russian induk_v_tsiane 2023-08-12 18:42:59 2303
ru1 Russian induk_v_tsiane 2023-08-12 18:38:22 1467 Первая редакция (сохранено в черновиках)