It was the last day of the year 2016. The spirits were flying high as people all around the globe dressed up in an impeccable manner for the final party of the year on New Year’s Eve. Good or bad, however, the year 2016 had been, everyone seemed pumped and optimistic about 2017. We too were, and had our little celebration with our December LunchTime 2016.

Set on the last day of the year, our final contest for 2016 had a fun theme attached to it. Be it the names of the problems like Superheroes and villains & Fly height mode or the excited participants to wrap up the year doing what they love doing. Set by Pawel Kacprzak, who also doubled as the editorialist for the contest, the final course of the year was tested contest ready by Misha Chorniy. Accompanying them on the problem setting bench were our contest admin Praveen Dhinwa, our Russian, Mandarin, and Vietnamese translators namely Sergey Kulik, Hu Zecong, and VNOI Team. And then there were us, excited as ever. So, let’s see how the December LunchTime 2016 was.

Set on New Year’s Eve, the December LunchTime 2016, the contest started in typical New Year’s party where everyone is calm and composed at the start, but as the night progresses things starts getting interesting. The first fifty submissions into the contest didn’t create any major ripple to grab the attention of onlookers. Most of the ACs into the first 50 submissions of the contest came from the big guns like uwi, additya1998 and many other popular names. All of whom are well versed with our contests and have been on the top of the rank tables on more than one occasions. Furthermore, none of them were a school student, so our wait to see some action from the school students got stretched a tad.

But it was after 30 minutes when things started getting interesting. In and around the 44^{th} minute into the contest we were joined by rubabredwan, tasmeemreza, and shivam312. All of them have been on CodeChef enough and none of them had the most fluent of the start to the contest. So, they didn’t catch our attention immediately. However, as we moved into the contest things started heating up. By now we were joined by the seasoned LunchTime campaigners like zscoder, barenuz, kmcode, yylidiw and many others. And when you have familiar names climbing up the rank table, you tend to focus more on them and less on others. We did that too. And we could not have been more wrong.

The sheer perseverance of rubabredwan, tasmeemreza, and shivam312 stunned us all as they took over the big guns and paved their way to the top. They had their fair share of tumbles as well. In fact, both rubabredwan and tasmeemreza got their first problems wrong in the first attempt. But they got hold of the problems real quick. The final hour of the contest was the most exciting one, as it was only a 20 point difference separating the top two with rubabredwan and tasmeemreza tied up on the same score. And we almost fell out of our seats, as it will be the first LunchTime victory for all three and we were all too excited for them.

shivam312 seemed to have more calculated approach as he took over 40 minutes to fully solve SBSWAP, while tasmeemreza was the fastest of the three as he tool minimum submissions to solve the 3 of the 4 problems in the contest. Then there was rubabredwan, who fully solved his third problem with just 2 minutes for the contest to get over. All three of them showed great composure and courage in the final few minutes of the contest. But they weren’t alone. There were quite a few other performances as well that caught our attention and to introduce them all to you, let us take you to the rank table.

Let’s start with the ROW top 10 school students:

- tasmeemreza of SOS Hermann Gmeiner School and College
- rubabredwan of Rajshahi University School
- giraffe_harold of Uzhhorod Specialized Boarding School
- zscoder of Chung Ling High School
- barenuz of Uzhhorod Specialized Boarding School
- ruhanhabib39 of Regent Educare, Malibagh First Ln, Dhaka, Bangladesh
- yylidiw of Shantou Jinshan High School
- mrkerim of Bashkent Turkmen-Turkish High School
- mysteryname of Mahidol Wittayanusorn School
- kmcode of Omori 7th Junior High School

Now, the Indian top 10 school students:

- shivam312 of Delhi Public School, Rohini
- debjit99 of Hijli High School, IIT, Kharagpur
- nibnalin of Delhi Public School, Faridabad
- msalpha99 of Sumermal Jain Public School, New Delhi
- adhyyan1252 of Oberoi International School
- sidhant007 of Delhi Public School, Dwarka
- wittyshreya10 of Podar International School
- dev127 of Delhi Public School, Dwarka
*aulene*of- dev2001 of Veda Vyasa DAV Public School

A big round of applause for all our winners from the final LunchTime of the year 2016!

We now move towards the editorials, which we are sure you would have devoured by now. However, if you missed them due to any reason, here they are for you.

With that it’s time to draw curtains on the final post for the year 2016 and the year as well. We now, move into a New Year and with that a series of new tales from our contests.

We hope you had a wonderful 2016 and will have an even better 2017. And on that note, it’s time to say farewell.

If you have any further queries or questions, kindly do let us know.

See you at the contests.

- Rudreshwar

Team CodeChef

