myst-6's blog

By myst-6, history, 3 weeks ago, In English

Hello Codeforces! Me and yud08 are excited to invite you to take part in Codeforces Round 982 (Div. 2), which starts on Oct/26/2024 17:35 (Moscow time). You will be given 5 problems and 2 hours to solve them. Two problems are divided into two subtasks.

This round will be rated for all participants whose rating is strictly below 2100.

The problems were authored by me and yud08, and prepared by me.

We would like to thank:

We hope you enjoy the problems!

Score Distribution: $$$500 - 1000 - 1250 - (1250 + 1000) - (2000 + 1000)$$$

We actually wanted to continue the trend of posting photos of contest writers, but we could only find one photo containing both of us, which was a group photo that we took with some other UK informatics people! (I'm the one in the back of the picture who is wearing the MHC T-shirt and yud08 is the one whose head is popping out from the left side of the photo.)

20240921-153321

UPD1: Congratulations to the winners of the contests:

Div 1:

  1. jiangly
  2. neal
  3. SSerxhs
  4. A_G
  5. kotatsugame

Div 2:

  1. nathan_higgs
  2. purupurupururin
  3. Nonoze
  4. Hong_Meiling
  5. Nika_Tamliani

Also, first solves! (if any of these are wrong please let me know)

UPD2: Editorial is available here

Full text and comments »

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

By myst-6, history, 2 months ago, In English

The British Informatics Olympiad (BIO) is the UK's national computing challenge used to select students for the IOI, EGOI and WEOI. It is through this competition that I met most of my friends today. I feel privileged to have attended the finals twice, and as a result, represented the UK at the WEOI twice.

However, one issue I encountered during my first year of attempting this competition is the lack of helpful resources available online. There are a few YouTube video explanations, but for the vast majority of past problems from this competition, there are no editorials or model code.

That’s why I decided to create BIO Helper, a website dedicated to helping students prepare for both rounds of the competition by providing editorials and model code. With the help of many volunteers listed on the website (including, but not limited to, other BIO finalists), we now have a large proportion of Round 1 problems covered, along with a good number of Round 2 problems, with many more to come.

I want to share this site with as many people as possible so that more people can learn about competitive programming and find it easier to prepare for the BIO competition.

The website is relatively new, and we plan to add many features soon, including a grading system for Round 1. While there is publicly-available test data online, testing programs can be tedious, as it involves copying inputs, comparing outputs, and tallying points manually. Therefore, we plan to introduce a system where you can submit code, automatically receive your score, and see which test cases (if any) you failed. (Please note that in no way is this related to the official competition, during which participants will NOT be able to submit their code to be tested against any complete test data. This will just be a tool used for convenience during practice).

Finally, this project is open source, so if you find any bugs or have suggestions for improving the site, feel free to provide feedback by raising an issue on our GitHub.

Thank you for reading, and please don't forget to spread the word to those who you think may benefit from using this!

Full text and comments »

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

By myst-6, history, 7 months ago, In English

Hello Codeforces! Over the weekend I attended the British Informatics Olympiad final. Today I'd like to share my CP journey so far, some thoughts on how it was, and my plans going forward.

I started programming in general when I was 12; I learned JavaScript from an old book that was lying around in my house and wrote some small websites — as a lot do when starting out — and generally dabbled in whatever interested me.

Through the COVID lockdown I played multiplayer video games with some school friends such as Minecraft, and played various JRPGs with my sister such as Tales of Symphonia. I took a hiatus from programming but towards the end of the lockdown and as in-person school began to start, I decided to pick it back up again.

In April of 2021, I signed up to Codewars. I wouldn't describe this website as a competitive programming — problems feel less math-y and (usually) don't require complex algorithms but instead focus on implementation skills and knowledge language features. A personal favourite of mine is this!

I began with the easier problems, and on my way to climbing the ranks I learned some basic algorithms like Dijkstra's and A*, and some simple DP like knapsacks. I hit the second-highest rank, 1 dan, just before my 16th birthday.

When I first discovered the British Informatics Olympiad (BIO) at the start of 2022 when it was advertised by a newly-hired computer science teacher at my school, I tried some past papers and was surprised by my relatively consistent high scores. I decided to go straight for it, not knowing much about CP.

Luckily, the second question was an implementation-heavy problem similar to many Codewars questions I had done before, and I scored highly on it! I ended up just on the lower end of the score threshold and was invited to the finals. I was overjoyed, yet did not expect much of my to-be-performance; when I attempted the past questions on the website, I could barely solve any of them and didn't know where to find resources.

In the email invitation, we were suggested to use the USACO training gateway to learn the important concepts. Looking back on it, it's quite an outdated website and I don't know why they still recommended it to me, lmao. Anyhow, I progressed on that as far as I could as I didn't know of any better resources.

A week before the finals, I discovered Codeforces and manage to participate in two contests — two Div.2 contests where I solved two problems and one problem respectively — a foreboding for what I thought my performance would be like at the competition I was about to go to.

As my first time visiting Cambridge, where the finals was hosted, I couldn't tell you how nervous I was. I was expecting it to be an intimidating experience, and to fall behind the others. Yet it was an amazing weekend and I had so so much fun — especially because of the people I met, which I will certainly mention later in this blog.

After the contest day, I knew I didn't make the IOI team. Yet, at the closing ceremony, it was announced that a new Olympiad had been formed — the WEOI, and I had been selected as the 6th team member! Having been selected for this, I didn't want to let the organisers down — I needed to prepare for it, and try my best to get some kind of medal!

I went back on Codeforces and managed to get to the Expert rank after my 5th contest at exactly 1600 rating. I stayed there until the WEOI, at which time I was rated 1760. I can still say that going there was one of the most fun weekends of my life, and I came away with a bronze medal, which I was very proud of myself for getting :)

