[problem:DIVMAC] Please read this editorial for this problem on codechef.

Can some body please prove how the time complexity of the algorithm got reduced form O(Q N lgN) to O(N lgM lgN + Q lgN), where N is the size of the array, M is the bound on the elements of the array, and Q is the number of queries, by adding count_non_degenerate field to every node of the segment tree?

I have an intuition about the idea that we won't go into subtree rooted at node x if x has count_non_degenerate=0, which will reduce the time , but I cannot compute the exact time complexity quantitatively.

A sparse string is a string consisting of only 0's and 1's with the constraint that it has no 2 1's consecutive.

Let A and B be two positive integers. The weight of a string is defined as A^{# 1's in the string} + B^{# 0's in the string}. Given an integer N, find the total weight of all sparse strings of length N.

Constraints : 1 ≤ A, B, N ≤ 10¹⁹.

PS: I figured out that number of sparse strings with z zeroes and o ones will be Also note that z ≥  ceil(N/2) and z ≤ N. So basically the problem reduces to finding

. I believe that the time complexity of the solution must be O(1)( a closed form solution of G_N) or O(logn)(a recurrence relation for G_N).

Can anybody provide a complete solution to the above problem?

We are given a multi-set of whole numbers S of size 2n. All whole numbers in S are in the range [0, d]. We need to partition S into two multi-sets A and B such that |A| = |B| = n. Our task is to find such A and B which minimise |sum(A)-sum(B)|. What is an efficient algorithm to do so?

We are given an undirected graph G = (V, E), |V| ≤ 50. We are also given a starting vertex s. Each vertex v of the graph is associated with a natural number N_v. Initiall our profit is R = N_s.

Now we have to traverse the graph beginning from s in an order. We can visit each vertex or edge an number of times.Whenever we reach a vertex v, R = R XOR N_v. (Note that if we visit a vertex v k times, then we will XOR with N_v k times.

Find the maximum value of R that can be obtained while traversing G.

There are n subjects (1, .., n). Each subject can be offered at two levels : A or B. A combination of subject and level is called course(Examples of courses: 1A,1B,2A,2B etc). There are some students (S₁, ..., S_m). Each student has some requirement of courses ( Eg. student S₁ might require courses 1A,1B,2A,3B). We have to schedule the courses satisfying the following constraints:

(i) Each subject is offered at exactly one level : A or B

(ii) For each student, at least one course is offered from his/her requirements.

Now we need to find the schedule which minimizes the number of B level courses satisfying the above constraints.

PS: This problem looks like a variant of matching to me. Is there any algorithm related to it?