The year is about to end, and so is the ACM ICPC season with the India Final 2016! After 4 onsite contests, with almost 600 teams participating and intense battles between the best teams, we’re here to present you live updates from IIITM Gwalior where the ACM ICPC India Final 2016 is happening today! Stay tuned for interesting insights from the arena, problem discussions and more!

The **Mirror Contest** shall begin at 11:00 a.m. IST. You can register your team for the mirror contest here.

**Live Leaderboard**: www.codechef.com/rankings/ACM16INF

**10:00 IST**: The contest has begun. The problem set consists of 11 problems.

**10:08 IST**: No submissions on any problem yet.

**10:13 IST**: No submissions still. Teams might strategize to minimize their time penalty today, as it can play a huge role in the final leaderboard.

**10:15 IST**: We have our first accepted submission! **Problem I** has been solved by team **SRY** from Delhi Technological University!

Problem I is called “Pacman” – surprisingly, it is not related to the game in any way but it is based on the name of a Software Package Manager.

This problem has been set by Vaibhav Tulsyan (that’s me!).

The problem is as follow:

You are given a list of softwares and their dependencies. Each software has at most one dependency and there are no cyclic dependencies. Also, each software has a **download limit** D[i]. Given a subset of **ultra-special softwares**, you want to find the maximum no. of “**completely installable**” softwares. By “completely installable”, we mean that its entire chain of dependencies must first be downloaded, and then the software itself should be downloaded. Each ultra-special software does a fresh install of all its dependencies.

The first solution one may think of is finding the **max flow** in a transformed graph. A new graph can be constructed by splitting each node into an edge with capacity = D[i] value of that node. A source node will have edges to all ultra-special softwares with capacity = 1 and all nodes which don’t have dependencies, can have edges to a Sink node with capacity = infinity. The answer would be the value of max flow in this graph. The implementation can be done using **Dinic**‘s algorithm.

However, from some observation, it can be deduced that one can** select any ultra-special software** and completely install it, if it is possible. Hence, all you need to do is **traverse** over all the dependencies of the ultra-special software uptil the highest parent, keeping track of the download limit and updating the download limits while traversing. This is a **O(N^2)** solution.

There also exists a **Dynamic Programming** solution which is that in each node, store the minimum of: D[i] of the current node and sum(D[j]) of all children j of node i. This runs in **O(N)**.

**10:46 IST**: 20 teams now have Accepted Submissions on **Problem I**.

**FruitSalad** have solved **Problem E** as their first problem! However, they got **1 penalty** on that problem.

Team** SRY** remain atop the leaderboard.

**10:51 IST**: Team **believe** from MNNIT are the first team to solve **2** problems and now lead the scoreboard with **0** penalties.

**FruitSalad** have solved Problem I and have 2 problems solved as well – although with 1 penalty. They are now at Rank 2.

**11:00 IST**: 1 hour into the contest, only 2 teams have solved more than 1 problem.

Let’s discuss **Problem E** – Jumping Frogs III.

We have Triveni Mahatha with us who has described the problem in brief as follows:

“The problem is about finding **maximum number of frogs in a segment** of an infinitely long road (x-axis) at any instant of time. Frogs are moving with constant speed in the x-axis. Initial position of the frogs and their velocity are given.

The solution is that, for every frog find out the time range for which they are at any point in the given segment. Then among these time ranges you need to find a time which is contained by max number of ranges. This can be done by sorting the intervals and doing line sweep greedily. Fairly popular problem.”

**11:05 IST**: AC on **Problem H** for Team Rocket!

They have solved 3 problems and lead the ranklist.

**11 teams** now have at least 2 problems solved.

The live leaderboard can be seen here: https://codechef.com/rankings/ACM16INF

**11:15 IST**: Team **mobius_treap** gets AC on **Problem A**! They are the first team to solve that problem. This is their 2nd solved problem in the contest.

**11:25 IST**: Team Hopeless solves **Problem B**.

**11:32 IST**: **FacelessMen** solve Problem A and move to **rank 2** with 3 problems with 1 penalty.

**mobius_treap** solve Problem E and move to **rank 3** – they have 2 total penalties.

**11:35 IST**: **Triangulation** get AC on Problem H. They seem to have used a Persistent Trie + Binary Search for their solution.

**11:36 IST**: Team **Rocket** have solved **Problem C** and increase their lead with 4 problems solved.

Let’s discuss Problem A now. You are given a number **N** of the from **p * q**. Where p and q are prime numbers. p may be equal to q.

You need to **distribute N balls into k buckets** such that every bucket gets equal number of balls.

