Problem description, and the solution. Hey, this time I got first place! Although there's not much to talk about. The problem looks like a finite state machine problem. The states can be represented by a length $n$ ternary number, where the lowest digit represents the location of the largest disk, the second digit is the location of the second largest one, and so on. After each step, it transits to the next state, depending on the move. The solution can be found by, like the solution page says, finding the periods of the sequences. Both the state and the move must be considered. Or, just simulate the entire process. Out of all the problems that I've solved so far, this one is the most brute-forcible, if that's a word. Each game is represented by 3 integer arrays, which correspond to the disks on the 3 rods, and a index of the move. Each time, read the move and change the arrays accordingly. Usually the simulation of the periodic increment of the index is implemented as something like i=(i+1)%size; or i=i+1; if(i==size) i=0; But modulo and branching are costly operations, and the routine is called many times. To make it faster, I replaced it with a lookup table. The speedup is not huge, 90s to 63s, but still quite noticeable.
Monday, May 6, 2024
IBM Ponder this 2024 04 solution
Subscribe to:
Post Comments (Atom)
A Recursive Geometric Proof for 1962 IMO Problem 6
Youtube recommended a video to me, where the following problem is solved: Consider an isosceles triangle. Let $R$ be the radius of its circ...
-
H1269 description: You have a pointer at index 0 in an array of size arrLen. At each step, you can move 1 position to the left, 1 position ...
-
Since the solution is posted today , I'll share my solution below. Problem description is here . When I saw this problem, the first th...
-
M808 description: There are two types of soup: type A and type B. Initially, we have $n$ ml of each type of soup. There are four kinds of...
No comments:
Post a Comment