Will there be a live stream this time?
I did the same too. 
@aneee004 hey can you explain your logic… I want to do this question but not able to understand editorial if you can tell your logic in simpler words then I may do this question…
Let’s visualize this entire problem as a graph with n nodes (the array elements) and m edges, the LCM constraints. For simplicity, I will assume that there is only one prime p involved. Calculating for multiple primes is just the product of individual contribution.
Once we create our adjacency matrix to represent the power of the prime, we loop through all vertices. For each vertex, we loop through all it’s edges, and store the minimum power of p that occurs. Let’s say this is base_i. We can clearly see that the vertex i (that is the number A_i) cannot be more than p^{base_i}, as crossing this value will violate the LCM constraint ‘base_i’ for some edge from vertex i.
We do the same, and store the maximum possible power a node can take, for each node. After this, let’s loop through all the given edges.
If both base_i and base_j are strictly less than edge_{ij}, then this is not possible to achieve. So we can immediately print
0. (Also note that it is not possible for base_i > edge_{ij}, as base_i is the minimum of all edges from i). This leads to some observations and a couple of cases.
- base_i, base_j \le edge_{ij}
Cases:
- If base_i < edge_{ij} and base_j < edge_{ij}, we print
0. - If base_i = edge_{ij} and base_j < edge_{ij}, then node i doesn’t really have a choice. To maintain the LCM constraint, node i had to be at it’s maximum capacity, and node j can be anything between 0 and base_j. (Note that node j might also have a constraint depending on other edges from j).
- If base_i = edge_{ij} and base_j = edge_{ij}, here one of them has to equal to edge_{ij} and the other has a free choice.
After computing all these node constraints, we run a dfs. (Note that there can also be multiple components). If we hit a node which has only one possibility, we continue the dfs. (Type 2).
If we hit a node of Type 3, we first fix that node as base_{i} and give free will for all it’s neighbors. After we count this, we backtrack and give free will for node i, and constraint all his neighbors, and append this to the final result!
So that’s it! After we run dfs on each component, the product of possibilities in each of them is the result for this particular prime. Multiply the result of all primes for the final answer.
12 Likes
After checking all subsets of V1 for vertex cover, what does this mean in setter’s solution? Can someone please help?
for(int b = 0;b < N;b ++) {
loop(msk, (1 << N)) if(!(msk & (1 << b))) f[msk] = add(f[msk], f[msk ^ (1 << b)]);
}
aneee can u suggest some reading material for problem solving or
describe the way u learnt cp;
I read algorithms from algorithms.wtf.
I got familiar with the C++ stl as I solved some problems from leetcode.
For DS, and other advanced algorithms, I just learn it from CodeChef editorials as they appear after every contest. (Like this one).
And upsolving one or two problems after a contest always helps.
3 Likes
Hi there could you guys say how you became so good at solving these kind of problems like using backtracking pruning and all and let alone knowing what to do
Thank
Hey
I wanted to raise a concern about the testcases used. Below I am attaching 2 links, both of them are my submissions and are exactly the same( i have checked them using diff on the linux terminal ). The issue is that while one of them is partially correct, the other one gets a WA. There was no announcement during the contest about the testcases being changed. I would appreciate if the problem author and the editorialist could shed some light on it.
CodeChef: Practical coding for everyone - partially correct solution
CodeChef: Practical coding for everyone - wrong answer
Thanks man very clean explanation I thought similar to that during contest but couldn’t able to think to merge for different prime separately I was trying to do it simultaneously and couldn’t able to do it… Now after reading your explanation I am in situation to try this question… And what does backtracking with pruning means??
1 Like
Pruning is just cutting off your search when you know that this path is not going to lead to something fruitful.
Example: Placing N Queens on a N \times N board, such that no queen attacks each other.
After placing i queens, if wee see that queen i - 1 is attacking queen i, there is no point in continuing the search. So we just cut off this entire branch.
5 Likes
So like you said we have 3 cases
And that leads us to only 2 possibilities everytime
- The power of a prime at the node is equal to the base value
- It is less than base.
This made for a bitmasking kind of an approach where all the masks could be checked without pruning
Later i just added backtracking with pruning. I initially thought of using the graph but even that wasnt needed.
Check my submission CodeChef: Practical coding for everyone
I just went from node i to node i+1 without caring about the relation between them xD
1 Like
Oh! This is a really nice approach. Whenever we see such a small n, there is almost always a bitmask solution 
.
I visualized the problem as a graph, so I guess my mind stuck to the graph implementation 
3 Likes
tnx bro for being active every time we reply
1 Like
Ohk thanks…
What was your approach can you explain?. And what does that mean i just went from node i to node i+1 without caring about relation between them ??
Lets see the problem as a graph problem (However just for understanding, no DFS or BFS 
)
First of all we will calculate answers for each power base and then would
multiply for answers for all powers, to get the final solution:
Here in my graph , ith index of array represents node ‘i’.
Lets solve the problem for power base p.
Lets say in the queries, A is connected to B and C with lcm’s being,
x and y resp. then max value at node A can be min(x,y) always.
(Lets say x was min, then if we give x+1 as node value, then the lcm
between A and B would exceed the given lcm would be >x, not valid.)
Now if we go through queries,
we will have an array (a) with max values of each node stored.
Let say arr is like = (a1, a2, a3, a4).
If no restrictions were there, then our answer would have been
Total arrays = (1+a1)(1+a2)(1+a3)…
Since allowed values for each is [0,ai]
But now there are restrictions of lcm between 2 nodes.
Now lets say if A and B was connected with lcm between them for
power p be ‘c’. Then if max value of both A and B is less than ‘c’
then we can never achieve that LCM. Thus if it happens in the graph
for any edge, our answer would be 0.
Lets say one of them is >=c (can always be at max c (Think! ;))
Then, we have to give one node a value of c and other node
can take whatsoever is wants , since their lcm would be c.
Here in the product = (1+a1)(1+a2)(1+a3)…
We are actually multiplying each possible value of node with others.
But this is not possible in case when edges is there bw nodes(both being less than c would mean invalid combination.)
, thus we would remove those terms in which any two nodes is
connected by an edge
For example
The graph was 1--------2
With lcm for power p being 3, and a1=3 and a2=3.
The possible values of array are :
0,3 ; 1,3 ; 2,3 ; 3,0 ; 3,1 ; 3,2 ; 3,3 = 1+3+3 = 1+a1+a2
( we deleted the term a1*a2 since there was an edge between 1 and 2).
Thus by following this algorithm, we find answers for each power
and then would multiply each other and get the answer.
(Beware of self edges-> say node a has self edge, then all the terms
with a gets deleted).
Overall Time Complexity → O(n^4)
My solution → https://www.codechef.com/viewsolution/35531057
2 Likes
Why accepted solutions are giving WA
accepted-CodeChef: Practical coding for everyone
WA- CodeChef: Practical coding for everyone
both codes are same.
Is there any changes in test case?
Yes…tc were updated.
why were all solutions not rejudged? Why was there no announcement about it?