Connection Status:
Competition Arena > MoveStones

MoveStones

SRM 683 · 2016-01-04 · by Arterm

SRM 683 · 2016-01-04 · by Arterm · Greedy, Simple Search, Iteration, Simulation
Class Name: MoveStones
Return Type: long
Method Name: get
Arg Types: (vector<int>, vector<int>)
Problem Statement

Problem Statement

There are n piles of stones arranged around a circle. The piles are numbered 0 through n-1, in order. In other words: For each valid i, piles i and i+1 are adjacent. Piles 0 and n-1 are also adjacent.

You are given two int[]s a and b, each with n elements. For each i, a[i] is the current number of stones in pile i, and b[i] is the desired number of stones for this pile. You want to move some stones to create the desired configuration. In each step you can take any single stone from any pile and move the stone to any adjacent pile. Find and return the smallest number of steps needed to create the desired configuration, or -1 if the desired distribution of stones cannot be reached.

Notes

  • At any moment during the game some piles may be empty. Empty piles still remain in place. For example, if pile 5 is empty, you are not allowed to move a stone from pile 4 directly to pile 6 in a single step. Instead, you must place the stone onto the empty pile 5 first.

Constraints

  • n will be between 1 and 1000, inclusive.
  • a will have exactly n elements.
  • b will have exactly n elements.
  • Each element of a and b will be between 0 and 10^9, inclusive.
Examples
0)
{12}
{12}
Returns: 0

The desired configuration is the same as the initial configuration. No steps are needed.

1)
{10}
{9}
Returns: -1

We cannot add or remove stones, we can only move them around the circle.

2)
{0, 5}
{5, 0}
Returns: 5
3)
{1, 2, 3}
{3, 1, 2}
Returns: 2

Move one stone from pile 1 to pile 0 and another stone from pile 2 to pile 0.

4)
{1, 0, 1, 1, 0}
{0, 3, 0, 0, 0}
Returns: 4
5)
{1000000000, 0, 0, 0, 0, 0}
{0, 0, 0, 1000000000, 0, 0}
Returns: 3000000000

Watch out for integer overflow.

Submissions are judged against all 64 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class MoveStones with a public method long long get(vector<int> a, vector<int> b) · 64 test cases · 2 s / 256 MB per case

Submitting as anonymous