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^{6} 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! 🙂

I just want to know ,

ebmarah

BITS Pilani, Goa campus

solve 3 problem in 1 min . How ? They are superman I think

they gave the problems before 30mins

What?

they gave the problems 30mins before the contest on paper and the systems started after 30mins

Are you sure about this? How do you know? Did you participate from the same campus and get the problems 30 minutes before?

He’s right, we did got the problems half an hour before

Is this a joke or something? 😛

When did the contest end for you guys?

It was a clear advantage to teams at Bangluru site… and so is reflected in leaderboard… Authorities shd. take some action.

When final leaderboard is declared?

wow awesome

Faceless men -1 , mobius_treap – 2