SORTVS - Editorial

[sanket_markan]

My basic approach is

1. First find all connected components of robot graph, and treat all numbers in single component as one node of the graph. (I have used DSU for the same)
2. Now directed edge is added into the graph, if there is a requirement of B at position A and component of A and B are not same. so directed edge com[A] → com[B] is added.
3. Now, run the DFS on the generated graph. if reach at some node which is
   a. Not Visited - increase the ans
   b. Visited But not in current path - increase the ans
   c. Visited and in current path - dont increase the ans (this edge represents cycle, so not counting this edge towards final ans)
   Also dont increase the ans for starting node of dfs (Basically, there is no edge to be counted in this case)

CodeChef: Practical coding for everyone O(n) solution

[rajarshi_basu]

in the transformed graph, each edge represents a certain index. hence, only 18 edges max

[sarodesparsh]

@arthurfn

for (int i = 1; i < (1 << k); ++i) {
        for (int j = i; j > 0; j = (j - 1) & i) {
            if (dp[j] && dp[i ^ j])
                dp[i] = max(dp[i], dp[j] + dp[i ^ j]);
        }
}

What is the time complexity of this code snippet?

[sayan_1999]

Sir, in your solution why the get method is returning character values?@arthurfn
Also if anyone else has understood setter’s solution, kindly provide the reason

[mrajaryan]

(1<<n) - 1 - (1<<i) what does this mean in setter solution

[everule1]

O(3^k)

[sayan_1999]

This is actually taking the subset of edges of which they have spoken in the editorial.

[sarodesparsh]

My simplification :

{=\sum_{i=1}^{2^k-1}{2^{cnt(i)}}}
{= \sum_{i=1}^{k}{(k,i)*2^i}}
{<2^k*\sum_{i=1}^{k}{( k,i)}} = 2^k*2^k = 4^k

Therefore, I got {O(4^k)}

How do you simplify to get O(3^k)?

[everule1]

j=(j-1)&i This line. This implies the set bits in j will be a subset of i, as in j&i==j. There are \binom{k}{i} numbers with i set bits, and j will have 2^i possible values. So we get \sum\binom{k}{i}2^i=3^k

Infact, it will go through all possible values of x such that x&i==x.

Edit : It seems you don’t know the math behind \sum\binom{k}{i}2^i=3^k
I will give a simple combinatoric proof.

Proof

Each bit has 3 choices, Either not in i and j, Only in i but not in j, or in both i and j, therefore there are 3^k possible values of i and j.

[sarodesparsh]

Thank you, I got it.

[arpitpandey992]

yes you are right, thanks for pointing it out

[nimishbansal]

Its use is like this

#define debug(args…) printf(args)
when they ran it locally they used to log with printf but when they have to submit instead of commenting or deleteing they just remove “printf(args)” so logs don’t get printed

[ritika_gupta]

Hi Can you please explain this part of your code?
How can there be a case as you commented
“if node i occurs in the path,
// and if its not detected in the dfs,
// then this is not a simple cycle.”

[sarodesparsh]

2 Disjoint cycles can be an example

[sarodesparsh]

I didn’t get what args... is in debug(args...)

[nimishbansal]

well the pattern … (triple dot) is used to accept unknown number of parameters.For more information you can have a look at

what does this ... (three dots) means in c++

[ritika_gupta]

Thanks a lot I got it

[sarodesparsh]

Thanks. I got it.

[ak1010]

Please provide comments in the code for easy understanding

[stunn_areeb09]

its actually Iteration of All subsets of a mask Refer this for the proof SOS Dynamic Programming [Tutorial] - Codeforces