fork download
copy 
  1. /*
  2. QUESTION 1: Ordered Marble Grouping
  3.  
  4. Problem Statement:
  5. You are given marbles numbered from 1 to n. Each marble is currently placed
  6. in one of three boxes: A, B, or C.
  7.  
  8. In one operation, you may move any marble from its current box to another box.
  9.  
  10. After all operations:
  11. - Sort each box individually.
  12. - Join the boxes in this order: A, then B, then C.
  13. - The final joined sequence must be strictly increasing.
  14.  
  15. Return the minimum number of marbles that must be moved.
  16.  
  17. Hard Constraints:
  18. 1 <= n <= 100000
  19. Every value from 1 to n appears exactly once.
  20. Any box may become empty.
  21.  
  22. Example:
  23. A = [1, 5]
  24. B = [2, 3]
  25. C = [4, 6]
  26.  
  27. Expected Output:
  28. 2
  29.  
  30. Explanation:
  31. Move 5 from A to C.
  32. Move 4 from C to B.
  33.  
  34. Final:
  35. A = [1]
  36. B = [2, 3, 4]
  37. C = [5, 6]
  38.  
  39. Joined sequence:
  40. [1, 2, 3, 4, 5, 6]
  41.  
  42. Brute Force:
  43. Try every possible split of values.
  44. A gets the smallest segment, B gets the middle segment, and C gets the largest segment.
  45. For every split, count how many marbles are already in the correct final group.
  46.  
  47. Time Complexity:
  48. O(n^2)
  49.  
  50. Optimized Approach:
  51. While scanning values from 1 to n, final group labels must be non-decreasing:
  52. A...A B...B C...C
  53.  
  54. Use DP:
  55. dpA = maximum kept marbles if current value is assigned to A
  56. dpB = maximum kept marbles if current value is assigned to B
  57. dpC = maximum kept marbles if current value is assigned to C
  58.  
  59. Answer = n - max(dpA, dpB, dpC)
  60.  
  61. Time Complexity:
  62. O(n)
  63.  
  64. Space Complexity:
  65. O(n)
  66. */
  67.  
  68. #include <bits/stdc++.h>
  69. using namespace std;
  70.  
  71. class Solution {
  72. public:
  73.     int getMinMoves(vector<int>& groupA,
  74.                     vector<int>& groupB,
  75.                     vector<int>& groupC) {
  76.  
  77.         int n = groupA.size() + groupB.size() + groupC.size();
  78.  
  79.         vector<int> belongs(n + 1);
  80.  
  81.         for (int x : groupA) belongs[x] = 0;
  82.         for (int x : groupB) belongs[x] = 1;
  83.         for (int x : groupC) belongs[x] = 2;
  84.  
  85.         int dpA = 0;
  86.         int dpB = 0;
  87.         int dpC = 0;
  88.  
  89.         for (int x = 1; x <= n; x++) {
  90.             int keepA = (belongs[x] == 0);
  91.             int keepB = (belongs[x] == 1);
  92.             int keepC = (belongs[x] == 2);
  93.  
  94.             int newA = dpA + keepA;
  95.             int newB = max(dpA, dpB) + keepB;
  96.             int newC = max({dpA, dpB, dpC}) + keepC;
  97.  
  98.             dpA = newA;
  99.             dpB = newB;
  100.             dpC = newC;
  101.         }
  102.  
  103.         return n - max({dpA, dpB, dpC});
  104.     }
  105. };
  106.  
  107. int main() {
  108.     Solution sol;
  109.  
  110.     vector<int> A = {1, 5};
  111.     vector<int> B = {2, 3};
  112.     vector<int> C = {4, 6};
  113.  
  114.     cout << sol.getMinMoves(A, B, C) << endl;
  115.  
  116.     return 0;
  117. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/8KM1kH
language:
C++14 (gcc 8.3)
created:
9 hours 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!