*At CodeChef, we constantly stay in touch with CCDSAP holders to make the experience better for you and to fine-tune the certification. We spoke to Amit Upadhyay, a CCDSAP Foundation Level Certificate holder who is placed at Cleartax as a Software Engineer. We asked him about his CCDSAP experience and his tips for aspiring candidates. so read on!*

**A little background on Amit and his introduction to coding.**

Amit completed his engineering from the Army Institute of Technology in Pune in 2018. Amit has always been involved with the world of code. He started coding on the CodeChef platform in his first year, and eventually moved on to making mobile apps in his second year. During this he found that he had a wealth of knowledge (and libraries!) to share with the world, so he began blogging as well. Amit credits the environment in his college for boosting his interest in coding competitively. In his first year, his seniors informed him about the CodeChef platform and he quite enjoyed the thrill of competitive programming.

**How did Amit hear about CCDSAP and why did he decide to appear for it?**

Amit heard about CCDSAP when Directi landed up in his campus for a recruitment drive. Clearing the CCDSAP also allows one to interview with Directi and Amit decided to make use of this opportunity. Even though his concepts were clear, Amit decided to consolidate his learning before appearing by taking the mock test on the CodeChef website. He recommends taking them to get an idea about the exam format and the correct pacing needed to finish the exam in time.

**How should one prepare for CCDSAP?**

Amit believes that a strong understanding of the fundamentals of DSA is what is tested at CCDSAP. So how does one get there? He recommends using a good book of DSA theory matched with an equal amount of solving DSA problems, like the ones available on the CodeChef website. He advises that candidates should study one data structure at a time and then solve 10-20 problems based on it before moving to the next. There are also many videos available online to help with the conceptual part. Finally, he recommends the prepare section on the CCDSAP site as an invaluable resource, complete with mock tests.

**So where does DSA help one in the industry?**

While most products depend on existing frameworks which can be understood by reading the manual, Amit emphasizes that DSA helps you learn how to think. It lets you understand the most optimal way of going about solving a problem, no matter what platform or framework is used. After all, problem-solving skills are universal and carry over to your next assignment as well.

Amit also spoke about how college doesn’t quite prepare you for industry challenges, and a lot of the learning happens on the job. At CodeChef we agree that this is certainly an issue and efforts can be made to bridge the gap between recruiters and candidates. CCDSAP does address this in a small way, and eventually we can bring a systemic change together.

*The next CCDSAP exam takes place on the 7th of October. Check this link for details and get in touch if you have any questions for us!*

The final regional of the ACM ICPC season of 2017 is here!

**9:00am IST**: The contest has begun.

**9:05am IST**: Team Instincts from Sri Sivasubramaniya Nadar College of Engineering, Chennai get the first AC of the contest!

First 10 submissions of the contest have all got AC. 6 of them are in C++, 3 in Python, 1 in Java.

**9:18am IST**: **ScopeHotaHai** from **IIT Bombay** lead the ranklist with 2 problems solved.

Plenty of teams are trying the 2nd easiest problem of the contest at the moment. 60+ teams have correctly solved it so far.

**9:45am IST**: Bristomaticians are now at Rank 1 with 3 problems solved. They have 1 time penalty at the moment.

**9:47am IST**: **aglet** (**IIT Bombay**) get AC on the 3rd problem. They are at Rank 1 with 0 penalties. This team is to watch out for in this contest. They were among the top 5 in the Kolkata regionals and were the only team to solve one of the hard problems.

**9:51am IST**: **TooWeakTooSlow** (**IIIT Hyderabad**) solve their 3rd problem which is the **4th distinct problem** solved in this contest.

**9:52am IST**: **Geany** (**LNM Institute of Information Technology**) are at rank 1 with 3 problems solved. Just **1 minute time penalty difference** between Geany and aglet.

**9:55am IST**: **TooWeakTooSlow** solve 4 problems! They are now at first place.

**10:15am IST**: **TooLazy** (**IIT Madras**) solve 4 problems! They are ahead of TooWeakTooSlow by one **29 seconds**!

**10:20am IST**: **FutureGlory** (**IIT Bombay**) solve 4 problems with 0 penalties and are now at Rank 1.

Their team name seems to be inspired by tourist’s team – PastGlory

**10:23am IST**: The Vindicators (IIT Kharagpur) solve a graph problem which their 4th AC and this contest’s 5th distinct solved problem. Also, they are rank 1 now! 3 minutes ahead of FutureGlory.

