We’ve had a gruelling ICPC season so far and here we are today to give you live updates from the last Indian ICPC regional of the year being held at Amrita University.
This is the largest regional in Asia with over 270 teams participating across 2 sites – Coimbatore and Amritapuri.
We are expecting the contest to begin in 5 minutes.
Every regional this year has had nail-biting finishes. Today’s contest is expected to be even more intense with a lot of top teams competing against each other.
UniverseIsDeterministic (CMI) with Rajat De in their team and GeometryIsLove (IITM) with Teja Vardhan Reddy in their team who were rank 1 and rank 2 respectively at the Kgp regional, are participating in today’s contest.
Far_Behind (IITD) who solved 3 problems in the last 1 hour at the Kgp regional to end up at rank 3 will also be participating today.
tesla_protocol (IIIT Hyderabad) led the ranklist for a long, long time in the Gwalior regional but ended up at rank 3 after a magnificent performance by BhayanakMaut and ButterRoti. They will be targeting a podium finish today as well.
Hold right there Sparky!! (IIT Roorkee) won the Kolkata regional with a great performance in the last 1 hour. Will they take it easy today as they already have a potential WF slot in hand or fight it out?
Other teams like Microwave-O(1), proofByAC and MexFlow, to name a few, have done well in previous regionals but haven’t made it to the top 3-4 ranks. They will be itching to get that WF slot today.
Public Ranklist – https://www.codechef.com/public/rankings/ACM18AMR
9:45 am: Contest has begun
9:47 am: Kimi no Na wa (IIT Roorkee) score the first AC, 2 mins 19 seconds into the contest.
9:52 am: 7 minutes into the contest, 121 teams have solved 1 problem.
The title of the first problem is – “Is it a Cakewalk problem”. It definitely seems to be one
9:54 am: bits please solve CNTFAIL – first team to solve 2 problems, now at Rank 1.
9:57 am: tesla_protocol submit ARMYFGT and so do MexFlow at a difference of 4 seconds. Let’s see if their submissions are correct…
Yes they are! tesla_protocol move to rank 2 and MexFlow move to rank 3 respectively with a time difference of 23 seconds.
tesla_protocol has a time penalty gap of 40 seconds with bits please who are at Rank 1 currently.
10:00 am: UniverseIsDeterministic gets a WA on ARMYFGT.
Most teams are using Python to solve ARMYFGT.
10:07 am: tesla_protocol solve CNTFAIL and lead the ranklist with 3 problems solved.
10:28 am: 37 teams have solved 3 problems so far. tesla_protocol leads the pack, proofByAC is at Rank 2 and Laila (IIT Roorkee) is at Rank 3.
10:31 am: Team “ForgotToWarmup” just got WA on a problem called “SAUNA”.
“Apt team name”, says Balajiganapathi from the judging panel.
10:36 am: UniverseIsDeterministic are the first team to solve PALPATH. They are now at Rank 1 and we have 4 problems solved in total.
GeometryIsLove submit AVLBLT aaaaand it’s correct! They immediately replace UniverseIsDeterministic at the top of the leaderboard.
10:38 am: dilliMetro solve MARTING1, their 4th problem. They replace GeometryIsLove at Rank1.
The last 3 minutes have been quite exciting.
10:42 am: Laila (IITR) solve their 4th problem with 0 penalties and now lead the pack.
10:52 am: Hold right there Sparky!! from IITR solve their 4th problem and are the first to solve ALFRED, the 7th problem of the contest. They are now at Rank 3.
10:58 am: UniverseIsDeterministic solve ALFRED. They have now solved 5 problems and are back at Rank 1.
11:01 am: GeometryIsLove solve SAUNA. They have now solved 5 problems are at Rank 2. 8 distinct problems solved.
11:04 am: DeathNote from IITB solve ALIENINV. A very interesting, mathy problem. 9 distinct problems solved.
11:13 am: Math_maniac solve BALSUB. 10 distinct problems have been solved in the contest.
11:19 am: tesla_protocol solve MARTING1 and take away the lead from UniverseIsDeterministic.
11:21 am: Hold right there Sparky!! solve MARTING1 and are now at Rank 1.
This is turning out to be a very competitive contest. It seems to be quite non-trivial to predict who the winner will be.
11:44 am: GeometryIsLove get TLE on PALPATH.
12.54 pm: Laila has seized the lead by solving their 8th problem!
12.55 pm: bits please has also solved their 8th problem pushing UniverseIsDeterministic to third place. UniverseIsDeterministic has got 2 WAs on REFORMS, but can they make a comeback?
1.16 pm: Team UniverseIsDeterministic has solved SAUNA and jumped back to rank 1!
1.18 pm: The CMI team’s lead was short lived as bits please have now secured rank 1 with their 9th problem
1.38 pm: bits please has strengthened their lead by solving their 10th problem ALIENINV
1.45 pm: The rank list is now frozen, but you can still predict your winners here: https://goo.gl/forms/ng8a7xKBujzNAPtl1
Team bits please from IIT Kanpur secured the first rank while Hold right there Sparky!! and Laila – both from IIT Roorkee – landed the 2nd and 3rd spot respectively. Congratulations to the winning teams!
It’s day 2 of ICPC Regionals in India and today’s competition is taking place at two sites: IIIT Pune and IIITM, Gwalior. Keep up with all the contest action here!
Live Ranklist: https://www.codechef.com/public/rankings/ACM18GWR#
10.53 am: It’s been roughly an hour since the #ICPCRegionals at #IITTPune and #IIITMGwalior began and Team BhayanakMaut have swept into an early lead with 4 problems solved! tesla_protocol from #IIITHyderabad are close behind also with 4 problems.
11:18 am: tesla_protocol from IIITH lead the ranklist with 5 problems solved. 6 teams have solved 4 problems now. BhayanakMaut from IIITD are at Rank 2 and have a 40 minute time penalty difference from bits please who are at Rank 3.
11:24 am: BhayanakMaut solve their 5th problem and move up to rank 2!! Merely 4 minutes of time penalty gap separates them from tesla_protocol.
Top 4 teams have 5 problems solved now.
We also have 4 school teams participating in today’s regionals – antipro, exun_coder, bipolar and codeup_017.
antipro from Bodhicariya Senior Secondary School, Kolkata have solved 3 problems and are at rank 18 currently.
11:34 am: tesla_protocol get their 6th correct submission and extend their lead over BhayanakMaut.
They have had an incorrect submission on another problem (SIRUSERI) for a long time now. That problem would most likely be the next one they would target ACing.
Their solution seems to be almost there, but they seem to have made a minor mistake. The solution involves very less code, so once they spot the error they should be able to fix their code and submit quickly.
Time penalties could prove to be very costly in such a close contest. They should test out their solution rigorously before submitting!
11:40 am: Ranks 2 to 9 now have 5 problems solved.
11:45 am: tesla_protocol get another WA on SIRUSERI! They have 2 WAs on this problem now.
bits please solve THSTRS, their 7th submission and are now at Rank 5.
bits please, ButterRoti and Supercalifragilistic have solved 6 problems each now.
bits please is 20 minutes behind tesla_protocol. If they avoid WAs in the next 20 mins and get an AC, they could displace tesla_protocol from the top of the ranklist.
11:48 am: BhayanakMaut solve 6 problems and land at rank 3.
What a contest this is turning out to be! Top 5 teams have 6 problems solved and are separated just by time penalty.
11:54 am: tesla_protocol solve SIRUSERI, their 7th correct submission.
BhayanakMaut AC their 7th problem within 2 seconds of tesla_protocol!! They are separated by just 1 minute of time penalty now! Is this competitive programming or Formula 1?!
“bits please have 10 minutes to get their 7th AC to get to Rank 1.” – Jatin Yadav
12:02 pm: Persistent Matroid (IIT Kgp) solve 7 problems and are now at Rank 3.
With 3 hours to go in the contest, 7 problems are solved and 4 problems remain unsolved.
12:11 pm: bits please get WA on THSTRS. They also got a TLE before that.
12:18 pm: tesla_protocol solve WALKTREE, their 8th accepted submission.
12:26 pm: BhayanakMaut solve WALKTREE as well. They had a very very minor implementation bug that led to a WA. They are at Rank 2 now with a time difference of 39 minutes from tesla_protocol.
12:32 pm: ForTheDamagedCode from NITK are the first team to solve GAMEOFNUM. They have 6 problems solved in total now.
ButterRoti solve their 8th problem and are now at Rank 3.
12:34 pm: bits please solve their 8th problem 2 minutes after ButterRoti and are at Rank 4.
12:49 pm: BhayanakMaut solve 9 problems and take away the lead from tesla_protocol!
1.18 pm: BhayanakMaut are in the lead followed by ButterRoti from IIT Patna and bits please. Each team has solved 9 problems
1.26 pm: ButterRoti is now in 2nd place! Can they steal the top spot?
1:50 pm: BhayanakMaut seem to have a nearly correct solution for POLYSTR. Jatin Yadav and Animesh point out that they aren’t clearing their dp table and that’s their only bug! They have been debugging it for 15+ minutes now.
The setters are going to submit their code in practice with an extra statement to clear the table to see if it would AC.
1:54 pm: “Their solution passes by memsetting the dp table.” – Jatin and Animesh
Let’s see how much time BhayanakMaut takes to figure that out.
2:00 pm: The leaderboard will freeze in 10 minutes from now. We have 6 teams with 9 problems solved at the moment. Share your ranking predictions in the comments!
2.02 pm: tesla_protocol is back at rank 2 and have pushed ButterRoti to rank 3. BhayanakMaut maintains their lead.
2:07 pm: BhayanakMaut solve POLYSTR! They are at rank 1 with 10 problems solved now.
tesla_protocol seem to have a O(N^2) DP solution for POLYSTR too.
2:10 pm: Ranklist is now frozen.
The contest has ended. You can view the final ranklist here.
Congratulations to the winning teams BhayanakMaut from IIIT Delhi, ButterRoti from IIT Patna and tesla_protocol from IIIT Hyderabad!
Stay tuned for updates from the next ICPC Regionals at GNIT Kolkata and UIET Kanpur.
Today, we kick off the ACM ICPC 2017 season with the Chennai Regional hosted by Hindustan University. The contest is expected to begin at 10am IST. Stay tuned for live updates on the rankings and problem discussions!
Live Ranklist – https://www.codechef.com/public/rankings/ACM17CHN
11:15 am IST: The contest has begun.
11:16 am IST: Team volatile from Veermata Jijabai Technological Institute, Mumbai gets the first accepted submission of the contest!
11:38 am IST: Team TooWeakTooSlow from IIIT Hyderabad lead the ranklist with 3 problems solved!
Team BhayanakMaut from Indraprastha Institute of Information Technology, Delhi follow them at 2nd place with 3 solved problems but with 2 wrong submission penalties.
11:49 am IST: Triangulation from IIT Roorkee is the first team to solve 4 problems and are now at the top of the leaderboard! 2 ACs for them in the last 3 minutes.
11:57 am IST: Team Instincts from Sri Sivasubramaniya Nadar College of Engineering, Chennai has taken the lead from Triangulation with 4 problems solved and a 10 minute time-penalty gap between them.
12:08 pm IST: BhayanakMaut are at the top of the ranklist with 5 problems solved.
12:19 pm IST: TooWeakTooSlow get AC on ELHIDARR and move to first place, meanwhile Triangulation get AC on VRTXCOVR and move to 2nd place with a difference of 9 minutes between them. This is turning out to be a gruelling contest between the top 4 teams!
Triangulation (rank 2) and Majnu (rank 3) are separated by just a margin of 2 minutes.
12:25 pm IST: Instincts are back at Rank 1 after solving ELHIDARR. 10-minute gap between them and TooWeakTooSlow.
12:38 pm IST: Plumbus from IIT Roorkee are the first team to solve AREAFIGR. They currently stand at Rank 24. Maybe we can expect many of the top 20 teams to solve this problem in the next 1 hour.
12:43 pm IST: TooWeakTooSlow are the second team to solve VRTXCOVR and also the first team to solve 6 problems! They are back at Rank 1.
Which teams would be among the top 3 today? Share your predictions in the comments!
1:00 pm IST: Triangulation are now at Rank 2 with 6 problems solved.
Team Triangulation -
Here are a few glimpses from the contest which is being held at Hindustan University, Chennai.
1:26 pm IST: TooWeakTooSlow solve 7 problems and increase their lead over Triangulation.
1:30pm IST: Team Majnu from IIT Roorkee are the first to solve BLREDSET and have moved up to Rank 3, right behind Triangulation – another team from IIT Roorkee.
1:38pm IST: TooWeakTooSlow get AC on MANCBST and now have a total of 8 solved problems, followed by Triangulation with 6 solved problems. MANCBST was quite a non-trivial problem
1:50pm: It seems that TooWeakTooSlow have a solution for DEFOREST but they are trying to optimize it before submitting.
Triangulation is coding up a solution for BLREDSET.
Majnu (IIT Roorkee) are coding VRTXCOVR.
2:02 pm IST: One team member from NDTM is coding the solution for AREAFIGR while the others are thinking on BLREDSET.
2:06 pm IST: BhayanakMaut is coding BLREDSET.
2:10 pm IST: Triangulation solve BLREDSET, their 7th solved problem in this contest and continue to be at 2nd place.
2:25 pm IST: TooWeakTooSlow solve BLREDSET – they continue their lead with 9 solved problems.
Will they be able to solve all 11?
2:45 pm IST: TooWeakTooSlow solve DEFOREST and lead the ranklist with 10 solved problems.
2:56 pm IST: Bhayanak Maut solve their 8th problem and are on 3rd place.
3:15 pm IST: The ranklist is now frozen. TooWeakTooSlow look comfortable in the 1st place while Triangulation and Bhayanak Maut battle for 2nd place. Stay tuned for the final results!
Final Ranklist: https://www.codechef.com/public/rankings/ACM17CHN
- Team TooWeakTooSlow was the only team to get AC on MANCBST.
- Team Bhayanak Maut was the only team to get AC on CODIE. Fun fact: they got AC on the problem just 30 seconds before the contest ended!
Congratulations to the winners and we hope all participating teams had a great experience at the Chennai Regional!
Up next: ACM ICPC Kharagpur Regional on December 17, 2017. Stay tuned for latest updates!
The year is about to end, and so is the ACM ICPC season with the India Final 2016! After 4 onsite contests, with almost 600 teams participating and intense battles between the best teams, we’re here to present you live updates from IIITM Gwalior where the ACM ICPC India Final 2016 is happening today! Stay tuned for interesting insights from the arena, problem discussions and more!
The Mirror Contest shall begin at 11:00 a.m. IST. You can register your team for the mirror contest here.
Live Leaderboard: www.codechef.com/rankings/ACM16INF
10:00 IST: The contest has begun. The problem set consists of 11 problems.
10:08 IST: No submissions on any problem yet.
10:13 IST: No submissions still. Teams might strategize to minimize their time penalty today, as it can play a huge role in the final leaderboard.
10:15 IST: We have our first accepted submission! Problem I has been solved by team SRY from Delhi Technological University!
Problem I is called “Pacman” – surprisingly, it is not related to the game in any way but it is based on the name of a Software Package Manager.
This problem has been set by Vaibhav Tulsyan (that’s me!).
The problem is as follow:
You are given a list of softwares and their dependencies. Each software has at most one dependency and there are no cyclic dependencies. Also, each software has a download limit D[i]. Given a subset of ultra-special softwares, you want to find the maximum no. of “completely installable” softwares. By “completely installable”, we mean that its entire chain of dependencies must first be downloaded, and then the software itself should be downloaded. Each ultra-special software does a fresh install of all its dependencies.
The first solution one may think of is finding the max flow in a transformed graph. A new graph can be constructed by splitting each node into an edge with capacity = D[i] value of that node. A source node will have edges to all ultra-special softwares with capacity = 1 and all nodes which don’t have dependencies, can have edges to a Sink node with capacity = infinity. The answer would be the value of max flow in this graph. The implementation can be done using Dinic‘s algorithm.
However, from some observation, it can be deduced that one can select any ultra-special software and completely install it, if it is possible. Hence, all you need to do is traverse over all the dependencies of the ultra-special software uptil the highest parent, keeping track of the download limit and updating the download limits while traversing. This is a O(N^2) solution.
There also exists a Dynamic Programming solution which is that in each node, store the minimum of: D[i] of the current node and sum(D[j]) of all children j of node i. This runs in O(N).
10:46 IST: 20 teams now have Accepted Submissions on Problem I.
FruitSalad have solved Problem E as their first problem! However, they got 1 penalty on that problem.
Team SRY remain atop the leaderboard.
10:51 IST: Team believe from MNNIT are the first team to solve 2 problems and now lead the scoreboard with 0 penalties.
FruitSalad have solved Problem I and have 2 problems solved as well – although with 1 penalty. They are now at Rank 2.
11:00 IST: 1 hour into the contest, only 2 teams have solved more than 1 problem.
Let’s discuss Problem E – Jumping Frogs III.
We have Triveni Mahatha with us who has described the problem in brief as follows:
“The problem is about finding maximum number of frogs in a segment of an infinitely long road (x-axis) at any instant of time. Frogs are moving with constant speed in the x-axis. Initial position of the frogs and their velocity are given.
The solution is that, for every frog find out the time range for which they are at any point in the given segment. Then among these time ranges you need to find a time which is contained by max number of ranges. This can be done by sorting the intervals and doing line sweep greedily. Fairly popular problem.”
11:05 IST: AC on Problem H for Team Rocket!
They have solved 3 problems and lead the ranklist.
11 teams now have at least 2 problems solved.
The live leaderboard can be seen here: https://codechef.com/rankings/ACM16INF
11:15 IST: Team mobius_treap gets AC on Problem A! They are the first team to solve that problem. This is their 2nd solved problem in the contest.
11:25 IST: Team Hopeless solves Problem B.
11:32 IST: FacelessMen solve Problem A and move to rank 2 with 3 problems with 1 penalty.
mobius_treap solve Problem E and move to rank 3 – they have 2 total penalties.
11:35 IST: Triangulation get AC on Problem H. They seem to have used a Persistent Trie + Binary Search for their solution.
11:36 IST: Team Rocket have solved Problem C and increase their lead with 4 problems solved.
Let’s discuss Problem A now. You are given a number N of the from p * q. Where p and q are prime numbers. p may be equal to q.
You need to distribute N balls into k buckets such that every bucket gets equal number of balls.
It is clear that k can be either 1, N, p or q. You need to be alert that you are not counting twice for p and q if they are equal.
Print the answer modulo mod.
There are few things to observe here.
First how to factorize N which can be 10^12. But since max(p,q)/min(p,q) <= 10. It is easy by just doing brute-force.
Next observation is that the value of mod is small, this will be useful. Let’s first arrive at the solution.
Distributing N balls into k buckets is a fairly standard task in combinatorics. Say y = N/k then the number of ways is N!/(y! ^ k).
Here you may not take modular inverse as the denominator can have multiple of mod, since mod is very small.
So, rather you actually factorize the numerator and denominator to get the answer. Note that you need not go to prime factors more than mod. Because if the answer contains mod then answer is zero anyways.
That’s all about this problem. However, you need to be careful while implementing the idea. So many modulos and few cases as well. Factorization should be fast enough. Use sieve.
11:42 IST: Team Survivor from IIT Indore solve Problem L – a geometry problem. They are now at Rank 2 with 4 problems solved.
11:51 IST: Almost 2 hours into the contest, we have 7 distinct problems solved, with the top team solving a total of 4 problems.
Problem L, authored by Triveni is a really interesting geometry problem.
Quoting Triveni’s explanation of the problem and the possible solutions:
“Problem L is about finding approximate-smallest enclosing circle of N points in Cartesian plane. Smallest enclosing circle can be defines as a circle with minimum possible radius such that all the given points are either inside or on the circle.
If we allow few (4 for this question) points to be outside the circle, this is approximate smallest enclosing circle problem.
There are many possible solutions to this problem as the constraints are very small. N is just 51
I will discuss few.
Few things to observe. At most three points are needed to define the circle.
So we chose any three points and make the circumcircle. If all but 4 points are inside this then we have got an answer. complexity O(N^4). Fairly simple.
Another is based on Weizl’s algorithm.
You select any three points and make SEC of all the remaining points. If there are more than 3 points on the circle then you can not do much by removing one more point from the set. However, if there less than 4. Then we can try removing one point from the circle and regenerate the SEC of remaining points.
Weizl’s algorithm computes SEC in O(N). Its a randomized las-vegas algorithm. So random shuffling of points is needed to avoid TLE.
Total complexity is O(N^4) for this as well.
Apart from this one can write O(N^5) solution with optimizations to get AC.
That’s all.”
12:05 IST: Team Rocket have 5 problems solved and 2 penalties – Rank 1.
12:17 IST: thirdfloor have solved Problem D – they are the first to solve this problem and have moved up to Rank 4.
Balajiganapathi says that he expects more teams to solve D and is surprised with such a small number of submissions on that problem.
12:22 IST: FruitSalad solve their 3rd Problem with Problem H! They are at Rank 10 now.
8 distinct problems with the top team having solved 5. That says a lot about the diversity of difficulty of the problem-set.
12:33 IST: mobius_treap from IIIT Hyderabad at Rank 3 with 4 problems and 2 penalties.
12:47 IST: third floor have solved 5 problems and are now at Rank 2!!
Problem selection will be very, very important for the top teams now. With only a couple of hours remaining, they can’t afford to spend time on a problem and reach a dead-end.
12:52 IST: mobius_treap solve Problem H and are now are Rank 2, displacing third floor to the 3rd spot.
12:56 IST: mobius_treap solve Problem L and now are at Rank 1! 2 ACs within 5 minutes, they’re on fire today!!
1:28 IST: mobius_treap solve their 7th Problem and lead the ranklist. Survivor have now solved 6 problems and are at Rank 2, followed by FacelessMen with 6 problems at Rank 3.
1:29 IST: FruitSalad solve Problem L.
1:53 IST: As we approach towards the final hour of the contest, team mobius_treap looks comfortable at the top with 7 solved problems to their name.
2:00 IST: The final hour of the contest is in progress and the ranklist has been frozen. It means no more updates fromo us till the result announcement. So, join us back for the result announcements to find out who wins the first ever ACM ICPC India Finals.
4:00 IST: We are back live from the chilly campus of ABV IIITM, Gwalior, where the first ACM ICPC 2016 Multi-Site India Fials concluded, with some teams taking the part into the contest from Kolkata. And it is time to raise the mercury a bit with the final results of this ACM ICPC season. So, brace yourselves.
4:10 IST: The second runner-up is Team “Survivor” of Indian Institute Of Technology, Indore. A big round of applause for them.
4:15 IST: The first runner-up is Team “Rocket” of Indian Institute Of Technology, Bombay. Give it for them.
4:20 IST: And finally the big one. The winner of the first ever ACM ICPC India Finals is Team “mobius_treap” of International Institute Of Information Technology, Hyderabad. Great job guys. They seem to be making a habit out of it. And we are very pleased that they are.
4:30 IST: With that, it’s time to let the Sun set on ACM ICPC season for the year 2016 and the year 2016 itself. We hope you had a wonderful year, and have big plans for the coming year. So, on that note, from everyone here at CodeChef here’s wishing you and your love ones, a Very Happy New Year. Have a wonderful evening folks.
This is wittyceasor signing off for the final time in the year, 2016. See you on the other side.
- Vaibhav Tulsyan
It’s that time of the year again!
We are ready to start the Indian onsite rounds of the ACM ICPC, with our first round being held at Kharagpur. There are 76 teams competing today for spot(s) at the 2017 ACM ICPC World Finals, which will be held in Rapid City, USA! I’ll be doing live blogging throughout the contest and I’ll keep posting interesting facts as they come up. Stay tuned for some exciting action!
There is a slight delay before the start of the contest. The contest is expected to start at 10AM.
Let’s use this opportunity to talk about the top teams participating today. The ones to look out for today are “Triangulation” from IIT Roorkee and “FruitSalad” from DAIICT. Vaibhav Gosain from Triangulation and Sumeet Varma from FruitSalad are two of the most well known names in the Indian Competitive Programming Community. We also have team “Shockers” from IIT Madras with former ICPC World Finalists Sundar Annamalai and Karthik Vishwanathan.
10AM IST : There is further delay. Contest will start start at 10:30.
Some images of the contest arena :-
10:30AM IST : The contest has started! A long and arduous wait finally ends!
There are 11 problems in today’s problem set. In my opinion, this is a high quality problem set, with a lot of interesting problems. The easiest problem in the set is H, and we expect teams to start submitting solutions for it pretty soon. It is intended to be a basic implementation problem.
10:46AM IST : Phew! We finally get our first submission, and it is Accepted. Team “HappyTreeFriends” from IIIT-Delhi have solved H.
10:53AM IST : The AC on H has made the teams realize that its’ an easy problem, and now we’re seeing a flurry of submissions for it.
10:54AM IST : We have a submission on problem F by team “alwayslast” from The LNM Institute of Information Technology and it Accepted!
F is intended to be an easy-medium DP problem. You need to partition an array of N integers into K disjoint subsets S_{1}, S_{2}…S_{K}, such that the sum of the difference between the maximum element in each subset and minimum element in each subset is minimized. Formally, sum {i = 1 to K}{max(S_{i}) – min(S_{i})} should be minimized. Also, size of each subset should be atleast 2. The constraints are such that O(N * K) will work. To any experienced competitive programmer, the statement and the constraints will automatically indicate a dynamic programming approach. The key observation to make is that the we can sort the array and work with subarrays instead of subsets. After that, it’s just figuring out the transitions which is not very hard.
11:04 IST : “FruitSalad” from DAIICT, have solved 2 problems, F & H. However, they have a penalty on F.
11:07 IST : “alwayslast” have solved H, and are now on top of the leaderboard!
11:21 IST : We’ve had 4 accepted submissions on F till now, and about 48 on H!
Let’s talk about the next two problems that we expect the teams to solve. They are C and D. Both have trivial ideas, but require meticulous implementation and have a lot of edge cases. In fact, we expect solutions for C to be at least 100-150 lines long. Code for D should be shorter, but it is not trivial at all.
11:32 IST : We have 1 AC on both C and D. C has been solved by “FruitSalad”, moving them to first place. D has been solved by “triplethreat” from BITS Goa. Surprisingly, this is the first problem that they have solved!
11:42 IST : “FruitSalad” have solved problem D as well. They have solved 4 problems and are comfortably on the top of the leaderboard at the moment.
Seems like most teams will spend the next hour working on implementing C and D. In the meantime, let’s talk about problem E. Given a graph G(V, E), with no special properties (it might be disconnected as well), and the information that G has a dominating set of ceil(V/3) vertices, you need to find and print a dominating set with atmost ceil(2V/3) vertices. A subset of vertices of G is called a dominating set iff every vertex in G is either in the subset or is adjacent to a node in the subset. Looks hard doesn’t it? I’m going to talk about its solution later.
12:00 IST : “FruitSalad” seems to have solved E as well. They’ve got a WA, but it seems like the only thing they’re missing is a trivial edge case, which should be spotted soon!
12:05 IST : “FruitSalad” gets E. They’ve done 5 problems now. They’re on a roll!
So, E was designed by our very own Praveen Dhinwa. Upon first glance, the problem seems complex : The graph doesn’t have any special properties, the constraints are high and we know that minimum dominating set is NP complete. Also, it seems like we need some sort of 2-factor approximation of dominating set. Let’s use a common trick while solving problems : Solve simpler instances. Let’s make the graph the best kind possible, a tree. What can we do for a tree? Well it’s simple isn’t it? We know that trees are bipartite, so we can take any arbitrary bipartition, one of them will be of size <= (n / 2) and that will suffice.
Ok, so now let’s think about a general graph. What do we need to do? The answer is, quite simply, NOTHING! Notice that the dominating set for any spanning tree of G will be a dominating set for G as well. That’s it. Problem solved. Stop smirking, you’ve been PUNK’D!
Important Announcement : Ranklist is live!
12:30 IST : After two hours, “FruitSalad” sits comfortably in the lead with 5 problems solved. Team “code_phoenix” is at 2nd place, with 3 problems.
Team FruitSalad :-
It seems like other teams are still stuck coding the implementation problems C and D. For all of those who’re wondering why we have such type of problems in the first place, it’s because the World Finals also gives problem(s) each year which are easy logically but require one to write lengthy code without bugs!
Since it seems like the scoreboard will be a bit static, let’s talk about the next few problems. Whatever we’ve done till now was in the “easy” wave of problems. Now we’ll move on to Medium and Medium-Hard. Let’s discuss B, K and J.
B is a Geometry problem. Given a general quadrilateral (concave/convex) and 2 points S and T on a 2D Plane, compute the shortest distance needed to reach T from S without touching the quadrilateral. Again, this is not a terribly hard problem. We need to look at the line joining S and T and divide our solution into several cases, and take the minimum of all of them. Of course, the answer can also be impossible, such as in the case when S is inside the quadrilateral and T is outside it. Just like with any geometry problem, this requires careful implementation and consideration of all cases. Our model solution was ~ 90 lines!
1:05 IST : “FruitSalad” have solved B. This is gritty stuff. They’ve now increased their lead to three problems, and are sitting comfortably on top with 6 problems solved!
1:10 IST : “Rainbow” from IIT Hyderabad have solved K!
Update : All participating teams have solved H!
Let’s talk about K now. Suppose S = (a_{1}, a_{2}, .., a_{n}) is a string, then its ‘kth power’ is defined to be the string S^{k} = (a_{1}, a_{1}, … [k times], a_{2}, a_{2}, .. [k times], a_{n}, a_{n}, .. [k times]) where each character is repeated k times. Given strings T and P, you need to find all substring matchings of P^{k} in T, for all k ie. Find all occurrences of P in T, of P^{2} in T… etc. Also, it is guaranteed that P has at least 2 different characters in it.
First thing to notice is that the constraints are huge, 10^{5}, indicating that their definitely exists a linear or loglinear time solution. Here we describe the crux of one such solution. Note that checking whether P^{k} is in T for all k >= 1 is too slow. The idea is that, along with the kth power, there’s also a way to define the kth root of a string S, say S^{(1/k)}, with some nice properties. Firstly, counting the occurrences of P^{k} in T must be the same as counting the occurrences of P in T^{(1/k)}. Secondly, The length of T^{(1/k)} must be O(|T|/k). With this, the overall algorithm becomes O(|P| + |T|/1 + |T|/2 + |T|/3 + |T|/4 + …) = O(|P| + |T| log |T|). There are quite a few details to successfully defining the kth root of a string, but it can be done. This interesting problem was set by Arjun Arul, who also happened to have a linear time solution for the same!
1:52 IST : The scoreboard looks roughly the same. It seems like “FruitSalad” have amassed a sizable lead. With around 90 minutes remaining, something spectacular needs to happen for them to be dethroned!
1:57 IST : “FruitSalad” solves J. This is unbelievable. They keep their lead to 3 problems, with “code_phoenix” at 2nd place. It seems almost certain now that they will take first place!
Let’s talk about J now. It is one of the harder problems in the set. This interesting problem has also been set by Arjun Arul. Here is an abridged version of the problem : You’re given a directed graph G(V, E), where each edge is either vital or non-vital. You need to remove minimum number of non-vital edges from G, such that in the resulting graph, every node has it’s indegree equal to its outdegree. You should output the minimum number of edges that need to be removed, or print -1 if a solution doesn’t exist. Number of vertices in G is atmost 100, and number of edges is atmost 1000.
This problem, along with its low constraints, hints that the solution has something to do with minimum cost maximum flow routine. Indeed, that is the case. The graph construction for this problem is not apparent at first glance. Intuitively, notice that the quantity (outdegree – indegree) is important to us, and we want to make it zero for all nodes. We’ll continue on the solution later.
2:30 IST : The ranklist has frozen, with “FruitSalad” on 1st place with 7 problems solved, “code_phoenix” in 2nd place with 4 problems, and “included” in 3rd place with 3 problems. This means that from now onwards, we will not be giving you updates about submissions and changes in scoreboard.
Getting back to J. The graph construction is as follows. We’ll have V + 2 nodes, V for the graph, plus a source S and a sink T. For all nodes u which have outdegree > indegree, add an edge from S to u with capacity (outdegree – indegree) and cost 0. For all nodes u which have outdegree <= indegree, add an edge from u to T with capacity (indegree – outDegree) and cost 0. Now for all non-vital edges in E, add the same edge with capacity 1 and cost 1. The answer is the minimum cost we can obtain while maximizing flow from S to T in this network. To make sense of this construction, note that each augmenting path reduces the outdegree of the first node, indegree of the last node and both indegree and outdegree for intermediate nodes.
Here are some more pictures from the onsite contest :-
3:30 IST The contest has ended! Stay tuned for the final scoreboard reveal!
We are back folks, and it’s result time here at ACM ICPC 2016 Khragpur Regional. So, hold on to your seats as we reveal the “Winners.”
We start with the 2nd runner ups. And it’s Team “included” from NIT Warangal. Give a big round of applause to them. Well done guys.
On the 1st runner up place we have Team “code_phoenix” from National Institute of Technology, Karnataka. Kudos guys. Good job.
And finally, it’s time for the winners. Drum rolls!!!! At No 1 and “The Winners of the ACM ICPC 2016 Kharagpur Regionals” is Team “FruitSalad” from Dhirubhai Ambani Institute of Information and Communication Technology. Bravo guys. You are the first winners of ACM ICPC 2016 India Regionals.
That will be all from us here at the picturseque campus of IIT Kharagpur. We hope you enjoyed the contest and the updates. Now, from far East, we travel to down South for the ACM ICPC 2016 Chennai regionals to be held at Hindustan University. We will come back with all the live action and updates soon. Till then, do send in your messages and cheers for your favorite teams just to let them know that you are behind them as they compete for the ultimate programming glory. #GoForGold guys.
- Animesh
We are back with the third and final member of team “11coders” from Indian Institute of Technology – Roorkee. Let’s hear his side of the story.
Team name: 11coders
Team rank: Amritapuri regional: #2
Q. How old were you when you started programming and what got you started in programming?
A. I started coding when I was 18 (In my first year of B. Tech).
Q. What inspired you to get into competitive programming? Were you passionate about it since school or anything special in college?
A. I was very much interested in mathematics and puzzles, I enjoyed solving them, and I got similar fun in solving programming problems which required good logic. Then I continued solving problems, soon I got to know about ICPC in my first year itself. Thanks to PAG (Programming and Algorithms Group) in IIT Roorkee, which directed a bunch of puzzle lovers towards a bigger goal named ICPC.
Q. How to start preparing for ACM ICPC for those who are new to algorithms and competitive programming? It would be great if you could share your journey from a beginner to a World Finalist today.
A. Initially I used to practice problems on SPOJ; soon I realized that many problems require a well known algorithm which I was unaware of. Then I started to read new algorithms. Soon I started giving contests on CodeChef and codeforces, solving problems with a time constraint is really fun. Main goal for giving contests is to learn by up solving problems which I couldn’t solve during contest.
Q. Can you throw some light on how did you and your team manage the time and coordinate during the onsite finals? It would be great if you could share some tips for the next year ICPC aspirants.
A. Before onsite we did a lot of team practice; this helped us to know our weakness and strength. Knowing strength of other teammates can help to pass questions to the person who is strong in that topic. Our main weakness was a lot of penalties, so to overcome it we always used to read the code once to ensure correctness. This approach did slow us a bit but minimized the penalties.
Q. What did you do to improve over these years and maintain your target status for all these years with all the competition? What do you think was your most effective method to improve? Any hacks on how to reach where you are in less time ?
A. The only way to improve is practice and I too did the same. To decrease amount of time, one just need to increase the amount of practice.
Q. Do you have any other thoughts as we wrap up?
A. NO
That was Aman from team 11coders. We hope you enjoyed the interview. We have few more in the pipeline and will be publishing them soon. Till then, share this interview among your friends, and family and send in your wishes and questions for them. #GoForGold.
Regards,
Rudreshwar
Team CodeChef
Today we meet another member of Team “11coders” from Indian Institute of Technology – Roorkee, say hello to Kshitij Bathla. Let’s hear it from him. But before that, let us give you a brief info of his team.
Q. How old were you when you started programming and what got you started in programming?
A. I started programming in my first year of college. We have a programming club (Programming and Algorithms Group) in our college, I got selected and that is how it all started.
Q. What inspired you to get into competitive programming? Were you passionate about it since school or anything special in college?
A. I always liked math, solving puzzles and found competitive programming similar. I used to solve SPOJ problems (puzzles mostly) in my first year. I wasn’t aware about it during my school days.
Q. How to start preparing for ACM ICPC for those who are new to algorithms and competitive programming? It would be great if you could share your journey from a beginner to a World Finalist today.
A. I would recommend Topcoder tutorials as a starting point. You can start with some basic topics like Dynamic programming; greedy algorithms etc and solve the problems given in the tutorial. Make sure you code everything. Finding the solution and actually coding it and getting it accepted are two completely different things. Try to give lots of contests on Codeforces, CodeChef and Topcoder. Try out the problems that you could not solve during the contest. If you are not able to solve them, read the editorials and code them on your own. If you see a new algorithm/technique, try to learn it from online resources. Learn the logic and try to code it. Once you’re more used to solving contest problems, start forming a team. Pick your team early and do a few virtual contests with them. You can try out regionals from previous years from your region.For team practices, you can also try out the contests on Gym (Codeforces).
My Journey: We formed the team in our first year. We got selected for the 2013 Amritapuri regional(onsite) in our second year . We performed decently and secured a rank of 32 there. The 2014 Amritapuri regionals was a disappointment as we performed very badly in the onsite event. We came 8th in the Gwalior onsite that year. 2015 Amritapuri was again not great because of the technical glitches but we finally made it in the Chennai regional(our last attempt at the World Finals).
Q. Can you throw some light on how did you and your team manage the time and coordinate during the onsite finals? It would be great if you could share some tips for the next year ICPC aspirants.
A. In the last one month before the regionals, we used to give a gym contest every alternate day on one machine (similar to what it would be in regionals). This is important for finding out which way your team performs best. In our case, we had an idea about the strengths of each individual and hence we labelled the problems by their topics after reading them e.g Strings, graphs etc. One more important thing is proper utilization of machine time. Because only 1 PC is available, you need to use it wisely.You should think about the code structure in your own mind before starting to write it on the machine, this will save a lot of time as compared to thinking about the solution while writing the code.
Q. What did you do to improve over these years and maintain your target status for all these years with all the competition? What do you think was your most effective method to improve? Any hacks on how to reach where you are in less time ?
A. Participating in lots of contests is extremely important.This helps in improving accuracy as well as speed. Topcoder contests are recommended for improving accuracy. I used to take part in codeforces gym contests as well as normal rounds(Div 1,2) and that is what helped me improve. Practicing a lot is the only way through which you can qualify for world finals in my opinion. What matters is the number of hours you put in practicing.
Q. Do you have any other thoughts as we wrap up?
A. ACM-ICPC is not an individual activity. If you practice along with your team mates, it gives you different approaches for the same problem and keeps motivating you towards your goal. Learning new topics is also easier this way. Do lots of practice and enjoy coding.
We hope you enjoyed the interview. We have few more in the pipeline and will be publishing them soon. Till then, share this interview among your friends, and family and send in your wishes and questions for them. #GoForGold.
Regards,
Rudreshwar
Team CodeChef
We are back with our ACM ICPC World Finalist’s interviews. As we move closer to the World Finals, it’s just the perfect time to have a look back at the journeys of our World Finalists. Today we have Anubhav Bindlish of Team “11coders” from Indian Institute of Technology – Roorkee. Let’s hear it from him. But before that, let us give you a brief info of his team.
Q. How old were you when you started programming and what got you started in programming?
A. I was in class 11th when I started programming. I had it as a subject in school.
Q. What inspired you to get into competitive programming? Were you passionate about it since school or anything special in college?
A. A friend introduced me to competitive programming. It was in class 11th as well. I guess I always enjoyed solving puzzles, and that is why I found competitive programming interesting. I qualified for INOI but could not prepare well for it as I had to study for JEE entrance at that time. Participating in it was still a fun experience though!
Q. How to start preparing for ACM ICPC for those who are new to algorithms and competitive programming? It would be great if you could share your journey from a beginner to a World Finalist today.
A. I started competitive programming in 2010, and at that time the programming circle in India was not as active as it is today. When I started, I had doubts but didn’t know anyone who could resolve them. As a result, I didn’t really learn much in the first two years. The problems I solved were mostly adhoc in nature. Upon joining college, I became part of a programming group in campus. This I believe has been a most important factor in my growth. We had some inspirational seniors who we would look up to. Furthermore there were group ‘lectures’ (quoted because we really hated the word ‘lectures’:P), where members would share whatever little knowledge they had. This helped us collectively learn new concepts and techniques. Then I used to participate in contests and read editorials of unsolved problems to learn new topics.
Qualifying for the World Finals is really a dream come true for me. This was our last attempt at the Regionals, and I am happy that we gave in everything we had while preparing for it. Before the Chennai Regionals, it was almost as if we were giving a team contest every other day. Practice and perseverance are key to achieving anything in life, and competitive programming is no different.
Q. Can you throw some light on how did you and your team manage the time and coordinate during the onsite finals? It would be great if you could share some tips for the next year ICPC aspirants.
A. The Chennai onsite was a really good experience! (Food and accommodation aside ) Usually when we give contests, we are off to a flying start but then we lose track somewhere towards the middle or end. The Chennai onsite went completely opposite! We had a slow start, and as far as memory serves, even after solving 3-4 problems, we were still not among the top teams of the leader board. What worked to our advantage however was that we managed to make continuous progress throughout the contest? It was after solving our 6th problem that we came second in the leader board for the first time, and we knew we had a good chance of clearing the Regionals.
In several of our past contests, we had had a lot of penalties. As such we specifically wanted to minimize them in the finals. This is why, we took our time before submitting solutions, and mostly got them proof read by another teammate before submitting. As a result we had just one penalty overall (which too required exactly a single character change). Even though we lost out on time because of this, we are glad we made this bargain.
If you’re planning to participate in ICPC anytime in the future, my advice for you would be simple: remember this is a team contest. No matter how good you are individually; if your team is not balanced, it becomes really difficult to win in the Regionals. When forming your team, try to find members with slightly different areas of expertise. Have good interaction with them and try to give as many team contests as you can.
Q. What did you do to improve over these years and maintain your target status for all these years with all the competition? What do you think was your most effective method to improve? Any hacks on how to reach where you are in less time ?
A. I think participating in as many good contests as you can is an effective way to learn. But this only works if you find out the solutions to problems you could not solve in the contest after it ends. Otherwise you’ll feel that you have saturated after a point and there’s nothing more to learn. There are an insanely large number of tricks and techniques that are useful in competitive programming, and we can only learn these over time with practice. Then there are some really talented Indian programmers who are performing well on online judges. We should look up to them for inspiration!
Q. Do you have any other thoughts as we wrap up?
A. First of all, I’d like to thank CodeChef and the other Indian programmers who have been making commendable efforts to improve the programming culture in India. It’s no doubt that the Indian programming circuit has come a long way in the past few years. Sure, we still have a long way to go before we can compete with the best in the world, but I’m positive we’ll get there eventually.
We hope you enjoyed the interview. We have few more in the pipeline and will be publishing them soon. Till then, share this interview among your friends, and family and send in your wishes and questions for them. #GoForGold.
Regards,
Rudreshwar
Team CodeChef
The second in the series of #ICPC Indian finalist interviews comes from Kunal Singhal (a.k.a. knsn) from IIT Delhi. Here is a brief about his ICPC profile followed by the interview.
How old were you when you started programming and what got you started in programming?
I think, I started coding in c++ in class 9. My motivation was to compete in inter-school competitions happening all over Delhi. We did win some of those contests. But I really got introduced to competitive programming when I gave INOI in my 12th grade and cleared it. And then, I learnt systematically in the IOI Training Camp. I learnt almost all the algorithms there.
What inspired you to get into competitive programming? Were you passionate about it since school or anything special in college?
I always loved mathematics and was part of Robotics club in my school. But programming robots was not challenging enough, so I dived into competitive programming given the first chance.
How to start preparing for ACM ICPC for those who are new to algorithms and competitive programming? It would be great if you could share your journey from a beginner to a World Finalist today.
One simple advice. Practice, Learn as you do. Do not read theory first. Attempt problems, get blocked, search, ask, read, learn and apply. Follow it like a recipe.
Can you throw some light on how did you and your team manage the time and coordinate during the onsite finals? It would be great if you could share some tips for the next year ICPC aspirants.
Our time management at onsite was quite ad-hoc so not much to say. A good chemistry is needed though. So, make sure that your teammates are also your friends.
What did you do to improve over these years and maintain your target status for all these years with all the competition? What do you think was your most effective method to improve? Any hacks on how to reach where you are in less time ?
No hacks, genuine curiosity and perseverance is the key.
Hope you enjoyed the interview We are coming up with more, stay tuned!
Regards,
Chanukya
Team CodeChef
After a fierce battle of codes at the ACM ICPC 2015 – 2016 Indian Regionals (Amritapuri, Chennai and Kolkata), we finally have the teams which will be representing India and their respective institutions at the ACM ICPC World Finals 2016 at Prince of Songkla University Phuket, Thailand. If you are a programmer, you certainly would have or still has the dream of representing your nation/institution at these coveted programming contests. However, we all know, there can only be one winner, and in case of ACM ICPC World Finals, there can only be certain number of teams.
As Henry David Thoreau said, “Success usually comes to those who are too busy to be looking for it.” We are sure that every one of these individuals would have strived hard to be where they are right now. And, that is what makes it even more intriguing to find the secret behind their success. But, we will save you all the guessing time and bring to you the secret straight from the horses’ mouth. We have already snatched some valuable time from their busy schedule interviewing them and will be sharing the experiences of ACM ICPC Indian World Finalists starting this week. We are sure their insights and experiences will be inspiring and resourceful for everyone aiming to make it big in the world of competitive programming. So, sit back and enjoy them. Also, do not forget to send in your wishes for your favorite team, feel free to tag us in your cheer messages or use the following hash tags #ICPC2016 #GoForGold #CodeChef.
The first in the series of interviews comes from Man Mohan Mishra from IIIT Allahabad. Here comes his profile and the interview.
How old were you when you started programming and what got you started in programming?
I started programming in 1st semester of my graduation. I didn’t have any previous experience in programming during my school. So, things were kind of new & challenging in the beginning.
What inspired you to get into competitive programming? Were you passionate about it since school or anything special in college?
Major role in my involvement in competitive programming was the motivation and inspiration from my seniors. The environment of competitive programming is quite healthy in my institute (IIIT Allahabad). So, I came to know about competitive programming through seniors and I started it.
How to start preparing for ACM ICPC for those who are new to algorithms and competitive programming? It would be great if you could share your journey from a beginner to a World Finalist today.
As I recall my journey, I started mainly with SPOJ in my 1st semester. Along with it, Uva was really helpful and I am sure it will be of high help for any beginner. Though tutorial of problems are not available over these judges, but the time spent in debugging a code or finding the mistake in your logic also teaches you many things. After practicing on SPOJ for like 6 months (and solving nearly 100 problems), I started participating and solving problems on Codechef and Codeforces. I loved the contests hosted on both these websites and I hardly missed the contests hosted on them. Slowly, I started solving problems on Topcoder, Hackerrank and Hackerearth. In my 5th semester, we (I along with Aditya and Shiva) formed a team and started practicing in team contests. Codeforces gym was very helpful for team practice. We also listed down topics (Data structures and algorithms) and divided those among us so that we may get more time for focusing on our individual topics. We also participated in gym contests in our labs using only 1 system during the contest.
Can you throw some light on how did you and your team manage the time and coordinate during the onsite finals? It would be great if you could share some tips for the next year ICPC aspirants.
I believe my approach towards competitive programming was not the ideal one. I used to participate in live contests so much (100+ codeforces rounds till date). If I get another chance now (from 1st semester of course ), I would list down the topics and I’ll learn each topic in 8-10 days using online tutorials/blogs and then I’ll spend 4-5 days to solve problems based on that topic over various online judges. In this way, a large number of topics can be covered in 1-2 years.
Finally, about the coordination inside team. This part is very important. To reduce the panic and chaos during onsite contests, we practiced in a lot of team contests keeping the environment as similar to onsite contests as possible. Every member of team must formulate the process on paper before starting to type the code.
What did you do to improve over these years and maintain your target status for all these years with all the competition? What do you think was your most effective method to improve? Any hacks on how to reach where you are in less time ?
In the end, I firmly believe that practice (“smart practice” to be precise ) is the key for performing well in competitive coding.
Hope you enjoyed the interview We are coming up with more, stay tuned!
Regards,
Chanukya
Team CodeChef