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; } };