They haven’t solved a problem that the other top teams have solved yet, but maybe one member of the team would have figured out the logic for it by now. Let’s see if they get an AC on that problem in the next 10-15 minutes!

We also have 4 school teams participating today!

- int elligence = 0; (DPS Ruby Park)

- syntaxscrubs (DPS International School)

- int_elligence (Professor K K Anand’s Smart Minds Academy)

- Bashers (Professor K K Anand’s Smart Minds Academy)

**10:57am IST**: No team has solved 5 problems yet.

**11:03am IST**: Mochizuki (IIIT Bangalore) are the first team to solve 5 problems! They are now at Rank 1 with 0 penalties.

**11:14am IST**: Unity (IIT Delhi) solve 5 problems and move up to rank 2! They have 2 penalties. They have also solved the 6th distinct problem of the contest.

**11:25am IST**: **BhayankMaut** (**IIIT Delhi**) are now at Rank 2. with 5 problems solved.

**TooWeakTooSlow** (**IIIT Hyderabad**) solve their 5th problem as well and move up to Rank 3.

**11:31am IST**: **NotExperts** (**BITS Hyderabad**) solve their 5th problem and the 7th distinct problem of the contest.

**11:51am IST**: TooWeakTooSlow solve 6 problems and lead the ranklist now.

**12:05pm IST**: Tesla (IIITH) solve their 6th problem. They are at Rank 2 now!

**12:10pm IST**: Unity (IIT Delhi) solve their 6th problem and they are at Rank 2 now. Tesla moves to rank 3.

**12:31pm IST**: TheVindicators (IIT Kharagpur) move up to 2nd place. They are ~15mins behind TooWeakTooSlow on time penalty.

**12:55pm IST**: LastBreath (NSIT) solve the 8th distinct problem of the contest.

3 minutes left before the ranklist freezes.

**1:00pm IST**: Ranklist is now frozen.

Top 10 teams have all solved 6 problems.

Whom do you think will win at the ACM ICPC Amritapuri Regionals?

Vote now and cheer for your favorite team here: https://twitter.com/codechef/status/945928634279247872

Welcome back to the 4th regional of the season. This one is a multi-site regional, being organized by NITTTR Kolkata and hosted by JIS Group in Kolkata and University Institute of Engineering and Technology, CSJM University in Kanpur.

**Ranklist** – https://www.codechef.com/public/rankings/ACM17KOL

**10:10am IST**: The contest has begun.

No submissions so far in the first 5 minutes.

First AC of the contest by team **lastTry** from **NIT Durgapur**, 7 minutes into the contest.

Team **we_are_noobs** from **Indian School of Mines** solve a different problem – we now have 2 distinct problems solved.

The problem solved by lastTry is an easy implementation problem. So far, there has been 100% submission accuracy on that problem.

The one solved by we_are_noobs is an easy counting problem. The **submission accuracy** on this problem is **71%**.

**10:26am IST**: Team SSH from Jalpaiguri Government Engineering College solve the third distinct problem of the contest.

**imported_pandas** from **DTU**, Delhi lead the ranklist with 2 solved problems.

There are some rapid changes in the ranklist at this point as first 3 problems seem to be easy.

WeakMind from BITS Pilani, Supercalifragilistic from IIT Madras and Sudocrypt from BIT Mesra both gave fierce competition to LongTimeNoC in the Gwalior regional. They seem to be strong contenders for finishing in the top 3 today as well.

**10:46am IST**: WeakMind solve 4 problems and are at Rank 1.

**11:00am IST**: Supercalifragilistic solve a geometry problem, quite early on in the contest. This was their 4th solved problem.

**11:19am IST**: Supercalifragilistic get their 5th AC! WeakMind has some catching up to do.

Supercalifragilistic has 2 time penalties, by the way.

If WeakMind manage to get an AC within the next 30 minutes or so, they’ll be get ahead of Supercalifragilistic.

**11:31am IST**: **Know_no_algo, IIT Delhi** solve their 5th problem with a total time penalty of 3:07:23 and are at **rank 1**.

The top 3 teams have all solved the geometry problem. It is not a implementation-heavy problem.

**ButterRoti** from **IIT Patna** join the 5-solve-problems club. Currently at rank 4. They too, solve the geometry problem.

**TooLazyToPropogate** from **IIT BHU** solve 5 problems as well. Interesting team name

——

2 hours into the contest, 9 teams have solved 5 problems.

