0w1

SRM 687 Div2

Easy. Quorum:

Problem Description:
You are given N elements. Find the sum of the minimum K elements.

Constraints:
1 ≤ K ≤ N ≤ 50

Solution:
Sort and greedy.

Code:

class Quorum {
 public:
  int count(std::vector<int> arr, int k) {
    std::sort(arr.begin(), arr.end());
    return std::accumulate(arr.begin(), arr.begin() + k, 0);
  }
};

Medium. Quacking:

Problem Description:
Ducks "quack". You are interested in knowing the minimum possible number of ducks to generate a sequence. Also verdict if it is not a valid sequence.

Constraints:
1 ≤ s.size ≤ 2500

Solution:
Greedily gather each quack from the left as earlier as possible. Suppose a quack found in that way is in some interval [s, t], than we are to find the count of the position with maximum quacks lying on. We could simply add all values between [s, t], but it is more efficient to apply imosu.

Code:

class Quacking {
 public:
  int quack(std::string str) {
    const std::string QUACK = "quack";
    std::vector<int> vis(str.size()), field(str.size() + 1);
    int res = 0;
    int vis_cnt = 0;
    while (vis_cnt < str.size()) {
      int z = 0;
      int s = -1, t = -1;
      for (int i = 0; i < str.size(); ++i)
        if (!vis[i] && str[i] == QUACK[z]) {
          if (z == 0) s = i;
          if (z == 4) t = i;
          ++z;
          vis[i] = 1;
          ++vis_cnt;
          if (z == 5) break;
        }
      if (z < 5) return -1;
      ++field[s];
      --field[t + 1];
    }
    int cover_cnt = 0;
    for (int i = 0; i < str.size(); ++i) {
      cover_cnt += field[i];
      res = std::max(res, cover_cnt);
    }
    return res;
  }
};

Hard. Queueing:

Problem Description:
You have just finished shopping at a supermarket and you are heading to the checkout. There are two lines available. The first line currently has len1 people, while the second line has len2 people. In each line, the cashier is just going to start checking out the first person.
The time to check out a person depends on the cashier's experience. For each pair of positive integers (p,k): the probability that a cashier with experience p will take exactly k seconds to check out any single person is given by the formula *1. The cashier in the first line has experience p1, and the cashier in the second line has experience p2.
You are given the ints len1, len2, p1, and p2. Compute the probability that standing in the first line is a strictly better choice than standing in the second line. More precisely, compute the probability that the last person currently standing in the first line will finish checking out strictly before the last person in the second line is done.

Constraints:
All values are integers in range [1, 1000].

Solution:
dp[i][j]: i people in the first queue, j people in the second queue, the probability of the first queue finishes before the second
For each second, there will only be 4 types of transfer:
1. one person in the first queue is done, the second remains the same
2. one person in the second queue is done, the first remains the same
3. one person in the first queue is done, one in the second as well
4. no one is done in both queues So now let the probability that one person is done in queue z be p[z], nothing changes be q[z], we have
dp[i][j] = p[0] * q[1] * dp[i - 1][j]
+ p[1] * q[0] * dp[i][j - 1]
+ p[0] * p[1] * dp[i - 1][j - 1]
+ q[0] * q[1] * dp[i][j]
and moving around the equation we have
dp[i][j] = (p[0] * q[1] * dp[i - 1][j]
+ p[1] * q[0] * dp[i][j - 1]
+ p[0] * p[1] * dp[i - 1][j - 1])
/ (1 - q[0] * q[1])

Code:

class Queueing {
 public:
  double probFirst(int len1, int len2, int p1, int p2) {
    std::vector<std::vector<double>> dp(2, std::vector<double>(len2 + 1));
    for (int i = 1; i <= len2; ++i) dp[0][i] = 1;
    double p[2] = {1.0 / p1, 1.0 / p2};
    double q[2] = {1.0 - p[0], 1.0 - p[1]};
    for (int i = 1; i <= len1; ++i)
      for (int j = 1; j <= len2; ++j) {
        dp[i & 1][j] = p[0] * q[1] * dp[~i & 1][j];
        dp[i & 1][j] += q[0] * p[1] * dp[i & 1][j - 1];
        dp[i & 1][j] += p[0] * p[1] * dp[~i & 1][j - 1];
        dp[i & 1][j] /= (1.0 - q[0] * q[1]);
      }
    return dp[len1 & 1][len2];
  }
};

*1:1/p) * (1 - 1/p)^(k-1