The editorials for the problems SEAGCD2 and CHEFNUM in may long challenge 2016 which i’ve been waiting for are not yet posted. Plase upload them fast!!!
2 Likes
Chill mate. It’s not easy to prepare an editorial and they make really good editorials so it’s worth the wait. According to their tweet, they are still preparing the remaining two. https://twitter.com/codechef/status/732141915903279104
2 Likes
Kevin says that they will be ready till Wed.
well you can use bitmask dp in seagcd2.
For chefnum hint : no like 12xyz and 13xyz will have same amazingness . use can use this to find sum(club 100 no together so you will req 10^7 mem space for storing sum till 10^9 ) and store it in array.
My approach to SEAGCD2:
Create an undirected graph with vertices 1\sim 100 and edge (i,j) iif \gcd(i,j)=1. Remove all vertices whose number is a prime and >50. Then there are not many independent sets in this graph, brute force to find them all, and we can find the answer easily.
To CHEFNUM:
Hahaha I precalculated \sum_{i=1}^{125000}f(i),\sum_{i=125001}^{250000} f(i),\sum_{i=250001}^{375000}f(i),etc, where f is the function of amazingness. I stored these numbers in my program and its length is only 40K. And, I can answer a query using O(125000) time.
Detailed explanation here(Chinese)
1 Like
lol. I had the same idea with your CHEFNUM solution, but I didn’t think it would fit in the 50kb limit so I skipped it. I got AC wiht bitmasking dp solution though 
In SEAGCD2 I followed this approach:
Consider ‘large primes’ to be all primes greater than sqrt(n) and ‘small primes’ to be all primes lesser than or equal to sqrt(n). The key idea is that for any number upto n, it can have only one large prime as it’s factor. And all numbers except 1 can appear a maximum of once in any valid array so we can solve for 2,3…n and insert the required number of 1’s later.
Then I maintained a table indexed by the number of large primes used and the binary encoded sequence of small primes used. ( eg. if i used primes 2,3 and 7 the encoding will be 1101. The table has pow(2,number_of_small_primes) number of columns and number_of_small_primes + 1 number of rows. At every index I stored a vector containing the sizes of different sets following that pattern. I have not considered any 1’s yet, I’ll insert them later. I then ‘inserted’ the remaining number of large primes into the sets( remember only one large prime can be a factor, we deal with that then the others can be taken).
Finally To achieve the required size k I inserted remaining number of 1’s and took all possible permutations as we had to find number of arrays and not just sets.
See this answer for a better explanation . Note that in that question it was required to find sets and not arrays and so all numbers could be taken only once and order did not matter.
The question appeared here: Problem I coprime subsets
Here is my solution to the problem SEAGCD2: Solution Link
Explanantion:
I have solved the problem recursively. First of all I fix the number of one’s in the array. Then the task is to fill the remaining places with numbers between 2 to m. In the pre-computation part I have stored all the factors of a numbers as a vector, calculated the factorials and inverse factorials and for every number marked the smallest prime factor for it (for a prime, it is number itself). In the main loop, t1 contains list of primes and t2 contains list of composites to be considered for the given test case.
In the recursion part, I solve it in 2 parts:
- If a insert a prime number, say x, then the remaining places can also be inserted by a prime number only (which is basically choosing y remaining places from a list of primes i have, denoted by nCr(sz(li), r) in my code.
- If a insert a composite number, then I remove it’s prime factors and other composite numbers not co-prime to it and recurse further. (To do this efficiently, since i have calculated all the prime factors of the numbers initially, removing primes was a relatively easy task. For the composites there were 2 options either use inbuilt gcd function and check if it was not 1, remove the composite number or else check whether the composite number is divisible by any of the prime factor of given composite number. The second method proved to be faster because of just one mod operation whereas gcd option was bit slow because calculating gcd takes O(log(max(a,b))) complexity.)
Also, it can be seen that if I have an array of size greater than 25, than atleast one 1 has to be inserted to ensure gcd of all pairs is one. The proof is fairly trivial. So, just to ensure overall nice complexity, I inserted (n-m) to n ones and solved rest using recursion.
For further doubts, you can ask in comment section below.
The remaining editorials have been posted. You can check them [here][1].
[1]: https://discuss.codechef.com/tags/may16%2Ceditorial/