Problem Suggestion Thread

[SansPapyrus683]

decided to make a thread just for problem suggestions because of clutter
first gonna move all the previous suggestions here
add new suggestions in this thread i guess

[SansPapyrus683]

korean problems for the treap module:

• https://boj.kr/9548
• https://boj.kr/17777 <-- JOISC problem. It can also be easily solved using __gnu_cxx::crope

[SansPapyrus683]

range dp module:
https://hsin.hr/2010/school/seniors/tasks.pdf
judge link: https://boj.kr/3102

[SansPapyrus683]

korean problems for the counting mins w/ segtree module:
https://boj.kr/3392
https://boj.kr/2185
https://boj.kr/7626

[SansPapyrus683]

I would like to propose this problem to be linked as an application (https://oj.uz/problem/view/JOI21_foodcourt). Although from what I heard the solution doesn't use beats per se (but a more relaxed version), it looks still as a good example

add in segtree beats?

[SansPapyrus683]

https://atcoder.jp/contests/abc215/tasks/abc215_e can be added as a problem to this module.

in bitmask dp

[SansPapyrus683]

possible range dp problem: https://dmoj.ca/problem/pickit

[SansPapyrus683]

for binary jumping module:

https://codeforces.com/problemset/problem/1184/E2
as a binary lifting/jumping problem (suggested difficulty: easy).
Note that this problem also requires knowledge on MST.
If it's decided to put this problem into the Guide, it's a good idea to note that reading
https://codeforces.com/contest/1184/problem/E1
before solving this problem is useful for understanding what the problem statement is asking.

[SansPapyrus683]

bitmask dp: https://codeforces.com/problemset/problem/1185/G1 (suggested difficulty: normal)

[SansPapyrus683]

sliding window module: https://codeforces.com/problemset/problem/1195/E

[Usernametaken12]

LIS module: up down subsequence: http://usaco.org/index.php?page=viewproblem2&cpid=1238
Probably normal difficulty-ish, definitely easier than Candy and the Global Warming, but harder than Cow Run and the xor problem.

[SansPapyrus683]

i feel like we've enough of these problems? unless you feel this contributes something really novel to the understanding

[Usernametaken12]

I feel like it takes some priority given that it is an usaco problem and that the module is lacking in that regard, having only has one other usaco problem-- one from 8 years ago. The gimmick of having multiple states of LIS is probably important to know to be able to incorporate it into harder problems (though I'm not sure how many problems actually use that). While that gimmick is somewhat shared by Global Warming, I don't think you'd instantly be able to solve one having solved the other especially due to the fact that global warming only works with prefixes/suffixes (contrary to my prior statement it's definitely easier than up-down, idk why global warming took me a similar time to solve compared to up-down), and is probably easier to most people than the other. I don't mind having problems that have a similar gimmick to make the problemset easier by giving multiple ways to get to a particular technique (see rectangles, fancy fence, and maximum building I in stacks). Besides, worst case people just skip the problems if they think of the solution immediately, or if they don't get it immediately the topic wasn't clearly wasn't completely learned and they could probably use another problem on it.

Ultimately though I would agree that including this problem probably isn't the highest priority as the module is already very healthy and the topic doesn't occur particularly often in practice to warrant a ton of problems.

[SansPapyrus683]

BOI 2022 Passes for gold bitmask dp

[SansPapyrus683]

add CF 1472-F https://codeforces.com/contest/1472/problem/F to silver greedy

[SansPapyrus683]

hi add this problem to Usaco gold Range DP section
https://codeforces.com/contest/1132/problem/F

[WilliamYuan42]

ok, fair

[SansPapyrus683]

nah put it in normal imo

[Usernametaken12]

I'm not sure what makes this problem difficult. This problem is identical to Modern art 3 in all but the problem description. If this is bumped to normal so should modern art 3.

[SansPapyrus683]

lol idk who put modern art 3 in easy

[WilliamYuan42]

my face when ::::: ::: :: : : : : : : : : : : : : : : : :
i'll just leave it in easy for now

[SansPapyrus683]

https://oj.uz/problem/view/BOI21_prison for lagrangian relaxation or whatever that is

[SansPapyrus683]

time series tree on knapsack instead of dsu:
https://codeforces.com/contest/601/problem/E

[Usernametaken12]

"Harder" DSU
https://tlx.toki.id/problems/apio-2020/B

[Usernametaken12]

Floyd-Warshall problem (first time I've ever seen one in the wild lol):

https://oj.uz/problem/view/APIO17_merchant
Probably a bit hard for gold, but seeing how we only have one problem for it, it should probably go in.