fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. /*
  5. Problem: Minimum Operations to Make a Cuboid's Volume Zero
  6.  
  7. You are given three integers:
  8. - l = length
  9. - b = breadth
  10. - h = height
  11.  
  12. These represent the dimensions of a cuboid.
  13.  
  14. In one operation:
  15. 1. Compute g = gcd(l, b, h) using the current values
  16. 2. Choose exactly one among l, b, and h
  17. 3. Reduce that chosen dimension by g
  18.  
  19. You may repeat this operation as long as the dimensions stay non-negative.
  20.  
  21. Your task is to find the minimum number of operations needed to make
  22. the volume of the cuboid equal to 0.
  23.  
  24. Since volume = l * b * h, the volume becomes 0 as soon as any one
  25. of the three dimensions becomes 0.
  26.  
  27. ------------------------------------------------------------
  28.  
  29. Example 1:
  30. Input: l = 4, b = 6, h = 8
  31.  
  32. Step 1: gcd(4, 6, 8) = 2
  33. Reduce l by 2 -> (2, 6, 8)
  34.  
  35. Step 2: gcd(2, 6, 8) = 2
  36. Reduce l by 2 -> (0, 6, 8)
  37.  
  38. Now volume is 0, so answer = 2
  39.  
  40. ------------------------------------------------------------
  41.  
  42. Example 2:
  43. Input: l = 3, b = 3, h = 3
  44.  
  45. gcd(3, 3, 3) = 3
  46. Reduce any one dimension by 3 -> one dimension becomes 0
  47.  
  48. So answer = 1
  49.  
  50. ------------------------------------------------------------
  51.  
  52. Idea used here:
  53.  
  54. A useful trick is to normalize every state:
  55. - divide all three values by their gcd
  56. - sort them
  57.  
  58. Why does this help?
  59. Because multiplying all three dimensions by the same factor does not
  60. change the structure of future moves.
  61.  
  62. So normalized states are enough to represent the problem.
  63.  
  64. Then we do BFS:
  65. - each state is one normalized triple (a, b, c)
  66. - from that state, try decreasing one dimension by 1
  67.   (because after normalization, gcd becomes 1)
  68. - normalize again
  69.  
  70. BFS guarantees the first time we reach a state with one dimension = 0,
  71. it uses the minimum number of operations
  72.  
  73. ------------------------------------------------------------
  74.  
  75. Important note:
  76. This solution is exact, but it is practical only when the number of
  77. reachable normalized states is manageable.
  78.  
  79. If the actual hidden constraints are very large, then this BFS approach
  80. may be too slow and a more mathematical solution would be needed.
  81. */
  82.  
  83. struct State {
  84.     long long x, y, z;
  85.  
  86.     bool operator==(const State& other) const {
  87.         return x == other.x && y == other.y && z == other.z;
  88.     }
  89. };
  90.  
  91. struct StateHash {
  92.     size_t operator()(const State& s) const {
  93.         size_t h1 = hash<long long>()(s.x);
  94.         size_t h2 = hash<long long>()(s.y);
  95.         size_t h3 = hash<long long>()(s.z);
  96.         return h1 ^ (h2 << 1) ^ (h3 << 2);
  97.     }
  98. };
  99.  
  100. /*
  101. Normalize a state:
  102. 1. divide by gcd
  103. 2. sort the three values
  104.  
  105. This helps us avoid treating equivalent states as different.
  106. */
  107. static State normalizeState(long long a, long long b, long long c) {
  108.     long long g = gcd(a, gcd(b, c));
  109.  
  110.     if (g > 1) {
  111.         a /= g;
  112.         b /= g;
  113.         c /= g;
  114.     }
  115.  
  116.     array<long long, 3> vals = {a, b, c};
  117.     sort(vals.begin(), vals.end());
  118.  
  119.     return {vals[0], vals[1], vals[2]};
  120. }
  121.  
  122. class Solution {
  123. public:
  124.     int minimumOperations(long long l, long long b, long long h) {
  125.         State start = normalizeState(l, b, h);
  126.  
  127.         queue<State> q;
  128.         unordered_map<State, int, StateHash> dist;
  129.  
  130.         q.push(start);
  131.         dist[start] = 0;
  132.  
  133.         while (!q.empty()) {
  134.             State cur = q.front();
  135.             q.pop();
  136.  
  137.             int steps = dist[cur];
  138.  
  139.             // If any dimension becomes 0, volume becomes 0
  140.             if (cur.x == 0 || cur.y == 0 || cur.z == 0) {
  141.                 return steps;
  142.             }
  143.  
  144.             /*
  145.             Since this state is already normalized,
  146.             gcd(cur.x, cur.y, cur.z) = 1.
  147.  
  148.             So one move from here is equivalent to:
  149.             - decrease one dimension by 1
  150.             - normalize again
  151.             */
  152.             long long dims[3] = {cur.x, cur.y, cur.z};
  153.  
  154.             for (int i = 0; i < 3; i++) {
  155.                 if (dims[i] == 0) continue;
  156.  
  157.                 long long nextDims[3] = {dims[0], dims[1], dims[2]};
  158.                 nextDims[i]--;
  159.  
  160.                 State nextState = normalizeState(
  161.                     nextDims[0],
  162.                     nextDims[1],
  163.                     nextDims[2]
  164.                 );
  165.  
  166.                 if (!dist.count(nextState)) {
  167.                     dist[nextState] = steps + 1;
  168.                     q.push(nextState);
  169.                 }
  170.             }
  171.         }
  172.  
  173.         return -1;
  174.     }
  175. };
  176.  
  177. int main() {
  178.     Solution sol;
  179.  
  180.     cout << sol.minimumOperations(4, 6, 8) << '\n'; // 2
  181.     cout << sol.minimumOperations(3, 3, 3) << '\n'; // 1
  182.  
  183.     return 0;
  184. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
compilation info 
prog.cpp: In function ‘State normalizeState(long long int, long long int, long long int)’:
prog.cpp:108:26: error: ‘gcd’ was not declared in this scope
     long long g = gcd(a, gcd(b, c));
                          ^~~
prog.cpp:108:26: note: suggested alternative: ‘gcvt’
     long long g = gcd(a, gcd(b, c));
                          ^~~
                          gcvt
prog.cpp:108:19: error: ‘gcd’ was not declared in this scope
     long long g = gcd(a, gcd(b, c));
                   ^~~
prog.cpp:108:19: note: suggested alternative: ‘gcvt’
     long long g = gcd(a, gcd(b, c));
                   ^~~
                   gcvt
stdout 
Standard output is empty
https://ideone.com/pTuR7Q
language:
C++14 (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!