SRM 679 Div2

Easy. ListeningSongs

Problem Description:
There are two playlists.
A playlist consists of some songs, each described by the units of time it takes.
You have listen to at least T songs from each playlist.
Given that you have at most minutes to listen to songs, what's the maximum number of songs you can hear?

Constraints:
1 ≤ playlist.size ≤ 100
minutes ≤ 12000

Solution:
Sort and greedy.

Code:

class ListeningSongs {
 public:
  int listen(std::vector<int> durations1, std::vector<int> durations2, int minutes, int T) {
    if (std::min(durations1.size(), durations2.size()) < T) return -1;
    std::sort(durations1.begin(), durations1.end());
    std::sort(durations2.begin(), durations2.end());
    int seconds = minutes * 60;
    seconds -= std::accumulate(durations1.begin(), durations1.begin() + T, 0);
    seconds -= std::accumulate(durations2.begin(), durations2.begin() + T, 0);
    if (seconds < 0) return -1;
    int res = T << 1;
    int p1 = T, p2 = T;
    while (p1 < durations1.size() && p2 < durations2.size()) {
      if (std::min(durations1[p1], durations2[p2]) > seconds) break;
      seconds -= std::min(durations1[p1], durations2[p2]);
      ++res;
      durations1[p1] < durations2[p2] ? ++p1 : ++p2;
    }
    while (p1 < durations1.size() && seconds >= durations1[p1]) seconds -= durations1[p1++], ++res;
    while (p2 < durations2.size() && seconds >= durations2[p2]) seconds -= durations2[p2++], ++res;
    return res;
  }
};

Medium. ContestScoreboard

Problem Description:
Abbreviated.

Constraints:
The time is in range [1, 1e9)
A team has at most 25 submissions.
team.size ≤ 100

Solution:
Simulation. Instead of looking at every unit of time, look at those with at least one team's submission.

Code:

class ContestScoreboard {
 public:
   std::vector<int> findWinner(std::vector<std::string> scores) {
     std::set<int> clock = {0};
     for (std::string s : scores) {
       std::stringstream ss(s);
       std::string name;
       ss >> name;
       char t;
       int score, clk;
       while (ss >> score >> t >> clk) clock.emplace(clk + 1);
     }
     std::vector<int> res(scores.size());
     for (int e : clock) {
       int bid = -1;
       std::string bname;
       int bscore = -1;
       for (size_t i = 0; i < scores.size(); ++i) {
         std::stringstream ss(scores[i]);
         std::string name;
         ss >> name;
         char t;
         int score, clk;
         int sum = 0;
         while (ss >> score >> t >> clk) {
           if (clk < e) {
             sum += score;
           }
         }
         if (sum > bscore || sum == bscore && name < bname) {
           bscore = sum;
           bname = name;
           bid = i;
         }
       }
       res[bid] = 1;
     }
     return res;
   }
};

Hard. ForbiddenStreets

Problem Description:
Given a graph with N nodes and M edges, you want to know for each edge, if it were removed, how many pair of vertices will have their shortest distance changed.

Constraints:
N ≤ 100
M ≤ 2000
1 ≤ W[i] ≤ 1000

Solution:
Floyd Warshall to get all-pair distance and number of ways for shortest path, modulo some number (because it could be large).
An edge (x, y) is necessary for shortest path of (a, b) iff dist(a, x) + dist(x, y) + dist(y, b) == dist(a, b), and ways(a, x) * ways(y, b) == ways(a, b).
Check the latter with hash.

Code:

class ForbiddenStreets {
 public:
   std::vector<int> find(int N, std::vector<int> A, std::vector<int> B, std::vector<int> time) {
     constexpr int MOD[] = {int(1e9 + 9), int(1e9 + 31)};
     typedef std::vector<int> vec;
     typedef std::vector<vec> mat;
     std::vector<mat> ways(2, mat(N, vec(N, 0)));
     mat dist(N, vec(N, 0x3f3f3f3f)); {
       for (int i = 0; i < A.size(); ++i) {
         ways[0][A[i]][B[i]] = ways[0][B[i]][A[i]] = 1;
         ways[1][A[i]][B[i]] = ways[1][B[i]][A[i]] = 1;
         dist[A[i]][B[i]] = dist[B[i]][A[i]] = time[i];
       }
       for (int i = 0; i < N; ++i) {
         for (int j = 0; j < N; ++j) {
           for (int k = 0; k < N; ++k) {
             if (dist[j][i] + dist[i][k] < dist[j][k]) {
               ways[0][j][k] = 1LL * ways[0][j][i] * ways[0][i][k] % MOD[0];
               ways[1][j][k] = 1LL * ways[1][j][i] * ways[1][i][k] % MOD[1];
               dist[j][k] = dist[j][i] + dist[i][k];
             } else if (dist[j][i] + dist[i][k] == dist[j][k]) {
               (ways[0][j][k] += 1LL * ways[0][j][i] + ways[0][i][k] % MOD[0]) % MOD[0];
               (ways[1][j][k] += 1LL * ways[1][j][i] + ways[1][i][k] % MOD[1]) % MOD[1];
             }
           }
         }
       }
       for (int i = 0; i < N; ++i) {
         ways[0][i][i] = ways[1][i][i] = 1;
         dist[i][i] = 0;
       }
     }
     vec res(A.size());
     for (int i = 0; i < A.size(); ++i) {
       for (int j = 0; j < N; ++j) {
         for (int k = 0; k < N; ++k) {
           if (dist[j][A[i]] + time[i] + dist[B[i]][k] == dist[j][k]) { // shortest path length OK
             if (1LL * ways[0][j][A[i]] * ways[0][B[i]][k] % MOD[0] == ways[0][j][k]) { // must go through this edge OK -- first hash
               if (1LL * ways[1][j][A[i]] * ways[1][B[i]][k] % MOD[1] == ways[1][j][k]) { // -- second hash
                 ++res[i];
               }
             }
           }
         }
       }
     }
     return res;
   }
};