BRIEF EDITORIALS Winter Code Sprint

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]

)$ to remember which number is having $k$ $(0\leq k \leq7)$ distinct prime factors (refer setter's solution for more clarification). By precomputing this, we can solve each test case in $O(1)$ time. Setter's solution: [here](https://ideone.com/nNIhd9) ### [Seating Arrangement](https://www.codechef.com/WCS2019/problems/WCSF) **Prerequisites:** Connected component and depth-first traversal or disjoint sets, permutations, modular arithmetic. Using depth-first or disjoint sets we can easily find connected components. Lets say we have $K$ connected components each is having $C_i$ nodes ($1 \leq i \leq K$). Now, all $C_i$ members have to sit together, therefore we have $C_i !$ possibilities for each valid-$i$. Now as there are $K$ groups, so again there are $K!$ ways in which each group can be arranged. Formally, answer will be $C_1! * C_2! * ... *C_K! * K!$ **Feel free to Share your approach, If it differs. Suggestions are welcomed.**
2 Likes

I was stuck on the Prime Addition problem for all the time and I couldn’t attempt the last three problems.
Reason: The time complexity of my code was O(10^6) which is enough to pass in one second AFAIK but I was getting TLE all the time. I tried checking if for any input I would get infinite loop or anything like that by using asserts and what not xD.

After the contest ended, I saw a solution same as mine getting accepted because the guy used scanf and printf instead of cin and cout

Just now I tried solving the problem by including Fast I/O and it got accepted :stuck_out_tongue:

Solution:
With fast I/O :https://www.codechef.com/viewsolution/23210654

Without fast I/O: https://www.codechef.com/viewsolution/23210648

PS: Nice contest btw

You can precompute all the prime numbers till 10^6 using sieve of Eratosthenes, so that you can answer each query in O(1) time.
But I was looking some solutions and I found this one pretty interesting,
Here are the two solutions made by Abdullah Aslam,
TLE solution: here
AC solution: here
He just replaced all the endl statements with “\n” and he got AC in just 0.08 seconds.

My java code was getting accepted in 0.7 seconds, so I thought time limit of 1sec for C++ is fair enough.

I used Sieve as well, even Segmented sieve :stuck_out_tongue:
Fast I/O was needed
scanf and printf are faster than cin and cout
same with \n and endl

Yes, Indeed.
Java programmers have to use fast I/O all the time :stuck_out_tongue: