SecondThread's blog

By SecondThread, history, 23 months ago, In English

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.

Full text and comments »

  • Vote: I like it
  • +273
  • Vote: I do not like it

By SecondThread, history, 23 months ago, In English

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.

Full text and comments »

  • Vote: I like it
  • +95
  • Vote: I do not like it

By SecondThread, history, 2 years ago, In English

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.

I wish this blog was more pretty
I'm a true introvert who doesn't want to see a human's face

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

Full text and comments »

  • Vote: I like it
  • +236
  • Vote: I do not like it

By SecondThread, history, 2 years ago, In English

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.

Full text and comments »

  • Vote: I like it
  • +28
  • Vote: I do not like it

By SecondThread, history, 2 years ago, In English

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

Full text and comments »

  • Vote: I like it
  • +203
  • Vote: I do not like it

By SecondThread, history, 2 years ago, In English

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?

Full text and comments »

  • Vote: I like it
  • +93
  • Vote: I do not like it

By SecondThread, history, 2 years ago, In English

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

Rank Handle Country/Region Codeforces Rating Hacker Cup R3 Place tourist factor*
1 tourist Belarus 3870 1 50.00%
2 jqdai0815 China 3681 13 25.20%
3 Radewoosh Poland 3418 2 6.90%
4 Petr Switzerland 3408 4 6.54%
5 maroonrk Japan 3387 11 5.84%
6 ko_osaga South Korea 3334 8 4.37%
7 jiangly China 3334 3 4.37%
8 ecnerwala United States 3325 6 4.16%
9 Egor Germany 3211 23 2.20%
10 Um_nik Ukraine 3189 7 1.95%
11 mnbvmar ???? 3179 5 1.84%
12 duality Canada 3151 9 1.57%
13 Subconscious China 3107 22 1.22%
14 ainta South Korea 3102 16 1.19%
15 snuke Japan 3099 24 1.17%
16 molamola. South Korea 3076 15 1.02%
17 yosupo Japan 3071 12 1.00%
18 dotorya South Korea 3060 17 0.94%
19 heno239 Japan 3051 20 0.89%
20 Sugar_fan China 3018 18 0.74%
21 budalnik Russia 2840 10 0.27%
22 majk Czechia 2828 19 0.25%
23 TadijaSebez Serbia 2800 21 0.21%
24 Suika_predator China 2606 25 0.07%
25 s-quark China 2428 14 0.02%

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

Full text and comments »

  • Vote: I like it
  • +225
  • Vote: I do not like it

By SecondThread, history, 2 years ago, In English

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!

Famous Signings

Signers:

*, **

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.

Full text and comments »

  • Vote: I like it
  • +772
  • Vote: I do not like it

By SecondThread, history, 3 years ago, In English

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))$$$?

Full text and comments »

  • Vote: I like it
  • +106
  • Vote: I do not like it

By SecondThread, history, 3 years ago, In English

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

Full text and comments »

  • Vote: I like it
  • +136
  • Vote: I do not like it

By SecondThread, 3 years ago, In English

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

Full text and comments »

  • Vote: I like it
  • +464
  • Vote: I do not like it

By SecondThread, history, 3 years ago, In English

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.

Full text and comments »

  • Vote: I like it
  • +570
  • Vote: I do not like it

By SecondThread, history, 3 years ago, In English

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.

Full text and comments »

  • Vote: I like it
  • +23
  • Vote: I do not like it

By SecondThread, history, 3 years ago, In English

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!

Full text and comments »

  • Vote: I like it
  • +969
  • Vote: I do not like it

By SecondThread, 4 years ago, In English

Algo Talk

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

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

Full text and comments »

  • Vote: I like it
  • +342
  • Vote: I do not like it

By SecondThread, history, 4 years ago, In English

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:

Full text and comments »

  • Vote: I like it
  • +1924
  • Vote: I do not like it

By SecondThread, history, 4 years ago, In English

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:

Spoiler

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.

Full text and comments »

  • Vote: I like it
  • +21
  • Vote: I do not like it

By SecondThread, 4 years ago, In English

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!

Full text and comments »

  • Vote: I like it
  • +148
  • Vote: I do not like it

By SecondThread, history, 4 years ago, In English

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?

Full text and comments »

  • Vote: I like it
  • +761
  • Vote: I do not like it

By SecondThread, history, 4 years ago, In English

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:

Feel free to post any questions below!

Full text and comments »

  • Vote: I like it
  • +145
  • Vote: I do not like it

By SecondThread, history, 4 years ago, In English

