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

**x**such that

**x**is positive and

**ax – 1**is divisible by

**n**. You must print

**-1**if such an

**x**does not exist.

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

**b**first

_{i}‘s**i**characters are the same as the first

**i**characters of

**a**.

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

**i**there are atmost

**sqrt(L)**distinct lengths possible for the strings in the set, where

**L**is the sum of lengths of all the strings. So instead of considering suffixes of all lengths, you can simply only consider these particular lengths. Using this, you can perform the suffix equality check(s) using hashing or Aho-Corasick algorithm, which is the intended solution. The time complexity of such solution is

**O(L sqrt(L))**.

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

can you please put a link of leader board!

Here’s the link to the live ranklist: https://www.codechef.com/rankings/ACM16CHN

When the leaderboard goes live for us ?

You can check the ranklist here: https://www.codechef.com/rankings/ACM16CHN

From where can we see current leaderboard??

Here’s the live ranklist: https://www.codechef.com/rankings/ACM16CHN

for problem C

solution exists iff(a,n)=1 ?? Can You explain this.

i think that will be GCD(a,n)=1

(a, b) is notation for GCD.

(a, b) denotes GCD(a, b) 🙂 {It is the notation commonly used for it}

okkk Thanx.. 🙂

Isn’t it a bad idea to discuss solution when mirror contest is going on?

The mirror contest is for practice and if you are seeking help during practice it’s your loss.

Nice blog pro

mobius_treap made 7 submission.They are on top.

how do you know 😮

Nah, mobiles_treap came 2nd, CMI 3rd and faceless men 1st

are results out ??

Not sure a friend who participated told me about it

We can see the number of problems solved by team from the team profile page.. 😛

hi sir u r very inspire thnx bye

finally FacelessMen won

Can you please make mirror contest problems to practice section so that we can try our solution ?

There was a mirror contest running.

I know mirror contest was running. I had even participated in it. But after mirror contest is over,problems are not shifted to practice section. So i am just requesting codechef to please transfer question to practice section so that even after mirror contest is over I can make my submissions to remaning problems that remain unsolved

The problems are now available in the practice section. 😀

Thanks for Informing.

Can someone give an elaborated tutorial for problem A, mancunian and sonu generate strings?I have understood until sqrt(L) , what next?

De addiction Centre in Punjab

CBSE Patrachar Vidyalaya is a second option to clear all classes for those students who failed in 9th, 10th, 11th and 12th class. This is completely recognized by government. CBSE Patrachar Vidyalaya Shalimar Bagh is our center to study so you can come anytime whenever you want.

Patrachar

Dead Body Freezer Box on rent hire in Delhi for transporting dead body in all over India. Aggarwal Ambulance service provides best quality dead body freezer box by which dead body will be safe from bacteria or other infections. For more info, contact us or visit the website.

Dead Body Freezer Box

Rehabilitation centre in Punjab provides several types of therapies and facilities by which addicted people can get best aid. We have certified and professional medical staff who always care of patients. For more details, visit the website or call us.

Rehabilitation Centre in Punjab

De Addiction Centre in Punjab

Nasha Mukti Kendra in Punjab

Rehabilitation Centre in Jammu

De addiction centre in Jammu

Rehabilitation Centre in Ambala

De Addiction Centre in Ambala

Nasha Mukti Kendra in Ambala

Rehabilitation Centre in Patiala

De addiction centre in Patiala

Whenever you want to sell gold so that time getting cash for gold is not a troublesome process because we are here to give you the highest cash for gold in minimum time. If you want to know more about getting cash for gold by the gold buyer in Delhi, Noida, Gurgaon, Ghaziabad, Faridabad so call us on our number 9999821702, 9999333245 or visit our website: http://www.cashgolddelhi.com

Best Nasha Mukti Kendra and Nasha Mukti Kendra in Delhi

Are you looking for office furniture manufacturers in Delhi? So we are here, CPM systems is one of the best office furniture manufacturers dealing with several types of furniture like modular office, toilet cubicles and so on. Contact us for more information or designs. Our number +91-9292928080 or visit here: https://www.cpmsystems.in/