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 S1, S2…SK, 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(Si) – min(Si)} 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 = (a1, a2, .., an) is a string, then its ‘kth power’ is defined to be the string Sk = (a1, a1, … [k times], a2, a2, .. [k times], an, an, .. [k times]) where each character is repeated k times. Given strings T and P, you need to find all substring matchings of Pk in T, for all k ie. Find all occurrences of P in T, of P2 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, 105, indicating that their definitely exists a linear or loglinear time solution. Here we describe the crux of one such solution. Note that checking whether Pk 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 Pk 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
Will there be a live rank list of the contest?
Unfortunately, there will not be a public live ranklist throughout the contest. But I’ll try to keep updating this blog as frequently as possible to keep everyone updated 🙂
Why not?
Update : Ranklist will be made public very soon!
How much time until ranklist is made public?
It’s live now!
link Please !
It’s in the blog. But here https://www.codechef.com/rankings/ACM16KGP
Hey ! Atleast mention the name of team “included” too.
Can you elaborate more on problem “OPTIMAL PARTITION” . I was using the same sorting and then sub-array approach to look for the answer but I couldn’t do that during contest time.
Just elaborate on how to take care of transitions after the array is sorted.
Please make the ranklist public !
or atleast tell about top 10 teams
Assuming I have understood F correctly there is an O(nlogn + k) solution too. Once you sort the array, if you don’t split it at all then the answer you get is x = s_2 – s_1 + … + s_n-1 – s_n. If you split it into two parts s_1,s_2,…,s_i and s_i+1,…,s_n then the answer you get is x – (s_i+1 – s_i). So optimally splitting into K subsets requires you to simply pick the largest k differences and subtract them from x.
Ah, sorry. Minimum size of each subset should be 2. I’ve updated problem description!
When we will get to see the live ranking ?
looks like we already have one world finalist decided
Haha! You never know, teams might still catch up, but it seems pretty unlikely right now!
heyy can you explain in detail how to solve F ??
You can wait till after the contest for a detailed explanation!
It’s been 11 days. Nobody has posted the solutions of the contest. It would be great if you will provide the solutions to the problems. I am specially looking for ‘Optimal Partition’ problem. Thanks in advance
Sumeet(Fruit Salad) is in ultimate form.Last year unfortunately he couldn’t make it to ICPC WF but this time I was sure when I had a chat with him few days ago before leaving the college, his attitude was “I will”. I am going to take a grand party from him now. 😛
Will rank list froze 1 hour before the end of the contest ? Please give us updates on who is leading. Thanks
Ranklist is freezed now ?
Yes
Will World Finalist be decjde today or all of them will be done after Gwalior India finals round
When will the final scoreboard be revealed?
how many world final slots are form kharagpur?
I think we can see the number of problems solved by a team from the team page.. Total problems solved minus the problems listed..
Can somebody please provide a detailed solution of Optimal Partition problem? Please help.