Meta Hacker Cup Qualification Round Editorial

Good morning!

As usual, written editorials are available in the solution section of all problems on the Hacker Cup site. I thought this post might also be useful to see what people thought of the problems.

A: Second Hands

• Problem Statement, with written editorial
• Solution Video

B1/B2: Second Friend

• B1 Problem Statement, with written editorial
• B2 Problem Statement
• Moderately Entertaining Solution Video

C1/C2: Second Meaning

• C1 Problem Statement, with written editorial
• C2 Problem Statement
• Solution Video

D: Second Flight

• Problem Statement, with written editorial
• Solution Video

So, what'd you think of the problems?

Meta Hacker Cup Qualification Round

Good morning! The Meta Hacker Cup Qualification Round starts on Friday, August 26th in under 48 hours! If you haven’t yet, be sure to register on the Meta Coding Contests page.

Important info:

• In order to qualify for Round 1, you’ll need to solve at least one problem in this round.
• Once you've registered, you may wish to confirm that the information in your competition profile is up to date, including your display handle and which country you’d like to represent.
• In Hacker Cup, you run your own submissions on your computer, and upload your source code and the output of your source code to be graded. You’ll have 6 minutes to run your code locally and upload your solution, and whether you got the problem correct will be revealed at the end of the contest. Check out the FAQ for more details.

As a reminder, unlike some other multi-round coding contests, you may not share ideas or solutions about the problems with anyone until after the round has ended. We will be disqualifying contestants we believe to have participated illegitimately or shared their solutions or ideas online in any form before the end of the contest.

As usual, the 2022 season will have some great prizes, including 2,000 t-shirts, and cash prizes for all 25 finalists, including a $20,000 grand prize.

We’ve put a lot of work into these problems, and we hope you enjoy the contest. Good luck, and see you on the scoreboard!

Update: Editorial

Good morning everyone! The Hacker Cup team is excited to announce the schedule for our 2022 season, kicking off on August 26th! And for those of you who were wondering, yes–we’ve officially rebranded from Facebook Hacker Cup to Meta Hacker Cup.

• Qualification Round: Fri. Aug. 26th, 10am PDT — Mon. Aug. 29th, 10am PDT (72 hours)
• Round 1: Sat. Sept. 10th, 10am PDT — Sun. Sept. 11th, 10am PDT (24 hours)
• Round 2: Sat. Sept. 24th, 10am — 1pm PDT (3 hours)
• Round 3: Sat. Oct. 8th, 10am — 1pm PDT (3 hours)

To compete, you can register here at any time between now and the end of the qualification round on August 29th.

Stay tuned for more details about the finals, which are expected to happen at the end of 2022, likely in December.

We’ll provide more announcements as we get closer to the start of the season in August. Thanks, and we look forward to seeing you on the Qualification Round’s scoreboard!

ICPC North American Championships Livestream

Good morning! The North American Championship is happening this weekend in Orlando Florida, hosted by the University of Central Florida. The best ICPC teams from North America will be competing to qualify for the ICPC World Finals. Although ICPC won’t be producing a stream themselves, I’ll be creating an in-person stream. Featured guests:

• ecnerwala Andrew He, LGM and ICPC Gold Medalist
• Bill Poucher, ICPC Executive Director
• Dean Michael Georgiopoulos, UCF Dean of Computer Science
• TankEngineer Haobin Ni, IGM and ICPC Gold Medalist
• rpeng Richard Peng, Georgia Tech and North American Programming Camp Coach
• wphsucf Arup Guha UCF Coach
• Friggstad Zach Friggstad U Alberta and North American Programming Camp Coach
• Possibly some ICPC Judges, if permitting

The stream will start at 9:45 Florida time Monday, May 30th, or at this time for you.

We hope to see you there! If you know any of the teams or competitors and have interesting fun facts, you can submit them in this google form.

Thanks everyone for participating. Link to the stream

Good morning!

I just published a video about my performance (+173) on Global Round 20 and the past Div 1 Round. It's heavily edited, only includes highlights, and is definitely more entertaining than the usual screencasts, so I thought I'd post about it here. Go check it out.

Here's the thumbnail!

If you want to see me in the Top 10 Contributors so you don't have to go to my profile to check my color, you know what to do.

Geothermal just got passed 3000 rating after round #783, making him the 5th American LGM (as of when ratings update). This came with a very clutch 1:59:56 solve on problem D, making it even more impressive. He's been a personal friend of mine since we met at an in-person contest in Texas that I drove 17 hours to go to back when he was still purple I believe, so it's great to see him reach this achievement. Well done, Jay, you've earned it.