**12:36pm IST**: **TooLazyToPropogate** solve **6 problems**! They are at Rank 1.

**1:18pm IST**: **NeverSettle** from **IIT Mandi** solve the 7th distinct problem of the contest, but they have 5 total problems solved at the moment.

——

1 hour and 48 minutes left in the contest. **How many problems do you think the top team will solve?**

The accuracy on the geometry problem is quite low, approximately 38%.

TooLazyToPropogate (IIT BHU), Know_no_algo (IIT Delhi), Supercalifragilistic (IIT Madras) are the top 3 teams right now and the battle between them is quite intense.

WeakMind (BITS Pilani) got TLE on a graph problem 2 hours ago – if they can optimize this one, they have a chance to be Rank 1 with 6 problems solved.

At the moment, they must be debugging that problem on paper.

Supercalifragilistic have a WA on the problem that the IIT BHU team solved an hour ago.

**1:52pm IST**: **iota** (**NIT Warangal**) solve their 5th problem which is solved only by 1 other team.

**2:06pm IST**: Know_no_algo (IIT Delhi) solve their 6th problem and are at Rank 1!!

TooLazyToPropogate is 38 minutes behind them on time penalty.

**2:07pm IST**: TooLazyToPropogate submit a solution .. still waiting to get a response…

TLE for TooLazyToPropogate.

Each penalty counts. Several teams could have equal no. of problems solved at the end.

—-

Contest has ended.

This has by far been the most exciting last 1 hour in any regional I have witnessed in the past 2 years.

Teams didn’t give up until the very last second.

Keep guessing the top teams, until the final results are announced!

Welcome to the 3rd regional of the season being held amidst the cracking cold of Gwalior! This year, **7 school teams** will also be participating at the regional along with the college teams as part of the ICPC for Schools initiative. Good luck to all teams!

**9:45am IST**: The contest has begun.

**9:49am IST**: **Accio ACs** gets the first accepted submission of the contest. Guess what? That’s a *school team with a single member* – **Udit Sanghi**! Quite an awesome birthday present for him.

10:05am IST:

**10:13am IST**: 34 teams have solved at least 2 problems in the contest now.

**10:19am IST**: Supercalifragilistic from IITM lead the ranklist with 3 problems solved!

We now have **5 distinct problems** solved in the contest so far.

**10:42am IST**: **Supercalifragilistic** solve 4 problems! They are on an AC-spree!

**10:49am IST**: **WeakMind** from **BITS Pilani** get 2 ACs within 5 minutes and are up to Rank 2. They are 17 minutes behind IITM’s Supercalifragilistic on time penalty.

6 problems have at least one accepted solution in the contest so far. 3 problems remain.

**11:12am IST**: 7 distinct problems are now solved! **JustAnotherTeam** from DAIICT Gandhinagar get AC on ZUBWALLT.

**11:20am IST**: 8 distinct problems now have at least one accepted submission in the contest as LongTimeNoC from IIT Kanpur solve their 4th problem.

The **top 19 teams all have 4 accepted submissions** so far.

**11:27am IST**: **Sudocrypt** from **BIT Mesra** solve their 5th problem! They are at **Rank 1** now.

Almost immediately, **JustAnotherTeam** (**DAIICT**) solve their 5th problem as well – that takes them to the 2nd place.

**11:46am IST**: Supercalifragilistic solve their 5th problem and move to Rank 1 based on time penalty.

**11:52am IST**: Supercalifragilistic solve their 6th problem. They are on fire!

A very early AC on P6 has given Supercalifragilistic a huge advantage.

**12:44pm IST**: Top 7 teams have solved 6 problems each.

**1:45pm IST**: Ranklist has been frozen. The current top 3 teams are:

1. **Supercalifragilistic** – IIT Madras

2. **TDCs** – IIIT Hyderabad

3. **Majnu** – IIT Roorkee

————–

**Final Rankings**

1. LongTimeNoC – IIT Kanpur

2. Supercalifragilistic – IIT Madras

3. TDCs – IIIT Hyderabad

It’s a wonderful sunny day out here at IIT Kharagpur as we wait for the start of the 2nd ACM ICPC Indian regional of this season – ACM ICPC Kharagpur.

Which team are you rooting for today? Who do you think will win the trophy? Share your thoughts in the comments section!

**Live Ranklist**: https://www.codechef.com/public/rankings/ACM17KGP

