Our 66th Lunchtime took place on November 24 and it was a showdown to remember with a major rank list shake-up! Keep reading to read who gained ratings and who lost them in the November Lunchtime.
Leading the pack in Div 1 was uwi, who is presently ranked number 1 in Japan and number 5 globally. Following our 100th Cook-Off, we mentioned in our Contest Recap that uwi was less than a hundred rating points short of a spot in the global top 5. Looks like, uwi took up the challenge and dethroned China’s ACRush to claim the world number 5 spot. But ACRush is a regular in our Long Challenges, stay tuned to see if he makes a comeback next month.
Other notable mentions in Div 1 are zemen from Russia who moved to 5-star status in this competition and rns5 from North Korea who went from 5 stars to 6. natsugiri, also from Japan, rounded out the top 4, all of whom scored 500. rns5 has risen rapidly through the rating system, gaining a whopping 6 stars since joining CodeChef in August this year. He needs just about 182 rating points to join another, rns4 another celebrated Kim Il-sung University student, in the 7-star club.
In Div 2 mzuev from Russia, took the lead going from 2 to 3 stars in the process. Close behind was xuzijian629 from Japan who was participating in a CodeChef contest for the very first time and made a rating jump of 275 points, which is the maximum jump possible! He promises to be a coder to watch out for. Dubai based antrikshh claimed the third spot, with Indonesia’s sidiqha in 4th place. While no Indians made it to the top 10 in Div 1, 4 Indians secured spots in Div 2’s top 10. A huge shoutout to its_ulure, mindjolt, radon12 and shubham698.
School students were well-represented in the November Lunchtime Div 1 with 9 of them earning places in the top 20. The best performers were tmwilliamlin from Taiwan who was at rank 5, farhod_farmon from Tajikistan at rank 7, and Ukraine’s adalbert at rank 8. Div 2’s best performing school students were its_ulure from India at rank 5, arafat_01 from Kazakhstan at rank 9, and fake_here from China at rank 15.
Special mentions go to female coders amina283 from Azerbaijan and mh755628 from Bangladesh, both of whom made it to the Div 1 top 100. In Div 2, it was hui_yin from Hong Kong and India’s own viralivora who reached the top 100.
Joining xuzijian629 on the list of users who made sizeable rating jumps are mzuev from Russia and tyakennikku from China who improved their rating by 233 points each. Indonesian sidiqha enjoyed a rating jump of 209 points while India’s own its_ulure from West Bengal, increased his rating by 201 points.
The highest participation this month came from India, followed by Bangladesh and Ukraine. India’s National Institute of Technology, Kurukshetra and Jaypee Institute of Information Technology had the most participants in this Lunchtime. If you’d like to spread the word about competitive programming in your school or college, start by creating or joining a CodeChef Campus Chapter today.
Probability (PPAP) emerged as the least solved problem of both Divisions with no successful submissions in Div 2 and just 7 in Div 1. Event (EVENT) was the most solved problem of Div 2 with 769 successful submissions out of a total of 5738 while in Div 1, Beats and Pieces (BPS) got 169 successful submissions from a total of 576. Check out the editorials for this Lunchtime’s problems here.
As we conclude this recap, we tip our hats to our problem setting panel:
Setter: Rehim Memmedli (nots0fast)
Tester: AmirReza PoorAkhavan (arpa)
Statement verifier: Jakub Safin (xellos0)
Editorialist: Hussain Kara Fallah (deadwing97)
Translators:
Mandarin Translator: Hu Zecong (huzecong)
Vietnamese Translator: Team VNOI (khanhptnk)
Russian Translator: Fedor Korobeinikov (gomelfk)
Bengali Translator: Mohammad Solaiman (solaimanope)
Hindi Translator: Akash Srivastava (devils_code)
And as always, many thanks to our problem panel admin Hasan Jaddouh (kingofnumbers) whose hard work helped us pull the contest together.
The November Cook-Off may be behind us, but the excitement still hasn’t left our system! This was CodeChef’s landmark 100th Cook-Off and we rewarded not only our top performers but also a bunch of participants, selected randomly, to show our gratitude. Keep reading to know what went down during this historic Cook-Off.
Over in Div 1, Japan’s number 1 competitive programmer uwi, stole the show by securing the first rank while the second spot went to India’s own rahuldugar. During this Cook-Off IITian rahuldugar increased his rating to 2484, he only needs a few more rating points to join the exclusive 7-star club. We’re rooting for you, Rahul! uwi, meanwhile, has enjoyed top billing in Japan (national rank 1) and a global rank of 8 for a while and only needs around 70 rating points to steal ACRush’s spot in the global top 5. We’ll be waiting to see if he takes up the challenge. (UPDATE: We may have inadvertently predicted a huge rank shift for uwi! Wait for our Lunchtime recap to know more!)
Also in Div 1, artistmusicant and ll931110 who were at ranks 3 and 4 respectively, both graduated to 5 stars during this Cook-Off. artistmusicant was notably the only female programmer in the top 10 during this Cook-Off so hope she inspires all the girl-coders out there!
grikukan from Russia stirred things up in Div 2 where he earned the first rank. This University student is teetering on the brink of Div 1 with a rating of 1786, but he’s had a tumultuous journey through CodeChef’s contests slipping from 6 stars to 3 stars last year, and nobody knows better than us that anything can happen in a CodeChef contest! petergendy4 from the US swooped into second place with a score of 2, and in the process went from 3 stars to 4.
Among school-level coders, sanroylozan from Hungary, evpipis from Greece and adhyyan1252 from India were a cut above the rest. These school students are all 6-star coders, we hope they can all graduate to 7 stars soon and give the more experienced coders some competition.
There were no seismic shifts in this month’s Div 1 and Div 2 order, but 61 users from Div 2 graduated to Div 1 while over double that number (137) fell back to Div 2 from Div 1. Just a reminder that in the word of competitive programming, you can’t get too comfortable with your rating! You have to keep practising and competing to stay on top.
As far as participation goes, India had the most participants with over 2000 coders taking part in the Cook-Off. The United States and Bangladesh were tied in second place with 23 participants each while 9 Cook-Off coders were from Russia.
The problem Truth and Dare, emerged as the most solved problem with 1781 successful submissions out of a total of 4355 while Data Pipelines was the least solved with 0 successful submissions in Div 2. In Div 1 Elephants in a Pond got just 1 successful submission. You can check out editorials for all the Cook-Off problems here.
We conclude this recap with a big thanks to our problem setting panel:
And an extra special thanks to our problem panel admin Hasan Jaddouh (kingofnumbers) who went above and beyond to make our 100th Cook Off memorable for everyone!
At CodeChef, we constantly stay in touch with CCDSAP holders to make the experience better for you and to fine-tune the certification. We spoke to Amit Upadhyay, a CCDSAP Foundation Level Certificate holder who is placed at Cleartax as a Software Engineer. We asked him about his CCDSAP experience and his tips for aspiring candidates. so read on!
A little background on Amit and his introduction to coding.
Amit completed his engineering from the Army Institute of Technology in Pune in 2018. Amit has always been involved with the world of code. He started coding on the CodeChef platform in his first year, and eventually moved on to making mobile apps in his second year. During this he found that he had a wealth of knowledge (and libraries!) to share with the world, so he began blogging as well. Amit credits the environment in his college for boosting his interest in coding competitively. In his first year, his seniors informed him about the CodeChef platform and he quite enjoyed the thrill of competitive programming.
How did Amit hear about CCDSAP and why did he decide to appear for it?
Amit heard about CCDSAP when Directi landed up in his campus for a recruitment drive. Clearing the CCDSAP also allows one to interview with Directi and Amit decided to make use of this opportunity. Even though his concepts were clear, Amit decided to consolidate his learning before appearing by taking the mock test on the CodeChef website. He recommends taking them to get an idea about the exam format and the correct pacing needed to finish the exam in time.
How should one prepare for CCDSAP?
Amit believes that a strong understanding of the fundamentals of DSA is what is tested at CCDSAP. So how does one get there? He recommends using a good book of DSA theory matched with an equal amount of solving DSA problems, like the ones available on the CodeChef website. He advises that candidates should study one data structure at a time and then solve 10-20 problems based on it before moving to the next. There are also many videos available online to help with the conceptual part. Finally, he recommends the prepare section on the CCDSAP site as an invaluable resource, complete with mock tests.
So where does DSA help one in the industry?
While most products depend on existing frameworks which can be understood by reading the manual, Amit emphasizes that DSA helps you learn how to think. It lets you understand the most optimal way of going about solving a problem, no matter what platform or framework is used. After all, problem-solving skills are universal and carry over to your next assignment as well.
Amit also spoke about how college doesn’t quite prepare you for industry challenges, and a lot of the learning happens on the job. At CodeChef we agree that this is certainly an issue and efforts can be made to bridge the gap between recruiters and candidates. CCDSAP does address this in a small way, and eventually we can bring a systemic change together.
The next CCDSAP exam takes place on the 7th of October. Check this link for details and get in touch if you have any questions for us!
The final regional of the ACM ICPC season of 2017 is here!
9:00am IST: The contest has begun.
9:05am IST: Team Instincts from Sri Sivasubramaniya Nadar College of Engineering, Chennai get the first AC of the contest!
First 10 submissions of the contest have all got AC. 6 of them are in C++, 3 in Python, 1 in Java.
9:18am IST: ScopeHotaHai from IIT Bombay lead the ranklist with 2 problems solved.
Plenty of teams are trying the 2nd easiest problem of the contest at the moment. 60+ teams have correctly solved it so far.
9:45am IST: Bristomaticians are now at Rank 1 with 3 problems solved. They have 1 time penalty at the moment.
9:47am IST: aglet (IIT Bombay) get AC on the 3rd problem. They are at Rank 1 with 0 penalties. This team is to watch out for in this contest. They were among the top 5 in the Kolkata regionals and were the only team to solve one of the hard problems.
9:51am IST: TooWeakTooSlow (IIIT Hyderabad) solve their 3rd problem which is the 4th distinct problem solved in this contest.
9:52am IST: Geany (LNM Institute of Information Technology) are at rank 1 with 3 problems solved. Just 1 minute time penalty difference between Geany and aglet.
9:55am IST: TooWeakTooSlow solve 4 problems! They are now at first place.
10:15am IST: TooLazy (IIT Madras) solve 4 problems! They are ahead of TooWeakTooSlow by one 29 seconds!
10:20am IST: FutureGlory (IIT Bombay) solve 4 problems with 0 penalties and are now at Rank 1.
Their team name seems to be inspired by tourist’s team – PastGlory
10:23am IST: The Vindicators (IIT Kharagpur) solve a graph problem which their 4th AC and this contest’s 5th distinct solved problem. Also, they are rank 1 now! 3 minutes ahead of FutureGlory.
They haven’t solved a problem that the other top teams have solved yet, but maybe one member of the team would have figured out the logic for it by now. Let’s see if they get an AC on that problem in the next 10-15 minutes!
We also have 4 school teams participating today!
- int elligence = 0; (DPS Ruby Park)
- syntaxscrubs (DPS International School)
- int_elligence (Professor K K Anand’s Smart Minds Academy)
- Bashers (Professor K K Anand’s Smart Minds Academy)
10:57am IST: No team has solved 5 problems yet.
11:03am IST: Mochizuki (IIIT Bangalore) are the first team to solve 5 problems! They are now at Rank 1 with 0 penalties.
11:14am IST: Unity (IIT Delhi) solve 5 problems and move up to rank 2! They have 2 penalties. They have also solved the 6th distinct problem of the contest.
11:25am IST: BhayankMaut (IIIT Delhi) are now at Rank 2. with 5 problems solved.
TooWeakTooSlow (IIIT Hyderabad) solve their 5th problem as well and move up to Rank 3.
11:31am IST: NotExperts (BITS Hyderabad) solve their 5th problem and the 7th distinct problem of the contest.
11:51am IST: TooWeakTooSlow solve 6 problems and lead the ranklist now.
12:05pm IST: Tesla (IIITH) solve their 6th problem. They are at Rank 2 now!
12:10pm IST: Unity (IIT Delhi) solve their 6th problem and they are at Rank 2 now. Tesla moves to rank 3.
12:31pm IST: TheVindicators (IIT Kharagpur) move up to 2nd place. They are ~15mins behind TooWeakTooSlow on time penalty.
12:55pm IST: LastBreath (NSIT) solve the 8th distinct problem of the contest.
3 minutes left before the ranklist freezes.
1:00pm IST: Ranklist is now frozen.
Top 10 teams have all solved 6 problems.
Whom do you think will win at the ACM ICPC Amritapuri Regionals?
Vote now and cheer for your favorite team here: https://twitter.com/codechef/status/945928634279247872
Welcome back to the 4th regional of the season. This one is a multi-site regional, being organized by NITTTR Kolkata and hosted by JIS Group in Kolkata and University Institute of Engineering and Technology, CSJM University in Kanpur.
Ranklist – https://www.codechef.com/public/rankings/ACM17KOL
10:10am IST: The contest has begun.
No submissions so far in the first 5 minutes.
First AC of the contest by team lastTry from NIT Durgapur, 7 minutes into the contest.
Team we_are_noobs from Indian School of Mines solve a different problem – we now have 2 distinct problems solved.
The problem solved by lastTry is an easy implementation problem. So far, there has been 100% submission accuracy on that problem.
The one solved by we_are_noobs is an easy counting problem. The submission accuracy on this problem is 71%.
10:26am IST: Team SSH from Jalpaiguri Government Engineering College solve the third distinct problem of the contest.
imported_pandas from DTU, Delhi lead the ranklist with 2 solved problems.
There are some rapid changes in the ranklist at this point as first 3 problems seem to be easy.
WeakMind from BITS Pilani, Supercalifragilistic from IIT Madras and Sudocrypt from BIT Mesra both gave fierce competition to LongTimeNoC in the Gwalior regional. They seem to be strong contenders for finishing in the top 3 today as well.
10:46am IST: WeakMind solve 4 problems and are at Rank 1.
11:00am IST: Supercalifragilistic solve a geometry problem, quite early on in the contest. This was their 4th solved problem.
11:19am IST: Supercalifragilistic get their 5th AC! WeakMind has some catching up to do.
Supercalifragilistic has 2 time penalties, by the way.
If WeakMind manage to get an AC within the next 30 minutes or so, they’ll be get ahead of Supercalifragilistic.
11:31am IST: Know_no_algo, IIT Delhi solve their 5th problem with a total time penalty of 3:07:23 and are at rank 1.
The top 3 teams have all solved the geometry problem. It is not a implementation-heavy problem.
ButterRoti from IIT Patna join the 5-solve-problems club. Currently at rank 4. They too, solve the geometry problem.
TooLazyToPropogate from IIT BHU solve 5 problems as well. Interesting team name
——
2 hours into the contest, 9 teams have solved 5 problems.
12:36pm IST: TooLazyToPropogate solve 6 problems! They are at Rank 1.
1:18pm IST: NeverSettle from IIT Mandi solve the 7th distinct problem of the contest, but they have 5 total problems solved at the moment.
——
1 hour and 48 minutes left in the contest. How many problems do you think the top team will solve?
The accuracy on the geometry problem is quite low, approximately 38%.
TooLazyToPropogate (IIT BHU), Know_no_algo (IIT Delhi), Supercalifragilistic (IIT Madras) are the top 3 teams right now and the battle between them is quite intense.
WeakMind (BITS Pilani) got TLE on a graph problem 2 hours ago – if they can optimize this one, they have a chance to be Rank 1 with 6 problems solved.
At the moment, they must be debugging that problem on paper.
Supercalifragilistic have a WA on the problem that the IIT BHU team solved an hour ago.
1:52pm IST: iota (NIT Warangal) solve their 5th problem which is solved only by 1 other team.
2:06pm IST: Know_no_algo (IIT Delhi) solve their 6th problem and are at Rank 1!!
TooLazyToPropogate is 38 minutes behind them on time penalty.
2:07pm IST: TooLazyToPropogate submit a solution .. still waiting to get a response…
TLE for TooLazyToPropogate.
Each penalty counts. Several teams could have equal no. of problems solved at the end.
—-
Contest has ended.
This has by far been the most exciting last 1 hour in any regional I have witnessed in the past 2 years.
Teams didn’t give up until the very last second.
Keep guessing the top teams, until the final results are announced!
Welcome to the 3rd regional of the season being held amidst the cracking cold of Gwalior! This year, 7 school teams will also be participating at the regional along with the college teams as part of the ICPC for Schools initiative. Good luck to all teams!
9:45am IST: The contest has begun.
9:49am IST: Accio ACs gets the first accepted submission of the contest. Guess what? That’s a school team with a single member – Udit Sanghi! Quite an awesome birthday present for him.
10:05am IST:
10:13am IST: 34 teams have solved at least 2 problems in the contest now.
10:19am IST: Supercalifragilistic from IITM lead the ranklist with 3 problems solved!
We now have 5 distinct problems solved in the contest so far.
10:42am IST: Supercalifragilistic solve 4 problems! They are on an AC-spree!
10:49am IST: WeakMind from BITS Pilani get 2 ACs within 5 minutes and are up to Rank 2. They are 17 minutes behind IITM’s Supercalifragilistic on time penalty.
6 problems have at least one accepted solution in the contest so far. 3 problems remain.
11:12am IST: 7 distinct problems are now solved! JustAnotherTeam from DAIICT Gandhinagar get AC on ZUBWALLT.
11:20am IST: 8 distinct problems now have at least one accepted submission in the contest as LongTimeNoC from IIT Kanpur solve their 4th problem.
The top 19 teams all have 4 accepted submissions so far.
11:27am IST: Sudocrypt from BIT Mesra solve their 5th problem! They are at Rank 1 now.
Almost immediately, JustAnotherTeam (DAIICT) solve their 5th problem as well – that takes them to the 2nd place.
11:46am IST: Supercalifragilistic solve their 5th problem and move to Rank 1 based on time penalty.
11:52am IST: Supercalifragilistic solve their 6th problem. They are on fire!
A very early AC on P6 has given Supercalifragilistic a huge advantage.
12:44pm IST: Top 7 teams have solved 6 problems each.
1:45pm IST: Ranklist has been frozen. The current top 3 teams are:
1. Supercalifragilistic – IIT Madras
2. TDCs – IIIT Hyderabad
3. Majnu – IIT Roorkee
————–
Final Rankings
1. LongTimeNoC – IIT Kanpur
2. Supercalifragilistic – IIT Madras
3. TDCs – IIIT Hyderabad
It’s a wonderful sunny day out here at IIT Kharagpur as we wait for the start of the 2nd ACM ICPC Indian regional of this season – ACM ICPC Kharagpur.
Which team are you rooting for today? Who do you think will win the trophy? Share your thoughts in the comments section!
Live Ranklist: https://www.codechef.com/public/rankings/ACM17KGP
9:24am IST: kgeccoders_11 from Kalyani Government Engineering College get the first accepted submission of the contest! They solve problem P6 – set by the one and only – Mr. Praveen Dhinwa.
9:34am IST: Tesla (IIIT Hyderabad) are the first to solve Problem P2. They lead the ranklist with 2 problems.
9:47am IST: 5 teams have solved P2. TheVindicators from IIT Kharagpur are at Rank 2 now followed by LongTimeNoC from IIT Kanpur at Rank 3.
Just 1 submission on the remaining 9 problems in the past 20 minutes. There are several candidates for the 3rd easiest problem in this contest.
10:14am IST: NDTM from IIT Guwahati solve the 3rd problem (P5). They lead the ranklist now. Some other teams have received WA on the same problem.
10:20am IST: ground floor from IIT Madras are the first to solve Problem P10. They are now at Rank 2.
10:56am IST: LongTimeNoC from IIT Kanpur are the first to solve Problem P9.
10:58am IST: NDTM solve NUMBGAME and lead the ranklist with 4 problems.
11:11am IST: 7 distinct problems have been solved in the contest but the team at the top of the ranklist has solved 4 problems!
11:13am IST: LongTimeNoC from IIT Kanpur lead the ranklist with 4 problems solved and 1 penalty.
11:20am IST: 8 distinct problems solved now. Problem selection is crucial at this stage for all teams.
11:23am IST: Triangulation (IIT Roorkee) solve their 5th problem and move up to 1st place!
Team Triangulation – IIT Roorkee
12:04pm IST: Triangulation solve their 6th problem and extend their lead. They have 5 penalties, however.
LongTimeNoC have 1 penalty and if they solve another problem, they might take the lead from Triangulation.
12:18pm IST: Tesla (IIITH) lead now with 6 problems. Just 3 minutes of gap between Tesla and Triangulation. A very, very close contest!
12:30pm IST: Tesla are on fire – 7 ACs for them now. Triangulation need to catch up.
11:45pm IST: Triangulation solve 7 problems and are on Rank 2 now – 15 minutes behind Tesla on penalty.
1:20pm IST: Ranklist has been frozen.
2:20pm IST: A very exciting contest comes to an end. Stay tuned for the final results!
Welcome to ACM ICPC Kolkata Regional 2016, the last leg regional before the India Final!
Animesh and I will be giving you live updates throughout the contest. Stay tuned!
Live Leaderboard – https://www.codechef.com/rankings/ACM16KOL
Mirror Contest – https://www.codechef.com/KOL16MOS
10:00 IST: Contest has begun.
10:10 IST: FruitSalad is the first team to get an accepted submission. Problem B it is!
10:15 IST: Several teams have got correct submissions on Problem J now! It seems to be the easiest problem in the set.
10:30 IST: Team Whipslash from NSIT is now at Rank 1 with 3 problems solved. They have solved problems B, H and J.
11:00 IST: FruitSalad is the first team to solve 4 problems! They are now leading.
The Mirror Contest has now started as well.
11:25 IST: Team Whipslash and Team n82696 are at rank 2 and 3 respectively with 4 problems each. The top 6 teams have solved 4 problems uptil now.
There are a total of 12 problems in today’s contest. There are 85 successful submissions on J, 71 on B and 49 on H.
We now have 2 Accepted Submissions on Problem E!
An interesting stat – There have been more than 20 Accepted Submissions in Python today. The language has been newly introduced at ICPC this year and it seems to have become quite popular among the participants.
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 Rocket has solved problem A! The problem statement is really interesting
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 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_{i}‘s first 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
© 2009, Directi Group. All Rights Reserved.