You may have wondered what competitive programmers do when not coding. So here's a little video I made to show the whole community a day in the life of an average competetive programmer.

Hope you enjoy:))

Screencast + Explanations for Codeforces Round 787 Div 3

Hope the explanations help:))

Screencast + Vide editorial

Hope this helps some of you!

Here's a screencast of todays codeforces contest!

P.s: I will stop posting a blog for every video after a while, but currently it's the only way people can discover my content:))

Here's a screencast of me doing todays codeforces round:))

Here's a screencast of me winning CodeChef START32C, I also explain my solutions at the end.

leaderboard

I'm announcing a new series called: Lets Upsolve! In this series I will choose some codeforces round and upsolve problems A-D, then explain my solutions. I reccomend that everyone tries the problems on their own at first, then if you get stuck, you can view my video. If you're reading this blog this is a great opportunity to upsolve some problems instead of making excuses;)

Lets Upsolve! — Episode 1: Codeforces Educational Round 125 A-D

Hi to all the amazing people in the codeforces community!

I just participated in todays round and tried to explain problems A-D1. I welcome everyone's feedback. (I recommend watching in 1,5x speed, i talk quite slow)

Codeforces Round 779: problems A-D1 explained

Hello to all the wonderful people here on codeforces!

I was first introduced to competetive programming two years ago, and as for many others, it became one of my favourite hobbies. When I was starting out, I rember RomeoFantastik's great videos after almost every codeforces round. Now that I've gained some experiance, I thought that I'll try and give back to the community (and also improve my explaining skills), by making video editorials and educational blogs for codeforces problems and contests. Please send me feedback!

Here's my first attempt, I try explaining A-C of todays codeforces round: CodeTON Round 1: A-C problems explained

MDST

There is a spoj problem where you need to find the diameter of the MDST for a given graph. The graph is undirected, connected and unweighted. There are up to 1000 nodes, but no bound is given on the number of edges. (the solution I found online looped through all the edges and than all the nodes, and got AC. I think its thus safe to assume the number of edges is O(n))

From what I've read online here's the logic of the solution:

1. find the shortest distance dist[u][v] from each node to each other node (done in O(n^2), with bfs from each node)

2. brute force the center of the MDST

   1. If the center of the MDST is a node v, I find the node u such that dist[v][u] is maximal. -> The diameter if v is center will be 2*dist[v][u] I keep a variable mdst as the minimum diameter I have found so far.

   mdst = INF;
   for(v = 0 to N){
      mx = 0
      for(u = 0 to N) 
          mx = max(mx, dist[v][u])
      mdst = min(mdst, 2*mx)
   }
   

   2. If the center of the MDST is an edge e = (u, v) I find the node x such that min(dist[u][x], dist[v][x]) is maximal. -> the diameter if e is the center will be 2*min(dist[u][x], dist[v][x]) + 1

   for((u, v) : edges){
      mx = 0
      for(x = 0 to N) 
          mx = max(mx, min(dist[u][x], dist[v][x]))
      mdst = min(mdst, 2*mx)
   }
   

In either of the above cases, if the chosen node/edge is not the center of the MDST, the resulting diameter I find will be strictly greater than that of the actual MDST. On the other hand if the chosen node/edge is the center of the MDST, I should find the correct diameter.

Above I give an explanation to why this solution works, but it relies on the fact : if the chosen node/edge is not the center of the MDST, the resulting diameter I find will be strictly greater than that of the actual MDST which I didn't prove.

I have worked out a proof on paper for why this is true, but I'm not sure how to write it down formally here so I will not try to do so. I recommend you try to prove it yourself, if you are struggling write a message to me and I will try to help with what I can.

CP3 has some solid implementations of common data structures, such as UFDS, Segment Trees, Fenwick Tree, etc. It also has some nice implementation of algorithms such as Suffix Array,Lowest Common Substring Array, and many others I haven't got around to reading yet. The thing in common with CP3 implementations is that they're all very C style codes. (geeksforgeeks also has similar implementations)

On the other hand I also use cp-algoritms.com for learning, and they also have very good implementations that use much more 'modern' code. For example CP3 always uses basic arrays, and C style string manipulation, whereas cp-algorithms uses the c++ std::vector and std::string classes.

I know style implementations are usually faster as they are less bulky, but they're also harder to deal with, and as a result, you can make mistakes easier.

So my questions are: Which should I use? Is there actually a noticeable difference at all between the two?

Thanks for anyone who read this whole thing!

(maybe I'll try submitting some problems with both CP3, and cp-algorithms implementations, and see which one has faster runtimes)

in both images the top one is the cp-algorithms, while the bottom one is the CP3 implementation. For the first problem is |s| <= 100000, for the second |s| <= 400000. The CP3 uses the same sized predefined for both, thats why it uses so much space for the first one.