Deleting Comments

Recently I have noticed several of my comments end up deleted. I don't think my comments were unhelpful, spammy, or otherwise something that shouldn't be seen. In fact, I'm quite confident that the reason they aren't there anymore is because the are children in the reply tree to some comment that was deleted earlier up the chain (and it was that comment that was unhelpful or could otherwise be deemed inappropriate).

Here are two examples:

There are some other examples as well of similar nature.

Why/how is it happening?

Who is making these decisions, and on what criteria? To me it isn't obvious. Are there just some special users who have the ability to delete other people's stuff? Is that an IGM/LGM privilege that I just haven't earned yet? Is Mike manually deleting rows in some SQL database every time this happens?

Why subtree delete?

In lots of these cases, I remember interesting and valid things being said by myself and others that are no longer visible. Is it intentional to delete the entire subtree of comments rather than just the egregious one(s)? I suppose for the case of deleting blogs it may be a different story; I can imagine technical difficulties that would arise when trying to hide a blog, but not its comments. But what about comment subtrees?

Full text and comments »

  • Vote: I like it
  • +196
  • Vote: I do not like it

By SecondThread, history, 4 years ago, In English

AlgorithmsThread 6: Convex Hulls

Hi everyone! I just released Episode 6 of AlgorithmsThread (now rebranded from Algorithms Dead after frodakcin's epic suggestion).

In it, I talk about:

  • Getting the convex hull
  • Checking if a point is in a convex hull in $$$O(log(n))$$$
  • Finding the farthest point in some direction in $$$O(log(n))$$$
  • The problem Trash Removal with $$$O(n^3)$$$ -> $$$O(n^2)$$$ -> $$$O(n*log(n))$$$ solutions
  • The more difficult problem Troop Mobilization from ICPC South East Regionals

I hope you enjoy. Feel free to ask questions below, as usual :)

Full text and comments »

  • Vote: I like it
  • +229
  • Vote: I do not like it

By SecondThread, history, 4 years ago, In English

AlgorithmsThread 5: Persistent Data Structures

Hello everyone! I just uploaded Episode 5 of Algorithms Dead in which I talk about persistent data structures. I talk about the ASC problem involving a persistent queue, describe how persistent segment trees work, and provide some interesting problems that can be solved and then optimized with persistent segment trees.

Some problems discussed in this video if you are interested in solving them yourself:

Harder PST problems (not covered in the episode but good practice):

Let me know if you have any questions of suggestions for how I can improve the series!

Full text and comments »

  • Vote: I like it
  • +166
  • Vote: I do not like it

By SecondThread, history, 4 years ago, In English

CF Notifications

Want an easy-to-use tool to notify you when you get a problem correct? Looking for an inspirational jingle to celebrate when you AC? Wish you could just move on to problem B immediately after submitting A and had someone to let you know in case you got it wrong? Now you can!

CFNotifications.com is a simple website that does this for you. All you have to do is type in your handle and click login.

It works on all CF rounds, and also other submissions if you are upsolving, practicing, or running a VP on your own. Personally, I just leave it on a second computer with the volume turned up and then I don't have to worry about it ever.

How it works

It rechecks Codeforces every 4 seconds for new submissions, or every 1 second if you have a submission that is judging. It uses the CF API and I did my best to make sure it is as low-impact to the servers as possible while still giving results pretty much instantly.

Let me know what you think!


Updates!

  • Per request, I added the ability to play a custom sound on AC (or play no sound at all). The changes are live now, so you should be able to see, but basically now you can enter 'none' if you just want the notification that you got the problem right and no 'distracting' inspirational sound effect, or something like 'https://www.youtube.com/watch?v=dZLfasMPOU4' if you want to hear 3 minutes of Stacy's Mom every time you solve a problem!

  • I also made it save your handle (and the custom sound if you choose to use one) as a cookie, so it should be even easier to use. If you have been there before, everything will auto-fill so you can literally just click the button and it's working.

Full text and comments »

  • Vote: I like it
  • +197
  • Vote: I do not like it

By SecondThread, history, 4 years ago, In English

AlgorithmsThread 4: Segment Tree Beats

Segment Tree Beats are a really cool, and fairly advanced, modification you can make to segment trees in order to handle range-min-with queries. I talk about what they are and why they work in Episode 4 of AlgorithmsThread.

Feel free to comment any questions about what I covered in the comments of this blog, and I'll answer them as soon as I get a chance to.


Other Resources

Full text and comments »

  • Vote: I like it
  • +144
  • Vote: I do not like it