fork download 
  1. /*
  2.     Problem: Maximum People That Can Sit Around a Table With Favorite Neighbors
  3.     Company Tag: Barclays OA
  4.  
  5.     Problem Statement:
  6.         We have N people.
  7.  
  8.         Each person likes exactly one other person.
  9.         A person will attend only if they sit next to the person they like.
  10.  
  11.         The table is circular.
  12.  
  13.         We need to find the maximum number of people who can attend.
  14.  
  15.     Constraints:
  16.         1 <= N <= 100000
  17.         1 <= likes[i] <= N
  18.         Each person likes exactly one person.
  19.  
  20.     Simple Brute Force:
  21.         Try every subset of people and every circular seating order.
  22.  
  23.     Why Brute Force Fails:
  24.         There are too many subsets and permutations.
  25.         This is impossible for N up to 100000.
  26.  
  27.     Better Idea:
  28.         Think of this as a directed graph.
  29.  
  30.         Each person points to the person they like.
  31.  
  32.         The answer can come from:
  33.             1. One big cycle of size at least 3.
  34.             2. Mutual pairs with chains attached to both people.
  35.  
  36.         For mutual pair a <-> b:
  37.             We can attach the longest chain ending at a
  38.             and the longest chain ending at b.
  39.  
  40.         Final answer:
  41.             max(largest cycle size, total contribution of all mutual pairs)
  42.  
  43.     Dry Run:
  44.         likes = [2, 1, 2, 3, 4]
  45.  
  46.         1 likes 2
  47.         2 likes 1
  48.         3 likes 2
  49.         4 likes 3
  50.         5 likes 4
  51.  
  52.         Mutual pair:
  53.             1 <-> 2
  54.  
  55.         Chain:
  56.             5 -> 4 -> 3 -> 2
  57.  
  58.         Seating:
  59.             1 - 2 - 3 - 4 - 5
  60.  
  61.         Answer = 5
  62.  
  63.     Time Complexity:
  64.         O(N)
  65.  
  66.     Space Complexity:
  67.         O(N)
  68. */
  69.  
  70. #include <bits/stdc++.h>
  71. using namespace std;
  72.  
  73. int maximumPeopleAroundTable(vector<int>& likes) {
  74.     int n = likes.size();
  75.  
  76.     vector<int> fav(n);
  77.     vector<int> indegree(n, 0);
  78.  
  79.     for (int i = 0; i < n; i++) {
  80.         fav[i] = likes[i] - 1;
  81.         indegree[fav[i]]++;
  82.     }
  83.  
  84.     queue<int> q;
  85.  
  86.     // depth[i] means the longest chain length ending at person i.
  87.     vector<int> depth(n, 1);
  88.  
  89.     // First remove all people who are not part of any cycle.
  90.     for (int i = 0; i < n; i++) {
  91.         if (indegree[i] == 0) {
  92.             q.push(i);
  93.         }
  94.     }
  95.  
  96.     while (!q.empty()) {
  97.         int person = q.front();
  98.         q.pop();
  99.  
  100.         int nextPerson = fav[person];
  101.  
  102.         // person can be placed before nextPerson, so update the chain length.
  103.         depth[nextPerson] = max(depth[nextPerson], depth[person] + 1);
  104.  
  105.         indegree[nextPerson]--;
  106.  
  107.         if (indegree[nextPerson] == 0) {
  108.             q.push(nextPerson);
  109.         }
  110.     }
  111.  
  112.     int largestCycle = 0;
  113.     int mutualPairTotal = 0;
  114.  
  115.     vector<int> visited(n, 0);
  116.  
  117.     for (int i = 0; i < n; i++) {
  118.         if (indegree[i] > 0 && !visited[i]) {
  119.             vector<int> cycle;
  120.  
  121.             int current = i;
  122.  
  123.             while (!visited[current]) {
  124.                 visited[current] = 1;
  125.                 cycle.push_back(current);
  126.                 current = fav[current];
  127.             }
  128.  
  129.             int cycleSize = cycle.size();
  130.  
  131.             if (cycleSize == 2) {
  132.                 int a = cycle[0];
  133.                 int b = cycle[1];
  134.  
  135.                 /*
  136.                     For a mutual pair, we can take the best incoming chain
  137.                     on both sides.
  138.                 */
  139.                 mutualPairTotal += depth[a] + depth[b];
  140.             } else {
  141.                 largestCycle = max(largestCycle, cycleSize);
  142.             }
  143.         }
  144.     }
  145.  
  146.     return max(largestCycle, mutualPairTotal);
  147. }
  148.  
  149. int main() {
  150.     int n;
  151.     cin >> n;
  152.  
  153.     vector<int> likes(n);
  154.  
  155.     for (int i = 0; i < n; i++) {
  156.         cin >> likes[i];
  157.     }
  158.  
  159.     cout << maximumPeopleAroundTable(likes) << endl;
  160.  
  161.     return 0;
  162. }
Runtime error #stdin #stdout #stderr 0.01s 5288KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
stderr 
double free or corruption (out)
https://ideone.com/GuV0zI
language:
C++14 (gcc 8.3)
created:
7 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!