fork download
copy 
  1. /*
  2. Problem: Can we transform string M into string C using restricted swaps?
  3.  
  4. You have two strings M and C of the same length n.
  5. You can swap characters in M at positions that are exactly distance d or d+1 apart.
  6. Question: Can you transform M into C using these swaps?
  7.  
  8. Example:
  9. M = "abc", C = "bca", d = 1
  10. - You can swap positions 0 and 1 (distance 1): "abc" -> "bac"
  11. - You can swap positions 0 and 2 (distance 2 = d+1): "bac" -> "cab"
  12. - You can swap positions 1 and 2 (distance 1): "cab" -> "cba"
  13. - Keep going... eventually you can reach "bca" → YES
  14.  
  15. ==================================================================================
  16. HOW WE SOLVE THIS:
  17. ==================================================================================
  18.  
  19. KEY INSIGHT: If two positions can be connected through a chain of swaps,
  20. then we can rearrange characters between those positions however we want!
  21.  
  22. Think of it like this:
  23. - Position i can swap with position i+d and position i+d+1
  24. - Position i+d can swap with position i+2d and position i+2d+1
  25. - And so on...
  26.  
  27. So some positions form "groups" where characters can move freely within the group.
  28.  
  29. APPROACH:
  30. 1. Build groups of positions that are connected by swaps
  31.    - Use DSU (Disjoint Set Union) / Union-Find data structure
  32.    - Connect position i with i+d (if it exists)
  33.    - Connect position i with i+d+1 (if it exists)
  34.    
  35. 2. For each group, check if transformation is possible:
  36.    - Collect all characters from M at those positions
  37.    - Collect all characters from C at those positions
  38.    - Sort both collections
  39.    - If they match → we can rearrange M's characters to match C's characters
  40.    - If they don't match → impossible (we'd need different characters)
  41.  
  42. 3. If ALL groups can be transformed, answer is YES
  43.    Otherwise, answer is NO
  44.  
  45. Example walkthrough:
  46. M = "abc", C = "bca", n = 3, d = 1
  47.  
  48. Step 1: Build connections
  49. - Position 0 connects to 0+1=1 and 0+2=2
  50. - Position 1 connects to 1+1=2
  51. - Position 2 has no further connections
  52. Result: All positions 0,1,2 are in one group!
  53.  
  54. Step 2: Check if transformation is possible
  55. - Characters in M at positions {0,1,2}: {'a','b','c'} → sorted: "abc"
  56. - Characters in C at positions {0,1,2}: {'b','c','a'} → sorted: "abc"
  57. - They match! ✓
  58.  
  59. Answer: YES
  60.  
  61. Why this works:
  62. If two positions are in the same group, we can swap characters between them
  63. (possibly through intermediate swaps). So we can arrange characters in that
  64. group in ANY order we want. We just need to have the right characters available.
  65.  
  66. Time complexity: O(n × α(n)) for DSU operations, where α is inverse Ackermann
  67.                  O(n log n) for sorting in the worst case
  68. Space complexity: O(n) for storing groups and DSU structure
  69. ==================================================================================
  70. */
  71.  
  72. #include <bits/stdc++.h>
  73. using namespace std;
  74.  
  75. // Union-Find / Disjoint Set Union data structure
  76. // Helps us group positions that can exchange characters
  77. struct UnionFind {
  78.     vector<int> boss;  // boss[i] = leader of the group containing position i
  79.     vector<int> depth;    // depth[i] = approximate depth of tree rooted at i
  80.  
  81.     UnionFind(int n = 0) {
  82.         setup(n);
  83.     }
  84.  
  85.     void setup(int n) {
  86.         boss.resize(n);
  87.         depth.assign(n, 0);
  88.         // Initially, each position is its own boss (separate group)
  89.         for(int i = 0; i < n; i++) {
  90.             boss[i] = i;
  91.         }
  92.     }
  93.  
  94.     // Find the boss/leader of the group containing position i
  95.     int find_boss(int i) {
  96.         if(boss[i] == i) {
  97.             return i;  // i is the boss
  98.         }
  99.         // Path compression: make i point directly to boss for faster future queries
  100.         return boss[i] = find_boss(boss[i]);
  101.     }
  102.  
  103.     // Merge the groups containing positions a and b
  104.     void connect(int a, int b) {
  105.         a = find_boss(a);
  106.         b = find_boss(b);
  107.  
  108.         if(a == b) return;  // Already in same group
  109.  
  110.         // Union by depth: attach smaller tree under larger tree
  111.         if(depth[a] < depth[b]) {
  112.             swap(a, b);
  113.         }
  114.         boss[b] = a;
  115.         if(depth[a] == depth[b]) {
  116.             depth[a]++;
  117.         }
  118.     }
  119. };
  120.  
  121. int main(){
  122.     ios::sync_with_stdio(false);
  123.     cin.tie(nullptr);
  124.  
  125.     int n, d;
  126.     cin >> n >> d;
  127.  
  128.     string start_string, goal_string;
  129.     cin >> start_string >> goal_string;
  130.  
  131.     // Build groups of positions that can exchange characters
  132.     UnionFind uf(n);
  133.  
  134.     for(int i = 0; i < n; i++){
  135.         // Position i can swap with position i + d
  136.         if(i + d < n) {
  137.             uf.connect(i, i + d);
  138.         }
  139.  
  140.         // Position i can also swap with position i + d + 1
  141.         if(i + d + 1 < n) {
  142.             uf.connect(i, i + d + 1);
  143.         }
  144.     }
  145.  
  146.     // Group positions by their boss (leader)
  147.     // boss_to_positions[boss] = list of all positions with that boss
  148.     unordered_map<int, vector<int>> boss_to_positions;
  149.  
  150.     for(int i = 0; i < n; i++) {
  151.         int boss = uf.find_boss(i);
  152.         boss_to_positions[boss].push_back(i);
  153.     }
  154.  
  155.     // Check each group: can we rearrange characters to match?
  156.     for(auto& [boss, positions] : boss_to_positions){
  157.         // Collect characters from start_string at these positions
  158.         vector<char> start_chars;
  159.         start_chars.reserve(positions.size());
  160.         for(int pos : positions){
  161.             start_chars.push_back(start_string[pos]);
  162.         }
  163.  
  164.         // Collect characters from goal_string at these positions
  165.         vector<char> goal_chars;
  166.         goal_chars.reserve(positions.size());
  167.         for(int pos : positions){
  168.             goal_chars.push_back(goal_string[pos]);
  169.         }
  170.  
  171.         // Sort both to compare
  172.         // If they have the same characters (in any order), we can rearrange
  173.         sort(start_chars.begin(), start_chars.end());
  174.         sort(goal_chars.begin(), goal_chars.end());
  175.  
  176.         // If the characters don't match, transformation is impossible
  177.         if(start_chars != goal_chars){
  178.             cout << "NO\n";
  179.             return 0;
  180.         }
  181.     }
  182.  
  183.     // All groups can be transformed successfully!
  184.     cout << "YES\n";
  185.     return 0;
  186. }
Runtime error #stdin #stdout #stderr 0.01s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::length_error'
  what():  vector::_M_default_append
https://ideone.com/laoHF4
language:
C++14 (gcc 8.3)
created:
79 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!