Advanced Topics Tutorials?

general
1

I want help regarding,

  1. What are some advanced topics one must know to be good in competitive challenges ?
  2. Can you share some materials regarding the same?

Many a times I get stuck at 3rd or 4th question in Long challenges, and get to know some different theories to solve it after reading the editorials. Hence I would love to know which are some of these topics or topics which are generally asked in such contests? @vijju123

2

If you are getting stuck at 3rd or 4th problems, I suggest following-

  • Look at all data structures like sets, priority_queue, vectors. Also, the inbuilt functions of your language, say sort() in C++. Familiarity with your language’s STL is a must.
  • Look at properties of operators, like \% or XOR. When looking at properties of modulo, do not forget to look at applications like fast expo, finding inverse etc. This helps to cover for some math asked at times.
  • Numbers in binary are a favorite and interesting topic. Make sure you are familiar with bitwise operations!
  • Sometimes, one sees basic questions on DFS and BFS, or near classical DP as P4.
  • Ad hoc problems to learn some tricks like difference array, frequency array etc.

These should be enough to solve most of the P3 and/or P4 of long in div2.

10 Likes
3

That sounds nice and helpful. Ahead of that, what are the topics for the last few questions ? Like I know one is Segment/fenwick tree, any more?

4

@vijju123 This is really helpful! Can you please suggest some resources as well?

5

On an average i solve around 5 questions in long challenge,
And i get stuck in 6th and 7th questions in division 2…

Can you help me with the topics I should learn to improve my performance?? I have already learned all the topics you mentioned above…
@vijju123

6

@nikmul19 - I will suggest to follow a plan. No use doing ahead topics until the fundamental and basic ones are clear. Eg - If data structures like stack, queue, maps and vectors arent clear you will have problem in graph and some DP problems.

@anon8947907 - Honestly, nothing particular. I think CCDSAP prepare section has extensive resources for it. All I did in my time was just learning what the data structure does, its applications and some basic practice problems. For rest of topics I searched for problems via tags.

@anon45451754 - The topics for last few problems of div2 are much wider and tougher. Mostly, you should try to have a grasp on-

  • Graph algorithms. BFS, DFS, shortest paths, directed graph algorithms (Toposort etc) are a must.
  • DP problems upto easy-medium or medium difficulty.
  • Tries. Have an idea of what they are so you can identify if the problem requires it.
  • Sometimes math comes. Not much can be recommended here. But a book called “Concrete Mathematics” is very nice to get idea of competitive coding maths.
  • Data structures like DSU, Seg tree.
  • Tricks like Difference Array, Square root decomposition.
  • Graph algos again! Many times graph algos are used in combination of above data structures. Eg- Euler Tour + Difference Array etc.

If you look at problems of August long this year, the distribution was as follows-

  • KS1 - Adhoc, math to come up with formulas, properties of XOR
  • ENCODING- Digit DP (easy-med or med level dp)
  • CHGORAM - Euler Tour, Segment Tree, DFS
2 Likes
7

Thanks. As of today I was able to solve 1,2,4 and 3rd partial in Nov long challenge Div2 :grimacing: