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
© 2009, Directi Group. All Rights Reserved.