Some questions about INOI

I know very little in CP, which topics should I know for INOI ? The things that I know are

  • Very basic DP
  • Very asic Graph Algos (DFS, BFS, Minimal Spanning Tree, DAG, Floyd Warshall, Dijkstra and nothing else)
  • Very basic data strucutres (Map, Vector, Segtree, BST, DSU)

In particular, I don’t know

  • Any number theory algo
  • Any geometry algo
  • Any other data structures/graph algo

So some questions:

  1. Which other things should I learn for INOI ? Are things like Flows/Hashing relevant for INOI ? Any string algos which are needed for INOI ?
  2. Like map, vectors, what other things of C++ STL (or whatever that’s called) are good to be familiar in ?
  3. How the difficulty of INOI problems, compared to, say - USACO Gold/Plat/CF Div 2/1 problems ?
  4. Where I can find good problems with solutions on Floyd Warshall/Dijkstra/etc ? I can’t find tags with them on codeforces.
  5. Which one should I use: “%printf %scanf” or “cin/cout with ios::syncwithstdio” ? (I use cin/cout now, so if it’s better to use the former then I have to be familiar with them).
1 Like

Graph questions are easy and the difficulty in DP varies a lot. You can easily do some subtasks of the DP problem and qualify.
You don’t need number theory algo, geometry or any other data structure other than you already know because it’s not in the INOI syllabus.

  1. Flows and String Algorithms are not even in the IOI syllabus and Hashing is not in the INOI syllabus.
  2. Map,vector,pair,sorting and comparator are mostly all that is needed for convenience.
  3. You can compare the DP problems to USACO Gold level and Graph is Silver maybe. Even the USACO difficulty level differs each month. Codeforces contest again are sometimes hard or easy but I guess it would be about Div2 D or Div1 B at most in difficulty.
  4. This is a codeforces blog which has topics and few problems on it with difficulty marker on most of them. You can easily find their solution easily by googling.
  5. You actually don’t need Fast IO in INOI because they have generous time limit and you will not get TLE because of using long long int instead of int or some constant factor in your solution.

P.S I see that you got 200 in ZCO so that indicates you are doing good and will mostly qualify INOI with this much knowledge.

2 Likes

What the hell is “comparator” ? I’m listening the name for the first time.

Thanks a lot for the link in #4 !

Good luck for INOI too !

Where’s the INOI syllabous btw ?

Also didn’t a number theory problem come in 2015 ? What about geometry problems (convex hull etc) ?

@kayak A comparator is just a function which compares which container should go first from a pair when you sort. It’s basically how you want something to be sorted. Maybe you want your “pair” to be sorted in non-decreasing order of second element so you need to write a custom comparator because its sorted by the left element by default. Here ( http://fusharblog.com/3-ways-to-define-comparison-functions-in-cpp/ ) is a nice link to understand them.

The INOI syllabus is the topics under Basic Topics ( https://www.iarcs.org.in/inoi/online-study-material/topics/ ) . Yes, you are right, there was a bit more mathematical question in 2015 but very few people solved it so they stopped asking those kind of problems :stuck_out_tongue: I have not seen a geometry problem in INOI and some easier national OIs and they won’t come because most people fear geometry. This is what I think.