It is clear that k can be either 1, N, p or q. You need to be alert that you are not counting twice for p and q if they are equal.

Print the answer modulo mod.

There are few things to observe here.

First **how to factorize N which can be 10^12**. But since max(p,q)/min(p,q) <= 10. It is easy by just doing brute-force.

Next observation is that the value of mod is small, this will be useful. Let’s first arrive at the solution.

Distributing N balls into k buckets is a fairly standard task in combinatorics. Say y = N/k then the number of ways is **N!/(y! ^ k)**.

Here you may not take modular inverse as the denominator can have multiple of mod, since mod is very small.

So, rather you actually factorize the numerator and denominator to get the answer. Note that you need not go to prime factors more than mod. Because if the answer contains mod then answer is zero anyways.

That’s all about this problem. However, you need to be careful while implementing the idea. So many modulos and few cases as well. Factorization should be fast enough. Use sieve.

**11:42 IST**: Team **Survivor** from IIT Indore solve **Problem L** – a geometry problem. They are now at Rank 2 with 4 problems solved.

A glimpse of the arena.

**11:51 IST**: Almost 2 hours into the contest, we have **7 distinct** problems solved, with the top team solving a total of 4 problems.

Problem L, authored by Triveni is a really interesting geometry problem.

Quoting Triveni’s explanation of the problem and the possible solutions:

“Problem L is about finding approximate-smallest enclosing circle of N points in Cartesian plane. Smallest enclosing circle can be defines as a circle with minimum possible radius such that all the given points are either inside or on the circle.

If we allow few (4 for this question) points to be outside the circle, this is approximate smallest enclosing circle problem.

There are many possible solutions to this problem as the constraints are very small. N is just 51

I will discuss few.

Few things to observe. At most three points are needed to define the circle.

So we chose any three points and make the circumcircle. If all but 4 points are inside this then we have got an answer. complexity **O(N^4)**. Fairly simple.

Another is based on **Weizl’s algorithm**.

You select any three points and make SEC of all the remaining points. If there are more than 3 points on the circle then you can not do much by removing one more point from the set. However, if there less than 4. Then we can try removing one point from the circle and regenerate the SEC of remaining points.

Weizl’s algorithm computes SEC in O(N). Its a **randomized las-vegas algorithm**. So random shuffling of points is needed to avoid TLE.

Total complexity is **O(N^4)** for this as well.

Apart from this one can write **O(N^5)** solution **with optimizations** to get AC.

That’s all.”

**12:05 IST**: Team **Rocket** have 5 problems solved and 2 penalties – Rank 1.

**12:17 IST**: thirdfloor have solved **Problem D** – they are the first to solve this problem and have moved up to Rank 4.

Balajiganapathi says that he expects more teams to solve **D** and is surprised with such a small number of submissions on that problem.

**12:22 IST**: FruitSalad solve their 3rd Problem with Problem **H**! They are at Rank 10 now.

**8 distinct problems** with the **top team having solved 5**. That says a lot about the diversity of difficulty of the problem-set.

**12:33 IST**: **mobius_treap** from **IIIT Hyderabad** at Rank 3 with 4 problems and 2 penalties.

**
12:47 IST**:

Problem selection will be very, very important for the top teams now. With only a couple of hours remaining, they can’t afford to spend time on a problem and reach a dead-end.

**12:52 IST**: **mobius_treap** solve **Problem H** and are now are Rank 2, displacing third floor to the 3rd spot.

**12:56 IST**: **mobius_treap** solve **Problem L** and now are at Rank 1! 2 ACs within 5 minutes, they’re on fire today!!

**1:28 IST**: **mobius_treap** solve their 7th Problem and lead the ranklist. **Survivor** have now solved 6 problems and are at Rank 2, followed by **FacelessMen** with 6 problems at Rank 3.

**1:29 IST**: **FruitSalad** solve Problem L.

**1:53 IST: **As we approach towards the final hour of the contest, team mobius_treap looks comfortable at the top with 7 solved problems to their name.

**2:00 IST: **The final hour of the contest is in progress and the ranklist has been frozen. It means no more updates fromo us till the result announcement. So, join us back for the result announcements to find out who wins the first ever ACM ICPC India Finals.

**4:00 IST: **We are back live from the chilly campus of ABV IIITM, Gwalior, where the first ACM ICPC 2016 Multi-Site India Fials concluded, with some teams taking the part into the contest from Kolkata. And it is time to raise the mercury a bit with the final results of this ACM ICPC season. So, brace yourselves.

**4:10 IST: **The second runner-up is Team “Survivor” of Indian Institute Of Technology, Indore. A big round of applause for them.

