Thanks :D.

LOL :)

At least in the 100 point problem, We don't need to use a 32 bit number to represent 32 numbers.

I went with recursion in index of a bit, starting with the lowest one. That is rather slow in the worst case, but one can cut off some of the recursion branches that are not promising.

Every time we try to set a bit to 0, the set of the numbers that need to be matched with the mask stays the same, and if we set a bit to 1, all the numbers that have that bit set are taken care of, so on average, the set is cut in half.

This is probably not much worse on average than the intended solution, but I am not so sure about possible hacks. I managed to get it to pass the test cases in barely under 1s.

#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> a;
int bestres = 1000000000;
int bestbits = 30;
int curnum=0;

void f(int b, int bits, vector<int> & s){
    if(bits>bestbits || b==26)return;
    
    if(s[0]>=(1<<(b+1)) ){ // set bit b to 0
        if(curnum &(1<<b))curnum-=(1<<b);
        f(b+1, bits, s);
    }
    if(bits==bestbits)return;
    bits++;
    // set bit b to 1
    vector<int> s2(0);s2.reserve(s.size()); //s2.clear(); s2.resize(0); 
    for(int i=0; i<s.size(); i++){
        if(!(s[i] & (1<<b))){
            s2.push_back(s[i]);
        }
    }
    if(s2.size() == s.size())return;
    curnum|=(1<<b);
    if(!s2.size()){ //solved
          if(bits<bestbits){
              bestbits=bits; bestres = curnum;
          } else if(bits==bestbits && curnum<bestres){
              bestbits=bits; bestres = curnum;
              
          } 
    }else{
            f(b+1, bits, s2);
    }
    if(curnum &(1<<b))curnum-=(1<<b);
    
}
int main() {
    ios::sync_with_stdio(false);
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    cin>>n;
    a.clear(); a.resize(n);
    for(int i=0; i<n; i++){
        cin>>a[i];
    }
    sort(a.begin(), a.end());
    f(0, 0, a);
    cout<<bestres<<"\n";
    return 0;
}

You need this observation to solve the problem City Construction:

Future addition of nodes cannot change the answer for past queries

That is, the answer remains the same whether you solve a query the moment it is given or you solve the query after considering all the updates. Let's see why this is true. There are two ways to add a node.

1. The new node has a directed edge towards an old node. In this case, this new node can never be reachable from any old node no matter what the future updates are. Think for yourself why this is true

2. The new node has a directed edge coming from an old node towards itself. In this case the new node can never reach any old node no matter what the future updates are. Again think for yourself.

So now we have established that we can take all the updates at first and add the edges for each update and then process the queries. So now the problem becomes, given a directed graph, answer some queries like if it is possible to reach x from y?

We can solve this problem using dp if the graph was acyclic i.e DAG. So we divide the graph into strongly connected components and build a new graph with those components which will indeed be a DAG. Now our definition for the dp will be:

dp[i] = nodes which are reachable from node i

And our recurrence will be:

dp[i] = union of node i and all possible dp[j] where j is any node which can be reached from node i using one edge

So the complexity would be O(N*M) This is because for every edge we have to union two sets each of which can have size as large as N. Think of dp array as an array of boolean arrays and you or two boolean arrays of size N for each edge.

But instead of using a boolean array, you can use bitsets to optimize the solution to have a time complexity of O( ( N * M ) / log( number of bits in an integer ) which is basically ( ( 5*10^4 * 10^5 ) / 32 ) or simply around ( 1.7 * 10^8 ) operations which can easily pass under the time limit.

Hope this helps.

Did you run dfs on each query? This is O(n*q) and I don't think it can be optimized with bitsets in any way.

The solution in editorial works fast only because of bitsets. It's something like O(n^2 / (bitset_constant)).

I did the same as you. Additionally, I got a full score D 'City Construction' just by doing the following:

• Group each node based on its SCC
• For each SCC, run a DFS. If i-th component can visit j-th component, store that information in Map/Set.

This solution is supposed to be quadratic in time and memory, yet passed all cases.

I am really sorry for that. I tried to hack "Best Mask" with brute force and some greedy, but managed to get at most 75% points with tons of optimizations. I can give a code a bit later, because hackerrank is not available now.

As for "Road Trip" I didn't try to submit any solution, because I couldn't find normal solution even assuming, that tests are random. Seems like there are many queries with equal x_i in the testset :(

Usually last task on Codesprint (especially on data structures) has binary scoring system. I wonder why didn't they do it this time.

In city construction , I did meet in middle bfs. Started bfs from one node amd another bfs from other node but in reverse direction(maintaining reverse graph). If both bfs meet in middle then path exist else not. PAssed all test in jAVA

What is the straightforward way?

I do! It works under 0.6s in all testcases.

#include <bits/stdc++.h>
using namespace std;

bool cmp(int a, int b) {
    return __builtin_popcount(a) < __builtin_popcount(b);
}

int main() {
    ios::sync_with_stdio(false);
    int n, a[100005] = {}, z1 = 30, z2 = 100000000;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a, a + n, cmp);
    for (int i = 1; i < 67108864; i++) {
        bool y = 0;
        int x = __builtin_popcount(i);
        if (x >= z1) continue;
        for (int j = 0; j < n; j++) if (!(a[j] & i)) {y = 1; break;}
        if (!y) {
            z1 = x;
            z2 = i;
        }
    }
    cout << z2;
}

By the way, I wonder if this method is actually correct. Can anyone prove its correctness or give a counterexample?