PROBLEM LINKS :
Author: Tushar Kadam
Tester: Rushang Gajjal
Editorialist: Tushar Kadam
DIFFICULTY:
EASY
PREREQUISITES:
Inclusion- Exclusion Principle
PROBLEM:
Problem boils down to : Given n number of Railway stations arranged arranged one after the other.
Count number of stations not reachable from any of m trains where each of the m trains can skip some Xi stations after each halt.
SUPER QUICK EXPLANATION:
Count how many stations are reachable from given point using inclusion-exclusion principle and subtract it from total stations.
EXPLANATION:
You can not maintain some array like isVisited[] for each station and marked some station visited by iterating and skiping some Xi stations.But problem is that there can be 10^18 stations in row and you can not allocate such a large memory (Approx 10^9 GB !).
Lets solve the simple case first. Suppose you have n stations and only one train and this train skips x stations. Then total number of stations visied by this train will be floor( n /(x+1) ) stations.
Now consider 2 trains :
In this case Suppose 2nd train skips y stations then number of stations visited by 2nd train will be floor( n /(y+1)) but it may happpen that 2nd train visited same station which was already visited by first station hence to count total number of unique stations visied by both trains ,we have to subtract number of common stations because it was added twice in addition n/(x+1) + n/(y+1).
To find common stations one can use ( n / lcm (x+1,y+1)) where lcm is lowest common multiple.
This is what inclusion -exclusion principle is. To solve the problem you can generalized this idea.
One can visit here to know how to implement this principle easily.
Complexity Analysis :
To use inclusion-exclusion principle we have to find all the sets of numbers taken 1 at time , 2 at a time ,3 at a time … i.e power set of set.
which costs O(m * 2^m) here m is total number of elements in set.
We have m <= 10 trains and t<=10^3 test cases.
Hence overall complexity is O( t * m * 2^m) with given constraints it turns out to be. O(10^7)
As mentioned in the question :
Product of all Xi <= 10^18
Reason :
As we know lcm of co-prime or prime numbers is product of them. Hence to avoid overflow in answers,it was deliberatly added. Otherwise as we know
lcm(x,y) = (x * y) / gcd(x,y) . As x * y can overflow long datatype too but at the same time lcm(x,y) can be within long’s range if gcd(x,y) is big enough to bring back overflowed product (x*y) by dividing it.
Hence to avoid such cases it was mentioned in question that product of all Xi’s is less than 10^18.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution Java.
Tester’s Solution Python.