Can someone tell the solution of DGTCNT of the long challenge.
this is out of context ,but could you provide the approach to solve the Bear and Clique Distances problem?
Mee too, Bear and Clique Distances.
In CLIQUED, you needed to do a normal dijkstra without the k edges amoung themselves.
Then take the minimum of the first k edges. Let’s call that c.
Then iterate for each of the first k vertices and if it is less than c+x update it with c+x.
Then do another dijkstra.
1 Like
I computed the answer using the following technique. The total number of elements in the range is r-l+1.
First consider {0,1,2,3,4,5,6,7,8,9} as a set of 10 elements.
Now I find the number of bad elements. To do this I computed the number of elements in the range having a0 0’s , a1 1’s and so on (subset of 1 element). But this has extra counting and so we must add elements having (a0 0’s , a1 1’s) , (a0 0’s , a2 2’s) and so on once(subset of 2 elements) . Now again we must subtract taking subset of 3 elements at a time and do the process for all 2^10-1 subsets (Numbers satisfying subsets containing even number elements must be added and odd number of elements must be subtracted).
Complexity - O(2^10 * 18 *10) (18 digits since 10^18 and each place has upto 10 values)
See my solution - CodeChef: Practical coding for everyone
3 Likes
@mathecodician could you elaborate ?
I did a normal dijkstra once on the k*(k-1)/2 + m edges but i could clear only the first subtask!
@mathecodician, Got it, Thanks. Could you tell me please when will they update the ratings for April Challenge as this was my 1st contest?
You can first simplify the problem from liked numbers between L and R to liked numbers between 0 and L and 0 and R and then subtract.
For liked number between 0 and x, the following strategy works:
Let’s say x is 321, then you can break it down into several subproblems:
321
320
31?
30?
2??
1??
9?
8?
7?
6?
5?
4?
3?
2?
1?
9
8
7
6
5
4
3
2
1
The fixed digits at the beginning modify the number of digits that are allowed in the variable part.
The ?? can be any combination of 0 to 9, if the combination of digits isn’t unlucky. To find the number of combination, we can use a bunch of n choose k’s. We start with 0 and pick try all choices that wouldn’t be unlucky and then choose how many 1 ones we want to have, etc. Some DP helps here, but I’m not sure if it is really required.
1 Like
I have done this problem using DP with bitmasking. Let’s say f(x) gives all the numbers till x such that no number violates the given conditions. So our problem breaks down to f(r) - f(l-1).
Then DP state that I used for this problem is :
dp[len][mask] stores the count of numbers with length len and only those digits which are set in the mask(thus mask can take up to 2^10 values for 10 digits [0 - 9]).
Pseudo code to compute this dp :
func f(x):
num_length = length(x)
for len in range[1 to num_length - 1]:
for mask in range[1 to 2^10]:
index = log2(mask & -mask) // this gives the first bit set in mask
new_mask = mask ^ (1<<index)
for count in range[1 to len]:
if count == a[index]
continue
if index == 0
if new_mask>0:
dp[len][mask] += dp[len - count][new_mask] * C[len-1][count]
else
dp[len][mask] += dp[len-count][new_mask] * C[len][count]
This way you can find all the numbers up till length - 1. To find the numbers with length equal the given number just fix digit one by one so the constraints will change, and build the dp following the same way again.
Hope this helps 
Here is the link to my solution : CodeChef: Practical coding for everyone
4 Likes
used 2 loops for k…hence TLE for large value of k.
You don’t need to use a double loop. First just leave those k*(k-1)/2 edges and do a normal dijkstra. Then take the min of all dist[i] (i -> 1 to k) and update what is given above.
Yes u got to do exactly the opposite. You do not need to add those k*(k-1)/2 edges. See my solution for more help.