matbensch

Untitled

Feb 18th, 2022
136
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.45 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. #include <set>
  5.  
  6. using namespace std;
  7.  
  8.  
  9. int knapsack(vector<int> weights, vector<int> profits, int target){
  10.  
  11. vector<int> w;
  12. vector<int> p;
  13.  
  14. w = weights;
  15. p = profits;
  16.  
  17. vector<vector<pair<int, int>>> dp;
  18.  
  19. int n = w.size() - 1; // Number of items
  20.  
  21. int totalDelegsUpForContest = 0;
  22. for (int i = 0; i < weights.size(); i++){
  23. totalDelegsUpForContest += w[i];
  24. }
  25. int c = totalDelegsUpForContest; // Number of delegates up for contest
  26.  
  27. dp.resize(n+1, vector<pair<int, int>>(c+1, {1000000000, 100000000}));
  28. dp[0][0] = {0,0};
  29.  
  30. // Tabulate
  31. for (int i = 1; i < n + 1; i++){
  32. for (int j = 1; j < c + 1; j++){
  33. if (j - w[i] < 0){
  34. dp[i][j].first = dp[i-1][j].first;
  35. dp[i][j].second = dp[i-1][j].second;
  36. }
  37. else{
  38. dp[i][j].first = min(dp[i-1][j].first, dp[i-1][j-w[i]].first + p[i]);
  39.  
  40. if (dp[i-1][j].first > dp[i-1][j-w[i]].first + p[i]){
  41. dp[i][j].second += dp[i-1][j].second;
  42. }
  43. else {
  44. dp[i][j].second += dp[i-1][j-w[i]].second + w[i];
  45. }
  46. }
  47. }
  48. }
  49.  
  50. /**
  51. for (auto row : dp){
  52. for (auto elem : row){
  53. cout << "{ " << elem.first << ", " << elem.second << "} ";
  54. }
  55. cout << "\n";
  56. }
  57. **/
  58.  
  59. // Linear search in the proper area of the table for the pairs
  60. set<pair<int, int>> valid;
  61.  
  62. for (int i = 0; i < n + 1; i++){
  63. for (int j = target; j < c + 1; j++){
  64.  
  65. if (dp[i][j].second >= target){
  66. valid.insert(dp[i][j]);
  67. }
  68. }
  69. }
  70.  
  71. // Return first item in the ordered set's minimum number of voters
  72. return (*valid.begin()).first;
  73. }
  74.  
  75.  
  76. int main()
  77. {
  78. int s, di, ci, fi, ui;
  79. cin >> s;
  80.  
  81. // Stores stateNum : [di, ci, fi, ui]
  82. map<int, vector<int>> m;
  83.  
  84. // Vector of pairs ({State Number, Number of Delegates})
  85. vector<pair<int, int>> S;
  86.  
  87. int delegsToF = 0;
  88. int delegsToC = 0;
  89. int totalDelegs = 0;
  90. bool end = false;
  91.  
  92. for (int i = 0; i < s; i++){
  93.  
  94. cin >> di >> ci >> fi >> ui;
  95. totalDelegs += di;
  96. vector<int> stateDataVec {di, ci, fi, ui};
  97. m.insert({i, stateDataVec});
  98.  
  99. // Get the only undecided voters that matter into S
  100. if (fi + ui < ci){
  101. delegsToC += di;
  102. }
  103. else if (ci + ui <= fi){
  104. delegsToF += di;
  105. }
  106. else{
  107. S.push_back({i, di});
  108. }
  109. }
  110.  
  111. if (S.empty() && delegsToC <= delegsToF){
  112. cout << "impossible" << endl;
  113. end = true;
  114. }
  115. else if (S.empty() && delegsToC > delegsToF){
  116. cout << 0 << endl;
  117. end = true;
  118. }
  119.  
  120. // Calculate sum of delegates Ci can get
  121. int posDelegsC = 0;
  122. for (auto i : S){
  123. posDelegsC += i.second;
  124. }
  125.  
  126. // If number of delegates F has already won is greater than
  127. // number of delegates C has already won and delegates in contest
  128. // then it is impossible to win
  129. if ( (delegsToF >= (delegsToC + posDelegsC)) and !end){
  130. cout << "impossible" << endl;
  131. end = true;
  132. }
  133.  
  134. // Find minimum voters required such that delegSum (number of delegates to C)
  135. // is greater than the majority
  136. if (!end){
  137.  
  138. // Create profit and weight arrays
  139. vector<int> weights;
  140. vector<int> profits;
  141.  
  142. weights.push_back(0);
  143. profits.push_back(0);
  144.  
  145. for (int i = 0; i < S.size(); i++){
  146. weights.push_back(S[i].second);
  147.  
  148. // Calculate min_ui
  149. int stateNum = S[i].first;
  150. vector<int> stateData = m[stateNum];
  151. int totalVotersInState = stateData[1] + stateData[2] + stateData[3];
  152. int min_ui = (totalVotersInState / 2) + 1 - stateData[1];
  153.  
  154. profits.push_back(min_ui);
  155. }
  156.  
  157. // Calculate target
  158. // Target to hit should be the total delegates / 2 + 1 - delegsToC
  159. int target = totalDelegs/2 + 1 - delegsToC;
  160.  
  161. int ans = knapsack(weights, profits, target);
  162. cout << ans;
  163. }
  164. return 0;
  165. }
Advertisement
Add Comment
Please, Sign In to add comment