DanAlex's blog

By DanAlex, 5 years ago, In English

When someone says nobody ain't doing no thing with CF, I be like

So, haven't you met the average Joe that keep saying that "efficiency is not that important", "my [Greedy wrong sh*t] solution is certainly correct", "who's Dijkstra"? You will. Therefore, we'll be...

Cutting to the chase

And show some situations where competitive programming was particularly useful. I would really like to hear more solutions as I am myself a CF Avg. Joe. #### Local extremes

The problem: Find all local extreme points on a given 2D surface with given heights. You can imagine something like the previous picture, but in the specific context all values were taken from some function(consider it O(1)), so you wouldn't actually need to iterate through all the data.

Avg. Joe:

  • DFS — ples avg. Joe

CF Joe:

Agario

The problem: To calculate total food in an Agario cliet side view for multiple users. You are on the server side. For short, you have a big matrix(say 10 000 x 10 000) on server side and a lot of small views (say 360 x 360) on client side with updates at different moments of time, find fast the sum off all elements on each view.

Avg. Joe:

  • it's a matrix son, just iterate thorough it

CF Joe:

  • Update only the margins of each view(max 60 pixels on each side)
  • Quad Tree
  • Segment/Fenwick Tree 2D
  • Range Tree

Graphics module

The problem: Fill a polygon.

Avg. Joe:

  • all points in bounding box, check if inside and draw

CF Joe:

  • split in triangle and linesweep feel for each triangle
  • fill from edges to inside

Tron

The problem: Tron with 2 players. AI to catch the other.

Avg. Joe:

  • uh, let's grab a beer

CF Joe:

  • greedy — expand heads, go in biggest component, go as close to a wall/body as possible
  • conex connected components
  • I think I can solve it on a tree
  • uh, let's grab a beer

Map projections

Transform a map from a equirectangular projection to a geostationary projection.

Chinese Joe:

  • do the actual math

All the other Joes:

  • take two products and encode the transformation in a matrix
  • find a library for that

PS: Felt like restart writing, don't take it too seriously. These are some examples that I actually encountered at work/university, so feel free to complain and add your own solutions/examples.

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by DanAlex (previous revision, new revision, compare).

»
5 years ago, # |
Rev. 3   Vote: I like it +29 Vote: I do not like it

People say: "efficiency is not that important", but in the same time they use Yandex/Google/etc and it spends only up to 15ms for a query, if not: people are buthearting.

BTW. One of my favourite example is the gamedev (really huge amount of algorithms is used there). I.e. landscape rendering:

Avg Joe: simple array for iterate through all triangles.

CF Joe: simple quadtree, ROAD, geomipmapping, etc. My thesis is based on one of this structures.