### tzaph_'s blog

By tzaph_, 5 weeks ago,

Dear Codeforces community,

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

Key details:

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:

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!

• +132

 » 5 weeks ago, # |   +16 uwu
 » 5 weeks ago, # |   +34 TMTTzaph_ Maji Tenshi
 » 5 weeks ago, # |   0 tzaph orz
 » 5 weeks ago, # |   +28 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.
 » 5 weeks ago, # |   +18 Friendly bump! The contest will start in an hour, good luck and have fun! :D
 » 5 weeks ago, # | ← Rev. 2 →   +10 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).
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +18 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
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +42 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)$.
 » 5 weeks ago, # |   +8 I am not able to access the editorials. Can you please look into it?
•  » » 4 weeks ago, # ^ |   +3 For confirmation, does the link work now? ThanksIf it still doesn't work, try opening the editorial link attached in the contest announcement.
•  » » » 4 weeks ago, # ^ |   0 It is working now, Thanks!
 » 5 weeks ago, # |   -7 smh why not show all of the top 10 ugh
 » 4 weeks ago, # |   +10 The editorial link in blog seems to be broken. The one in Announcements in TOKI works. ( btw tzaph orz )
 » 4 weeks ago, # |   0 tzaph is my emperor
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 What?
• »
»
»
4 weeks ago, # ^ |
0