The year is about to end, and so is the ACM ICPC season with the India Final 2016! After 4 onsite contests, with almost 600 teams participating and intense battles between the best teams, we’re here to present you live updates from IIITM Gwalior where the ACM ICPC India Final 2016 is happening today! Stay tuned for interesting insights from the arena, problem discussions and more!
The Mirror Contest shall begin at 11:00 a.m. IST. You can register your team for the mirror contest here.
Live Leaderboard: www.codechef.com/rankings/ACM16INF
10:00 IST: The contest has begun. The problem set consists of 11 problems.
10:08 IST: No submissions on any problem yet.
10:13 IST: No submissions still. Teams might strategize to minimize their time penalty today, as it can play a huge role in the final leaderboard.
10:15 IST: We have our first accepted submission! Problem I has been solved by team SRY from Delhi Technological University!
Problem I is called “Pacman” – surprisingly, it is not related to the game in any way but it is based on the name of a Software Package Manager.
This problem has been set by Vaibhav Tulsyan (that’s me!).
The problem is as follow:
You are given a list of softwares and their dependencies. Each software has at most one dependency and there are no cyclic dependencies. Also, each software has a download limit D[i]. Given a subset of ultra-special softwares, you want to find the maximum no. of “completely installable” softwares. By “completely installable”, we mean that its entire chain of dependencies must first be downloaded, and then the software itself should be downloaded. Each ultra-special software does a fresh install of all its dependencies.
The first solution one may think of is finding the max flow in a transformed graph. A new graph can be constructed by splitting each node into an edge with capacity = D[i] value of that node. A source node will have edges to all ultra-special softwares with capacity = 1 and all nodes which don’t have dependencies, can have edges to a Sink node with capacity = infinity. The answer would be the value of max flow in this graph. The implementation can be done using Dinic‘s algorithm.
However, from some observation, it can be deduced that one can select any ultra-special software and completely install it, if it is possible. Hence, all you need to do is traverse over all the dependencies of the ultra-special software uptil the highest parent, keeping track of the download limit and updating the download limits while traversing. This is a O(N^2) solution.
There also exists a Dynamic Programming solution which is that in each node, store the minimum of: D[i] of the current node and sum(D[j]) of all children j of node i. This runs in O(N).
10:46 IST: 20 teams now have Accepted Submissions on Problem I.
FruitSalad have solved Problem E as their first problem! However, they got 1 penalty on that problem.
Team SRY remain atop the leaderboard.
10:51 IST: Team believe from MNNIT are the first team to solve 2 problems and now lead the scoreboard with 0 penalties.
FruitSalad have solved Problem I and have 2 problems solved as well – although with 1 penalty. They are now at Rank 2.
11:00 IST: 1 hour into the contest, only 2 teams have solved more than 1 problem.
Let’s discuss Problem E – Jumping Frogs III.
We have Triveni Mahatha with us who has described the problem in brief as follows:
“The problem is about finding maximum number of frogs in a segment of an infinitely long road (x-axis) at any instant of time. Frogs are moving with constant speed in the x-axis. Initial position of the frogs and their velocity are given.
The solution is that, for every frog find out the time range for which they are at any point in the given segment. Then among these time ranges you need to find a time which is contained by max number of ranges. This can be done by sorting the intervals and doing line sweep greedily. Fairly popular problem.”
11:05 IST: AC on Problem H for Team Rocket!
They have solved 3 problems and lead the ranklist.
11 teams now have at least 2 problems solved.
The live leaderboard can be seen here: https://codechef.com/rankings/ACM16INF
11:15 IST: Team mobius_treap gets AC on Problem A! They are the first team to solve that problem. This is their 2nd solved problem in the contest.
11:25 IST: Team Hopeless solves Problem B.
11:32 IST: FacelessMen solve Problem A and move to rank 2 with 3 problems with 1 penalty.
mobius_treap solve Problem E and move to rank 3 – they have 2 total penalties.
11:35 IST: Triangulation get AC on Problem H. They seem to have used a Persistent Trie + Binary Search for their solution.
11:36 IST: Team Rocket have solved Problem C and increase their lead with 4 problems solved.
Let’s discuss Problem A now. You are given a number N of the from p * q. Where p and q are prime numbers. p may be equal to q.
You need to distribute N balls into k buckets such that every bucket gets equal number of balls.
It is clear that k can be either 1, N, p or q. You need to be alert that you are not counting twice for p and q if they are equal.
Print the answer modulo mod.
There are few things to observe here.
First how to factorize N which can be 10^12. But since max(p,q)/min(p,q) <= 10. It is easy by just doing brute-force.
Next observation is that the value of mod is small, this will be useful. Let’s first arrive at the solution.
Distributing N balls into k buckets is a fairly standard task in combinatorics. Say y = N/k then the number of ways is N!/(y! ^ k).
Here you may not take modular inverse as the denominator can have multiple of mod, since mod is very small.
So, rather you actually factorize the numerator and denominator to get the answer. Note that you need not go to prime factors more than mod. Because if the answer contains mod then answer is zero anyways.
That’s all about this problem. However, you need to be careful while implementing the idea. So many modulos and few cases as well. Factorization should be fast enough. Use sieve.
11:42 IST: Team Survivor from IIT Indore solve Problem L – a geometry problem. They are now at Rank 2 with 4 problems solved.
11:51 IST: Almost 2 hours into the contest, we have 7 distinct problems solved, with the top team solving a total of 4 problems.
Problem L, authored by Triveni is a really interesting geometry problem.
Quoting Triveni’s explanation of the problem and the possible solutions:
“Problem L is about finding approximate-smallest enclosing circle of N points in Cartesian plane. Smallest enclosing circle can be defines as a circle with minimum possible radius such that all the given points are either inside or on the circle.
If we allow few (4 for this question) points to be outside the circle, this is approximate smallest enclosing circle problem.
There are many possible solutions to this problem as the constraints are very small. N is just 51
I will discuss few.
Few things to observe. At most three points are needed to define the circle.
So we chose any three points and make the circumcircle. If all but 4 points are inside this then we have got an answer. complexity O(N^4). Fairly simple.
Another is based on Weizl’s algorithm.
You select any three points and make SEC of all the remaining points. If there are more than 3 points on the circle then you can not do much by removing one more point from the set. However, if there less than 4. Then we can try removing one point from the circle and regenerate the SEC of remaining points.
Weizl’s algorithm computes SEC in O(N). Its a randomized las-vegas algorithm. So random shuffling of points is needed to avoid TLE.
Total complexity is O(N^4) for this as well.
Apart from this one can write O(N^5) solution with optimizations to get AC.
That’s all.”
12:05 IST: Team Rocket have 5 problems solved and 2 penalties – Rank 1.
12:17 IST: thirdfloor have solved Problem D – they are the first to solve this problem and have moved up to Rank 4.
Balajiganapathi says that he expects more teams to solve D and is surprised with such a small number of submissions on that problem.
12:22 IST: FruitSalad solve their 3rd Problem with Problem H! They are at Rank 10 now.
8 distinct problems with the top team having solved 5. That says a lot about the diversity of difficulty of the problem-set.
12:33 IST: mobius_treap from IIIT Hyderabad at Rank 3 with 4 problems and 2 penalties.
12:47 IST: third floor have solved 5 problems and are now at Rank 2!!
Problem selection will be very, very important for the top teams now. With only a couple of hours remaining, they can’t afford to spend time on a problem and reach a dead-end.
12:52 IST: mobius_treap solve Problem H and are now are Rank 2, displacing third floor to the 3rd spot.
12:56 IST: mobius_treap solve Problem L and now are at Rank 1! 2 ACs within 5 minutes, they’re on fire today!!
1:28 IST: mobius_treap solve their 7th Problem and lead the ranklist. Survivor have now solved 6 problems and are at Rank 2, followed by FacelessMen with 6 problems at Rank 3.
1:29 IST: FruitSalad solve Problem L.
1:53 IST: As we approach towards the final hour of the contest, team mobius_treap looks comfortable at the top with 7 solved problems to their name.
2:00 IST: The final hour of the contest is in progress and the ranklist has been frozen. It means no more updates fromo us till the result announcement. So, join us back for the result announcements to find out who wins the first ever ACM ICPC India Finals.
4:00 IST: We are back live from the chilly campus of ABV IIITM, Gwalior, where the first ACM ICPC 2016 Multi-Site India Fials concluded, with some teams taking the part into the contest from Kolkata. And it is time to raise the mercury a bit with the final results of this ACM ICPC season. So, brace yourselves.
4:10 IST: The second runner-up is Team “Survivor” of Indian Institute Of Technology, Indore. A big round of applause for them.
4:15 IST: The first runner-up is Team “Rocket” of Indian Institute Of Technology, Bombay. Give it for them.
4:20 IST: And finally the big one. The winner of the first ever ACM ICPC India Finals is Team “mobius_treap” of International Institute Of Information Technology, Hyderabad. Great job guys. They seem to be making a habit out of it. And we are very pleased that they are.
4:30 IST: With that, it’s time to let the Sun set on ACM ICPC season for the year 2016 and the year 2016 itself. We hope you had a wonderful year, and have big plans for the coming year. So, on that note, from everyone here at CodeChef here’s wishing you and your love ones, a Very Happy New Year. Have a wonderful evening folks.
This is wittyceasor signing off for the final time in the year, 2016. See you on the other side.
- Vaibhav Tulsyan
It’s that time of the year again!
We are ready to start the Indian onsite rounds of the ACM ICPC, with our first round being held at Kharagpur. There are 76 teams competing today for spot(s) at the 2017 ACM ICPC World Finals, which will be held in Rapid City, USA! I’ll be doing live blogging throughout the contest and I’ll keep posting interesting facts as they come up. Stay tuned for some exciting action!
There is a slight delay before the start of the contest. The contest is expected to start at 10AM.
Let’s use this opportunity to talk about the top teams participating today. The ones to look out for today are “Triangulation” from IIT Roorkee and “FruitSalad” from DAIICT. Vaibhav Gosain from Triangulation and Sumeet Varma from FruitSalad are two of the most well known names in the Indian Competitive Programming Community. We also have team “Shockers” from IIT Madras with former ICPC World Finalists Sundar Annamalai and Karthik Vishwanathan.
10AM IST : There is further delay. Contest will start start at 10:30.
Some images of the contest arena :-
10:30AM IST : The contest has started! A long and arduous wait finally ends!
There are 11 problems in today’s problem set. In my opinion, this is a high quality problem set, with a lot of interesting problems. The easiest problem in the set is H, and we expect teams to start submitting solutions for it pretty soon. It is intended to be a basic implementation problem.
10:46AM IST : Phew! We finally get our first submission, and it is Accepted. Team “HappyTreeFriends” from IIIT-Delhi have solved H.
10:53AM IST : The AC on H has made the teams realize that its’ an easy problem, and now we’re seeing a flurry of submissions for it.
10:54AM IST : We have a submission on problem F by team “alwayslast” from The LNM Institute of Information Technology and it Accepted!
F is intended to be an easy-medium DP problem. You need to partition an array of N integers into K disjoint subsets S_{1}, S_{2}…S_{K}, such that the sum of the difference between the maximum element in each subset and minimum element in each subset is minimized. Formally, sum {i = 1 to K}{max(S_{i}) – min(S_{i})} should be minimized. Also, size of each subset should be atleast 2. The constraints are such that O(N * K) will work. To any experienced competitive programmer, the statement and the constraints will automatically indicate a dynamic programming approach. The key observation to make is that the we can sort the array and work with subarrays instead of subsets. After that, it’s just figuring out the transitions which is not very hard.
11:04 IST : “FruitSalad” from DAIICT, have solved 2 problems, F & H. However, they have a penalty on F.
11:07 IST : “alwayslast” have solved H, and are now on top of the leaderboard!
11:21 IST : We’ve had 4 accepted submissions on F till now, and about 48 on H!
Let’s talk about the next two problems that we expect the teams to solve. They are C and D. Both have trivial ideas, but require meticulous implementation and have a lot of edge cases. In fact, we expect solutions for C to be at least 100-150 lines long. Code for D should be shorter, but it is not trivial at all.
11:32 IST : We have 1 AC on both C and D. C has been solved by “FruitSalad”, moving them to first place. D has been solved by “triplethreat” from BITS Goa. Surprisingly, this is the first problem that they have solved!
11:42 IST : “FruitSalad” have solved problem D as well. They have solved 4 problems and are comfortably on the top of the leaderboard at the moment.
Seems like most teams will spend the next hour working on implementing C and D. In the meantime, let’s talk about problem E. Given a graph G(V, E), with no special properties (it might be disconnected as well), and the information that G has a dominating set of ceil(V/3) vertices, you need to find and print a dominating set with atmost ceil(2V/3) vertices. A subset of vertices of G is called a dominating set iff every vertex in G is either in the subset or is adjacent to a node in the subset. Looks hard doesn’t it? I’m going to talk about its solution later.
12:00 IST : “FruitSalad” seems to have solved E as well. They’ve got a WA, but it seems like the only thing they’re missing is a trivial edge case, which should be spotted soon!
12:05 IST : “FruitSalad” gets E. They’ve done 5 problems now. They’re on a roll!
So, E was designed by our very own Praveen Dhinwa. Upon first glance, the problem seems complex : The graph doesn’t have any special properties, the constraints are high and we know that minimum dominating set is NP complete. Also, it seems like we need some sort of 2-factor approximation of dominating set. Let’s use a common trick while solving problems : Solve simpler instances. Let’s make the graph the best kind possible, a tree. What can we do for a tree? Well it’s simple isn’t it? We know that trees are bipartite, so we can take any arbitrary bipartition, one of them will be of size <= (n / 2) and that will suffice.
Ok, so now let’s think about a general graph. What do we need to do? The answer is, quite simply, NOTHING! Notice that the dominating set for any spanning tree of G will be a dominating set for G as well. That’s it. Problem solved. Stop smirking, you’ve been PUNK’D!
Important Announcement : Ranklist is live!
12:30 IST : After two hours, “FruitSalad” sits comfortably in the lead with 5 problems solved. Team “code_phoenix” is at 2nd place, with 3 problems.
Team FruitSalad :-
It seems like other teams are still stuck coding the implementation problems C and D. For all of those who’re wondering why we have such type of problems in the first place, it’s because the World Finals also gives problem(s) each year which are easy logically but require one to write lengthy code without bugs!
Since it seems like the scoreboard will be a bit static, let’s talk about the next few problems. Whatever we’ve done till now was in the “easy” wave of problems. Now we’ll move on to Medium and Medium-Hard. Let’s discuss B, K and J.
B is a Geometry problem. Given a general quadrilateral (concave/convex) and 2 points S and T on a 2D Plane, compute the shortest distance needed to reach T from S without touching the quadrilateral. Again, this is not a terribly hard problem. We need to look at the line joining S and T and divide our solution into several cases, and take the minimum of all of them. Of course, the answer can also be impossible, such as in the case when S is inside the quadrilateral and T is outside it. Just like with any geometry problem, this requires careful implementation and consideration of all cases. Our model solution was ~ 90 lines!
1:05 IST : “FruitSalad” have solved B. This is gritty stuff. They’ve now increased their lead to three problems, and are sitting comfortably on top with 6 problems solved!
1:10 IST : “Rainbow” from IIT Hyderabad have solved K!
Update : All participating teams have solved H!
Let’s talk about K now. Suppose S = (a_{1}, a_{2}, .., a_{n}) is a string, then its ‘kth power’ is defined to be the string S^{k} = (a_{1}, a_{1}, … [k times], a_{2}, a_{2}, .. [k times], a_{n}, a_{n}, .. [k times]) where each character is repeated k times. Given strings T and P, you need to find all substring matchings of P^{k} in T, for all k ie. Find all occurrences of P in T, of P^{2} in T… etc. Also, it is guaranteed that P has at least 2 different characters in it.
First thing to notice is that the constraints are huge, 10^{5}, indicating that their definitely exists a linear or loglinear time solution. Here we describe the crux of one such solution. Note that checking whether P^{k} is in T for all k >= 1 is too slow. The idea is that, along with the kth power, there’s also a way to define the kth root of a string S, say S^{(1/k)}, with some nice properties. Firstly, counting the occurrences of P^{k} in T must be the same as counting the occurrences of P in T^{(1/k)}. Secondly, The length of T^{(1/k)} must be O(|T|/k). With this, the overall algorithm becomes O(|P| + |T|/1 + |T|/2 + |T|/3 + |T|/4 + …) = O(|P| + |T| log |T|). There are quite a few details to successfully defining the kth root of a string, but it can be done. This interesting problem was set by Arjun Arul, who also happened to have a linear time solution for the same!
1:52 IST : The scoreboard looks roughly the same. It seems like “FruitSalad” have amassed a sizable lead. With around 90 minutes remaining, something spectacular needs to happen for them to be dethroned!
1:57 IST : “FruitSalad” solves J. This is unbelievable. They keep their lead to 3 problems, with “code_phoenix” at 2nd place. It seems almost certain now that they will take first place!
Let’s talk about J now. It is one of the harder problems in the set. This interesting problem has also been set by Arjun Arul. Here is an abridged version of the problem : You’re given a directed graph G(V, E), where each edge is either vital or non-vital. You need to remove minimum number of non-vital edges from G, such that in the resulting graph, every node has it’s indegree equal to its outdegree. You should output the minimum number of edges that need to be removed, or print -1 if a solution doesn’t exist. Number of vertices in G is atmost 100, and number of edges is atmost 1000.
This problem, along with its low constraints, hints that the solution has something to do with minimum cost maximum flow routine. Indeed, that is the case. The graph construction for this problem is not apparent at first glance. Intuitively, notice that the quantity (outdegree – indegree) is important to us, and we want to make it zero for all nodes. We’ll continue on the solution later.
2:30 IST : The ranklist has frozen, with “FruitSalad” on 1st place with 7 problems solved, “code_phoenix” in 2nd place with 4 problems, and “included” in 3rd place with 3 problems. This means that from now onwards, we will not be giving you updates about submissions and changes in scoreboard.
Getting back to J. The graph construction is as follows. We’ll have V + 2 nodes, V for the graph, plus a source S and a sink T. For all nodes u which have outdegree > indegree, add an edge from S to u with capacity (outdegree – indegree) and cost 0. For all nodes u which have outdegree <= indegree, add an edge from u to T with capacity (indegree – outDegree) and cost 0. Now for all non-vital edges in E, add the same edge with capacity 1 and cost 1. The answer is the minimum cost we can obtain while maximizing flow from S to T in this network. To make sense of this construction, note that each augmenting path reduces the outdegree of the first node, indegree of the last node and both indegree and outdegree for intermediate nodes.
Here are some more pictures from the onsite contest :-
3:30 IST The contest has ended! Stay tuned for the final scoreboard reveal!
We are back folks, and it’s result time here at ACM ICPC 2016 Khragpur Regional. So, hold on to your seats as we reveal the “Winners.”
We start with the 2nd runner ups. And it’s Team “included” from NIT Warangal. Give a big round of applause to them. Well done guys.
On the 1st runner up place we have Team “code_phoenix” from National Institute of Technology, Karnataka. Kudos guys. Good job.
And finally, it’s time for the winners. Drum rolls!!!! At No 1 and “The Winners of the ACM ICPC 2016 Kharagpur Regionals” is Team “FruitSalad” from Dhirubhai Ambani Institute of Information and Communication Technology. Bravo guys. You are the first winners of ACM ICPC 2016 India Regionals.
That will be all from us here at the picturseque campus of IIT Kharagpur. We hope you enjoyed the contest and the updates. Now, from far East, we travel to down South for the ACM ICPC 2016 Chennai regionals to be held at Hindustan University. We will come back with all the live action and updates soon. Till then, do send in your messages and cheers for your favorite teams just to let them know that you are behind them as they compete for the ultimate programming glory. #GoForGold guys.
- Animesh
We are back with the third and final member of team “11coders” from Indian Institute of Technology – Roorkee. Let’s hear his side of the story.
Team name: 11coders
Team rank: Amritapuri regional: #2
Q. How old were you when you started programming and what got you started in programming?
A. I started coding when I was 18 (In my first year of B. Tech).
Q. What inspired you to get into competitive programming? Were you passionate about it since school or anything special in college?
A. I was very much interested in mathematics and puzzles, I enjoyed solving them, and I got similar fun in solving programming problems which required good logic. Then I continued solving problems, soon I got to know about ICPC in my first year itself. Thanks to PAG (Programming and Algorithms Group) in IIT Roorkee, which directed a bunch of puzzle lovers towards a bigger goal named ICPC.
Q. How to start preparing for ACM ICPC for those who are new to algorithms and competitive programming? It would be great if you could share your journey from a beginner to a World Finalist today.
A. Initially I used to practice problems on SPOJ; soon I realized that many problems require a well known algorithm which I was unaware of. Then I started to read new algorithms. Soon I started giving contests on CodeChef and codeforces, solving problems with a time constraint is really fun. Main goal for giving contests is to learn by up solving problems which I couldn’t solve during contest.
Q. Can you throw some light on how did you and your team manage the time and coordinate during the onsite finals? It would be great if you could share some tips for the next year ICPC aspirants.
A. Before onsite we did a lot of team practice; this helped us to know our weakness and strength. Knowing strength of other teammates can help to pass questions to the person who is strong in that topic. Our main weakness was a lot of penalties, so to overcome it we always used to read the code once to ensure correctness. This approach did slow us a bit but minimized the penalties.
Q. What did you do to improve over these years and maintain your target status for all these years with all the competition? What do you think was your most effective method to improve? Any hacks on how to reach where you are in less time ?
A. The only way to improve is practice and I too did the same. To decrease amount of time, one just need to increase the amount of practice.
Q. Do you have any other thoughts as we wrap up?
A. NO
That was Aman from team 11coders. We hope you enjoyed the interview. We have few more in the pipeline and will be publishing them soon. Till then, share this interview among your friends, and family and send in your wishes and questions for them. #GoForGold.
Regards,
Rudreshwar
Team CodeChef
Today we meet another member of Team “11coders” from Indian Institute of Technology – Roorkee, say hello to Kshitij Bathla. Let’s hear it from him. But before that, let us give you a brief info of his team.
Q. How old were you when you started programming and what got you started in programming?
A. I started programming in my first year of college. We have a programming club (Programming and Algorithms Group) in our college, I got selected and that is how it all started.
Q. What inspired you to get into competitive programming? Were you passionate about it since school or anything special in college?
A. I always liked math, solving puzzles and found competitive programming similar. I used to solve SPOJ problems (puzzles mostly) in my first year. I wasn’t aware about it during my school days.
Q. How to start preparing for ACM ICPC for those who are new to algorithms and competitive programming? It would be great if you could share your journey from a beginner to a World Finalist today.
A. I would recommend Topcoder tutorials as a starting point. You can start with some basic topics like Dynamic programming; greedy algorithms etc and solve the problems given in the tutorial. Make sure you code everything. Finding the solution and actually coding it and getting it accepted are two completely different things. Try to give lots of contests on Codeforces, CodeChef and Topcoder. Try out the problems that you could not solve during the contest. If you are not able to solve them, read the editorials and code them on your own. If you see a new algorithm/technique, try to learn it from online resources. Learn the logic and try to code it. Once you’re more used to solving contest problems, start forming a team. Pick your team early and do a few virtual contests with them. You can try out regionals from previous years from your region.For team practices, you can also try out the contests on Gym (Codeforces).
My Journey: We formed the team in our first year. We got selected for the 2013 Amritapuri regional(onsite) in our second year . We performed decently and secured a rank of 32 there. The 2014 Amritapuri regionals was a disappointment as we performed very badly in the onsite event. We came 8th in the Gwalior onsite that year. 2015 Amritapuri was again not great because of the technical glitches but we finally made it in the Chennai regional(our last attempt at the World Finals).
Q. Can you throw some light on how did you and your team manage the time and coordinate during the onsite finals? It would be great if you could share some tips for the next year ICPC aspirants.
A. In the last one month before the regionals, we used to give a gym contest every alternate day on one machine (similar to what it would be in regionals). This is important for finding out which way your team performs best. In our case, we had an idea about the strengths of each individual and hence we labelled the problems by their topics after reading them e.g Strings, graphs etc. One more important thing is proper utilization of machine time. Because only 1 PC is available, you need to use it wisely.You should think about the code structure in your own mind before starting to write it on the machine, this will save a lot of time as compared to thinking about the solution while writing the code.
Q. What did you do to improve over these years and maintain your target status for all these years with all the competition? What do you think was your most effective method to improve? Any hacks on how to reach where you are in less time ?
A. Participating in lots of contests is extremely important.This helps in improving accuracy as well as speed. Topcoder contests are recommended for improving accuracy. I used to take part in codeforces gym contests as well as normal rounds(Div 1,2) and that is what helped me improve. Practicing a lot is the only way through which you can qualify for world finals in my opinion. What matters is the number of hours you put in practicing.
Q. Do you have any other thoughts as we wrap up?
A. ACM-ICPC is not an individual activity. If you practice along with your team mates, it gives you different approaches for the same problem and keeps motivating you towards your goal. Learning new topics is also easier this way. Do lots of practice and enjoy coding.
We hope you enjoyed the interview. We have few more in the pipeline and will be publishing them soon. Till then, share this interview among your friends, and family and send in your wishes and questions for them. #GoForGold.
Regards,
Rudreshwar
Team CodeChef
We are back with our ACM ICPC World Finalist’s interviews. As we move closer to the World Finals, it’s just the perfect time to have a look back at the journeys of our World Finalists. Today we have Anubhav Bindlish of Team “11coders” from Indian Institute of Technology – Roorkee. Let’s hear it from him. But before that, let us give you a brief info of his team.
Q. How old were you when you started programming and what got you started in programming?
A. I was in class 11th when I started programming. I had it as a subject in school.
Q. What inspired you to get into competitive programming? Were you passionate about it since school or anything special in college?
A. A friend introduced me to competitive programming. It was in class 11th as well. I guess I always enjoyed solving puzzles, and that is why I found competitive programming interesting. I qualified for INOI but could not prepare well for it as I had to study for JEE entrance at that time. Participating in it was still a fun experience though!
Q. How to start preparing for ACM ICPC for those who are new to algorithms and competitive programming? It would be great if you could share your journey from a beginner to a World Finalist today.
A. I started competitive programming in 2010, and at that time the programming circle in India was not as active as it is today. When I started, I had doubts but didn’t know anyone who could resolve them. As a result, I didn’t really learn much in the first two years. The problems I solved were mostly adhoc in nature. Upon joining college, I became part of a programming group in campus. This I believe has been a most important factor in my growth. We had some inspirational seniors who we would look up to. Furthermore there were group ‘lectures’ (quoted because we really hated the word ‘lectures’:P), where members would share whatever little knowledge they had. This helped us collectively learn new concepts and techniques. Then I used to participate in contests and read editorials of unsolved problems to learn new topics.
Qualifying for the World Finals is really a dream come true for me. This was our last attempt at the Regionals, and I am happy that we gave in everything we had while preparing for it. Before the Chennai Regionals, it was almost as if we were giving a team contest every other day. Practice and perseverance are key to achieving anything in life, and competitive programming is no different.
Q. Can you throw some light on how did you and your team manage the time and coordinate during the onsite finals? It would be great if you could share some tips for the next year ICPC aspirants.
A. The Chennai onsite was a really good experience! (Food and accommodation aside ) Usually when we give contests, we are off to a flying start but then we lose track somewhere towards the middle or end. The Chennai onsite went completely opposite! We had a slow start, and as far as memory serves, even after solving 3-4 problems, we were still not among the top teams of the leader board. What worked to our advantage however was that we managed to make continuous progress throughout the contest? It was after solving our 6th problem that we came second in the leader board for the first time, and we knew we had a good chance of clearing the Regionals.
In several of our past contests, we had had a lot of penalties. As such we specifically wanted to minimize them in the finals. This is why, we took our time before submitting solutions, and mostly got them proof read by another teammate before submitting. As a result we had just one penalty overall (which too required exactly a single character change). Even though we lost out on time because of this, we are glad we made this bargain.
If you’re planning to participate in ICPC anytime in the future, my advice for you would be simple: remember this is a team contest. No matter how good you are individually; if your team is not balanced, it becomes really difficult to win in the Regionals. When forming your team, try to find members with slightly different areas of expertise. Have good interaction with them and try to give as many team contests as you can.
Q. What did you do to improve over these years and maintain your target status for all these years with all the competition? What do you think was your most effective method to improve? Any hacks on how to reach where you are in less time ?
A. I think participating in as many good contests as you can is an effective way to learn. But this only works if you find out the solutions to problems you could not solve in the contest after it ends. Otherwise you’ll feel that you have saturated after a point and there’s nothing more to learn. There are an insanely large number of tricks and techniques that are useful in competitive programming, and we can only learn these over time with practice. Then there are some really talented Indian programmers who are performing well on online judges. We should look up to them for inspiration!
Q. Do you have any other thoughts as we wrap up?
A. First of all, I’d like to thank CodeChef and the other Indian programmers who have been making commendable efforts to improve the programming culture in India. It’s no doubt that the Indian programming circuit has come a long way in the past few years. Sure, we still have a long way to go before we can compete with the best in the world, but I’m positive we’ll get there eventually.
We hope you enjoyed the interview. We have few more in the pipeline and will be publishing them soon. Till then, share this interview among your friends, and family and send in your wishes and questions for them. #GoForGold.
Regards,
Rudreshwar
Team CodeChef
The second in the series of #ICPC Indian finalist interviews comes from Kunal Singhal (a.k.a. knsn) from IIT Delhi. Here is a brief about his ICPC profile followed by the interview.
How old were you when you started programming and what got you started in programming?
I think, I started coding in c++ in class 9. My motivation was to compete in inter-school competitions happening all over Delhi. We did win some of those contests. But I really got introduced to competitive programming when I gave INOI in my 12th grade and cleared it. And then, I learnt systematically in the IOI Training Camp. I learnt almost all the algorithms there.
What inspired you to get into competitive programming? Were you passionate about it since school or anything special in college?
I always loved mathematics and was part of Robotics club in my school. But programming robots was not challenging enough, so I dived into competitive programming given the first chance.
How to start preparing for ACM ICPC for those who are new to algorithms and competitive programming? It would be great if you could share your journey from a beginner to a World Finalist today.
One simple advice. Practice, Learn as you do. Do not read theory first. Attempt problems, get blocked, search, ask, read, learn and apply. Follow it like a recipe.
Can you throw some light on how did you and your team manage the time and coordinate during the onsite finals? It would be great if you could share some tips for the next year ICPC aspirants.
Our time management at onsite was quite ad-hoc so not much to say. A good chemistry is needed though. So, make sure that your teammates are also your friends.
What did you do to improve over these years and maintain your target status for all these years with all the competition? What do you think was your most effective method to improve? Any hacks on how to reach where you are in less time ?
No hacks, genuine curiosity and perseverance is the key.
Hope you enjoyed the interview We are coming up with more, stay tuned!
Regards,
Chanukya
Team CodeChef
After a fierce battle of codes at the ACM ICPC 2015 – 2016 Indian Regionals (Amritapuri, Chennai and Kolkata), we finally have the teams which will be representing India and their respective institutions at the ACM ICPC World Finals 2016 at Prince of Songkla University Phuket, Thailand. If you are a programmer, you certainly would have or still has the dream of representing your nation/institution at these coveted programming contests. However, we all know, there can only be one winner, and in case of ACM ICPC World Finals, there can only be certain number of teams.
As Henry David Thoreau said, “Success usually comes to those who are too busy to be looking for it.” We are sure that every one of these individuals would have strived hard to be where they are right now. And, that is what makes it even more intriguing to find the secret behind their success. But, we will save you all the guessing time and bring to you the secret straight from the horses’ mouth. We have already snatched some valuable time from their busy schedule interviewing them and will be sharing the experiences of ACM ICPC Indian World Finalists starting this week. We are sure their insights and experiences will be inspiring and resourceful for everyone aiming to make it big in the world of competitive programming. So, sit back and enjoy them. Also, do not forget to send in your wishes for your favorite team, feel free to tag us in your cheer messages or use the following hash tags #ICPC2016 #GoForGold #CodeChef.
The first in the series of interviews comes from Man Mohan Mishra from IIIT Allahabad. Here comes his profile and the interview.
How old were you when you started programming and what got you started in programming?
I started programming in 1st semester of my graduation. I didn’t have any previous experience in programming during my school. So, things were kind of new & challenging in the beginning.
What inspired you to get into competitive programming? Were you passionate about it since school or anything special in college?
Major role in my involvement in competitive programming was the motivation and inspiration from my seniors. The environment of competitive programming is quite healthy in my institute (IIIT Allahabad). So, I came to know about competitive programming through seniors and I started it.
How to start preparing for ACM ICPC for those who are new to algorithms and competitive programming? It would be great if you could share your journey from a beginner to a World Finalist today.
As I recall my journey, I started mainly with SPOJ in my 1st semester. Along with it, Uva was really helpful and I am sure it will be of high help for any beginner. Though tutorial of problems are not available over these judges, but the time spent in debugging a code or finding the mistake in your logic also teaches you many things. After practicing on SPOJ for like 6 months (and solving nearly 100 problems), I started participating and solving problems on Codechef and Codeforces. I loved the contests hosted on both these websites and I hardly missed the contests hosted on them. Slowly, I started solving problems on Topcoder, Hackerrank and Hackerearth. In my 5th semester, we (I along with Aditya and Shiva) formed a team and started practicing in team contests. Codeforces gym was very helpful for team practice. We also listed down topics (Data structures and algorithms) and divided those among us so that we may get more time for focusing on our individual topics. We also participated in gym contests in our labs using only 1 system during the contest.
Can you throw some light on how did you and your team manage the time and coordinate during the onsite finals? It would be great if you could share some tips for the next year ICPC aspirants.
I believe my approach towards competitive programming was not the ideal one. I used to participate in live contests so much (100+ codeforces rounds till date). If I get another chance now (from 1st semester of course ), I would list down the topics and I’ll learn each topic in 8-10 days using online tutorials/blogs and then I’ll spend 4-5 days to solve problems based on that topic over various online judges. In this way, a large number of topics can be covered in 1-2 years.
Finally, about the coordination inside team. This part is very important. To reduce the panic and chaos during onsite contests, we practiced in a lot of team contests keeping the environment as similar to onsite contests as possible. Every member of team must formulate the process on paper before starting to type the code.
What did you do to improve over these years and maintain your target status for all these years with all the competition? What do you think was your most effective method to improve? Any hacks on how to reach where you are in less time ?
In the end, I firmly believe that practice (“smart practice” to be precise ) is the key for performing well in competitive coding.
Hope you enjoyed the interview We are coming up with more, stay tuned!
Regards,
Chanukya
Team CodeChef
Hello World!
It’s a bright sunny day here in Chennai and brighter are the smiles on our young ACM ICPC 2015 – 2016 World Finals aspirants. It’s the final of the three ACM ICPC India regionals here at Hindustan University, Chennai. The blokes look in good spirit after a good night’s sleep and lots of fun activities they partook with team CodeChef last night. If the initial spirit is something to go by, we all are in for a crunchy 5 hour programming battle for that coveted slot for the world finals. The stage is set, and the curtain rises at 10:00 AM IST. So, grab your bowl of cereals and get ready for the live action as we bring it to you straight from Chennai.
9:45 AM: 15 minutes to the contest start. The teams have settled in and are eager to shoot down them problems.
9:50 AM: The gamut of expressions and feels that you get by looking at the participants few minutes before the contest are bemusing. You just don’t know who’s going to come on top after the contest.
10:00 AM: The contest has been delayed by 30 minutes. The contest will now start at 10:30 AM IST.
10:05 AM: The cause for delay is “INCORRECT PROBLEM CODEs” on the printed problem statements. It has been resolved now, and we are looking good.
10:10 AM IST: While we wait for the contest to start, send your predictions on who you think will win here at Chennai. We are running a contest on our Facebook and Twitter streams. The correct prediction wins a cool goodie. So, check that out and send in your guesses.
10:29 AM IST: Just one minute for the contest to start. hold on to your seats folks.
10:30 AM IST: Update: The contest has been further delayed by 30 minutes. We hope this is the final delay.
10:38 AM IST: Update: The contest has been scheduled to start at 11:00 AM IST and will end at 16:00 PM IST.
10:45 AM IST: While we wait for the contest to start, here are few glimpses of the contest arena for you.
10:52 AM IST: The ACM-ICPC Asia-Chennai Onsite Mirror Contest 2015 has been rescheduled for 12:30 PM IST.
10:58 AM IST: 2 minutes to the contest. Are you guys ready?
11:00 AM IST: The final ACM ICPC 2015 – 2016 India Regional is on its way at Hindustan University. Follow the live rank list here.
11:05 AM IST: After 5 mins we have 4 teams with 1 solved problem each.
11:07 AM IST: And we now have 11 teams with 1 problem each.
11:09 AM IST: The problems named after some of the brightest programmers from schools in India will decide which Indian college will go to World Finals. Interesting, it is.
11:15 AM IST: Update: The ACM-ICPC Asia-Chennai Onsite Mirror Contest 2015 has been rescheduled for 11:30 AM IST.
11:25 AM IST: 109 Teams have cracked the at least 1 problem. And only 1 team have got the penalty. Amazing stuff.
11:26 AM IST: Team Instincts of Sri Sivasubramaniya Nadar College of Engineering, Chennai leads the rank table with two solved problems in their kitty.
11:29 AM IST: Team DAFruitSalad of DAIICT, Gandhinagar takes over team Instincts at the top of the table.
11:30 AM IST: The ACM-ICPC Asia-Chennai Onsite Mirror Contest 2015 has been served.
11:35 AM IST: Team shockers of Indian Institute of Technology Madras bags their 3rd. Not so shocking, is it?
11:40 AM IST: Team Instincts of Sri Sivasubramaniya Nadar College of Engineering, Chennai regains the lead atop the rank table.
11:45 AM IST: All top 10 teams have solved three problems.
11:46 AM IST: The absence of some heavy weights in top 10 is kind of amazing. What do you think?
11:54 AM IST: The calmness on the rank table is severely alarming. What’s cooking there Chennai?
12:02 PM IST: Team Tianhe_3 of Birla Institute of Technology & Science Pilani, Pilani Campus solves their 4th and moves at 1st place on rank table.
12:09 PM IST: The problem statements features three familiar names from the programming fraternity. Do you know who they are?
12:12 PM IST: A lot of teams have shown their love for balloons by solving “Malvika is peculiar about color of balloons” first. however, not many are ready to take the voyage to the Sun with King Animesh.
12:20 PM IST: Team Encore of IIT, Bombay moves into top 3 with 4 solved problems. We now have three teams with 4 solved problems. Other than Encore and Tianhe_3, we have team Divide&Conquer of IIT, Delhi enjoying the weather atop the rank table.
12:25 PM IST: Team Divide&Conquer from IIT Delhi is at Rank 3 having solved 4 problems. Leading just ahead is Team Encore at Rank 2.
12:30 PM IST: There are 4 teams with 4 problems solved now as Team One_LastTime of IIIT Delhi has moved up to Rank 3. Things are starting to speed up now!
12:42 PM IST: The elves have spoken as Fractal_Elves of DTU solved their 4th problem and moved to 2nd place in the rank list. Team Tianhe_3 has still not budged from top place!
12:46 PM IST: Rank 1 has been taken over by Encore of IIT Bombay as they solved their 5th problem and are the only team to do so as of now! As the top ranks remain vaguely the same, contendors like TarjanHorse and 11Coders are also inching upwards!
12:59 PM IST: There is a lot that goes behind every single contest we host. And to tell you the story behind the Chennai regionals, here are the sleepy eyes of our Dev team.
01:13 PM IST: As we approach the half way mark into the contest, the action on the rank table is starting to heat up. Team Greed_for_Speed of Indian Institute of Information Technology, Allahabad moves on to second spot with 5 solved problems to their name.
01:47 PM IST: IIT Roorkee Team 11Coders make it to Rank 2 with 5 problems under their belt.
01:53 PM IST: Encore cracks the 6th and strengthens their position atop the rank table.
02:21 PM IST: Team 11Coders of IIT, Roorkee closes in on Team Encore, as they cracks their 6th problem. This is going to be interesting.
02:44 PM IST: WOAH! As we approach towards the final hour of the hugely popular team Heuristics of IIIT, Hyderabad jumps onto second place with 4 consecutive ACs. Now, that’s the pinch of excitement you need just before the ranklist freezes. Put on your thinking hats, will ya?
02:48 PM IST: Within 20 mins Heuristics of IIIT, Hyderabad have jumped 35 positions to reach 2nd place from 37th, where they were.
3:00 PM IST: The curtain has fallen on the Rank List as the last hour of the contest sets in. Nobody knows what the outcome might be and the frozen Rank table looks even more intimidating. We saw steadily improving performances, strong footholds on the top spot and huge leaps from lower ranks into the limelight. Chennai Regionals were a delight to watch for everyone, we are sure. But the final verdict only time will tell if we will be pleasantly surprised or completely shocked! All the best teams, it was an ever entertaining fight. watch this space for more to come.
04:00 PM IST: The ACM ICPC 2015 – 2016 Chennai Regional has concluded. The teams will now have a small break, before gathering for the problem discussion and the closing ceremony, where we will meet the winning teams. So, keep your fingers crossed and keep watching this space.
05:35 PM IST: It’s result time here at Hindustan University Chennai. Drum Rolls!
05:35 PM IST: 2^{nd} Runner Up is team Greed_for_Speed of Indian Institute of Information Technology, Allahabad.
05:40 PM IST: 1^{st} Runner Up is team 11Coders of Indian Institute of Technology Roorkee.
05:45 PM IST: And finally, the Winner of ACM ICPC 2015 – 2016 Chennai Regional is team Encore of Indian Institute of Technology Bombay.
05:46 PM IST: Here are the winning teams posing for the shutterbugs.
05:46 PM IST05:49 PM IST: And that will be all from us here at ACM ICPC 2015 – 2016 Chennai Regionals. A big round of applause for all the teams for their tremendous performance. We wish the teams representing India at the ACM ICPC 2015 – 2016 World Finals at Prince of Songkla University Phuket, Thailand all the Very Best. Go For Gold
05:52 PM IST: Also a big shout out to all the volunteers and committee members for putting up such a great contest. We hope you enjoyed our coverage of the final India regionals. We hope to see you soon, in a different city with a different contest.
05:54 PM IST: It’s time for us to sign off, but before we do that a huge round of applause for our dev team, operations team for their rigorous efforts to ensure a smooth contest.
That’s all for now. It’s me Rudreshwar with my fellow team members Rhuta and Chanukya signing off.
See you at the contests.
Sayonara.
Regards,
Rudreshwar
Team CodeChef
P.S: The rank list for the contest is live for everyone, you can check it here.
The floods in Chennai that engulfed the city have passed and the city is coming out from its state of disarray and wreckage. Our empathies are with all those it affected. The spirit of the individuals and organizations that helped out during Chennai’s time of need was truly inspiring.
As everything came to a halt, the ICPC regionals were naturally rescheduled. In the aftermath of the floods, the Chennai ICPC Regionals will now be held on the 23rd of January and undoubtedly, enormous efforts were put in to resurrect this contest. Team CodeChef will visit the regional site to support the teams, help out with registrations, and most importantly see the contest go superbly for everyone.
The CodeChef kitchen is already emptying once again as we leave for the Regionals in anticipation of a great contest and a rejuvenated Chennai.
We hope that with all the combined efforts going into the contest, the teams will have a good environment to code in, and will make this chance to go to the World Finals really count. That being said, our heartiest congratulations to all the teams for making it to the onsite contest. And all the very best for #ICPC2016 regionals.
That’s all from Team CodeChef for now, we will be in with more news from #ICPC2016 soon. Till then, keep coding!
Regards,
Team CodeChef
It is morning and people are on their way to work, nursing their Monday blues. While the repetitive nature of the work-week waits to unfold for many, things are not quite the same for the students gathered at the ACM ICPC 2015 Amritapuri Regionals sites. The air is singing with enthusiasm and anxiety all at the same time. The participants have entered the contest arena and the next few hours will decide who goes to the ACM ICPC 2015-2016 finals at Songkla University Phuket, Thailand.
8:45 am: The teams have received their login details and questions for the contest will come up soon.
Bated breath. Watch this space for more to come.
9:05 am: Team “Epsilon Zero” cracks the first problem within four minutes. That’s great start we say.
9:15 am: Almost 85 teams have bagged the problem “BDAY”. That’s one big birthday party we are having here at ACM ICPC 2015 Amritapuri Regionals.
9:30 am: 10 teams have cracked at least 2 problems. Leading the rank table is team “stronglyConnected”.
9:55 am: Team Facelessmen from IIT Kanpur gets 3 questions before anybody else and are leading the scoreboard.
We have balloons coming up now as the contest completes its first hour!
10:05 am: The scoreboard is in a flurry of change as the teams scramble to make it to the top. Team “Instincts” from SSN Colege Of Engineering, TN also get 3 questions in and have moved to the 2nd spot.
Problems ‘Birthday’ and ‘Longest Palindrome’ remain on top of the ‘solved’ list of the teams!
10:17 am: Team Pynapple of BITMesra moves to 2nd place with 3 solved problems. The top ranks are currently carrying Teams Facelessmen, Pynapple, epsilon_zero and Instincts. Let’s keep a tab on them, shall we?
10:37 am: The clock is ticking and the teams are yet to get their 4th problem. Wonder who will get it first?
The contest was paused due to some technical glitch but not to worry, it has been moved over to the CodeChef platform at https://www.codechef.com/ACM15AMR
Let’s get the show on the road
1:18 pm: The team from IIT Roorkee ‘Invincibles’ are leading on the ranklist after solving their 4th problem. Let’s cheer them on and keep our eyes on the ranktable!
The Invincibles in action:
1:37 pm: ‘angle’ from IIT Delhi closely follow and have set up camp at Rank 2 on the ranklist. Who get’s the 5th question first, let’s see!
Team angle at the contest:
1:50 pm: Look what we have here, Rank 1 is occupied by doped_ducks from IIT Kharagpur. The top position has been captured, nobody knows for how long. Keep reading. More coming up soon!
doped_ducks in a tangle of balloons:
2:13pm: The rank table has bitbees, angle, Nullstellensatz, doped_ducks leading with maximum scores in this order. Changing rank tables have us waiting on the sidelines, but we will keep you posted on the happenings at the ICPC Regionals. Hold your breath
2:45 pm: Coins, Coprimes and Magical Matrix seem to have stumped most teams. let’s wait to see who gets them first!
While the ranklist decides who is beating whom, lets sidestep and go see the jury room!
The Rank list can only tell you so much Last few minutes of the contest and nobody knows what will happen. Cross your fingers and wait a while.
Regards,
Team CodeChef
© 2009, Directi Group. All Rights Reserved.