CSES advance techniques section

Problems and Contests
#1

Hi community! I hope you are having a great day!

First, a little thing about me: I am the type of person who prefer learning by doing, that means instead of reading a bunch of boring techniques, i usually find random problems and try to solve them by the techniques that i have already known, if i get stuck then I would look for help on that problem to see if a new techniques is required , if it is than I would learn it and then apply it to the problem that I am getting stuck. This way of learning makes me progress quite fast so I really like it.

Currently I am practicing on cses advance techniques section using the approach described above. The first half was not quite bad, I solved some of them by myself, the others I tried to google some relevant stuff and i actually found the new techniques that I needed and learned them. But the last half was a nightmare, I wasted a lot of time trying to solve them by myself and finally ended up no where, I tried to google some stuff but none of helpful thing is found. And I know now it’s time to get some help from smarter people ^^.

Here is a list of problems that I am currently getting stuck:

Can you guys kindly provide me the techniques that I need to learn to solve each one of them . You guys do not need to give me the full solution 'cause I mainly need the technique, those problems are very fundamental, so if you have solved some similar tasks I believe you can solve them at the first glance ^^.

Thanks in advance and once again, hope you guys are having a nice day!

#2

See https://usaco.guide/adv/LC?lang=cpp and the prerequisite modules

FFT

There are some modules in the guide about flows but they’re not complete.

Reduces to Range Minimum Query. Maybe someone else can elaborate.

3 Likes
#3

I have solved most of them by now! Thanks for your reply, it did help me a lot, I really appreciate it!

#4
  1. find minimum spanning tree using DSU (edge cost is day when it is constructed)
  2. heavy-light decomposition over minimum spanning tree
  3. query answer is maximum edge on path from one node to another (range maximum query)(path is unique because when we find MST it is then tree instead of graph), or -1 if nodes are not in same connected component
#6

Just another note: Parallel Binary Search can be used to solve “New Road Queries” (in fact, this is the approach given in “Guide to Competitive Programming”, which has a full explanation on page 294 for me).