baobab's blog

By baobab, history, 5 years ago, In English

Bot Land is a competition where you code AI for robots which fight other peoples' robots. I think anybody who loves competitive coding and strategy games will absolutely love it. For the past few weeks I've sank most of my free time into developing strategies and coding bots. Bot Land was released a month ago after effectively being in beta for 4 years.

The game has 2 programming interfaces: a scratch-like interface (for non-programmers) and a subset of JavaScript (for programmers). In addition to coding, you also design your bots (choose weaponry etc.) and you position your bots on the map. The battles are asymmetric: the defender saves their defense and then anyone can attack it (the defender does not have to be online). All battles have 3 rounds, so the attacker can exploit discovered weaknesses of the defender in subsequent rounds. This advantage is mitigated by allowing the defender a higher number of bots, etc. Naturally, there are two leaderboards: one for attacking and one for defending.

The website for the game https://bot.land has some videos and tutorials if you want to try it out. The game can be played entirely in-browser. I'm not affiliated with the developer, I just enjoy the competition and I would love to see more competitors!

Full text and comments »

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

By baobab, history, 6 years ago, In English

Link to problem statement

Let's first fill up the sack with as small items as possible, until we can't fill it anymore. The difference between current weight and max weight can be at most 8 (with the exception of trivial inputs) and there are only 8 distinctive items. So if we need to create a sequence of actions which takes us from the current weight to the optimal weight, we don't need many actions to do that. Now, here comes the funny part: instead of constructing a short, smart sequence of actions, we can simply construct a long, dumb sequence of actions. If we choose every action in a greedy, randomized way, we will probably visit the optimal weight at some point in the sequence. What do I mean by greedy? If we are under max weight, let's add a random item to the sack. If we are over max weight, let's remove a random item from the sack. That's it!

There's still time to hack my solution. Have fun!

Full text and comments »

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

By baobab, history, 6 years ago, In English

Here is a similar feature from StackOverflow:

Would be nice to have something like this for CodeForces as well. In addition to being cool, it could bring more visitors to CodeForces (both directly from personal websites, and indirectly by improving SEO rankings with many legitimate links).

Full text and comments »

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

By baobab, history, 6 years ago, In English

This is a common subtask in many geometry problems. Today I was unable to solve 1059D because my point-to-point distance calculation is not accurate enough. To summarize the problem, "Find the smallest circle which encompasses all the points, such that its border touches the x axis." I understand there are other ways to solve the problem, but I really want to learn to complete this subtask accurately, since it's recurring in many different problems.

Here's how I would usually calculate it:

double xDist = Math.abs(x1 - x2)
double yDist = Math.abs(y1 - y2)
double dist = Math.sqrt(xDist*xDist + yDist*yDist)

However, this was failing test #4 due to double precision issues. I got some help with this and refactored the calculation into:

double dist = Math.sqrt(xDist) * Math.sqrt(yDist) * Math.sqrt(xDist/yDist + yDist/xDist);

Somehow, this was still not enough. I don't understand how I could possibly calculate distance between 2 points more accurately with Java doubles. Can you help me out? I condensed the failing test case into very little code here.

Full text and comments »

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

By baobab, history, 9 years ago, In English

The editorial and other published solutions for this problem have at least O(n log n) time complexity. Here is a O(n) solution.

tl;dr for those who solved this problem with the Convex Hull Trick is that we can keep lines in a queue rather than a tree/sorted list, because we only add lines of increasing/decreasing slope. This solution doesn't require conceptualizing the geometry though

Full text and comments »

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