**4:15 IST: **The first runner-up is Team “Rocket” of Indian Institute Of Technology, Bombay. Give it for them.

**4:20 IST: **And finally the big one. The winner of the first ever ACM ICPC India Finals is Team “mobius_treap” of International Institute Of Information Technology, Hyderabad. Great job guys. They seem to be making a habit out of it. And we are very pleased that they are.

**4:30 IST: **With that, it’s time to let the Sun set on ACM ICPC season for the year 2016 and the year 2016 itself. We hope you had a wonderful year, and have big plans for the coming year. So, on that note, from everyone here at CodeChef here’s wishing you and your love ones, a Very Happy New Year. Have a wonderful evening folks.

This is wittyceasor signing off for the final time in the year, 2016. See you on the other side.

- Vaibhav Tulsyan

Welcome to ACM ICPC Kolkata Regional 2016, the last leg regional before the India Final!

Animesh and I will be giving you live updates throughout the contest. Stay tuned!

**Live Leaderboard** – https://www.codechef.com/rankings/ACM16KOL

**Mirror Contest** – https://www.codechef.com/KOL16MOS

**10:00 IST**: Contest has begun.

**10:10 IST**: FruitSalad is the first team to get an accepted submission. Problem **B** it is!

**10:15 IST**: Several teams have got correct submissions on Problem J now! It seems to be the easiest problem in the set.

**10:30 IST**: Team Whipslash from NSIT is now at Rank 1 with 3 problems solved. They have solved problems **B**, **H** and **J**.

**11:00 IST**: FruitSalad is the first team to solve 4 problems! They are now leading.

The Mirror Contest has now started as well.

**11:25 IST**: Team Whipslash and Team n82696 are at rank 2 and 3 respectively with 4 problems each. The top 6 teams have solved 4 problems uptil now.

There are a total of 12 problems in today’s contest. There are **85** successful submissions on **J**, **71** on **B** and **49** on **H**.

We now have 2 Accepted Submissions on Problem **E**!

An interesting stat – There have been more than ** 20** Accepted Submissions in

Some teams seem to be trying Problem **K** at the moment.

We have 5 distinct problems already solved – J, B, H, F, E.

**11:57 IST**: 12 teams now have 4 problems solved.

**12:04 IST**: Team **solah** have solved 5 problems and have taken over the lead from FruitSalad!

Sumeet Verma seems to be checking his code before submitting on problem E.

Sumeet Varma from Team FruitSalad.

**12:05 IST**: Aaaand FruitSalad get their 5th AC in the contest!! They’re back at rank 1. They didn’t let **solah** hold the lead even for a minute!

A glimpse of Team Rocket’s monitor.

**
12:18 IST**: Team

**12:30 IST**: FruitSalad solve Problem L.

**12:44 IST**: **Triangulations** have done Problem K! FruitSalad lead with 6 problems.

Meanwhile, in the Mirror Contest we have Rajat De‘s team leading with 6 problems.

Total 8 distinct problems have now been solved and only one team has solved 6 problems. This seems to be a set with a good variety of problems, that suits to teams with different strengths.

**1:14 IST**: The competition just got more interesting as **Triangulation** have solved their 6th problem!! They are now at Rank 2, lagging behind FruitSalad only based on time penalty. This is going to be one intense battle between Triangulation and FruitSalad.

Team Triangulation.

**1:20 IST**: **Triangulation** seem to be trying **Problem K** and **FruitSalad** seem to be trying **Problem L**.

Triangulation coding Problem K.

**1:25 IST**: Team **Rocket** joins the party with 6 problems in their kitty. They’ve replaced Triangulation for the number 2 spot at the moment! What a contest this is turning out to be!

With 1 hour 45 minutes left for the contest to end, who do you think will the winner be today? Give a shoutout to the team you support in the comments section!

**1:36 IST**: Triangulation now have** 7 problems** solved and are leading the ranklist!

**1:54 IST**: Triangulation seem to be trying the unsolved Problem **C**.

Meanwhile, FruitSalad seem to have written a brute-force to verify their solution.

FruitSalad debugging Problem L.

**1:59 IST**: Team Rocket solve **Problem I** to claim the top spot!

The last hour of this contest is going to be really, really interesting. To keep the mystery alive, we won’t be giving you updates after the scoreboard freezes.

We now have 9 distinct problems solved in the contest.

**3:00 IST**: The contest has ended. This has to be one of the most exciting Indian regionals we have witnessed in recent past.

Animesh presenting solutions of today’s problems.

Finally, let’s present to you the top teams on the leaderboard today, after a grueling contest!

