Please post solutions of CCDSAP

help
28

Unordered map has a huuuge constant. In fact, if you replace it with array, I will not be surprised if the code becomes more than 10 times faster. Try that.

29

I have seen sometimes, un-ordered map working faster than normal map and sometimes the other way round… There is a blog in cf where a guy shows some policy based super-fast map and it has been the fastest till now compared normal/un-ordered-map :slight_smile:

2 Likes
30

I tried ordered map but it also giving TLE.

Edit: Thanks @vijju123 Got AC using ( array of size 5 instead of map) + OptimizeIO + using “\n” instead of endl

2 Likes
31

Hey guys , i have a doubt regarding ccdsap . Right now i have very littke knowledge of Dynamic programming and graphs . Can you please suggest me when to attempt CCDSAP advanced exam and how much time does it take for practicing these concepts. I have already cleared foundation level .

32

6-Months it takes to become good in Dp+Graphs combined on an average. So start practicing now ! :slight_smile:

1 Like
33

Thanks dude !! :slight_smile:

1 Like
34

Will you please provide simple recursion approach for BADMATH, at least pseudo code for python. I’ve been trying for recursion since yesterday using Python, I am not able to do it. Please help us with recursion approach.

35

Fill out the leftmost blank ( or rightmost, anything is fine) with 0 or 1 and keep on doing this until there are no blanks left. Then check whether the number is divisible by the given number N.

For example: 1__1–>(11_1,10_1)
11_1–>(1111,1101)
10_1–>(1001,1011)

Check whether 1101,1111,1001,1011 are all divisible by the given number, if so, return 1

36

@dormordo Will you please help me where am I going wrong in the following code

def ans(a,i):
    global cnt 
    if i>=n-1:
        b = int(str(''.join(a)),2)     #converts binary to decimal
        if b%m==0:
            cnt += 1
            return cnt
    else:
        while i<n:
            if a[i]=='_':
                a[i] = '0'
                ans(a,i+1)
                a[i] = '1'
                ans(a,i+1)
            i+=1
    return cnt
for _ in range(int(input())):
    n,m = map(int,input().split())
    s = list(input())
    cnt = 0;ans(s,0)
    print(cnt)
37

Example :
1
5 2
1 _ _ _ 0
My assumption in recursion with this example is, the recursion should traverse in following way :
1 0 0 0 0
1 0 0 1 0
1 0 1 0 0
1 0 1 1 0
1 1 0 0 0
1 1 0 1 0
1 1 1 0 0
1 1 1 1 0
Recursion should be like following tree:

                                      _
                                    /    \
                                  0        1
                                /   \     /  \ 
                               0    1    0     1
                              /\   /\   / \   / \
                             0  1 0  1  0  1  0  1

Edit : Please correct me if I am wrong.

38 
def ans(x,b):
    if "_" not in x:
        return int(int(x,2)%b==0)
    else:
        j=x.index("_")
        p=x[:j]+"0"+x[j+1:]
        q=x[:j]+"1"+x[j+1:]
        return ans(p,b)+ans(q,b)
        
        
    
for a0 in range(int(input())):
    a,b=list(map(int, input().split()))
    s=input()
    print(ans(s,b))
1 Like
39

Thanks a lot @dormordo , you made logic simple :hugs:
This(me) dumb … need more practice on recursion problems.

1 Like
40

I wrote a solution to FASTROAD but only one test case passes. i cant find the error in the code!
Please help
code link - 7eyPGH - Online C++0x Compiler & Debugging Tool - Ideone.com

41

@nuttela can u explain logic of your solution, please!!

42

Suppose, you have the string as :

1 _ 0 _ 1 0

Now, let us try placing all combinations possible in the blank spaces :

Since, the total blank spaces are 2, I used a 2D array to store the binary combinations :

For this example :

0 0
0 1
1 0
1 1

Now, all you have to do is place every row in the blank gap from left to right and find the value under a modulo (the number which is to be divided) constraint to avoid large number errors.

If the modulo equals zero. I increment.

Print result. :slight_smile:

1 Like
43

Thankyou very much, your approach looks similar to BITMASKING.
I mean if we use Bitmasking for the blank spaces only, then at worst for 15 blank spaces we will have
2^15 combinations of 0’s nd 1’s.
i.e. 1. 000000000000000
2. 000000000000001
3. 000000000000010
so on… till
15. 111111111111111

44

Hi, can anyone tell why my code isn’t working?
Problem: CodeChef: Practical coding for everyone
My sol: 1T0FZ7 - Online C++0x Compiler & Debugging Tool - Ideone.com

45

This link doesn’t work! It says “403 access denied! you don’t have permission to see this page.”
What is the problem link, man?

46

Edited

47

Overflowing in function toint, instead precompute the values of 2^i\ mod\ m.