When you have a big day tomorrow, you tend to calm down, relax, and just prepare your mind for it. It holds true for many big sportsperson, many big movie stars, and pretty much everyone, except for programmers. Programmers are the most restless creatures on the night before. And after being with, knowing, and interacting with so many programmers over the years, we certainly can assert that. It was not different the night before the first ACM ICPC 2016 India regional was scheduled to take place at Hindustan University. Knowing that most of the top programmers in the country will either be travelling for the onsite event, or will be relaxing at home to compete in the coming ones, we thought it’s an ideal situation for a newcomer to rise and shine. And we could not have been far from the truth.

That he is talented and perhaps an emerging legend in the Indian programming world is something we have been hearing about rajat1603. Time and again, he even has proved it in various competitions. From being among the top school teams to come for the SnackDown 2015 Onsite to being one of the few school students to have secured a place in top 5 in our Cook-Offs, he has proven his mettle time and again. And the December Cook-Off 2016 was yet another display of his sheer brilliance. This time though, the setup had changed a tad.

He no longer is a school student, he was competing in his very first ACM ICPC Regional, and just like himself, his counterparts in uwi, yenthanh132, biginnnner, and many others had evolved too. And considering all that, we thought a night before his first ACM ICPC regional he might want to catch a breather and focus his energy on the big day tomorrow. He, on the other hand, had totally different plans. The December Cook-Off 2016 started sharply at 09:30 pm on 18th December 2016 and in the very first minute, CHEFSETC was cracked by, you guessed it, rajat1603. One minute is all it took him to crack the first problem of our Cook-Off. If that doesn’t send strong signals to your counterparts, we don’t know what does. And with that, it was on.

Contrary to the blistering start from Rajat, uwi had a slippery start when he got TLE in his first submission on CHEFINS. However, he was quick to recover and bagged his first AC inside the first 8 minutes of the contest as he cracked CHEFSETC. If truth be told, CHEFSETC was almost solved by everyone who attempted it. Off the first 100 submissions into the contest, 98 were on CHEFSETC, and that made it obvious that it was the easiest problem in the contest. However, getting the easy problem quickly doesn’t win you the Cook-Off. So, it was better for the participants to move on to the other problems as soon as they can, and they did.

Rajat grabbed his second in CHEFARRB in the 8th minute of the contest, while uwi took further 10 minutes to crack the same. By this time, the competition was nicely balanced. But then, uwi decided to revisit CHEFINS, however, nothing changed this time as well, TLE is what he got this time as well. By this time, Rajat had already cracked CHEFNUMK and got a significant lead over uwi. With 3 problems to his name inside the first 45 minutes of the contest, Rajat seemed comfortably cruising to the top. However, CHEFINS was not easy for him either. It took him more than half an hour to get it right. That’s pretty much the time he needed to crack the first three problems of the contest. But once he got that, with no penalty to his name, it pretty much sealed the deal for him. And a top slot for him into the contest was almost assured, however, there still was a problem unsolved, yet no one had attempted it and with uwi struggling CHEFINS it was highly unlikely that he was going to attempt that one. So we sat back and waited for the final bell to ring and find out whether 4 out of 4 ACs can get Rajat a Cook-Off win, and turns out they could.

With that Rajat had sent a strong signal to all his counterparts competing with him at the ACM ICPC regionals. And he didn’t disappoint at the regionals either. If you were following our ACM ICPC live coverage, you would know what we are talking about. For now, let us quickly take you to the rank table for December Cook-Off 2016 and see who stood where.

We start with the Global top 10:

Now, the Indian top 10:

- rajat1603
- vagesh_verma
- vsp4
- tanmay273
- aayushkapadia
- fauzdar65
- additya1998
- pheonix123
- amitgoel248
- vedaytas17

Let’s give it up for all our winners and for all you wonderful people on your performances in the contest.

The fifth problem from COOK77 i.e. CHEFTRI4 remained solved during the contest, which makes the editorials of the contest even more important. So, if you are still wondering around CHEFTRI4, check out the editorials for the contest below and get over it.

And that completes the tale of the December Cook-Off 2016. We hope you enjoyed the contest and its tale. If you have any interesting insight, story, or any event that made COOK77 memorable for you, kindly do share it with us.

With that, there remains only 1 final story from our contests in the year 2016, that is the December LunchTime 2016 and we will publish that too very soon. Till then, keep watching this space, keep sharing the stories you like and do let us know what you think of our contests and their stories.

That will be all for now from everyone here at CodeChef.

Till next time, adios.

- Rudreshwar

Team CodeChef

