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

**Lecture 1: ****Sqrt decomposition, **By Sergey Kulik

Slides

**Lecture 2: ****Dynamic connectivity problems and their applications, **By Sergey Kulik

**Lecture 3: **Chinese Remainder Theorem, By Praveen Dhinwa

**Lecture 4: **Introduction of Algebra, By Kevin Charles Atienza

Slides can be found here

**Lecture 5: **Mobius inversion and related sums, By Kevin Charles Atienza

Slides can be found here

**Lecture 1:** Aho Corasick algorithm and its applications, By Sergey Kulik

**Lecture 2:** Biconnectivity and Applications, By Tanuj Khattar

Material can be found at https://tanujkhattar.wordpress.com/2016/01/10/the-bridge-tree-of-a-graph/

*Problems to solve:*

* *1. http://codeforces.com/problemset/problem/555/E

2. https://www.hackerrank.com/contests/godaddy-hackathon/challenges/special-pairs

3. http://codeforces.com/problemset/problem/521/E

4. http://codeforces.com/problemset/problem/97/E

5. http://codeforces.com/problemset/problem/487/E

6. https://www.codechef.com/JUNE16/problems/SADPAIRS

**Lecture 3:** Combinatorics, By Kevin Charles Atienza

Slides can be found here

**Lecture 4: **Geometry, By Kevin Charles Atienza

Slides can be found here

**Lecture 5: **Finding maximum length anti chains in partially ordered sets, By Arjun Arul

Posets:

https://en.wikipedia.org/wiki/Mirsky%27s_theorem#CITEREFMirsky1971

https://en.wikipedia.org/wiki/Dilworth%27s_theorem

http://codeforces.com/blog/entry/3781

Problems:

http://www.spoj.com/problems/MDOLLS/

https://www.codechef.com/problems/RECRECOV

http://poj.org/problem?id=1065

https://www.facebook.com/hackercup/problem/847639175277938/

