Advertisement
VladNitu

honsLawnMowingVlad

Feb 12th, 2024
963
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.80 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include<ext/pb_ds/assoc_container.hpp>
  3. #include<ext/pb_ds/tree_policy.hpp>
  4. using namespace __gnu_pbds;
  5. using namespace std;
  6. template <typename T>
  7.  
  8.  
  9. #define NMAX (int)(2e3 + 2)
  10. #define MMAX (int)(2e3 + 2)
  11. #define INF (int)(1e9)
  12. #define ll long long
  13. #define mkp make_pair
  14. #define mkt make_tuple
  15. #define lsb(x) (x & -x)
  16.  
  17. void __print(int x) {cerr << x;}
  18. void __print(long x) {cerr << x;}
  19. void __print(long long x) {cerr << x;}
  20. void __print(unsigned x) {cerr << x;}
  21. void __print(unsigned long x) {cerr << x;}
  22. void __print(unsigned long long x) {cerr << x;}
  23. void __print(float x) {cerr << x;}
  24. void __print(double x) {cerr << x;}
  25. void __print(long double x) {cerr << x;}
  26. void __print(char x) {cerr << '\'' << x << '\'';}
  27. void __print(const char *x) {cerr << '\"' << x << '\"';}
  28. void __print(const string &x) {cerr << '\"' << x << '\"';}
  29. void __print(bool x) {cerr << (x ? "true" : "false");}
  30.  
  31. template<typename T, typename V, typename W>
  32. void __print(const std::tuple<T, V, W> &x) {cerr << '{'; __print(std::get<0>(x)); cerr << ','; __print(std::get<1>(x)); cerr << ','; __print(std::get<2>(x)); cerr << '}';}
  33. template<typename T, typename V>
  34. void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
  35. template<typename T>
  36. void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
  37. void _print() {cerr << "]\n";}
  38. template <typename T, typename... V>
  39. void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
  40. #ifndef ONLINE_JUDGE
  41. #define dbg(x...) cerr << "[" << #x << "] = ["; _print(x)
  42. #else
  43. #define dbg(x...)
  44. #endif
  45.  
  46. enum REMOVE {top_row, bottom_row, left_col, right_col};
  47.  
  48. struct Candidate {
  49.     ll val;
  50.     REMOVE type;
  51. };
  52.  
  53.  
  54. int  N, M, K;
  55. vector<vector<int>> a, aT;
  56.  
  57.  
  58. /*
  59.  * Returns the sum of the submatrix that spans: top_left corner: {i_up, j_up} and bottom_right corner {i_down, j_down}
  60.  *
  61.  */
  62. int get_sum(const vector<vector<int>>& prefix_sum, int i_up, int j_up, int i_down, int j_down) {
  63.     // See notes for drawing
  64.     return prefix_sum[i_down][j_down] -  prefix_sum[i_up - 1][j_down] - prefix_sum[i_down][j_up - 1] + prefix_sum[i_up - 1][j_up - 1];
  65. }
  66.  
  67. /*
  68.  * Helper funtctions that computes the prefix sum of `a` : N x M (2D array) and returns it
  69.  * Returns: N x M matrix of prefix sum
  70.  */
  71. vector<vector<int>> precompute_prefix_sum(const vector<vector<int>>& a, int N, int M) {
  72.     //Reference:  https://www.pbinfo.ro/articole/5615/sume-partiale-in-tablouri
  73.      vector<vector<int>> prefix_sum(N + 1, vector<int>(M + 1, 0));
  74.     for (int i = 1; i <= N; ++i)
  75.         for (int j = 1; j <= M; ++j)
  76.             prefix_sum[i][j] = a[i][j] + prefix_sum[i-1][j] + prefix_sum[i][j-1] - prefix_sum[i-1][j-1];
  77.     return prefix_sum;
  78. }
  79.  
  80. /*
  81.  * Helper function that reduces all Rows of 2D Array `a`, where `a`: N x M
  82.  * Returns: min. # of mowing sessions required
  83.  */
  84. int solve (const vector<vector<int>>& a, int N, int M) {
  85.  
  86.     vector<vector<int>> prefix_sum = precompute_prefix_sum(a, N, M);
  87.  
  88.     int mn = N + M - 1; // worst-case solution
  89.  
  90.     for (int remove_left_cols = 0; remove_left_cols <= M - 1; ++remove_left_cols) { // O(M)
  91.         // Try removing all rows; when stuck (no row is removable): remove `remove_left_cols` columns from the left; when we get stuck: remove columns from the right as many as needed
  92.         // if no solution found => We cannot solve the problem w/ these many "tokens"
  93.  
  94.         // NOTE: the order of removing top or bottom row is IRRELEVANT, as in the end we will have been removed all the rows
  95.  
  96.         int top = 1, bottom = N, left = 1, right = M;
  97.         bool foreverStuck = false;
  98.  
  99.         while (top <= bottom && !foreverStuck) { //  while there are still rows to be removed; O(N + M)
  100.            if (get_sum(prefix_sum, top, left, top, right) <= K)  // top row can be removed
  101.                top ++;
  102.             else if (get_sum(prefix_sum, bottom, left, bottom, right) <= K) // bottom row can be removed
  103.                 bottom --;
  104.             else if (remove_left_cols > left - 1 && get_sum(prefix_sum, top, left, bottom, left) <= K) // Stuck from removing rows => if we allow ourselves to still remove rows from the left & `k` constraint holds
  105.                 left ++; // left col can be removed
  106.             else if (get_sum(prefix_sum, top, right, bottom, right) <= K) // `k` constraint can be removed and no other row/col can be removed (for rows we are stuck, for cols we can't remove `left` col anymore
  107.                 right --;
  108.             else
  109.                 foreverStuck = true;
  110.         }
  111.  
  112.         if (!foreverStuck) // potential solution found
  113.         {
  114.             int left_cols_removed = left - 1;
  115.             int right_cols_removed = M - right;
  116.             int cand = N + left_cols_removed + right_cols_removed; // `N` = all rows were removed
  117.             mn = min(mn, cand);
  118.         }
  119.  
  120.     }
  121.  
  122.     return mn;
  123. }
  124.  
  125. int main() { // O((N + M) ^ 2) TC
  126.     // TC Analysis:
  127.     // Case 1: remove all rows : O(M * (N +M)) = O(M*N + M^2)
  128.     // Case 2: remoev all cols <=> remove all rows in aT (transpose of `a` 2D array): O(N * (N + M)) = O(N^2 + NM)
  129.     // Summing up these 2 cases: O((N+M)^2) tc
  130.  
  131. //    freopen("instances/small/22_test.in", "r", stdin);
  132. //    freopen("instances/small/22_test.out", "w", stdout);
  133.  
  134.     // N * M matrix
  135.     cin >> K >> M >> N;
  136.  
  137.     a.resize(N + 1, vector<int>(M + 1));
  138.     aT.resize(M + 1, vector<int>(N + 1));
  139.  
  140.     for (int i = 1; i <= N; ++i)
  141.         for (int j = 1; j <= M; ++j) {
  142.             cin >> a[i][j];
  143.             aT[j][i] = a[i][j];
  144.         }
  145.  
  146.  
  147.     int minReduceAllRows = solve(a, N, M);
  148.     int minReduceAllCols = solve(aT, M, N);
  149.     int ans = min(minReduceAllRows, minReduceAllCols);
  150.  
  151.     std::cout << ans << '\n';
  152.  
  153.  
  154.     return 0;
  155. }
  156.  
  157.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement