ACM ICPC Chennai Onsite Contest 2016 – Live Updates

We’re ready to start the 2nd of the 4 onsite rounds we have before heading to the India Finals!
Today, we have 122 teams competing in the Chennai Onsite Round for spot(s) at the 2017 ACM ICPC World Finals, which will be held in Rapid City, USA! Satyaki and I will be doing live blogging throughout the contest and we’ll keep posting interesting facts as they come up. Stay tuned for some exciting action!

Link to leaderboard : Live Ranklist

10:30 IST : Contest has started!

10:33 IST : We have our first Accepted submission by “embarah” from BITS Goa Campus on Problem G! It was solved in Python, which has been introduced this year into ICPC. Seems like a nice idea to solve cakewalk problems quickly in Python! 15 teams have AC in the first 5 minutes on that problem.

10:40 IST : 35 teams have solved Problem G already!

Teams would now be working on the other easy problems which are F and and C.

10:45 IST : 3 different problems have now been solved by atleast 1 team. Team mobius_treap from IIIT Hyderabad lead the standings having solved 2 problems, F and G. BetTrumpWon from IIT Bombay have solved 2 as well, and they’re in second place.

10:50 IST : 10 teams have solved 2 problems at this point. Most of the teams are now working on C which is the hardest of the “easy” problems in our problemset!

10:52 IST : BetTrumpWon from IIT Bombay solves C to become the first team to have solved the 3 easy problems. They did it in just 23 minutes!

10:54 IST : [matrix] from IIT Delhi solves 3 problems as well to take 2nd place on the leaderboard. However, they have one penalty on F.

The first problem that we’ll discuss today is C set by Bipin . In brief, the problem is as follows. Given two integers a and n (a, n <= 10¹², 10⁵ test cases), print the smallest x such that x is positive and ax – 1 is divisible by n. You must print -1 if such an x does not exist.

11:01 IST : ladders from Motilal Nehru National Institute of Technology, Allahabad have solved 3 problems and are now at 2nd place. They have no penalties yet!

Continuing on C, note that the constraints are too high to implement a brute force approach. Let’s first try to figure out when the answer is -1. So we have ax – 1 divisible by n. This means, ax – 1 = ny for some y > 0 . This means ax – ny = 1. Basic number theory tells us that a solution for this exists iff (a, n) = 1. If that condition is satisfied, we have infinite solutions. However, we need the one where x is minimum and positive. Note that ax = 1 (mod n), thus modular inverse of a wrt n is a unique solution and we must print it modulo n. However, note that traditional methods of finding mod-inverse such as using euler phi function will time out. What we observe is that we only need any solution to ax – ny = 1 and then we can print a modulo n. This can be done in O(log n) using the extended euclidean algorithm!

11:15 IST : The leaderboard stays the same with 12 teams having solved 3 problems each.

11:24 IST : [matrix] from IIT Delhi have solved problem B. They’re now leading with 4 accepted solutions!

The next “wave” of problems are easy-medium to medium level problems. These are A, B and I. A and B were set by Satyaki Upadhyay, and I was set by Lalit Kundu.

Let’s talk about B. The abridged version is as follows. Given a set of mixtures with two different types of solutes each having a cost associated with it, find the minimum cost to prepare all of them. You can either prepare one from scratch incurring the respective cost or use a linear combination of previously prepared mixtures without incurring any additional penalty. Let’s take an example to understand linear combination better. Consider three mixtures having quantity of solutes (4,2), (2,4) and (3,3). Then (3,3) can be represented as a linear combination of the other two, in the ratio 1:1.

The trick in this problem is think in terms of geometry. A well-known fact is that any point inside a polygon can be represented as a linear combination of its vertices and the sum of weights is 1. If you consider the quantities of solutes as a point on the X-Y plane, then you can prepare a mixture from others iff it is inside the convex hull formed by those points. Convex hull for a set of points is the smallest convex polygon enclosing all of the points. So you simply need to find the convex hull and print the sum of the cost values associated with its vertices.

11:35 IST : third_floor from CMI have solved problem I. They’re now at 2nd place with 4 accepted solutions!

Let’s talk about problem I. The problem basically asks the following. Given two sets of strings A and B. For each string a in A, we need to compute the size of the maximal ordered subset (b₁, b₂, b₃… b_k) of B such that each b_i‘s first i characters are the same as the first i characters of a.

This is standard application of the trie data structure. We insert all strings in B into a trie, and maintain for each node the number of leaves below that node (denoting the number of words in B having that particular prefix). After this, we iterate over each string a in A and go over our trie to compute the size of the maximal ordered subset. This can be done by just finding the deepest prefix of a in the trie that ensures that each picked up word is distinct. The complexity of such solution is simply O(|Sum of String Lengths|)