With a new sense of motivation, I returned to Codeforces with a new aim: to get onto the IOI team next year. A month later I reached CM and after just two more months, I hit Master. I looked back on my first contests where I solved a single problem and saw how far I came.

With school starting again, I continued to practice at a slower rate since I had less free time on my hands as this was now the last year of high school. Skipping forward to December, where the first round of the BIO was now held again, I participated and received an invitation to the finals yet again. This time, I was more confident in my skills and knew I had what it took to get onto the team.

Contrary to the year before, I solved every past question that was available to me on the closed-access grader which we were all given to help in our preparation. And at last we end up at the weekend which just passed; this year's finals.

It was just as fun as last year, if not more fun, since I knew more about what was happening and was excited to meet again with similar faces from last year. I went into the contest with high hopes and tried to stay calm as it was the moment that I had been preparing for almost the last year.

In the end, I did not do as well as I had hoped to do in the contest. I only managed to solve a single problem, the same performance as last year. Due to a submission limit of 5, I failed to solve a DP question which I had a bug on, and I couldn't get enough constant optimisation for the third problem I had a solution to, to pass. I had failed to get into the IOI team, and I was devastated. I tried to forget about it and convince myself that I wasn't upset, but deep down I was.

The past year, my motivation for studying was getting to go to IOI and having a chance at winning a medal. With the chance of that now gone, I didn't know what to do, or what to think.

I got home, and I thought long and hard about why I did was what I was doing. I thought back to how I begun — how I would study long and hard, spending lots of time solving problems on Codewars without any motivation of getting any medals or accolades — just for fun. It was then that I realised that I lost track of the reasons why I do what I do.

I love competitive programming, and this failure isn't going to stop me. I'm going to keep learning because it's what I love doing! And next year, I'll participate in the ICPC and try my best, not making it a life-or-death situation to win anything.

Most importantly, the people I met along the way made the entire thing SO worth it. That's why I'd like to give a HUGE thanks to all of these people for being such great friends and supporting me:

  • erekle, for being someone who I look up to and who I asked many times for advice and who always happily responded.
  • L3ungj and sammyuri, for being the two contestants I spoke to the most at the Olympiad, and who I endured a long journey back to London with — and for agreeing to possibly being on the same ICPC team as me next year!
  • Jasonwei08, for inviting me to participate in team contests together, and for always supporting me on my IOI journey.
  • yud08, kflippy and others, for starting conversations with me on discord and being great people to talk to.
  • All the finalists, of which I'll try to mention as many as I can of here (but regrettably I won't be able to get all of them), for making the weekend as fun as it could have been: OliaVolia, vladimirfilip, macaquedev, darysani, garamlee500 and anango

Lastly, huge congratulations to those who made it onto the UK's IOI and EGOI teams for this year. I'll leave it for another user's more dedicated blog post to mention their names as it's not my place, but they all deserve it massively and I wish them great success for this year (and for three of them, the next year(s) as well!).

Full text and comments »

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

By myst-6, history, 11 months ago, In English

I'm back with a strange error... I came back on codeforces recently to see that my solution for problem E in the most recent educational codeforces round had failed the system tests.

I had the correct algorithm, and I was stuck debugging my code for ages until I submitted a new piece of code which was almost exactly the same and it got accepted. This gets WA, and this gets AC. The only difference in the codes, is that in the second program, I casted a size_t to a long long before multiplying it to n.

Original: ans += s[i].size() * n;

Modified: ans += (long long) s[i].size() * n;

I wouldn't think it would be an overflow error since size_t is the same as unsigned long long (unless it isn't? — but it is on my machine). This doesn't get marked as an overflow error by the codeforces diagnostics either. What is happening here?

Full text and comments »

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

By myst-6, history, 15 months ago, In English

I was practising earlier today on this problem from the most recent contest. When I use a bitset of size 5005, I get a memory usage of 3688KB. When I use a bitset of size 50005, I get a memory usage of 31168KB. When I use a bitset of size 400005, I get a memory usage of a huge 244924KB! But then, if I take the bitset operations outside of the recursive function call, even with a bitset of size 400005, I get a memory usage of only 796KB!

Inside my recursive function, I am defining no new variables except a single long long and a single int — to my knowledge, combined with an absolute worst of 5000 function calls, this should only yield around 60KB of extra memory usage compared to a blank dfs. Obviously I am wrong. But I am confused — I am not declaring any new bitsets inside the recursive function, so why does the memory usage spike so high, and why does it depend on the size of the bitset?

If anybody understands why, I would be grateful for you to leave an explanation in the comments. Thanks

Full text and comments »

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