December is a busy month for every programmer around the world, for it is the ACM ICPC season. The regionals take place across the globe and the crème de la crème of the programming world battle it out to secure a coveted place at the ACM ICPC World Finals. It was no different this year as well. As we stepped into December, some of the regionals across the world had just concluded and we were just weeks away from the ACM ICPC Indian regionals.

With everyone looking for means to put the finishing touches to their ACM ICPC preparations, our December Challenge 2016, was their final big chance to test the waters, before they move towards the final frontier. While, for everyone else, it was the final chance to spend some time with their beloved computers and keyboards, before they step into the festive season and treat themselves with the sugary goodness that every festive season brings with it. It was an interesting setup. So, let’s see how the December Challenge 2016 fared.

The start to the contest was akin to pretty much like any other long contest we have had all through the year. It took saurabhrathi12 only 6 minutes to get the first AC of the contest on ANKTRAIN; it was followed by a couple of more ACs on the same problem. The second problem that saw an AC was SEAINCR, soon after ANKTRAIN. It remained like this for quite some time. The number of participation kept going up in the first half of the contest, while it stagnated in the latter half. And that is when the positions on the rank tables get decided. And it was an interesting looking rank table this time around. And we will tell you why.

When in the final days of the contest, the rank tables are generally occupied by the favorites. It was no different this time, the likes of sumeet_varma, rajat1603, mugurelionut, notimesea and many others still shining brightly on the rank tables. However, what was striking this time was the number of consistent performers, occupying the top slots. It’s one of those moments when you see your hard-work finally paying off. And the feeling certainly cannot be described in words. To see the likes of gvaibhav21, jtnydv25, ccz181078, come through the ranks and stamp their authority on the top slots of the rank table.

It was not easy to reach there and it certainly was not going to easy to stay there, especially when the seasoned campaigners have you in their sight. Every submission made now will decide their fate and position into the contest. But it seems that after years of wondering through the rank tables, they had mastered the art of defending their position on the rank table. So, as the fabulists would have it, it was a contest when persistence and grit won over experience. And now, we take a quick tour of the rank tables to meet all the winners from December Challenge 2016.

We start with the girls *Big round of applause*:

Now, on to the ROW top 10:

Now, the Indian top 20:

- gvaibhav21
- jtnydv25
- rajat1603
- architk
- gravity0905
- sumeet_varma
- wodahs_cc
- mustafa1sms2_3
- kaspers
- deva2802
- apoorv_kulsh
- d7hsrah7
- yash_mittal
- archit_jain08
- samarth_1996
- n1t1n_153012
- drexdelta
- abhirup17
- miteshag
- aakashrockstar

Now, let us move towards the schools to meet the young geniuses:

We start with the ROW top 5 from schools:

Now, the Indian top 5 from schools:

Now, for the special achievers, the top three scorers of the challenge problem, outside the winners:

First, the ROW top 3:

And finally, the Indian top 3:

Kudos to everyone on their brilliant performance in the contest!

With that, there are two more stories to tell from the month of December, which we will be updating pretty soon. We hope you had a wonderful 2016 and will have an even better 2017. And on that note, we would like to draw curtains on this delayed tale of December Challenge 2016. We hope you enjoyed the tale as much as you enjoyed the contest. If you have any feedback or words to say about the contest, the post, or CodeChef in general, you can always write to us at: feedback@codechef.com

Till next time, take care.

- Rudreshwar

Team CodeChef

Even though we are here in Mumbai a rather tropical part of India with very little to minimum winters, somehow, this final part of the year makes us lazy. As a result we fall behind on putting up some important post contest blogs, not many, but few. And the year 2016 has been no exception. So, we would like to apologize for the missed blog posts and will try to publish all the missing ones, before taking on the posts for year 2017.

These posts will be a tad concise, so if you think we have missed any important event or something worth mentioning, do let us know in the comments section.

We start with the final contest of November, the November LunchTime 2016. With an all Indian problem setting and testing panel featuring Praveen Dhinwa and Animesh Fatehpuria, the November LunchTime 2016 promised some beautiful and delectable problems. And the participants comprehended that, as soon as the contest started.

We knew that the students are coming out of a big festive seasons and are staring at another big one too. What we didn’t know was that, the festive season had hardly made them any lethargic. The contest started at 7:30 pm IST and we got our first AC at 7:33 pm IST on CHEFSTUD. And it was soon followed by a flurry of AC on CHEFSTUD and few more on CHEFSSET. The plethora of ACs against the two aforementioned problems made the difficulty level of the problems rather apparent. So, the flow of submissions was almost in their direction only, with every now and then, someone trying their hand on the other two.

