TheScienceGuy's blog

By TheScienceGuy, history, 15 months ago, In English

There's an old ITMO course on EdX (How to win coding competitions: Secrets of Champions): https://learning.edx.org/course/course-v1:ITMOx+I2CPx+3T2017/home It includes some good problems as homework and exam, but it no longer accepts solution submissions. Can I find the same problems anywhere else so that I can submit my solutions?

Full text and comments »

  • Vote: I like it
  • +1
  • Vote: I do not like it

By TheScienceGuy, history, 3 years ago, In English

There's a website that looks like Codeforces, I read about it here on Codeforces. It had contests very often and their problems were oriented towards implementing standard algorithms. There problems also had very technical wording (instead of "Peter loves to play in snow. He made 10^6 snowballs..."). I cannot recall the name. Could you please help me?

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By TheScienceGuy, history, 4 years ago, In English

We are given the 2D coordinates (all integers) of 2 points: the first point is where the ray starts and it goes through the second point. We are given another ray in the same way. How do we determine if they have a point of intersection? I would like to know the general algorithm and its explanation, don't mind about the extreme cases (e.g. when the rays have the same starting point). P.S. I saw a similar question on stack exchange, but the answers were not backed up by explanation.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By TheScienceGuy, history, 6 years ago, In English

Hi, I think it is a good idea to add standard problems (like DFS, find cycle in graph, Convex Hull...) in codeforces problemset which most of competitive programmers learn, so that we can test our solutions as we are learning the algorithm. The problems should look exactly like the original ones (for example, the problem of printing a cycle from an unweighted directed graph should look like this: "Given the vertices of an unweighted directed graph, print any of the cycles in this graph. If it has no cycles, print -1"; then we describe the limits and IO format. Formulating problems this way saves time while training). I will start writing a list of standard problems/algorithms, feel free to add:

Sorting: 1. MergeSort 2. QuickSort 3. SelectionSort 4. RadixSort 5. BucketSort 6. Binary Search

Graph Algorithms: 1. DFS 2. BFS 3. Finding Cycle 4. Checking if graph is bipartite 5. Dijkstra's algorithm 6. Floyd-Marshall's algorithm 7. Checking connectivity 8. Kruskal’s Minimum Spanning Tree Algorithm 9. Finding if there is a path between two vertices

Dynamic Programming: 1. Knapsack problem 2. Edit Distance 3. Longest increasing subsequence 4. Longest common subsequence

Computational Geometry: 1. Constructing Convex Hull 2. Checking orientation of 3 points

I will add more problems/algorithms to the list if the users like the idea. Creating and adding problems is discussed in this post: https://codeforces.me/blog/entry/52135 . I will add some problems, but it is better if the users with high rank do this.

Full text and comments »

  • Vote: I like it
  • +36
  • Vote: I do not like it