12:02 IST : mobius_treap from IIITH have solved problem B and I. They’re now the first team to have solved 5 problems and are leading the scoreboard!

We feel that the first 2.5 hours would be spent by the top teams in solving the 6 problems that we’ve mentioned till now. Next, we will discuss problem A, our last “easy-medium” problem!

12:11 IST : [matrix] from IIT Delhi have solved 5 problems as well and they’re leading (based on time). At second place, we have FacelessMen from IIT Kanpur. It will be interesting to see which is the first team to get to 6 problems, which probably means the first team to solve A!

12:50 IST : Team FacelessMen from IIT Kanpur are the first team to solve A! They jump to the top of the leaderboard having solved a total of 6 problems.

Now we can discuss problem A. The abridged version is as follows. Given a set of strings, a generating set is a subset of those strings such that every string in original set can be formed by concatenation of some strings from the generating set. You can use the same string from the generating set multiple times. For example, for the set {a, b, adbc, c, cbad, ad}, {a, d, ad, c, cbad} is a generating set. The problem asks to find the size of the smallest generating set. In the above sample, the answer is 4 corresponding to {a, b, c, ad}.

To any experienced competitive programmer, a Dynamic Programming solution immediately springs to mind. For each string, try to consider all of its suffixes as a member of the original set and recurse on the remaining string. But this will TLE as it is O(n²). The key observation needed is that for a given position i there are atmost sqrt(L) distinct lengths possible for the strings in the set, where L is the sum of lengths of all the strings. So instead of considering suffixes of all lengths, you can simply only consider these particular lengths. Using this, you can perform the suffix equality check(s) using hashing or Aho-Corasick algorithm, which is the intended solution. The time complexity of such solution is O(L sqrt(L)).

We’ve had some interesting developments. Team third_floor has submitted problem A, but they’ve got a WA. It seems that they’ve used the correct approach i.e. DP + Aho Corasick, and that they have some trivial bug.

Team mobius_treap seems to have got the main idea for E, but they have not added T test cases! Their submission has thus given a WA. It seems that they have missed the announcement(s) made on the contest page!

1:30 IST : Team mobius_treap have solved A as well, and they’re now in 2nd place! No team has done 7 problems yet.

Here are some pictures from the contest :

Team FacelessMen(left) and MobiusTreap(right) :-

1:47 IST : Team third_floor have finally debugged their A, and they’re now in 3rd place with 6 problems! However, they have a lot of penalties on A, which might prove to be costly in the long run!

Team third_floor :

Seems like the top 3 teams are trying different problems now. mobius_treap is trying E, they’ve fixed their test cases issue but it seems like there graph construction is wrong. third_floor has Rajat De submitting random heuristics for problem D, which hopefully won’t pass. The leaders, FacelessMen, interestingly, haven’t made even one submission in the last hour!

Meanwhile, the onsite mirror is being led by Malaysian High Schooler Zi Song Yeoh known as zscoder on most competitive programming websites. He has solved 5 problems till now.

We have just 8 minutes to go before the scoreboard is frozen. We’re definitely heading towards a nail biting finish! In the last fifteen minutes, we haven’t seen submissions from the top 2 teams. However, third_floor has submitted several heuristics for problem D, and none of them have passed. For example, one of their approaches was to sort the nodes based on its degree. In another submission, they’ve done a floyd warshall to compute reachability, and then again done a priority_queue degree based heuristic.

2:30 IST : Scoreboard has frozen. There haven’t been significant changes to the scoreboard. Unfortunately, from here on, we can’t give you any updates. We shall leave you in suspense. Please write your predictions in the comments!

3:30 IST : Contest has ended! Stay tuned for the results 🙂

We are back with the results of the ACM-ICPC Asia-Chennai Site Onsite round 2016. 5 hours and 10 problems later, it’s time to meet the winners. So, put your hands together and give a big round of applause to all the winenrs.

At No. 3 we have Team third floor of Chennai Mathematical Institute. It was their first ACM ICPC regional and to secure a podium on the debut, certainly is a special feat. Let’s give them a big round of appaluse.

At No. 2 we have Team mobius_treap of International Institute of Information Technology, Hyderabad.

And finally, at No. 1 and the winner of ACM-ICPC Asia-Chennai Site Onsite round 2016 is team Team FacelessMen of Indian Institute of Technology, Kanpur.

And that will be all from us here at ACM-ICPC Asia-Chennai Site Onsite round 2016. We hope you enjoyed the updates. We now move to the ACM-ICPC Asia-Amritapuri Onsite Contest 2016 to be held at 4 stunning campuses of Amritapuri University at Bangalore, Mysuru, Kollam, and Coimbatore. It is the largest regional in the world, so we are expecting a lot of action there. So, do come back for all the action from Amritapuri University on 22nd & 23rd December 2016.

Till then, adios.

– Animesh