3rd Runner-up – Team **How you doing** from IIIT Bangalore who solved 7 problems.

2nd Runner up – Team **Triangulation** from IIT Roorkee – solved 8 problems.

1st Runner up – Team **FruitSalad** from DAIICT – solved 8 problems.

And, the winning team – Team **Rocket** from IIT Bombay – with **10 problems** solved!!

That’s it from our side for the ACM ICPC Kolkata Regional 2016. Up next is the ACM ICPC India Final which is to take place on December 30. We’ll see you then!

- Vaibhav Tulsyan

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!

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 ^{12}, 10^{5}** test cases), print the smallest

**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 _{1}, b_{2}, b_{3}… b_{k})** of B such that each

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 ^{2})**. The key observation needed is that for a given position

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

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

**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

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

**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

A lot happened in the month of November, both on national as well as international front. From political changes to the financial transformation, there was just a little too much going on around the world to take your attention elsewhere. Not that we had any plans to. But it’s always good to clear that out. So, we decided to do what we know and sat down for the second last Cook-Off of 2016, the November Cook-Off 2016. On the problem setting bench for the contest, we had Istavan Nagy, Kevin Charles Atienza, and the contest admin Praveen Dhinwa. Joining our problem setters with their translations were Hu Zecong, Sergey Kulik, and Team VNOI.

We knew that while some of the participants are coming from a long holiday season, some will be looking at one, when we sit for November Cook-off 2016. And in both the conditions, expecting a blistering start to the contest seemed rather unrealistic. So, with no-to-minimum expectations in mind, we welcomed our Cook-Off Sunday. And it worked brilliantly for us.

We had a smooth start to COOK76. However, that was only for us. The contestants, though, seemed to have trouble finding their way around the problems. Of the first 50 submissions that we received, we only had 2 accepted submissions. And while that was shocking, what made it even interesting was the fact that 4 out our 5 problems from the contest had already seen a submission. Not necessarily an accepted one, but a submission nonetheless. The only problem that did not get a submission was SELECT. The lack of green ticks on the rank table made it hard for the participants to find out the easiest problem and bag it.

The first AC of the contest came from watcher on SETELE after 10 minutes into the contest; the second one came from chemthan on SECUBE quickly after the first. However, the two different problems seeing green ticks caused a whole lot of confusion as a lot of submissions started flowing on their directions considering them the easy. However, everyone who tried them could confirm that they were anything but easy. It remained that way for a while and even though the flow of submission was not as smooth as some of our other contests, some activity had begun on the submission table and we were pleased to have it.

The real action, though, started after about half an hour into the contest when al13n and uwi joined the contest almost at the same time. While, al13n cracked SEBIHWY in his first attempt, uwi got SETELE as his first. For their second submissions, it seemed as if they exchanged the problems, as uwi went for SEBIHWY and al13n went for SETELE, and there wasn’t a huge difference in the submission times either. There was a difference in the results though. While uwi got his right, al13n had to face RTE. And that’s where the difference started to build up. Joining them in the fight for the top was chemthan, one of the earlier submitters into the contest.

All that and the slow submission rate made it very clear that the contest isn’t an easy nut to crack. So, slow and steady seemed to be the mantra for success. And to find out who used it to perfection, let us take you through the rank table.

We start with ROW top 10:

Now, the Indian top 10:

- djdolls
- gvaibhav21
- dhrumil140396
- bhargav104
- tanuj_khattar
- ajinkya1p3
- ankit1s10_3
- ajs97
- jtnydv25
- prashantmahesh

A big round of applauds for all our winners. We hope you enjoyed the contest.

After the hard-fought places on the rank table, let us take you to the editorials for November Cook-Off 2016. We hope you have gone through them all, but if you have not, here they are for you.

And that sums up the tale of November Cook-off 2016 and takes us one step closer to the final Cook-Off of the year 2016. So, while we set the arena for the final party of the year you enjoy the winters with your preferred choice of beverage and with our sizzling contests.

We will come back soon with the tale from the November LunchTime 2016.

Till next time, adios.

See you at the contests.

- Rudreshwar

Team CodeChef

Last month, I participated CodeChef November Challenge 2016 and win 2nd prize as a high school student, which makes me delighted. Thanks to CodeChef for giving me a chance to share my thoughts on this contest.

Before the contest, actually, I was not confident in my ability to solve difficult problems, I just wanted to try my best and get a relatively high score. In my last participation, September Challenge, I only had solved 6 problems, so in this month, I wanted to make a difference.

