@all_too_well can u put the first question as well?
All you have to do is for every interval find the valid no. of walks of length = query range.
This can be done by matrix exponentional
1 Like
Anyone who was actually able to do the 3rd Q?
Can you elaborate a bit on your approach for the second problem?
Can anyone share the code for the first question who passed all the testcases.
Thanks in advance!!
1 Like
There was some error in my code so i have uploaded the updated code now.
We only need to know the parity of path length so dp[i][0] represents number of paths from x of even length and dp[i][1] for odd. We will mark dp[x][0]=0 and dp[x][1]=1 and then proceed with dfs.
We should only call dfs function for a node if all the nodes who have incoming edges to this node are already visited. Then simply number of odd length paths from vertex u to v is equal to number of even length paths to vertex u. Using this we compute values for all dp[i].
I didnât submit this in the contest so i couldnât check if its working.
@loopfree Can you have a look into this?
@all_too_well Bro can you explain your approach for first problem my code passed 35/42 testcases only�?
Yes, I passed all test cases for 3rd problem with simple dp.
dp_odd[i] += dp_even[j]
dp_even[i] += dp_odd[j],
where node i and j are neighbours and i preceeds j in topo order.
Since I am a beginner in Graphs, can you please explain your solution in a bit detail with an example? Will be of great help to beginners like me.
Refer to this thread for the authorâs solutions: Help needed in Codenation Hiring Test problem - Codeforces
@ankur314 ankur314 why the expected value of sum of divisors did not work ? , first i found sum of divisors of all numbers in range L1 , R1 and then in L2,R2 then divide by their size ie. (R1-L1+1)
thus is would get expected value of the sum of divisors and it was giving WA, can you explain why? and which ever range has higher expected value i outputed it.
Because expected value and probability are quite different things. For example, suppose the number of factors for A = [3, 5] and number of factors for B = [1, 7], the probability of A winning = 1/2 and probability of B winning = 1/2. Now consider different set of number of factors, for A = [3, 5] and B = [1, 100]. The answer is still going to be draw as pA = 1/2 and pB = 1/2. But the expected value is much higher for B, so EV approach will give B as answer.
1 Like