jo_on's blog

By jo_on, history, 9 months ago, In English

Spoiler alert: This post contains a solution to the problem.

Problem Yeetzhee of Google Kickstart 2020 Round F

Recently, a friend who participated in this round asked me to explain the solution of this problem. So I tried and managed to come up with a solution. It is nearly identical to the official analysis. It goes something like this.

My solution

I implemented this solution and got AC. But while I was explaining this solution to him, I realized that my submitted code sorted the configurations in descending order! I re-submitted the code after fixing it to ascending order. Of course got AC too.

This led me to think that the following strategy may always work: re-roll the die if and only if it is impossible to reach the final goal.

I implemented this solution and submitted. Guess what? Another AC!

My implementation

As a math student, I want to prove that such strategy is always optimal, or the test cases are weak (which seems less probable). The official analysis does not mention this incident at all. Any idea how to prove?

Read more »

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

By jo_on, history, 10 months ago, In English

Hi Codeforces!

What if there are badges on Github profile that show our Codeforces ratings?

Recently, GitHub introduced a new feature in GitHub profile. In short, if you create a special repository with a name same with your GitHub username, its README.md file will appear on your main page, just like this.

While I was thinking about what to write in my profile, I thought it would be great if there is a way to put badges that show my ratings of competitive programming platforms such as Codeforces, TopCoder, and AtCoder. I first googled to find out if there is already someone who created such badges, but I couldn't. (Perhaps because I am a bad googler...)

So I decided to make my own! Fortunately, Shields.io offers great features to customize your badges. I used Shields.io functionality together with CF, TC, AC APIs to build a very simple server that serves badge images. It works like this:

https://run.kaist.ac.kr/badges/codeforces/jo_on.svg

https://run.kaist.ac.kr/badges/topcoder/kuratowski.svg

https://run.kaist.ac.kr/badges/atcoder/topology.svg

CF TC AC

How do they look like? Despite being the most basic design of Shields.io, they look pretty neat, don't they?

Currently, I'm using these badges in my GitHub profile. However, the server is not reliable since it depends on the health of the physical machine it is running on; it is very old and slow, and under certain circumstances, we (server admins) even have to turn off the machine for a while. So I'm hoping that one day someone will build a reliable competitive programming badge server with better badge designs.

Or are there already this kind of badges somewhere but simply I cannot find them? If you know any, please share!

Read more »

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