SORTVS - Editorial

editorial
, , ,
63

Indeed, the complexity would be O(N^3 * 2^N) if we had, for instance, a complete graph, but this can’t happen, because the number of arcs is at most N. This means that the avarege number of transitions in a state is O(1)

Another way to of phrasing this argument is that, for fixed values of ini and unused , the sum of the running times of all dp[ini][cur][unused] , over all possible values of cur , will be N.
So, if we sum up the running time of all states, we get O(N^2 * 2^N)

Apart from that, it does seem true that most of the states are not visited. I think we can prove some bound like the one you said by noticing there are some parity conditions on valid states

64

Ah thanks, I understand the complexity now. I realized that I kind of messed up in my own implementation, since I used an edge list and iterated over all N bits of the mask even if for some of them there wasn’t a transition.

I’ll think some more later about any parity conditions/finding a bound when I’m less tired lol. Thanks for the super interesting problem nonetheless! The proof that all the robot moves can be done first is the best part imo

1 Like
66

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

1 Like
67

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

69

What is the time complexity of this code snippet?

70

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

1 Like
71

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

72

O(3^k)

1 Like
73

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

74

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)?

75

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.

1 Like
76

Thank you, I got it. :smile:

77

yes you are right, thanks for pointing it out

79

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

80

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.”

image

81

2 Disjoint cycles can be an example

82

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

83

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

84

Thanks a lot I got it

86

Thanks. I got it.