yz_'s blog

Invitation to TOKI Regular Open Contest #15
By yz_, 4 years ago, In English

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:

  1. Benq
  2. neal
  3. nuip
  4. awoo
  5. BohdanPastuschak

Div 2:

  1. jschnei
  2. saketh
  3. riantkb
  4. uwi
  5. 300iq

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!

  • Vote: I like it
  • +132
  • Vote: I do not like it

Comments Comments (15)
| Write comment?
»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

uwu

→ Reply
»
4 years ago, # |
  Vote: I like it +34 Vote: I do not like it

TMT

Tzaph_ Maji Tenshi

→ Reply
»
4 years ago, # |
  Vote: I like it +28 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +18 Vote: I do not like it

    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

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +42 Vote: I do not like it

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

    → Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like 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.

    → Reply
»
4 years ago, # |
  Vote: I like it -7 Vote: I do not like it

smh why not show all of the top 10 ugh

→ Reply
»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

tzaph is my emperor

→ Reply