Winter Camp 2014 – Selected Students List

Hi,

We have finally come up with the selection list for the Winter Camp 2014.

Selection Criteria –

1. Topcoder Rating of 900+ and should have attended at least 10 SRMs.

2. Codeforces Rating of 1600+ and should have attended at least 15 contests.

Applications who cleared 1 or 2 or both have been selected. The selection list can be found here.

Selected Candidates – The relevant details have been e-mailed to you.

Day Scholars – We have bandwidth to allow a few day scholars. If you can manage your accommodation and food in Bangalore, and interested in attending the camp, kindly drop me an e-mail at sai16vicky@gmail.com. A filtering will be done based on the number of responses.

 

 

 

Winter Camp 2014 – Coding all the way :)

Are you crazy about programming contests?

Do you like to code all day in a focussed environment?

Want to know how your peers are doing and take a leaf out of their book, and improve?

Feel you are saturated and to move forward, you need to learn new topics?

If your answer to all the above questions is yes, Winter Camp 2014 is here for you. The aim is to bring together interested students under one roof and create a competitive environment amongst them, by throwing challenging problems. What happens then? People start figuring  out the way they learn the best – interacting with peers, reading up solutions of others and so on.

Dates – 27 December 2014 to 4 January 2015

Place – Amrita University, Bangalore Campus

Interested in participating? – Please Fill out this form before November 15 9:00 pm IST.

Interested in teaching topics? – Please Fill out this spreadsheet as soon as possible.

We will be getting back to you with more details in the near future.

Cheers!

Sai

Divide and Conquer on Trees – Centroid Decomposition

I am currently working on a research project which involves modeling Database Join Queries as special graphs(trees, cliques, etc.) and improving worst case bounds for them. While working on trees, I came across this approach.

Separator Decomposition(also known as Centroid Decomposition) is based on a 1869 result by Jordan:

Given a tree on n vertices, there exists a vertex whose removal partitions the tree into components, each with at most n/2 vertices.

Proof – We can pick any arbitrary vertex v from the tree. Now assuming v is deleted, check the sizes of the connected components the tree will be split into. If all the connected components have a size <= n/2, then we are done. Else, select the component that contains more than n/2 vertices and choose w(an adjacent vertex of v) in it. Continue the same process till we get the vertex that partitions the tree into components, each with at most n/2 vertices. The tree has a finite number of vertices and each vertex is processed at most once. Hence, this method will terminate for sure.

We will be calling that vertex a centroid hereon.

Given a tree T, we can build a centroid tree using this approach –

1. Find the centroid C of T and make it the root of the centroid tree that we are building.

2. Recursively find the centroids of the connected components(think of them as new trees) and add them to the centroid tree.

3. As we are limiting the component size as half of the total nodes, its easy to see that the centroid tree will have depth O(log n). Finding the centroid takes at most O(n) time and hence, this tree can be constructed in O(nlogn) time.

Let’s see how to implement this –

Step 0 : Root the tree arbitrarily.

Step 1 : Calculate the size of each subtree(excluding the vertex rooted at it).

http://pastebin.com/H8dtk34p

Step 2 : Finding the center of the tree.

http://pastebin.com/E2rdgC4j

Step 3 : The Divide and Conquer function.

http://pastebin.com/SWn8b5QX

Shortcomings – 

This technique cannot be as widely applied as Heavy-Light-Decomposition(http://blog.anudeep2011.com/heavy-light-decomposition/) especially when “Query on a Path” is asked for. It is due to the fact the centroids of x and y need not belong to the path from x to y.

Problems to Try – 

1. http://ioi2011.contest.atcoder.jp/tasks/ioi2011_1_2 – Direct application of this idea. For each center, just figure out what to do and then you’re done.

2. http://www.codechef.com/problems/PRIMEDST – Basic idea is Divide and Conquer on Trees but FFTs make it harder.