Invitation to TOKI Regular Open Contest #15

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	166
2	maomao90	163
2	Um_nik	163
4	atcoder_official	161
5	adamant	160
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

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: yz_
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:

Div 2:

A: 300iq
B: 300iq
C: 300iq
D: uwi
E: 300iq
F: jschnei

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!

Комментарии (15)

Показать архивные | Написать комментарий?

Pyqe

4 года назад, # |

+16

uwu

→ Ответить

Sadrian

+34

TMT

Tzaph_ Maji Tenshi

steven.novaryo

+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.

yz_

+18

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

XGptw

← 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).

4 года назад, # ^ |

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

rama_pang

+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)$$$.