The Junior Quiz Finals are scheduled to be held on Tuesday, 5th August, 2014 in the Blossoms Basement (Seminar Room) in the 5th – 6th periods.
Monthly Archives: July 2014
e-Lite 2014 Senior Quiz Update
The following students are required to reach the Web Resource Center in the 9th period on Wednesday, 30th July, 2014 :
S.No. | Name | Class-Section |
---|---|---|
1 | Neel Bakshi | XI – G |
2 | Archit Aggarwal | XI – G |
3 | Sambhav Anand | XI – L |
4 | Shivain Arora | XI – Q |
5 | Anav Aggarwal | XI – H |
6 | Siddhant Jain | XI – L |
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 B . 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:
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 Quiz Update
The Junior Quiz finals have been postponed. The revised schedule shall be intimated to the participated as soon as possible. Any inconvenience caused is regretted.
e-Lite 2014 Creative Event Update
The creative event finals have been postponed to Wednesday, 23rd July 2014. The finals will be in the Shogun Lab from 5th to 9th periods. All participants are advised to be there as early as possible.
e-Lite 2014 Hardware Final Results
The following are the hardware final results:
S.No. | Name | Class-Section |
---|---|---|
1 | Harshil Kashyap | XI – I |
2 | Aditya Garg | XI – J |
3 | Nitin Mathai | XI – J |
Congratulations to all winning participants. You will be contacted by us very soon. Stay tuned.
e-Lite 2014 Senior Quiz Final Result
The following are the final results of the Quiz finals:
S.No. | Name | Class-Section |
---|---|---|
1 | Neel Bakshi | XI – G |
Archit Aggarwal | XI – G | |
2 | Sambhav Anand | XI – L |
Shivain Arora | XI – Q | |
3 | Anav Aggarwal | XI – H |
Siddhant Jain | XI – L |
e-Lite 2014 Senior Group Discussion
The Senior Group Discussion (Classes IX-XI) will be held on Monday, July 21, 2014 in the OAT from 3rd period onwards.
Interested Students can register themselves online at : http://exunclan.com/elite/
Please Note: On the spot registrations WILL NOT BE entertained
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!