I am trying to solve the problem for a while but couldn't come up a idea. It would be great if someone can help me to solve the problem. I am a bit weak at math. I think its related to probability. Problem Link: https://vjudge.net/contest/312875#problem/E PS: The contest is Ended.
Thanks a lot :) sorry for my poor English. :)
Let's first try to solve an easier version of the same problem, i.e for some $$$N$$$ and $$$X$$$, find the probability that the required sum is equal to $$$X$$$. Let's just focus on the $$$N^{th}$$$ roll for now (since each roll is independent). What are the possibilities? We see that if get $$$k$$$ ($$$1 \le k \le 6$$$) on the $$$N^{th}$$$ roll, then to get a sum $$$X$$$ we have to find the probability that sum was $$$X-k$$$ in the previous roll (i.e the $$$N-1 ^{th}$$$ roll). So if we have stored the previous answer (in this case answer to state $$$N-1,X-k$$$) then we can use it to find the current answer. Thus we can use this observation to get the dp recurrence as $$$ dp[i][j] = \frac{\sum_{k=1}^{6} dp[i-1][j-k]}{6} $$$ (base cases when $$$N=1$$$). However, we are not done yet. Since we need the answer for required sum to be atleast $$$X$$$, thus the final answer is $$$= \sum_{i=x}^{6N} dp[N][i]$$$ (the total sum can go till maximum $$$6N$$$). Total Time Complexity = $$$O(6NX)$$$ which is enough to pass the given constraints.
Can you please help me of this problem also. Problem Link: https://vjudge.net/problem/LightOJ-1032 Thanks :)
This problem can be solved using Digit DP on the bits (Read about Digit DP here if you haven't solved such problems before). Let $$$A$$$ be the binary representation of the given number $$$N$$$. Lets define some quantities now, namely:
$$$cnt[i][pre]$$$ where $$$i$$$ is the bit number and $$$pre$$$ is the tight parameter indicating if the prefix of the current number matches the binary representation of $$$A$$$ (read on Digit DP if you didn't understand this). This table will give the count of such integers.
$$$dp[i][bit][pre]$$$ where $$$i$$$ is the bit number (index), $$$bit$$$ is the previous bit (i.e bit at $$$i-1^{th}$$$ index, 0 or 1) and $$$pre$$$ is same as defined above. This $$$dp$$$ will store our required answer.
Now we can take cases (if $$$A[i] = 1$$$ or $$$0$$$, if $$$bit=1$$$ or $$$0$$$, if $$$pre= 1$$$ or $$$0$$$) and formulate a recurrence to calculate this $$$dp$$$. Time Complexity $$$= O(logN)$$$ per testcase
Few other resources to read up Digit DP: Hackerrank, GFG
For this problem you can refer to my code if you don't get it.