(Hint: http://codeforces.com/blog/entry/16124?#comment-210482)

https://code.google.com/codejam/contest/dashboard?c=204113#s=p2

https://www.codechef.com/LTIME32/problems/TABLECOV

https://www.codechef.com/problems/POSTERS/

https://www.hackerrank.com/challenges/problem-solving

https://community.topcoder.com/stat?c=problem_statement&pm=12080&rd=15179

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2283

(ZOJ is down now. So see: http://www.it610.com/article/1363190.htm for the statement)

http://codeforces.com/contest/590/problem/E

The road to December Cook-Off 2015 came through the galore of examinations and preparations. Programmers across the globe were busy honing their skills for the busy ACM ICPC season, while trying to keep up with their exams and trying hard to ensure good pointers. To add more chills to that entire setup, we had the winters in its full glory. All in all, it was a thrilling set up for an exciting two and half hour programming contest and we couldn’t have asked for more. But we got more.

The December Cook-Off 2015 was exactly the night before the ACM ICPC 2015 Amritapuri Regionals. While the teams attending the regionals were trying to stay calm before the big contest, there were participants from all over the globe raring to get their hands on the problems of Misha Chorniy. Amid that mixed batch of participants began our COOK65, the last one for the year 2015.

And what a start it was. Just like a big flashy Sunday party, the December Cook-Off started to 98 ACs out of the first 100 submissions in the contest. All this and we were 10 minutes into the contest. What’s even more exciting was the fact that all of those 100 submissions, and the next 100 to follow came on Chef and Subarrays. Perhaps, every who joined the contest that night made their first submission to Chef and Subarrays. Just to have a nice and smooth start to it. It remained the same way until lebron submitted to Chef and Queries. It was also an AC. So, if we have to sum up the first half an hour of the contest it will be like: 2 problems, lots of ACs, very few WAs, and even fewer TLEs and CEs.

As we moved into the contest, the happy start made way for the fury and rage brought onto the participants by Chef and Vectors, Chef and Tree, and Chef and LCS. If you got your hopes high on your performance into the contest after the green ticks you got on the first and second problem, it must not have felt nice trying your hands on those problems. So, do let us know how it was in the comments section below. The immaculate job by our tester Jingbo Shang ensured the right mix of difficulty levels in the problem set. What did you thought of it?

The flow of the submissions in the second half of the contest did slow down, but the intensity of the competition prevailed till the very last moment. notimesea, who made the first submission into the contest, defended his spot atop the rank tables bravely from the challengers in lebron, alex_2008, Ra16bit, and the mighty ACRush. They all had 4 problems in their account and while ACRush cracked all the problems in the first submission, CHEFVEC took two to crack. And with that, he secured the top slot in the contest. And that was our final Cook-Off for the year 2015. We hope you all enjoyed the contest as much as we did putting it up for you.

Now, let us take you through the rank table to introduce you to the winners of COOK65.

We start with the ROW top 10:

The Indian top 5:

Now, the final stats for the contest:

- Total Users: 1006
- Total Submissions: 2384
- Number of distinct users with correct submissions: 944
- Total users from India: 581
- Total users not from India: 425

Congratulations to you all on your performance.

Now, let us serve you the editorials for the December Cook-Off 2015, penned by our young editorialist Pushkar Mishra. We are sure you would have tasted them by now, but if you have not, here they are for you once again.

That will be all from us all here. We hope you had a wonderful 2015 and are ready for an exciting 2016 in front of us.

Till next time, adios.

See you at the contests.

Regards,

Rudreshwar

Team CodeChef

Dear CodeCheffers,

As the time nears the declaration of the selected list of teams for the onsite, we think we must own up the mistake and issue an apology. We understand that there were some problems with the online round for ACM ICPC 2013 IIT KGP regionals. For those who missed it:

- Despite a few days of frantic optimising and working hard, we still experienced some issues during the last few minutes of the contest. This was due to heavy load on our database server which was unexpected given that we had fixed all such issues long back and had not experienced anything like this in any recent contest. There were multiple complaints of people not being able to access the site towards the end of the contest.
- The problem statement of the problem EDITLIST was slightly ambiguous and to make matters worse, at 49th minute into the contest, we answered to a query in a haste making a comment that changed the problem specification and made the problem much easier to solve, but led to getting WA for many who tried to solve it in this way. Quite a few of you were not affected by it and were able to still get the solution accepted. Well done. For others, this led to a lot of frustration.

For the first issue, we investigated and found out that it was caused due to an un-optimised query that fetches you all the submissions of a particular problem in the practice section! We are in the process of fixing it, but we thought we should at least tell you what the reason is while the fix happens. To make up for it, we had extended the contest by another 10 minutes. We also eliminated all penalties for those who were affected by the slowness and ended up submitting the same solution multiple times.

The second issue impacted users much more. And we realised that we had goofed up, only after the contest. At this stage, we sat down and evaluated all the options to salvage the situation. We knew that we could not be fair to everyone from that point. No matter what we did from there, there would be one section who would be affected by this mistake of ours. Considering every possible scenario (including a re-contest), here’s what we decided to do:

Change the test data such that the solutions which solved the problem without sorting the output list also passes. This essentially also meant that the problem no longer required a DP solution to pass and became easier than what it was intended to be. We rejudged all the solutions which had not passed during the contest for this problem with the new test data, leaving aside those that had passed. This resulted in more teams now solving the problem.

Some of you are bound to feel (especially those who wasted a lot of time on this problem) that this isn’t fair. We know it, but there is not much that we can do about it. We screwed up, and we’re really sorry. Here are the other options and an explanation of why we took this approach:

- Do nothing – Everyone had access to the same problem statement and the same comment, right or wrong. Many teams were able to solve it based on that. So why not do nothing about it and ignore the mistake. We almost did this, but then we felt it was just not right. There were also teams who read the comment made by us and kept trying to solve this seemingly new version of the problem without any success. And we had guided them towards this. So it was important for us to correct our mistake and acknowledge their effort at the very least.
- A re-contest – Those affected have called for this, and though this may seem to be a fair solution, it is not and there are many factors that makes it almost impossible for us to do so. The execution of each contest (including this one) involves just about as many man hours of work on the problem setter’s / testers end as the number of man hours extended by the participants when the contest runs. And then finding the right schedule for all the people to participate is also not trivial. A re-contest would also waste the time of so many more people. And most importantly, it will be unfair to those teams who have already done very well in this contest and deserve to be there onsite.
- Re-judge EDITLIST, altering the test data to accept both solutions – This is what we did. As mentioned earlier, it was not fair to everyone. It was specially unfair on those who spent more time in solving the DP version of the problem and not the new easier version. And also to those who got stuck at solving this one problem. But it did allow us to be fair to those who got misguided by our comment and acknowledge their effort.

While we acknowledge that we have goofed up and we regret it beyond what we can put across, we also think, that not being stuck on a problem, you are unable to solve, is among the many things that can propel your team to be a good ICPC team. A team of three wasting all their time on a single problem can cause a lot of frustration, but then that should not warrant wasting the time of so many other teams that have done well and also learnt to deal with such situations and got more efficient.

Some people will undoubtably feel like we should’ve taken one of the other approaches listed above. We’re sorry, we cannot do that. Don’t hate us. We know we have goofed up. And we did try our best to be as fair as we possibly can in the given circumstances. We wanted a good fair contest as much as you all did. We did receive some positive feedback on the problems being good as well. We have also published the editorials for the problems. We did try to do as much as we can.

For those who will not be able to make it to the onsites due to this mistake of ours, we sincerely apologise. We know, nothing can make up for it. But there is only so much we can do. Please do not get demotivated and **do not** give up. Please practice hard for next year. We will be around to help you all in your preparations. We assure you, that we will be extra careful next time around. We are sorry.

Anup

This is a truly interesting question, and I thought it would be a great way to have this opened to the CodeChef community so that we can get their views on various styles, as well as what works and what doesn’t. I’d also like to particularly invite other Editorialists (Anton, Shilp etc.) to describe their process and their reasoning etc.

All of these have their own unique style of Editorials.

- TopCoder generally has a slightly personal touch, describing some tidbits about the match, followed by Problem by Problem solutions. Further, there is source code for most problems.
- Codeforces has a similar style, again focussing on describing the solution.
- CodeChef however, caters to the
*Indian*community. In other words, we cater to*quantity*over quality, and would always like to go the extra mile in describing a solution. The Editorials here are continuously evolving, all in the goals of getting as many Indians as possible more equipped to solve harder problems contest by contest. Hence, the CodeChef Editorialist’s job is not merely to state do-this-do-that because this-implies-this-implies-that, but also to make the entire thought process simple, natural, complete and convincing.

Now, I’ll put in some of my views on what makes a good Editorial, and how I’ve learnt over the past few months.

This, I believe, is something worth striving for. Personally, I tend to often take up a very conversational tone in my Editorials (imagining that I am explaining everything from scratch). This tends to make my Editorials unnecessarily verbose. I fear that although the tone is light, I would lose the engagement of an experienced coder. And if its too verbose, I would even lose an intermediate one, while a beginner may wonder “why is this being mentioned”. Having said that, if it is made too *technical*, then anyone who doesn’t know what’s going on would stop reading. There needs to be a balance between what needs to be said, what is said, and what isn’t said – and striking this balance may not be easy.

In particular, I tend to provide justification after each assertion, while I think it is often better to leave the reader to try out justifying some of the things as he reads them, and if he fails, to find justification later on in the Editorial.

*Try not to beat about the bush!*

This is not contradictory to what I said earlier about it being non-verbose. When I say thorough, I mean that it should give a complete description of anything related to the problem. Things like “related problems”, “tutorials” on other sites, “mathematical concepts” from other sources – anything related to the problem and its solution should ideally be packaged under the one same Editorial. Imagine reading the solution to a problem on Heavy-light Decomposition. The next thing you need, is somewhere to practice. Imagine having an entire network of **Related Problems** from which you can shift and browse and practice one by one!!

However, the flipside is that the Editorialist needs to be aware of various resources, and should be able to call them up from memory as required. Again, calling up past problems from memory, is another personal failing (heck, in TC matches, I have often forgotten the 250 pointer by the time I get done with the 500!!).

*Add as much information as possible under the one encapsulated Editorial.*

Here, “Top-down” style is where the Solution starts with the problem, and then step by step talks about what is required and how each subproblem gets fixed. The “Bottom-up” style on the other hand, first describes the solutions to the subproblems and then puts them together to show you the solution to the whole problem.

Almost always, I’d say the Top-down style is better. It keeps the reader motivated instead of wondering (“why are we doing this”). It also tends to make the solution *look simple*. By saying “Okay, so X is the problem – that means we need Y – so how do we get it, lets say if we could have Y1, then we could get Y by Z. That just leaves getting Y1 – so lets try to do PQR…”, you are at each step making every requirement and consequent solution seem natural.

Compare that with saying, “First, let us consider Y1. To solve Y1, lets do PQR… Now, finally, you should see that you can get Y from Y1 using Z, and that means you have solved X.” Here, the reader is left wondering “whats up with Y1? Ouch, here comes PQR”.

As a concrete example, consider the following “Tutorial” on Heavy-Light Decomposition:

**Problem:** You have a tree, where each node has a weight. You can either change the weight of a node, or are asked to query the sum of weights on nodes along a path in the tree. You need O(logN^2) time per operation.

## Bottom-up Style

First, find the size of the subtree rooted at each node. Also, we will need to answer LCA queries, so fill in information for that too.

Then, for each node, let us call the edge to the largest (by number of nodes in subtree) child a “heavy” edge. Ties are broken arbitrarily. All other edges are called “light” edges. The set of heavy edges now forms a set of disjoint paths in the tree.

We count the number of different paths from a node to the root. Since you shift from one path to another only through light edges, and since each shift atleast doubles the size of the subtree, you would have shifted only at most log(N) times.

Now, consider each path as a segment tree, so when you update the weight of a node, it takes O(logN) time. Finally, for finding the sum of weights along the path between nodes u and v, first find the LCA w, and then find the sum of weights along the path from u to w, and v to w. Since from any node there are atmost log(N) different paths, overall complexity is O(logN^2).## Top-down style

Let us suppose our tree was a path. Then we could easily solve the problem using a segment tree.

Now, if instead our tree were divided into a set of disjoint paths, and consider each path as a segment, then an update will just take O(log(path_length)) time. And we know path_length <= N.

To answer a query (u, v), let us first find the LCA w, and then divide the path from u to v into u to w and w to v. Then, we just go across each of our segments and take the sum along the way.

Thus, if there are K segments along the path from u to w or v to w, we would like that K is small: since our query will take O(K logN) time.

Finally, if we were to make our segments in such a way that the largest subtree gets to continue the segment, then from any node, along the path to the root, we would shift segments only when doubling our subtree size. Hence, under this scheme, K is always O(logN).

This was to illustrate (hopefully) how the Top-down approach maintains motivation by assuming the least and filling in gaps only as they appear.

Now, I’ve noticed, atleast while learning, that when things *look simple*, they’re *taken to be simple*. And when things are taken to be simple, a lot of the intricacies are often taken for granted. In which case, the next time something like this comes up, one might not be able to reconstruct the whole picture by oneself. Thus, in cases where a technique can be applied widely, it might be better to describe it in bottom-up fashion. (One can illustrate use of Binary Indexed Tree by taking the example of dynamic prefix sums being required – or one can start with what Binary Indexed Trees are, and then show how they solve a dynamic prefix sum problem; the latter being favoured although it is bottom-up in this case).

*This is just my personal opinions, and if you feel differently, do say so and explain why.*

Its always nice to see the entire solution at one stretch. It gives you an overview of what to do, where you failed, how to get the whole thing, all in one picture. Thats what Quick Explanation is for. As far as possible, I’d prefer to have Quick Explanation + Detailed Explanation used. The Quick Explanation should indeed cover all aspects of the solution, and shouldn’t just be about dropping hints (that’s in some sense what “pre-requisites” is for).

In some cases however, just Explanation is good enough. These would be when either the problem is so simple that the Quick Explanation is the entire explanation, or when the problem is so hard, that the solution cannot be summarized without leaving large loopholes.

*Whenever possible, Editorials should have a summarized Quick Explanation.*

This idea I had picked up from a comment on one of my Editorials. It said, (paraphrased), “Often, it is easier to understand what is going on from the pseudocode rather from the explanation.” In some sense, it is saying that you can say “do this – do that” as much as you like, but it won’t hit home as well as the same thing in pseudocode. The way Mathematics has its own set of symbols: ∀. ∃, ∑ etc. which help clearly and concisely state things, Algorithms uses the language of *Pseudocode* to convey its ideas succinctly.

*Key points of the solution should be written in pseudocode.*

During the (Indian) IOI Training Camp last year (2012), we had a set of “coding commentaries” which concentrated not so much on the solution itself, as much as on the various bugs that people had made, and on all the points where the code could have been made neater and easier to debug. It would be great if we could have such sections in the CodeChef Editorials as well (they would largely help reduce the number of “what is wrong with my code” questions being posted after all).

The logistics of running this in a IOITC vs on codechef are very different: in one, you have twenty students coding in a two hour window, on the other you have hundreds-thousands of coders submitting solutions. As such, there is scope for such sections during short contests, wherein the “cooks” browse through a whole load of random submissions, spot bugs, find commonalities and add them to the Editorial. Tips on coding style are relatively harder due to the large and varied range of submissions (20 students writing varied shades of clean/dirty code is different from thousands writing varied shades of “code”: harder to classify dirt from cleanliness). In Long Contests, unless the setting panel made testcases to beat various bugs or suboptimal solutions, it is hard to browse through even “random” codes of people over 10 days and glean knowledge of bugs worth mentioning. Also, the fact that the short contests are far more high energy on the setting side during the course of the contest makes this section relatively more viable in such cases.

*As important as it is to describe what works, it is also important to describe what doesn’t!*

Editorials are the *Editorialist’s* labour of love.

Generally, when the Editorialist sees the problem, he first tries to find the solution himself. Alternately, he follows discussions between Setter and Tester and makes sense of the solution from there. Or, he looks at the codes of the Setter/Tester, and justifies what is being done from that point. And if all these aren’t enough (which is the case for the Hard problems a lot of the time), he takes the direct help of the Setter/Tester.

When he arrives at the solution himself, it is then often presented well.

However, in a lot of other times, what can happen (and *what should be avoided*) is that the solution is presented from the point of view of the setter. One of the comments that I got on one of my Editorials, was “This is just a description of the Setter’s code, and not a solution itself”. The point was very valid, and the fact was that since I hadn’t arrived at the solution myself, I did not outline the thought process of someone who is attacking the problem from scratch. What I had done was present justification for why what the setter had done works.

The Editorialist, by being privy to the solutions, should put in his own effort in making them palatable. His job boils down to answering “Given that this is the solution, and that I know it, how do I make someone who doesn’t know it see it?”

The **use of diagrams** esp. for Geometry problems, although it takes a little more effort, can speak a thousand words, and would consequently form a bond between the Editorial and the Editorialist (I always enjoy viewing my TRIQUERY Editorial, with the use of its colour-coded lines etc. and I’m sure Utkarsh would do the same for his TAACUTE Editorial).

*If the Setter cooks the dishes, and the Tester tastes them, then it is the Editorialist who serves the dessert!*

If you have any further suggestions on how to make Editorials better, do post them as answers in the discussion forums.

I hope this post opens discussions on what to do, and how to do all-things-editorials.

[If you merely agree/disagree with any point, post those as comments rather than separate answers].

I hope that this would grow into a “Guidelines/FAQ for Editorialists” or something in time.

- Here’s why there was a delay in updating the March contests’ ratings
- SnackDown 2017 is here and this time it is truly Open!
- A Star Studded Rating System
- New Goodies, New Categories & New Prizes Every Contest
- CodeChef’s 8, mate!

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

- abhinav vinci on The new Karma system
- Ashu on A Star Studded Rating System
- Hemant Mangla on New Goodies, New Categories & New Prizes Every Contest
- Protap Ghose on New Goodies, New Categories & New Prizes Every Contest
- Shivam Fialok on New Goodies, New Categories & New Prizes Every Contest

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