0w1

SRM 673 Div2

Easy. BearSong

Problem Description:
Given an array with N elements, count number of elements that appeared exactly once.

Constraints:
1 ≤ N ≤ 50
1 ≤ A[i] ≤ 1000

Solution:
Functional

Code:

class BearSong {
 public:
  int countRareNotes(std::vector<int> notes) {
    return std::accumulate(notes.begin(), notes.end(), 0, [&](int s, int x) { return s + (std::count(notes.begin(), notes.end(), x) == 1); });
  }
};

Medium. BearSlowlySorts

Problem Description:
You are given an array with N elements.
Each turn you can apply an operation:
Choose a continuous segment with N - 1 elements, and sort them in place.
Output the minimum number of turns you need to sort the whole array.

Constraints:
3 ≤ N ≤ 50
1 ≤ A[i] ≤ 1000

Solution:
If one of the extreme values (min/max) were put in the right place (min at begin or max at end), obviously it only needs 1 turn.
The worst case to put an extreme value to its right position, is 2.
This happens in case like min element is at where max element is supposed to be at.
Anyway, we can ensure that the answer always does not exceed 3.
Hence we will try each possible configuration, and obviously doing the same operation in consecutive moves is redundant, hence the number of operations we will have to try is less than 3 + 3.

Code:

class BearSlowlySorts {
  bool sorted(const std::vector<int> &vec) {
    for (int i = 0; i + 1 < vec.size(); ++i) {
      if (vec[i] > vec[i + 1]) return false;
    }
    return true;
  }
  int solve(std::vector<int> w, int r) {
    if (sorted(w)) return 0;
    std::sort(w.begin() + !r, w.end() - r);
    return solve(w, !r) + 1;
  }
 public:
  int minMoves(std::vector<int> w) {
    if (sorted(w)) return 0;
    int ans = 0x3f3f3f3f;
    for (int i = 0; i < 2; ++i) {
      std::vector<int> t = w;
      std::sort(t.begin() + i, t.end() - !i);
      ans = std::min(ans, solve(t, i) + 1);
    }
    return ans;
  }
};

Hard. BearCavalry

Problem Description:
There are N warriors and N horses.
We have to match them.
The value of a pair is the product of their values.
The pair with the first warrior must not have lower value than any other pair.
Output the number of possible configurations, modulo 1e9 + 7.

Constraints:
2 ≤ N ≤ 50
1 ≤ V[i] ≤ 1000

Solution:
Enumerate each horse that the first warrior should use.
Then sort the remaining warriors in increasing order, the remaining horses in descending order.
Let T(i) be the number of warriors that could use horse[i] without exceeding the value of the pair of the first warrior.
The number of combinations when the horse for the first warrior is determined is the product of T(i) - i for each i.
We have monotonicity for T(i).
Since horse[i] ≥ horse[j] when i < j, T(i) ≥ T(j).
Hence the complexity is O(N**2).

Code:

class BearCavalry {
 public:
  int countAssignments(std::vector<int> warriors, std::vector<int> horses) {
    const int MOD = int(1e9 + 7);
    std::sort(warriors.begin() + 1, warriors.end());
    std::sort(horses.rbegin(), horses.rend());
    int res = 0;
    for (int i = 0; i < horses.size(); ++i) {
      int pi = 1;
      for (int hp = 0, wp = 1; hp < horses.size(); ++hp) {
        if (hp != i) {
          while (wp < warriors.size() && warriors[wp] * horses[hp] < warriors[0] * horses[i]) ++wp;
          pi = 1LL * pi * std::max(0, wp - 1 - (hp - (i < hp))) % MOD;
        }
      }
      (res += pi) %= MOD;
    }
    return res;
  }
};