I've create a private Codeforces mashup and would like to disable manager mode and submit solutions to the ongoing mashup as a contestant. I'm trying to click this button:

Instead of disabling manager mode as expected, Codeforces just refreshes the page, and I stay in manager mode. If it's helpful for debugging, here's a video of it happening.

If I'm using the tool incorrectly (or my account is in an invalid state or something), A) what am I doing wrong, and B) IMO, I think it would be helpful if CF displays an error message or something telling me what the problem is rather than just silently failing.

Good morning! AlphaCode, Google's AI to compete in programming contests, has done some pretty awesome stuff. The engineers who made it also wrote a whitepaper which you can read here. If, like me, you prefer to have it explained to you by somebody else who has already done the reading for you, I made a video explaining what I feel are the important parts.

Anyway, I hope you enjoy the video. As usual, questions, comments, and good mornings are always welcome :)

Good morning!

If you earned a shirt in Facebook Hacker Cup 2021 by placing in the top 2000 of Round 2 and did not yet get an email with a code to claim your shirt, please DM me on CF with the following information:

1. Your place in Hacker Cup Round 2 in 2021 (such as 1999th place)
2. A link to your facebook account (such as https://www.facebook.com/profile.php?id=100008893002051 )
3. The email address linked to your facebook account (such as [email protected])

Pi day, 2022, (March 14th, 2022) will be the last day that we ship 2021 shirts. For the 25 finalists, prizes are handled separately, and you can contact us individually.

Focus is a Virtue

I know current geopolitical events are on the top of a lot of people's minds at the moment. I wish for those involved the safety of their families, land, and heritage. I truly don't mean for this to come off as insincere, insensitive, or trying to diminish the importance of these events to people's personal lives.

But that being said...

Codeforces isn't the place for such debates and politics. I'm not saying these discussions don't need to happen. They do. But them happening on this surface is essentially well-intentioned spam. In particular, beyond the fact that Eastern Europeans and Russians are disproportionately good at competitive programming, this has really nothing to do with competitive programming, with the interests of this community, or with a competitive programming website.

This stuff belongs on social media, or places like Reddit and Discord. Or if, for whatever reason, we feel it really has to happen here, can we please at least keep it to one post, rather than half of the recent actions?

Alright, I've spoken my peace, bring on the flood of downvotes...

Context

Codeforces currently supports embedded Youtube and Twitch livestreams. Hacker Cup Finals is streamed only to Facebook, but I imagine there are lots of people who would like to watch it [or at least would like to know about it] on Codeforces. Unfortunately, it seems unlikely that Hacker Cup would be streamed to Youtube or Twitch in the foreseeable future.

Implementation?

It looks like embedding the stream is as simple as using an iframe, from the little research that I've done on this page, which is about a church for some reason.

I don't know how Codeforces implements this integration, but if it is with an iframe, it might be as simple as a third case to the supported stream link regex.

Why should Codeforces want to add Facebook Livestream support?

Because Hacker Cup is a big-name programming contest. If Codeforces wants to continue to be the place for everything competitive programming related, it would be good to support at least the major CodeJam Finals/Hacker Cup Finals/ICPC World Finals streams, since most competitive programmers are interested in them.

The direct payoff from Codeforces's perspective is that it's support for a major contest and something very beneficial to it's users. The payoff from Hacker Cup's perspective to use this feature is that it provides greater visibility and integration with the community of people who are interested in programming contests. It's clear that there's a huge overlap in Hacker Cup contestants and CF users.

What do you think? Would you like to watch the Hacker Cup Finals stream here?

Good Morning! I'm no Laggy, but I thought I would continue the tradition of making a "Teams" list for the 2021 Facebook Hacker Cup Finals, since I always found the ICPC World Finals lists fun. So here goes!

Facebook Hacker Cup 2021 Finalists

*An individual's tourist factor is defined as the probability that this person would perform better than tourist in a Codeforces round, as predicted by the Elo Rating System.

**Contestants with question marks in their country have not told us which country you wish to represent, and this is my best guess based on your Codeforces profile.

Does CF Rating Predict Hacker Cup Performance?

Here's a graph of the finalists' rating vs. their Round 3 place:

So yes, it's a good predictor, but it certainly doesn't explain everything; it's not out of the question that any competitor could have an unusually good or bad contest, as you would expect.

Post-Contest Livestream (on Facebook)

Yep, be sure not to miss all the excitement in the post-contest livestream, during which Zef and I reveal the final scoreboard! Get excited--I'll see you Saturday!

Good morning! ICPC World Finals just concluded in Moscow. I was lucky enough to be participate representing the University of Central Florida, who finished in a respectable 17th place.

While there, friends, acquaintances, and CF Legends signed my Codeforces sweatshirt in their handle with their current color. The most common request of the people I asked was to show off what it ended up looking like on a blog post of Codeforces, so here that is!

Signers:

• MikeMirzayanov the creator and maintainer of Codeforces and Polygon who deserves our eternal thanks, and Una_Shem without whose work there would be no sweatshirt to sign.
• tourist the legend and best competitive programmer of all time
• Petr the legend and programming philosopher
• Um_nik, KAN, and Ekler* the 2021 ICPC World Finals Champions, (who signed before being such champions), and their coaches vepifanov and ashmelev
• Golovanov399, AndreySergunin, amethyst0 gold medalists from the host university MIPT
• Monogon the contribution overlord whom you should upvote, and his teammate richzli from Perdue
• Benq, sqrtdecompton, and C_SUNSHINE from MIT, with their coach jcvb
• andrewzta legendary coach of ITMO and author of all ASC sets
• davidberard, .rem, ehnryx, from UBC and their coaches zhed and inutard
• RobeZH my friend with whom I had a friendly wager with to race to IGM, and his teammates top34051 and LUL____SEPLED1305* from Wisconsin Madison
• bicsi from the University of Bucharest who came in with the clutch sign 10 minutes before I left
• kpw29**, _h_, and zdolna_kaczka from Cambridge, the most obnoxious competitors I have met in my life
• miagkov** my friend from Stanford who competed against me at unofficial in-person NAP Camp, and his teammate andyshih12**
• brunomont who I've discussed some CF blogs with and his teammate Paniago who appears to have misspelled his own name
• tbuzzelli my friend and Google CodeJam contributor
• TheOneYouWant representing the Indian Institute of Technology, Bombay
• SecondThread me, my teammates Harpae and Xylenox, and my coach wphsucf

Thanks to everyone for signing it! I hope you all had a great time at World Finals, and I'll see you on the scoreboard on the next Codeforces Rounds! It was great to finally meet so many people who I've only seen virtually before in person. If you have any fun pictures from WF that you're itching to share, the comments below are always open.

I started thinking about this during my livestream of the solution to round 731, and discussed this in a comment a bit earlier, but it seems novel enough and might require enough debate that I thought it makes sense to be it's own blog post:

Suppose I have an array $$$a$$$ of $$$n$$$ integers, each up to a million. What is the worst-case runtime of the following code?

int gcd(int a, int b) {
   return b==0?a:gcd(b, a%b);
}

//in main
int gcd=a[0];
for (int i:a) gcd=gcd(i, gcd);

Conventionally, I have always thought it was $$$n*log(MAXVAL)$$$. However, each time the gcd call runs, the answer decreases by an expected factor of about 1.6 (the golden ratio). But really, we only do all $$$log(n)$$$ calls if the gcd gets quite small. In that case, future gcd calls will be $$$O(1)$$$, not $$$O(log)$$$. So do we have a clean potential function like: the number of prime factors in gcd, which can bound the total GCD recursion? I know that this is some very hand-wavey logic, but it seems almost legit enough for me to believe it. Or is this totally not true? I'm secretly wishing it's true because it would be cool, but also I feel like I would have seen this before if it was both commonly known and true.

TLDR: is the above code really $$$O(n + log(MAXVAL))$$$, instead of $$$O(n * log(MAXVAL))$$$?

Good morning everyone!

After the tremendous popularity of our first article, the CF Hot News team is back! This time, we have just come across some irrefutable evidence of hidden operations involving the ICPC 2021 World Finals, provided to us by several top-secret CF sources.

We sincerely hope that these insights can be helpful to all competators optimize their training in the coming months to optimally prepare for the contest.

Please enjoy: https://youtu.be/Xf8DwlipmG4

What other top secret revelations lie undiscovered? I bet the comments will tell us...

SecondThread vs. galen_colin Lockout Duel (ft. neal, stevenkplus)

Good morning everyone!

There are three great unsolved questions on Codeforces that every pupil dreams to one day know the answer to:

• What's the best opening move when playing the Epsilon Guessing Game against a geometry problem?
• How many cyans is Um_nik worth, modulo $$$10^9+7$$$?
• Who is really the 229th best programmer on Codeforces: SecondThread or galen_colin?

While we may never know the answer to the first two, Colin and I will settle the third question once and for all this Sunday in a 1v1 duel! Don't miss it!

Join us at this time on Sunday where we will compete head-to-head in a 1v1 lockout at https://www.twitch.tv/nealwu, with live commentary from neal!

Update: stevenkplus, the initiator of the first Lockout grudge match, will be co-commentating as well! Woohoo!

Update: YouTube video of the duel is posted: https://www.youtube.com/watch?v=WCqs6hbTMJY. Now includes Twitch chat!

Exciting clip of the last minute of the duel -- spoiler alert: https://www.twitch.tv/nealwu/clip/ConfidentGenerousTarsierDoubleRainbow

CF Hot News: Seattle Builds galen_colin orz Statue

Good morning everyone!

We have just received word that the City of Seattle has completed their recently funded galen_colin orz statue. City planners say that this is the latest update in their recent endeavor to honor their favorite CF personalities.

"I'm proud to announce that the galen_colin orz statue has finally reached completion," announced city planner Vasya. "You know, after we decided to shape the space needle as a symbol praising the great Monogon, some of us thought that we would never be able to make such an amazing work of art again. We're truly delighted that we were able to prove all the skeptics wrong with this new piece."

The project was built entirely using renewable energy created by water turbines run exclusively on the tears of java programmers TLEing on system tests. The city hopes that, with enough publicity, the statue might one day become a tourist attraction.

Is the "Update Contest" button for gym contests suppose to work while the contest is going on? I would like to fix a small issue with one of the statements in the ongoing Treap set, and add a testcase to another problem to make a certain solution to TLE. I have updated both statements on polygon, and rebuilt the packages.

When I try to click the "Update Contest" buttons to move these into the live gym set, CF redirects me to the "All your bugs are belong to us" page. Do any problem authors know if this is a known bug, and if so, is there a workaround? It seems like it has been broken for about 10 hours now, so it doesn't look like a transient issue.

Algorithms Thread Episode 9: Treaps

Good morning everyone!

Episode 9 of AlgorithmsThread comes out shortly after the Div2 round ends. This episode is on Treaps! It covers:

• Fundamentals of Treaps
• Splitting and Merging
• Range reversing

... and more! I also decided to keep up the super-high quality style and made a custom gym set with 5(+2) original problems to make sure you really understand everything that was covered in the lecture. The gym set will be released shortly after the lecture ends, and I hope that the problems will be challenging and fun, even for people who aren't seeing treaps for the first time.

If you have any questions or suggestions, feel free to leave them below. I hope you enjoy the problem statements, and, in the spirit of the upcoming holiday, I'll leave you all with this:

Update: The scoring distribution for this round will be: 1 — 1 — 1 — 1 — (+1) — (+1) — 1

Update2: Solution video is out now and solutions to all problems are available here. Hope you all enjoyed the contest!

Algo Talk

Good morning everyone! Errichto and I each just released new videos in which we discuss some cool problems:

• On his channel, we discuss a very neat problem which he wrote called Parades

• On mine, we talk about the 2006 IOI problem Joining Points, which has a quite beautiful solution, as well as the more general version of it

Please check them out and let us know what you think. More will be coming soon!

Algorithms Thread Episode 8: Tree Basics

Episode 8 of Algorithms Thread comes out in <90 minutes! This one is a bit more beginner-friendly and covers the following ideas:

• Graph/Tree Diameters
• Binary Lifting
• Tree Flattening with Euler tours

Also, to make sure you have actually learned that stuff, I made a custom Gym set on CodeForces that will last two weeks that hopefully is really good practice for making sure you have learned this stuff. Here is a link to the gym set; it will be available 45 minutes after the video comes out so that people have time to watch the video before starting the set, if they are interested in penalty points. All of the problems in the gym are original to this set (in their flavortext at least, some are simple enough that I'm sure they have appeared in other contests before).

The new gym integration was heavily inspired by Errichto's Matrix Expo set format. Let me know whether it's helpful. I think it might be, but also it's a pretty big time commitment to make it, so whether I keep doing them depends on how helpful they are to people.

If you have any questions or suggestions, feel free to leave them below. I hope you enjoy the problem statements, and I'll leave you all with this:

Solutions

Update:

• Video solutions to all problems

• Github containing solutions to all problems and data generators

Brookfield Computer Programming Challenge (BCPC)

Hi everyone!

TLDR: Speedrunnable contest here, bad solution videos + original standings here.

Last week I learned how to use Polygon, so I uploaded and regenerated data/solutions to the first contest I ever wrote, and uploaded it to the gym. The final score of the original contest is available here. In the original contest, the last problem was only unlocked after solving everything else (which no teams did). Originally this was a set for high school students in Wiscosin, but I thought some people here might enjoy speedrunning it.

Solution videos are also available here. They aren't very good because I was a young child when I made them, but they should at least convey the main ideas pretty well. The one interesting thing to mention is:

For problem LAST Robotics:

I hope you enjoy! Let me know if there are any technical issues, because those may indicate that I've set something up incorrectly, which was kind of the main thing I was trying to avoid here.

TLDR: Stream at this time! See you there!

Hi everyone! I very recently reached 1<<12 subscribers on Youtube! To celebrate, I'm going to be doing my first ever livestream! I'll be on Youtube only this time (maybe I'll do both youtube and twitch later if there's demand for it). The stream will include looking at and trying to solve Code Jam Finals problems, which will be going on at the same time. In general, live-streaming participation in a contest is considered cheating and is very bad. Do not do this for any public contests!

To be careful not to leak solutions or anything:

1. I will significantly delay my start of the round.
2. I will spend the beginning of the contest (where my participation overlaps with the real thing) reading all problems instead of solving.
3. I will not explain solution ideas of any problems until the round is over.

That way, this isn't any more revealing than the ICPC NAC Livestreams which present solution sketches to easy and medium problems on the stream and expect the small number of participants to be honorable. Besides, if a finalist actually wanted to be a bad sport, there are much better ways than trying to get some tiny amount of info from me. (I won't give ideas here, but I'm sure you can think of some)

Cool, hopefully I'm morally redeemed! I'll also be doing some other stuff, unrelated to Code-jam, like upsolving problems from the Div2, answering random questions if people have them, and maybe even setting up some stuff for a super-cool open source project that I know Codeforces will be hyped about!

I'll start streaming at whatever this time is for you on my Youtube channel SecondThread. Hope to see some of you there!

Update: Tech check went well, see everyone soon!

Unrated Account Disaster

Recently there have been an obscene number of unrated accounts showing up. Several of them have inappropriate names, so I won't give examples because I want to keep this post clean, but I'm sure you have seen them in the comments. They are likely all by the same individual, possibly with a few copy-cat troublemakers as well.

Recently, certain ones have begun to spam useless comments on old posts to clog up the recent actions, effectively hiding all relevant conversations except on the blog posts they spam on. For whatever reason, these are overwhelmingly on Errichto's old blog posts. Occasionally there are also a flood of obscene blog posts made by the user themselves.

Here's an example of what I mean:

This is obnoxious and I would like to see it stop.

The current solution clearly doesn't work. As soon as they get banned or muted or whatever, they can just make another throw-away account and continue spamming tomorrow.

A slightly less extreme problem is that lots of new users have created alt accounts in order to ask fairly meaningless 'How do I get better', 'please solve this problem for me', et cetera type of questions.

Suggested Solution

Make it so that users who haven't competed in any contests don't have permissions to post blogs or comments. At the very least, this should deter a lot of these fake accounts from being created.

What about legit accounts who don't compete?

I know there are a few accounts used by companies/media which are used for public announcements, for instance: NercNews. In cases like this, if it is actually a legitimate news source, we can 'trust' these users with the GM 'trust this user' feature. As far as I know, there aren't really that many accounts like this that are run by large companies/media organizations. I think each of them should be able to find at least one GM who is either a part of the organization or can verify that the organization is trustworthy enough to not intentionally spam Codeforces.

Do you agree? If so, can you please tag some people who would have the ability to fix this so that this post actually gets noticed within the haystack of worthless spam?

AlgorithmsThread Episode 7: All Point Pairs

Hi everyone! I just published Episode 7 of AlgorithmsThread, which talks about processing all pairs of points, while keeping the rest of the points sorted in a helpful way. I talk about the following problems in it:

• Biggest Triangle in a set of points
• Smallest Triangle in a set of points
• Number of pairs of non-intersecting triangles
• Minimum Area Quadrilateral in a set of points

I find this to be a really helpful trick that isn't super well known, so feel free to check it out if any of these sound like things you want to learn!

Problem Links:

• Biggest/Smallest triangle
• Number of pairs of non-intersecting triangles
• Smallest area 4-gon

Feel free to post any questions below!