fork download
copy 
  1. /*
  2. QUESTION 5: Rebuilding the Hidden Order from Photos
  3.  
  4. Problem Statement:
  5. You are given 5 photos of the same group.
  6.  
  7. Each photo contains the same N distinct IDs exactly once.
  8.  
  9. There is one hidden original order.
  10. Each photo was formed from that original order by moving at most one ID
  11. to another position.
  12.  
  13. Recover the original order.
  14.  
  15. Hard Constraints:
  16. 1 <= N <= 20000
  17. Exactly 5 photos are given.
  18. All IDs are distinct.
  19. The answer is guaranteed to be unique.
  20.  
  21. Example:
  22. photos =
  23. [
  24.   [7, 3, 9, 1],
  25.   [3, 7, 9, 1],
  26.   [7, 9, 3, 1],
  27.   [7, 3, 1, 9],
  28.   [7, 3, 9, 1]
  29. ]
  30.  
  31. Expected Output:
  32. 7 3 9 1
  33.  
  34. Explanation:
  35. For any two IDs, their correct relative order appears in most photos.
  36. So majority comparison can rebuild the hidden order.
  37.  
  38. Brute Force:
  39. Try every possible ordering.
  40. Check whether each photo can be obtained by moving at most one element.
  41.  
  42. Time Complexity:
  43. O(N!)
  44.  
  45. Optimized Approach:
  46. For any two IDs x and y:
  47. x should come before y if x appears before y in at least 3 out of 5 photos.
  48.  
  49. Sort one photo using this majority comparator.
  50.  
  51. Time Complexity:
  52. O(N log N)
  53.  
  54. Space Complexity:
  55. O(N)
  56. */
  57.  
  58. #include <bits/stdc++.h>
  59. using namespace std;
  60.  
  61. class Solution {
  62. public:
  63.     vector<int> recoverOriginalOrder(vector<vector<int>>& photos) {
  64.         int k = 5;
  65.         int n = photos[0].size();
  66.  
  67.         vector<unordered_map<int, int>> pos(k);
  68.  
  69.         for (int p = 0; p < k; p++) {
  70.             for (int i = 0; i < n; i++) {
  71.                 pos[p][photos[p][i]] = i;
  72.             }
  73.         }
  74.  
  75.         vector<int> answer = photos[0];
  76.  
  77.         sort(answer.begin(), answer.end(), [&](int a, int b) {
  78.             int count = 0;
  79.  
  80.             for (int p = 0; p < k; p++) {
  81.                 if (pos[p][a] < pos[p][b]) {
  82.                     count++;
  83.                 }
  84.             }
  85.  
  86.             return count >= 3;
  87.         });
  88.  
  89.         return answer;
  90.     }
  91. };
  92.  
  93. int main() {
  94.     Solution sol;
  95.  
  96.     vector<vector<int>> photos = {
  97.         {7, 3, 9, 1},
  98.         {3, 7, 9, 1},
  99.         {7, 9, 3, 1},
  100.         {7, 3, 1, 9},
  101.         {7, 3, 9, 1}
  102.     };
  103.  
  104.     vector<int> ans = sol.recoverOriginalOrder(photos);
  105.  
  106.     for (int x : ans) cout << x << " ";
  107.     cout << endl;
  108.  
  109.     return 0;
  110. }
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
7 3 9 1
https://ideone.com/5KwJ1K
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!