IceKnight1093's blog

Invitation to CodeChef Starters 131 (Rated till 5-Stars) — 24th April
By IceKnight1093, 8 months ago, In English

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!

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

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    8 months ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    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).
    → Reply
»
8 months ago, # |
  Vote: I like it +5 Vote: I do not like it

My solution discussion stream

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

Fun problems, kudos to the authors!

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply