ACM ICPC Amritapuri Regionals 2016 – Live Updates

Welcome to Amritapuri Regionals, the third leg of this year’s ICPC Regionals. It is the largest regional in the world, with over 400 teams and 1200 participants! We look forward to an intense contest today. Vaibhav and I will keep giving you live updates throughout the contest!

Live Leaderboard: http://results.cloudcontest.org/amrita2016/ACMICPCRC.html

9:30 IST: Contest has started.

9:50 IST: 20 minutes into the contest, we have Survivor at the top of the leaderboard with 3 problems solved, followed by HappyTreeFriends from IIIT Delhi and White Tigers from IIT Roorkee both with 3 problems solved.

Team Survivor from IIT Indore (left) and White Tigers from IIT Roorkee (right).

9:52 IST: 7 teams have 3 problems solved now.

10:01 IST: Team BetTrumpWon from IIT Bombay are the first to solve 4 problems!

Team BetTrumpWon from IIT  Bombay.

10:02 IST: FacelessMen from IIT Kanpur are now on top with 4 problems solved and a time penalty of 61 minutes. BetTrumpWon are second with 84 minutes of time penalty.

Problems C, D, H, I and J are now solved by at least one team.

code_phoenix from NIT Karnataka and mobius_treap from IIIT Hyderabad now have 4 problems solved!

code_phoenix is now ranked 2nd with 74 minutes of time penalty!

10:15 IST: 239 teams now have at least 2 problems solved.

10:17 IST: mobius_treap have solved problem J! They now have 5 problems solved in total and are at the top of the leaderboard.

10:19 IST: _MSN_ from IIT Roorkee have solved problem C and are now at Rank 1.

10:31 IST: FacelessMen have overtaken Team _MSN_. They have solved 5 problems but with lesser time penalty.

Team FacelessMen from IIT Kanpur.

The first problem we will discuss today is Problem C – Influence on Social media. In this problem, we are given a list of N distinct integers. We need to find integers from the given list which have an odd prime number of divisors. Such integers are called supporters. For each supporter, we need to find the number of integers greater than itself in the original list.

A number can be represented as p1^e1*p2^e2*…*pk^ek. The number of divisors would be (1 + e1)*(1 + e2)*…*(1 + ek). Let this product be P. We need P to be prime. Hence, there has to be exactly one pi whose power ei should be even and (1 + ei) should be prime. To solve this within time limit, pre-compute all even powers of primes uptil 10⁶ and for each integer in the list, check if it is an even power of a prime.

11:04 IST: mobius_treap solve Problem B. They now have 7 problems solved now and they’re 2 problems ahead of FacelessMen.

Team mobius_treap from IIIT Hyderabad.

11:15 IST: Team Rocket from IIT Bombay have rocketed to the 2nd position with 6 problems solved!

11:25 IST: Survivor from IIT Indore have solved problem J and are at Rank 2 now! Among teams who have solved 6 problems, they have the least time penalty.

11:28 IST:  Team n82696 from IIT BHU have solved problem B and are now at Rank 3.

11:49 IST: Team Rocket from IIT Bombay have solved problem G and have 7 problems solved in total. FacelessMen

11:52 IST: Problems A and F remain unsolved, still.

12:14 IST: FacelessMen have solved Problem B after 2 wrong submissions. They have taken Rank 2 and displaced Team Rocket to rank 3.

Let’s discuss Problem G – Hawala Arrests. We have a tree T(V, E) and k connected subgraphs {S1, S2, S3, … , Sk}. We need a minimal set H which is a subset of vertices V, say {v1, v2, v3, … , vh} such that each of the k connected subgraphs has at least one vertex from H.

In this problem, one needs to iterate over the nodes in reverse depth order. For each node, if it is the only member of some unselected subgraph, then choose it, otherwise skip it.

12:50 IST: FacelessMen solve E! They are now at the top of the leaderboard with 8 problems now!

Let’s discuss problem E. The problems asks to find if a spanning tree of weight X can be constructed in a given graph G whose edge-weights are either 0 or 1. There are Q queries in which you are given X.

Here, we need to find the Minimum Spanning Tree (T1) and the Maximum Spanning Tree (T2) of the graph.
If X is less than the weight of T1 or greater than the weight of T2, then such a spanning tree cannot be constructed.

Let E denote the set of weight one edges which is in T2 but not in T1. Iterate through edges in E, and add them one by one to T1. After adding each edge, there will be one simple cycle formed. This cycle will have at-least one edge which is not in T2 : We have to have atleast one such edge, if we don’t, there is a cycle in T2, and that is a contradiction. Remove any such edge. Repeat this process over all edges in E. Take any minimum spanning tree T1. Also take any maximum spanning tree T2. Let E denote the set of weight one edges which is in T2 but not in T1.

Iterate through edges in E, and add them one by one to T1. After adding each edge, there will be one simple cycle formed. This cycle will have at-least one edge which is not in T2 : We have to have atleast one such edge, if we don’t, there is a cycle in T2, and that is a contradiction. Remove any such edge. Repeat this process over all edges in E.

1:56 IST: mobius_treap have solved 9 problems and are at Rank 1. FacelessMen and [matrix] follow with 8 problems each.

Problems A and K remain unsolved with 1 hour remaining in the contest.

2:00 IST: The leaderboard is now frozen. There’s a tough fight going on between mobius_treap, FacelessMen and [matrix]. May the best team win!

Meanwhile, FruitSalad leads the ranklist in the Mirror Contest with 8 problems solved.

3:00 IST: The contest has ended. Stay tuned to know the results! 🙂