CodeGames Editorial

From Grundy
Jump to navigation Jump to search

This is the editorial for the CodeGames CP Contest held by WNCC.

Kalsubai or Goa

Here we have to sort the two arrays and use two pointers to iterate both of them as follows -

Initialize i = 0, j = 0

If a[i] is smaller than b[j] then increment i

If a[i] is greater than b[j] then increment j

If both are same then print the common element and increment both

Welcome to IITB

Observe that two numbers are related iff the exponents in their prime factorsitations have the same parity. You can therefore use sieve of eratostenes to calculate the prime factorisation of each number and encode the parity wrt every prime such that two numbers will have the same encoding iff they are related. This can be done using string hashing over primes (google how to do this!). Once you have the hash you can use a map in C++ to count the number of elements that have a paritcular hash and the max over all of them will be the initial power.

For the second part, observe that if a set of integers having the same hash are transformed they will either remain in the same hash if their count is odd or else they will all get converted to the set of integers that have the same hash as 1 (this happens if even elements are there, for instance p1^1*p2^3, p1^3p2^1 after transformation become p1^4p2^4 which has the same hash as 1).

Thus you can simply iterate over those hashes that are even in count and add them to a global counter initialised to the number of elements having hash 1. The ,max of the value of this global counter at the end and the initial power will be the final answer.

The Line in SAC - Easy

This problem just needs you to count the inversions in an array in an online manner. This can be done easily using a Segment Tree (you were supposed to google for this problem!) Refer to: https://www.geeksforgeeks.org/counting-inversions-in-an-array-using-segment-tree/

The Line in SAC - Hard

Here we have to swap two numbers to minimise the inversions.

Let's calculate the difference in number of inversions given that you swap ai and aj. We can assume that i<j. There are three kinds of pairs of indices whose status (being inversions or not) could change as a result of the swap: (i,j) and, for i<k<j, (i,k) and (k,j). We can distinguish two cases: ai<aj and ai>aj.

If ai<aj then the pair (i,j) becomes an inversion, and for every i<k<j, there are three possible cases:

ak<ai<aj: number of inversions stays the same.

ai<aj<ak: number of inversions stays the same.

ai<ak<aj: number of inversions increases by 2.

This is clearly not a good idea if you can avoid it. If you must (when the permutation is monotone increasing), it's best to switch a pair ai,ai+1.

In contrast, if aj<ai then the number of inversions decreases by one plus twice the number of indices i<k<j such that aj<ak<ai. As a consequence, if the permutation is not monotone increasing, your goal is to choose a pair (i,j) such that aj<ai and the number of indices i<k<j satisfying aj<ak<ai is maximal.

We can implement this with using a sweep-line algorithm and segment-tree offline.

Missed the Deadline

In this question, a simple sorting of numbers in decreasing would not work as we can see in the example of - {9, 56}. Sorting would form number 569 whereas the largest should be 956.

We make a custom sorting algorithm where if nxny > nynx then nx comes before ny in the order formed by our algorithm. (nxny is nx concatenated with ny).

C++ allows us to make our custom comparison functions for sorting so total time taken would be O(nlog(n)). The sorted list formed is concatenated to get the largest number.

A Real Opportunity

Iterate over the values of x from 1 to m and store the minimum and maximum value of the remainder obtained. While calculating the remainder for x = i, one can use the remainder (r(i-1)) for x = i-1 as r(i) = (r(i-1)*n) mod m.

Proof - We know that for any number n, m, as we have here, if we iterate over x, the remainder repeats itself after m steps. Since, the constraints of the problem allow iteration over m within as m <= 10^6.

The complexity for the solution is simply O(m).

A code in C++ for the same can be found here.

Save Me From Assignments

We can binary search the answer. Let us take two extremes left = 0, right = 10^13. Suppose, that we are able to check efficiently that if lenght of session = mid for some value of mid, then are the number of sessions >= k? Then, we can simply do a binary search as.

while(condition)

   mid = (left+right)/2
   if poss(mid)
       left = mid
   else
       right = mid

This is correct, since if we are able to conduct atleast k sessions each mid minutes long, then we can conduct atleast k sessions of any length <= mid. Since, we need to find to the correct 6th decimal place. condition is left <= right-10^{-7}.

What remains is to figure out is the poss function which checks if mid length sessions suffice the conditions. This is trivial by evaluating the sum floor(a[i]/mid) and checking sum >= k.

The complexity for the solution is O(nlog(10^{14})).

A C++ Code for the same can be found here