And while CHEFSTUD & CHEFSSET brought the initial smiles for the participants, it were TOMJERGA and BALANPOL, which seemed like the deciding factor for who stands where on the rank table. So, let’s head over the rank list and meet the top 20 schools students from our November LunchTime 2016.

We start with the ROW top 10:

- ycdfwzy of Middle School Attached to Nanchang University
- kmcode of Omori 7th Junior High School
- zscoder of Chung Ling High School
- inovak of Osh Sema High School
- zedthirtyeight of Gymnasium 51
- mysteryname of Mahidol Wittayanusorn School
- antimirage of H. Karasaev Kyrgyz-Turkish lyceum, Karakol, Kyrgyz Republic
- bolot_b of Bishkek Kyrgyz – Turkish High School
- sslotin of
*School Number 179* - bakirovmirbek of Osh Sema High School

Now, the Indian top 10:

- newrahul of Delhi Public School, Dwarka
- dev127 of Delhi Public School, Dwarka
- sidhant007 of Delhi Public School, Dwarka
- nibnalin of Delhi Public School, Faridabad
- dev2001 of Veda Vyasa DAV Public School
- vivek1_007 of Delhi Public School, Dwarka
- anupam_datta of DAV Model School, Durgapur
- rashish2202 of Veda Vyasa D.A.V Public School
- ritik_27 of Bal Mandir Public School
- rohitkv77 of Army Public School, Dighi Pune

A big round of applause for everyone on the rank table and for everyone who participated in the contest! You all did well.

For those looking to have a better look at the solutions of the problems from our November LunchTime 2016, we have the editorials waiting for you. So, head over to the link below and let the nom begin.

And with that, it’s time to put the pen down on this curtailed tail of November LunchTime and quickly move towards the pending stories of December. So, that will be all from us folks. We will come back soon, with three more exciting stories from our December contests.

Till then, keep coding and if you have any queries or feedback, shoot them our way at: feedback@codechef.com.

- Rudreshwar

Team CodeChef

You all must be well aware about the Goodies site and our own, Laddus, that we launched when CodeChef turned seven. The objective behind our initiative towards this sweet project was to motivate our users to perform better and that too consistently so that they earn and accumulate more laddus. You can redeem these Laddus for the goodies that we have listed on our site.

Motivation persists only when a person finds her goal achievable. We have been continuously analysing our user activity on the Goodies site of their behaviour and what goodies they redeemed with their Laddus. Apart from our most popular goodies, the funky bottle, the cool bag, the classic CodeChef t-shirt and the elegant pen, we found very few users redeeming the Hard Disk Drive which made us take the decision of reducing its price.

Here is the good news for the readers who read this post till this point. The new price of Hard Disk Drive is 3500 Laddus. Just grab your laptop and start coding, collect more Laddus and get the HDD. We just made it easier for you, 30% easier. We know we are being too generous. You can thank us by performing better in the contests and we will be happier to see more users redeem the hard disk drive.

So what are you all waiting for? The Long Challenge contest is coming. Sharpen your skills, prepare your templates and get ready for the battle. See you on the leaderboard.

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

- 2018 Recap: A look back on CodeChef’s adventures over the past year
- SnackDown19 Live Contest Updates
- “It was a nice experience teaching the blooming competitive coders in INOI workshop”
- ACM ICPC Amritapuri Regionals 2018-19 – Live Updates
- ACM ICPC Pune + Gwalior Regionals 2018 – Live Updates

- About (14)
- ACM ICPC (23)
- Announcement (298)
- API (2)
- Campus Chapters (7)
- CCDSAP (2)
- Certification (4)
- College Contests (9)
- Contests (273)
- Events (54)
- FAQ (1)
- Features (51)
- Interviews (24)
- Languages (1)
- Meetup (4)
- Open Source (1)
- Practice Problems (8)
- Prizes (20)
- Problems (9)
- ProblemSetting (1)
- Programmer of the Month (34)
- Schools (12)
- SnackDown (2)
- Tech Talks (23)
- Tutorials (33)
- Uncategorized (1)
- Volunteers (4)
- Winners (121)

- Rehabilitation Centre Punjab on ACM ICPC Chennai Onsite Contest 2016 – Live Updates
- champ 2814 on Important announcement concerning rating changes following plagiarism
- kuldeep singh on Tutorial For Small Factorials
- kuldeep singh on Tutorial For Small Factorials
- kuldeep singh on Tutorial For Small Factorials

- March 2019
- February 2019
- January 2019
- December 2018
- November 2018
- October 2018
- September 2018
- August 2018
- July 2018
- June 2018
- April 2018
- March 2018
- February 2018
- January 2018
- December 2017
- November 2017
- September 2017
- August 2017
- July 2017
- June 2017
- March 2017
- February 2017
- 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.