Connection Status:
Competition Arena > RaceCondition

RaceCondition

TCO19 Semifinal 1 · 2019-11-14 · by misof

TCO19 Semifinal 1 · 2019-11-14 · by misof · Greedy
Class Name: RaceCondition
Return Type: String
Method Name: minimize
Arg Types: (vector<int>)
Problem Statement

Problem Statement

Somebody implemented a distributed program that counts people entering a venue. The venue has N <= 26 gates, labeled by the first N letters of the English alphabet. Each gate runs a separate process that counts people who enter through that gate. There is a single global counter of people. Initially, the venue is empty and the counter is at zero.

Whenever a person enters through one of the gates, the process for that gate executes the following steps:

  1. Reads the current value of the counter into a local variable X.
  2. Increments X by one.
  3. Stores the new value X into the global counter.

Each step may take an arbitrary positive amount of time. All reads and writes happen sequentially, but as there are no locks, they can happen in any order. For each individual gate, the people are processed sequentially: the process for the next person is only started after the process for the previous person who used that gate terminates.

You are given the int[] gates with N elements: for each gate, the number of people who used it. Determine the smallest possible final value of the global counter, and return one possible sequence of events that produces it. Use lowercase letters to denote reads and uppercase letters to denote writes. (See Examples.)

Notes

  • Each increment of a local X implicitly happens between the corresponding read and write. The exact moment when that happens does not matter, so we do not denote these actions in the return value.

Constraints

  • gates will have between 1 and 26 elements, inclusive.
  • The elements of gates will be nonnegative.
  • sum(gates) will not exceed 500.
Examples
0)
{7}
Returns: "aAaAaAaAaAaAaA"

There is a single gate that is used by seven people, one after another. Nothing can go wrong, after everyone enters the global counter contains the value 7 as expected.

1)
{1,1,1,0,1}
Returns: "abceCBEA"

Five gates: four of them used once, the fifth one unused. The example output corresponds to the following sequence of actions: The four people enter at roughly the same time. The process for gate A reads the current value of the counter (0) into its local variable. The process for gate B reads the current value of the counter (0) into its local variable. The process for gate C reads the current value of the counter (0) into its local variable. The process for gate E reads the current value of the counter (0) into its local variable. The process for gate C writes the incremented value (1) into the global variable. The process for gate B writes the incremented value (1) into the global variable. The process for gate E writes the incremented value (1) into the global variable. The process for gate A writes the incremented value (1) into the global variable.

2)
{2,2,2}
Returns: "abcABCabcABC"
3)
{0}
Returns: ""
4)
{0,0}
Returns: ""

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

Coding Area

Language: C++17 · define a public class RaceCondition with a public method string minimize(vector<int> gates) · 79 test cases · 2 s / 256 MB per case

Submitting as anonymous