Monthly Archives: July 2014

e-Lite 2014 Creative Event Results

The following students have successfully cleared the final round of Exun Clan’s Creative Event; They’re requested to reach the eGuruKul Lab on Thursday, 23rd July 2014:

Name Class – Section
Sana Gujral XI-L
Rohan Dhar IX-H
Vishrut Malik VIII-A
Tanmay Bansal X-I

Congratulations to all the winners!

E-lite 2014 Programming Senior Finals Solutions Part1

Here is the editorial for the Senior Programming Finals. The contest can be found here

Problem1. Odd
This was a straightforward question. Only perfect square numbers have an odd number of factors. Though this can be seen by observation(and is sufficient for solving this problem), you may want to know how we formally prove this:
Assume that there is a perfect square N. Let A be the set of natural numbers which are strictly smaller than floor(square_root(N)) . Let B be the set of natural numbers derived form A such that for every element(a) belonging to A there is a corresponding element N/a in . The sets A and B do not intersect since if they did, a=N/a => a^2=N => a is the square root of N, but the square root of N does not belong to set A and we have a contradiction. Since these sets do not intersect, the total number of factors of N is 2*k + 1(where k is the number of elements in A, and 1 extra factor is the square root of N). Thus, N had an odd number of factors.
So, we need to output the sum of the first N perfect squares(where N was given in the problem) modulo M. The formula for that is N*(N+1)*(2*N+1)/6.
Some of you had a problem outputting the answer modulo 10^9 + 7.  This is where language matters : python can easily handle large numbers and you could have just done (print ans % M) to get your solution accepted. Its different with C++ however since there can be overflows while handling large numbers, You can read more about modulo operations here. Another common mistake was using x^y over pow(x,y):  x^y does not mean x raised to power y in C++, it means x XOR y.

Problem2. Walk Over Me
This is a classic Dynamic Programming problem. First of all you would need to figure out the intersection points, since the arrays are sorted this can be done in linear time. After this is done, the recurrence is simple,
maxSum(i) = max_(over all intersections j<i){ maxSum(j) + branchSum(j..i) }
For the people who got interviewed, the above recurrence is what I wanted as an answer: when we are given the optimal solutions to 1..i-1, we can find the optimal solution to i using the above recurrence.

Problem3. Mad Scientist
This was a tough problem to solve if you are not familiar with graphs. Unfortunately, some people jumped to this problem without attempting the first one(!). How you choose the problems pretty much decides how well you do in a programming contest.
For each pair of chemicals which can react, we add an edge in the graph. Once we have this information in a graph, we can find the “connected components” of this graph. When two chemicals are in a connected component, it basically means there is a sequence of links by which one can reach one of the chemicals starting from the other. For example, if A reacts with B, B reacts with C, and A reacts with D, then A,B,C,D form a connected component. Note that the order of adding chemicals within a connected component does not matter, the final power after adding all the chemicals is always initialPower * 2^(Size of Component – 1). So, the solution is to form the graph and then report the answer as 2^(V-number of  distinct connected components).

Problem4. Non Zero
This was an AdHoc implementation problem. Going from the left, maintain a counter recording the position of the last zero. Whenever a nonZero element is seen, swap that element with the element at counter, and increment the counter. I think the above is better understood by some code:

nonZero

Problem 6. Knights
This was a relatively hard graph problem. Consider the N*N squares on the (chess?)board as vertices. Then find the shortest distance between each pair of vertices. I used Breadth First Search to do this. The running time of this step is O(N4). Floyd-Warshall is not recommended here, since the graph is relatively sparse, and using it will cause solutions to time out. Then we wish to find the optimal point for the knights to gather at, and the total distance they need to travel to get there. For this, we iterate over each of the N*N candidate points and for each candidate point, we sum the distance each knight would need to travel to get to that point. Then we find and print the minimum value among the so-calculated distance sums of each point. The running time of this step is O(N2*M), which simplifies to O(N4) for lazy implementations, like my own. The total running time is hence O(N4).

e-Lite 2014 Junior Programming Results

Junior Programming Results

The following students have qualified from Junior Programming which was held on Tuesday, 15 July 2014.

Name Class – Section
Sumay Mishra VII – A
Ruchi Dhewal VII – G
Khushi Bahl VIII – A
Udit Malik VII – A
Anusha Das VIII – A
Suryan Yash VIII – A
Prateek Srivastava VIII – B
Eesha Shekhar VII – G
Gursher Aujla VIII – A
Anusha Shekhar VIII – A

All of the above will be contacted soon for further information.

Congratulations to all the qualifiers!