**9:24am IST**: kgeccoders_11 from Kalyani Government Engineering College get the first accepted submission of the contest! They solve problem P6 – set by the one and only – Mr. Praveen Dhinwa.

**9:34am IST**: Tesla (IIIT Hyderabad) are the first to solve Problem P2. They lead the ranklist with 2 problems.

**9:47am IST**: 5 teams have solved P2. **TheVindicators** from IIT Kharagpur are at Rank 2 now followed by **LongTimeNoC** from IIT Kanpur at Rank 3.

Just 1 submission on the remaining 9 problems in the past 20 minutes. There are several candidates for the 3rd easiest problem in this contest.

**10:14am IST**: NDTM from IIT Guwahati solve the 3rd problem (P5). They lead the ranklist now. Some other teams have received WA on the same problem.

**10:20am IST**: ground floor from IIT Madras are the first to solve Problem P10. They are now at Rank 2.

**10:56am IST**: LongTimeNoC from IIT Kanpur are the first to solve Problem P9.

**10:58am IST**: NDTM solve NUMBGAME and lead the ranklist with 4 problems.

**11:11am IST**: **7 distinct problems** have been solved in the contest but the team at the top of the ranklist has solved **4 problems**!

**11:13am IST**: LongTimeNoC from IIT Kanpur lead the ranklist with **4 problems** solved and **1**** penalty**.

**11:20am IST**: 8 distinct problems solved now. Problem selection is crucial at this stage for all teams.

**11:23am IST**: Triangulation (IIT Roorkee) solve their 5th problem and move up to 1st place!

Team Triangulation – IIT Roorkee

**12:04pm IST**: Triangulation solve their 6th problem and extend their lead. They have 5 penalties, however.

LongTimeNoC have 1 penalty and if they solve another problem, they might take the lead from Triangulation.

**12:18pm IST**: Tesla (IIITH) lead now with 6 problems. Just **3 minutes** of gap between Tesla and Triangulation. A very, very close contest!

**12:30pm IST**: Tesla are on fire – 7 ACs for them now. Triangulation need to catch up.

**11:45pm IST**: Triangulation solve 7 problems and are on Rank 2 now – 15 minutes behind Tesla on penalty.

**1:20pm IST**: Ranklist has been frozen.

**2:20pm IST**: A very exciting contest comes to an end. Stay tuned for the final results!

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

Set in the colorful and glittery backdrop of Diwali, the October LunchTime 2016 had a rather joyous feel to it. The sweetness of the festive season had taken over and you could see everyone embrace it. Draped in our traditional attires, on the eve of Diwali, we sat down for one final contest of October, before the fireworks of Diwali. Joining us for the contest was our problem setting panel featuring Sergey Kulik, Misha Chorniy, Praveen Dhinwa, Pawel Kacprzak, Hu Zecong, and VNOI Team. Now, knowing that it was Diwali eve, we were keeping our expectations modest regarding the participation numbers for the contest, however, our excitement about the action into the contest was at par with any other contest we have had in the past. So, with that in mind and plenty of sweets on the table, we sat for the October LunchTime 2016. And here’s how it went.

The contest opened to a barrage of submissions on BOUQUET right from the very first minute of the contest, by lebron. Soon to follow him was lg5293, both of them accounted for 7 out of the first 10 submissions in the first 5 minutes of the contest. And it made up for the cracking start of the contest that we hoped for. The colorful symbols for different result codes were giving the colorful festive decoration that you see almost everywhere this time of the year. Now, we know not many with the red cross against their submission would have appreciated it as much as we did, but their determination to change it into green tick was something to cheer for.

After BOUQUET, the road to glory seemed a tad tougher for most of the participants and even though lebron had solved FFCOMB partially in the first 10 minute of the contest, it took him well over an hour to fully solve it. For kefaa though, it was a totally different story. It took him only a couple of minutes to completely solve FFCOMB. And with two fully solved problems to his name, kefaa looked set to take LTIME41 home. Closest to kefaa, was hloya_ygrt on the rank table, and even though he had a tough time battling with FFCOMB, he eventually got it right in his 13th attempt. Strange number to get something right, isn’t it? But, it didn’t seem to bother him as he quickly moved on to RESTPERM. And all the time he lost in battling with the previous problem was made up this time, as it took him only 3 minutes to crack it. kefaa, on the other hand got it right in the very first attempt and with that stamped his authority over the October LunchTime 2016. With less than half an hour to go, the picture of the top of the table became pretty clear. Unless there was any last minute surprise, we knew who is taking home the October LunchTime 2016.