As soon as the contest started, I entered into the contest page. It was not difficult to solve ALEXTASK, CHSQR, CPERM and GIFTCHEF. FRIEMEET and URBANDEV were also two classic problems, but a bit hard to code. It took me about 3 hours to solve the problems above. When I met KIRMEME, I knew I had to code for a long time – divide and conquer on a tree and something else. I finished my first version at about 22:00 (UTC+8), but got a WA, which made me sad and tired. In the following day, I got up early because I kept thinking of my WA program. It took me about half an hour to fix it and finally passed.

However, I found it difficult to solve any of the remaining 3 problems. SEAWCU was a challenge problem, BIKE seemed closely related to the matrix and SEAPERM3 was likely to be a hard counting problem. After submitting 2 brute force programs, I decided to think about SEAWCU and SEAPERM3. For SEAWCU, first I submitted a naive program, which cost less than 0.01 pts. Thus I spent the whole afternoon to think about how to optimize and came up with an idea of DP. When I submitted again, it was surprising that there were still really low points. Ah, there was a fatal mistake in the program! Finally I got 1 pts after fixing it (but now only 0.52 pts >_<, for ceilks' solution was really great).

During the night, I used brute force to find the clue of SEAPERM3. After observing lots of data, I felt that there was some magic relations between **i** and **p _{i}** and code for over 3 hours to pass it. I had to say it really required patience and concentration to solve it, it was a great problem indeed.

For BIKE, I had no any thoughts on it at all for almost a week. One day afternoon, when I learned a paper about 2-dimensional DFT, I remembered BIKE. The 2-dimensional DFT method fits this problem very well! Thinking of some details about the problem, I spent about 3 hours on the program and got Accepted eventually.

This contest meant a lot to me. It is my first time that I have solved all the problems (except the challenge problem), which builds up my confidence a lot. I also feels excited to meet all these algorithm problems, they shows me bright ideas and brings more fun to my life. Anyway, I will keep learning and study much harder in the future. At the end of this blog, I want to express my thanks to CodeChef Teams for providing us with a fantastic problem and contest platform.

Frank Chen

Dec. 6, 2016

- A New Year, Some New Names to Look Forward To
- Meet the new top trio
- Rajat stamps his authority, once again
- When persistence and grit won over experience
- A quick look back at November LunchTime 2016

- About (12)
- ACM ICPC (20)
- Announcement (277)
- Campus Chapters (7)
- College Contests (9)
- Contests (258)
- Events (47)
- FAQ (1)
- Features (49)
- Interviews (18)
- Languages (1)
- Meetup (4)
- Open Source (1)
- Practice Problems (8)
- Prizes (20)
- Problems (6)
- ProblemSetting (1)
- Programmer of the Month (34)
- Schools (9)
- Tech Talks (23)
- Tutorials (25)
- Uncategorized (1)
- Volunteers (2)
- Winners (119)

- Udit Sanghi on A New Year, Some New Names to Look Forward To
- Nilabja Bhattacharya on Tutorial for problem “Paying Up”
- Aravind Gopal on Tutorial For Small Factorials
- Mayank Nainwal on CodeChef Tutorial: Input and Output (I/O)
- Aman Aggarwal on The Cheating Cases Saga

- January 2017
- December 2016
- November 2016
- October 2016
- September 2016
- August 2016
- July 2016
- June 2016
- May 2016
- April 2016
- March 2016
- February 2016
- January 2016
- December 2015
- November 2015
- October 2015
- September 2015
- August 2015
- July 2015
- June 2015
- May 2015
- April 2015
- March 2015
- February 2015
- January 2015
- December 2014
- November 2014
- September 2014
- August 2014
- July 2014
- June 2014
- May 2014
- April 2014
- March 2014
- January 2014
- December 2013
- November 2013
- October 2013
- September 2013
- August 2013
- July 2013
- June 2013
- May 2013
- April 2013
- March 2013
- February 2013
- January 2013
- December 2012
- October 2012
- September 2012
- August 2012
- July 2012
- June 2012
- May 2012
- April 2012
- March 2012
- February 2012
- January 2012
- December 2011
- November 2011
- October 2011
- September 2011
- August 2011
- July 2011
- June 2011
- May 2011
- April 2011
- March 2011
- February 2011
- January 2011
- December 2010
- November 2010
- October 2010
- September 2010
- August 2010
- July 2010
- June 2010
- May 2010
- April 2010
- March 2010
- February 2010
- January 2010
- December 2009
- November 2009
- October 2009
- September 2009
- August 2009
- July 2009
- June 2009
- May 2009
- April 2009
- March 2009
- February 2009
- January 2009

© 2009, Directi Group. All Rights Reserved.