Please post solutions of CCDSAP

Can anyone provide solutions of problems of the contest?

4 Likes

Problem tags / Hints -
BADMATH - Digit Dp, read any blog about it.
FASTROAD - Dijkstra. (Consider len/sp as road length find shortest path.)
SMCMP - DSU (Disjoint set union), read any blog about it.
NOTSIEVE - Note B−A≤1e6. Segmented sieve. Expected time complexity O(1e6*log(1e6)) per test case.
VERYHARD - Note 1≤K≤5. Maintain answer for all 5*5 (rem,k) possible pairs. You can use 25 BIT or 25 segment trees etc.

9 Likes

In VERYHARD won’t we need just 5 BIT’s instead of 25 ? As the k is given so we will only build for that given k , rem can be [0-4] for that we need 5 ?

True. Didnt noticed K is fixed.

Thanks a lot. :slight_smile:

BADMATH doesnt need dp , normal resursion is enough as number of empty space in string is not more than 15.

2 Likes

Nice catch.
2^{15} brute force is also enough.
@babangain My 2 cents after seeing this contest. Check constraints twice before implementing something in CCDSAP.

7 Likes

where can I find the CCDSAP Advanced level problem which gave it(july 2019).I badly need to upsolve it

@admin
@vijju123

AFAIK they are not made public.

3 Likes

then can it be made private(unique link with lot of random letters) for those who participated in it

Can someone please provide the solution of Problem HASHRAD.
https://www.codechef.com/FLPAST01/problems/HASHRAD

No. There is a lot of possibility of people leaking out the questions like that, especially those who failed to clear the exam.

I can share my code for BADMATH. Am I allowed to @vijju123 ?

so because of cheaters I understand

1 Like

for NOTSIEVE segmented sieve will find all primes in range but how to extend it to calculating score??

let i=p1^a1*p2^a2…pm^am
so i’ will be i divided by the prime factor with lowest power(exponent)
let that prime factor be pj
score=(a1+1)(a2+1)…(a(j-1)+1)(a(j+1)+1)…(an+1)

how will we calculate all this with segmented sieve in log(n) per number

So did u clear the exam ?

can you check my algorithm(https://www.codechef.com/viewsolution/26638584) in VERYHARD. I just want to know if my algorithm is correct as I know segment tree questions never get 100 in python

Plz can anyone share his or her solution of these questions

https://codeforces.com/blog/entry/8989
https://www.codechef.com/problems/CHEFDIV

I dont debug others codes. :slight_smile:
Submit it in c++ to know if its correct or incorrect.
P.S. - Link is inaccessible.