Invitation to TOKI Regular Open Contest #15

№	Пользователь	Рейтинг
1	tourist	3690
2	jiangly	3647
3	Benq	3581
4	orzdevinwang	3570
5	Geothermal	3569
5	cnnfls_csy	3569
7	Radewoosh	3509
8	ecnerwala	3486
9	jqdai0815	3474
10	gyh20	3447

№	Пользователь	Вклад
1	maomao90	174
2	awoo	164
3	adamant	162
4	TheScrasse	160
5	nor	158
6	maroonrk	156
7	-is-this-fft-	152
8	orz	146
9	pajenegod	145
9	SecondThread	145

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