Discussion of Problem Yeetzhee of Google Kickstart 2020 Round F

Revision en1, by jo_on, 2020-10-05 08:24:51

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?

Tags #googlekickstart

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English jo_on 2020-10-05 08:24:51 3737 Initial revision (published)