And if you have not met them already, let us introduce you to the winners of our LTIME41:

We start with ROW top 10 school students:

- kefaa of Gymnasium #1, Brest
- hloya_ygrt of Club of Young Firefighters, Mozyr
- nurbakhyt of Almaty Kazakh – Turkish High School
- zscoder of Chung Ling High School
- sslotin of School Number 179
- kmcode of Omori 7th Junior High School
- iman_gh of Allameh Helli High Schools
- aktl of Almaty Kazakh – Turkish High School
- erzhan9800 of Issyk Kazakh – Turkish High School
- klinchuh of Gymnasium No 1, Novogrudok, Belarus

Now, the Indian top 10 school student:

- rajarshi_basu of Salt Lake School
- newrahul of Delhi Public School, Dwarka
- nibnalin of Delhi Public School, Faridabad
- mjguru of Amar Jyoti Saraswati International School
- geekpradd of Delhi Public School Guwahati
- rohitkv77 of Army Public School, Dighi Pune
- shreerockz15 of Ryan International School
- tanmay_sachan of Delhi Public School, Faridabad
- shivam312 of Delhi Public School, Rohini
- anupam_datta of DAV Model School, Durgapur

Congratulations everyone, we hope you enjoyed the contest and had a blast in it.

Here are the final stats for the contest:

- Total Users: 1685
- Total Submissions: 8176
- Number of distinct users with correct submissions: 1248
- Total users from India: 384
- Total users not from India: 1301

Now, for the editorials, let us take a walk to the discussion forum, where they are:

We are sure you would have enjoyed the editorials as much as the contest.

Now, it’s time to get away from October LunchTime 2016 and move towards the November contests. We are already approaching towards December, so, we will be quick with the November contest posts and will serve them soon. And while we do that, you let us know your thoughts, suggestions, or feedback on any aspect of CodeChef you would like to talk. You know where to find us.

That will be all for now.

See you at the contests.

- Rudreshwar

Team CodeChef

Here are all the video lectures from the Indian Programming Camp 2016.

- Biconnectivity By Tanuj Khattar
- Discrete Fourier Transforms By Kevin Charles Atienza
- Chinese Remainder Theorem by Praveen Dhinwa
- Posets Mirsky’s Theorem and Dilworth’s Theorem By Arjun Arul
- Path Problem By Akashdeep Nain
- Mini–cut By Anudeep Nekkanti
- Yate’s Dp, Zeta and Mobius Transforms By Arjun Arul
- Algebra By Kevin Charles Atienza
- Combinatorics By Kevin Charles Atienza
- Number Theory and Mobius Inversions By Kevin Charles Atienza
- Dynamic Connectivity Problems and Their Applications By Sergey Kulik
- Aho Corasick Algorithm and Applications By Sergey Kulik
- Geometry and Number Theory By Kevin Charles Atienza
- Merge Sort Tree and Persistence in Data Structures By Sergey Kulik
- Square Root Decompositions By Sergey Kulik

Enjoy the lectures and share them among your friends and families.

Rudreshwar

Team CodeChef

- Five Problems A Day, Kept The Worries At Bay For Cleartax Intern Avjot Singh
- Thrice the coding fun for school students this October
- How Amit Upadhyay got placed at Cleartax
- A brand new CodeChef API – Happy Independence Day from CodeChef.
- SnackDown is here!

- About (14)
- ACM ICPC (21)
- Announcement (294)
- API (1)
- Campus Chapters (7)
- CCDSAP (2)
- Certification (4)
- College Contests (9)
- Contests (271)
- Events (54)
- FAQ (1)
- Features (49)
- Interviews (23)
- Languages (1)
- Meetup (4)
- Open Source (1)
- Practice Problems (8)
- Prizes (20)
- Problems (7)
- ProblemSetting (1)
- Programmer of the Month (34)
- Schools (11)
- SnackDown (2)
- Tech Talks (23)
- Tutorials (30)
- Uncategorized (1)
- Volunteers (3)
- Winners (119)

- Rajbir Singh on ACM ICPC Chennai Onsite Contest 2016 – Live Updates
- hansika hans on Important announcement concerning rating changes following plagiarism
- Harsimran Singh on The Cheating Cases Saga
- Harsimran Singh on The Cheating Cases Saga
- sarovar ram on The Cheating Cases Saga

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