Contact Form Submission - Suggestion (Silver - More Operations on Sorted Sets)

[maggieliu05]

Someone submitted the contact form!

URL: https://usaco.guide/silver/intro-sorted-sets
Module: Silver - More Operations on Sorted Sets
Topic: Suggestion
Message:

About sorted sets specifically: Shouldn't these be in Gold instead of Silver? There is only one Silver problem in this module for which sorted sets / maps are used (Milk Measurement). Whereas for Convention II the solution can easily be rewritten to use priority queue instead.

[bqi343]

I submitted the issue above. I've been thinking this for a while though I never got around to posting it.

Bit Inversions, the in-module problem that demonstrates the use of sorted sets, already has a note about it being too hard for Silver, so it really should not be in a Silver module.

Probably the problems that require the use of sorted sets / maps specifically (not just priority queue) should be split into a separate module and moved to Gold.

The module after this (https://usaco.guide/silver/custom-cpp-stl) should also be moved to Gold.

[bqi343]

Btw, I think the most recent problem about sorted sets / maps was https://usaco.org/current/data/sol_prob3_gold_jan25.html, which was the hardest problem in its contest.

[SansPapyrus683]

which module of ours covers priority queue

[bqi343]

Priority queues are introduced in this module.

That being said it would make more sense for priority queue to be introduced before sorted sets given that they are simpler and also available in Python. The use cases are also rather different.

[bqi343]

I went through all of the in-module problems, here are the ones I found that can easily be rewritten to avoid the use of sorted maps / sets.

Cellular Network: Binary Search / Sorting / Two Pointers
Room Allocation: Priority Queue
Convention II: Priority Queue
Survival of the Weakest - Priority Queue
Mahmoud & Ehab - Binary Search
William and Robot - Priority Queue
Covered Points Count - Sorting
Packing - Priority Queue

All of these can be moved into other modules or a new priority queue-specific module.

Side note: The ordering of topics in Silver sorting & searching is very strange. lower_bound on vectors should be introduced before all of the following topics:

• coordinate compression
• lower_bound on sorted sets
• binary search on the answer
  but currently it is the other way around ...