Блог пользователя IceKnight1093

Invitation to CodeChef Starters 131 (Rated till 5-Stars) — 24th April
Автор IceKnight1093, 7 месяцев назад, По-английски

We invite you to participate in CodeChef’s Starters 131, this Wednesday, 24th April, rated till 5-Stars (ie. for users with rating < 2200).
Time: 8:00 PM — 10:00 PM IST

Joining us on the problem setting panel are:

Written editorials will be available for all on discuss.codechef.com. Pro users can find the editorials directly on the problem pages after the contest. The video editorials of the problems will be available only to Pro users.

Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.

Hope to see you participating.
Good Luck!

  • Проголосовать: нравится
  • +38
  • Проголосовать: не нравится

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to do 1F? I could only think of MST, if we ignore the updates.

→ Ответить
  • »
    »
    7 месяцев назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    3/4 people did it with a simple $$$O(q x\log^2{n})$$$ (x is unordered map) cheese.

    The two solutions I had:

    1. $$$O(q\log^2{n})$$$ using a segment tree, with a treap stored in each node. Although this is theoretically better than the second solution, it would probably run slower.
    2. $$$O(q\sqrt{n \log{n}})$$$ using square root decomposition and maintaining a fenwick tree for each block. For the $$$b$$$-th block, the $$$l$$$-th element of its fenwick tree stores the sum of all lengths of the elements in the $$$b$$$-th block which are the first of their kind after indice $$$l$$$. This has a very good constant factor and runs in just 600 ms (code).
    → Ответить
»
7 месяцев назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

My solution discussion stream

→ Ответить
»
7 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Fun problems, kudos to the authors!

→ Ответить
»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The information regarding subtasks could have been given beforehand.
We don't come to know about it until we click on each and every problem.

→ Ответить