Contest: Winter Code Sprint
### [Good Indices](https://www.codechef.com/WCS2019/problems/WCS) **Prerequisites:** None The question is very straight forward as we just need to check whether $A_{A_i}$ is equal to $i$ or not. If it is not equal to $i$ then the given index is not good. And at last the total number of indices which are not good is the answer for a given test case.
Find X
Prerequisites: XOR properties, prefix arrays, bit manipulations
- For three non-negative integers A, B and C;
- A \oplus B = C
- A \oplus C = B
- B \oplus C = A
- For any integer A,
- A\oplus A = 0
- If A and B can be represented in n and m bits respectively then number of bits required to represent A \oplus B will never exceed max(n, m) bits.
Now, it is given that the maximum value of any A_i and X will never exceed 2^{31}-1, therefore based on the third property described above, XOR value will never exceed 2^{31}-1. Which means the maximum possible value is 2^{31}-1.
Our task is to find X such that A_L\oplus A_{L+1}\oplus … \oplus A_R \oplus X = 2^{31}-1.
Let say A_L\oplus A_{L+1}\oplus … \oplus A_R = Y
Now, X \oplus Y = 2^{31}-1. Based on the first property described above we can say that Y \oplus (2^{31}-1) = X, which is our required answer.
But we still have to calculate the value of Y efficiently. Here we can apply the concept of prefix arrays.
For each valid-i, prefix[i]=A_1\oplus A_2\oplus ... \oplus A_i
A_L\oplus A_{L+1}\oplus … \oplus A_R = prefix[R] \oplus prefix[L-1]
Now, simply X = prefix[R] \oplus prefix[L-1] \oplus (2^{31}-1)
Prime Addition
Prerequisites: Goldbach’s Conjecture and Goldbach’s Weak Conjecture
We can divide the solution into two parts:
-
N is even:
When the given integer N is even, then as per the Goldbach’s Conjecture we can simply say that only 1 addition operation is required as an even number can always be represented as the sum of two prime numbers. -
N is odd:
When the given integer N is odd, then as per Goldbach’s Weak Conjecture every odd number can be represented as the sum of 3 prime numbers. But if very carefully observe for a given odd number N if N-2 is a prime number then the number N can be represented as the sum of two prime numbers i.e. (N-2) + 2, this is because 2 is the only even prime number. Therefore for a given odd N if N-2 is prime then answer is 1 else answer is 2.
Corner cases:
As 1, 2 and 3 cannot be represented as the sum of two or more prime numbers, the answer for these numbers is -1.
An Odd Question
Prerequisites: Graph theory, modular arithmetic, fast exponentiation, combinatorics.
It is given that the input graph is complete with N nodes. Therefore the total number of edges E in a complete graph having N nodes is N*(N-1)/2.
-
If E is odd then the given graph is already an odd graph.
- Out of E edges we can select and delete any 2, 4, 6, ... , E-1 edges to make the graph odd.
- \binom E0 + \binom E2 + \binom E4 + ... + \binom E{E-1} = 2^{E-1}
-
If E is even then given graph is not an odd graph.
- Out of E edges we can select and delete any 1, 3, 5, ... , E-1 edges to make the graph odd.
- \binom E1 + \binom E3 + \binom E5 + ... + \binom E{E-1} = 2^{E-1}
-
Since E can be as large as 10^{18}, we need to use concept of fast modular exponentiation to find value of 2^{E-1}.
Corner case: N = 1 is a corner case here and the answer will be 0 as there is no way we can convert it into an odd graph.
Prime Factors and Ranges
Prerequisites: Sieve of Eratosthenes, prefix arrays
The question simply asks you to calculate the number of integers are having k distinct prime factors in a given range [L, R].
We have to calculate the number of distinct prime factors for each number until 10^6. By applying some modifications on the sieve of Eratosthenes we can do that efficiently. On each visit of a number, we can increment a count by 1 for that number to remember about its distinct prime factors.
Here one observation you have to make is that no number till 10^6 will have distinct prime factors greater than 7. Therefore, In each query having the value of k > 7, the answer will always be 0.
For 0\leq k \leq7,
We can create 2D prefix array$(prefix[10^6][8]
