Google Code Jam 2018 1B-B题算法代码问题求助

Hey there! Let's break down potential issues with your code for the 2018 Google Code Jam 1B Problem B, since you mentioned you're unsure where it's going wrong. First, let's ground this in the problem's core: it's all about tracking resource conversion paths, with each machine offering two options—direct conversion (producing M[i] = d+a units of the next resource) or a "reverse" conversion (using N[i] = d-b units to feed into the other machine's chain). Your code starts setting up arrays for straight and crossed start points, but since it's cut off, I'll cover the most common pitfalls that trip up solvers here, plus tie them to what you've written so far.

Common Algorithm Defects to Check #

• Incomplete State Tracking
  You initialized arrays like straightMstart and crossedMstart, but if you're not properly updating these to track the minimal initial resource requirement for each machine's output, you'll miss optimal (or valid) conversion sequences. For this problem, every resource needs two tracked values:

  • The minimal initial resources needed to produce it via the straight, machine-specific path
  • The minimal initial resources needed if you cross over to use the other machine's conversion chain
    It's easy to neglect comparing these two paths and keeping the better (lower-cost) option for each step.

• Mishandling Equal Conversion Outputs
  Your code has a check if M[i] == M[i-1]:—but just checking equality isn't enough. If two machines produce the same resource, you need to merge their conversion paths to find the cheapest way to get that resource. For example, if machine i and i-1 both output resource X, you should compare the initial cost of getting X via machine i versus machine i-1, then retain the cheaper of the two for all future calculations.

• Ignoring the Circular Dependency
  The problem's conversion chain is circular: the last machine feeds back into the first resource. If you're processing machines in a linear order without accounting for this cycle, your state tracking will be incomplete. You typically need to break the cycle at a chosen point, process all machines, then verify that your state is consistent (i.e., the cost you calculated for the starting resource matches the cost you end up with after looping through all machines). Skipping this consistency check will lead to incorrect answers for cyclic cases.

• Incorrect Cross-Path Cost Calculation
  When calculating the cost for a crossed path, it's easy to miscalculate how much of the alternate resource is needed. For example, if you want to produce resource i via the crossed path, you need to compute how much of resource i-1 is required from the other machine's output, then translate that back to the initial resource cost. If your math here is off (like not accounting for the exact conversion ratios or integer division correctly), your entire cost model will be wrong.

Next Steps for Debugging #

Since your code is cut off, sharing the full implementation would let us pinpoint exact bugs, but here's a quick actionable step: test your code against the problem's sample inputs. For example, the first sample has 2 machines:

Machine 1: d=1, a=2, b=1 (converts 1 unit of resource 1 to 3 units of resource 2, or uses 1 unit of resource 1 to eliminate 1 unit of resource 2)
Machine 2: d=1, a=1, b=2 (converts 1 unit of resource 2 to 3 units of resource 1, or uses 1 unit of resource 2 to eliminate 2 units of resource 1)
If your code can't correctly compute the minimal initial resources for cases like this, that's a great starting point to isolate where your state tracking or cost calculation is failing.

内容的提问来源于stack exchange，提问作者MinSung Kim