Dear Codeforces community,

We are excited to invite you to **TOKI Regular Open Contest (TROC) #15!**

Key details:

- Contest links: Div 1 (rating ≥ 2000) and Div 2 (rating < 2000 or unrated)
- Time: 1st November 2020, 14:05 UTC
- Writer: tzaph_
- Duration: 2 hours
- Problems: 6 for every division

Scoring distribution:

- Div 2:
**100 — 200 — 300 — 400 — 550 — 650** - Div 1:
**100 — 200 — 350 — 400 — 500 — 600**

I would like to thank prabowo as coordinator, hocky for helping with problem preparation, fushar for the TLX platform, and ayaze and steven.novaryo as testers.

Please register to the contest, and we hope you will enjoy TROC #15!

P.S. we encourage you to read all problems! :)

**UPD:** Contest is Over!

Congratulations to our top 5:

Div 1:

Div 2:

Congratulations to our first solvers:

Div 1:

- A: antontrygubO_o
- B: antontrygubO_o
- C: neal
- D: Pa.Nic
- E: antontrygubO_o
- F: Benq

Div 2:

Editorial is available here (English version is available on page 8)

You can upsolve the problems here.

Thank you for participating and see you on the next contest!

uwu

TMT

Tzaph_ Maji Tenshi

tzaph orz

I am glad I have given a chance to test some quality problems. Good luck to the participants. I hope you can enjoy the contest as much as I could.

Friendly bump! The contest will start in an hour, good luck and have fun! :D

Regarding Div 1C. Tzaph and Good Array.

Can anyone explain why timecomplexity is O(NlogN)

Below para is taken from official editorial

Our time complexity now is worst case O(N²) if every time we are observing a subarray [L, R], we iterate X from L to R one by one. To achieve a better complexity, we iterate X in a zig-zag , from the leftmost element, then the rightmost element, and so on. Formally, we iterate X with the order {L, R, L + 1, R — 1, L + 2, R — 2, …}. With this optimization, the time complexity is reduced to O(N log N).

The worst case of the code happens when we iterate all R — L + 1 values. Then, the subarray is split to exactly two subarrays of size (R — L) / 2. The iteration now forms a binary tree which has a logN height. Thus, the number of iterations is NlogN at most.

Edit: My explanation is incomplete. Refer to rama_pang's explanation

Let $$$T(N)$$$ be the time complexity of the algorithm when considering an array of size $$$N$$$. Then if we iterate in a zig-zag manner, the moment we detect a valid splitting position we split the array into two. Thus we have $$$T(N)=T(bigger)+T(smaller)+O(smaller)$$$, where $$$bigger \geq smaller$$$ and $$$bigger + smaller + 1 = N$$$. This is exactly the same as the small-to-large technique but in reverse, which has complexity $$$O(N \log N)$$$.

I am not able to access the editorials. Can you please look into it?

For confirmation, does the link work now? Thanks

If it still doesn't work, try opening the editorial link attached in the contest announcement.

It is working now, Thanks!

smh why not show all of the top 10 ugh

The editorial link in blog seems to be broken. The one in Announcements in TOKI works. ( btw tzaph orz )

tzaph is my emperor

What?

## tzaph is my emperor