undefined_error_'s blog

By undefined_error_, history, 5 years ago, In English

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. :)

  • Vote: I like it
  • +8
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please help me of this problem also. Problem Link: https://vjudge.net/problem/LightOJ-1032 Thanks :)

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Code