crazySegmentTree: Segment Tree implementation with 5x faster queries than bottom-up tree Hello, Codeforces! A few days ago [user:MohammadParsaElahimanesh,2021-04-06] posted a blog titled [Can we find each Required node in segment tree in O(1)?](https://mirror.codeforces.com/blog/entry/89377) Apparently what they meant was to find each node in $\mathcal{O}(ans)$, according to [ecnerwala's explanation](https://mirror.codeforces.com/blog/entry/89377?#comment-777885). But I was too dumb to realize that and accidentally invented a parallel node resolution method instead, which speeds up segment tree a lot. A benchmark for you first, with 30 million RMQ on a 32-bit integer array of 17 million elements. It was run in custom test on Codeforces on Apr 6, 2021. - **Classic implementation from cp-algorithms:** 7.765 seconds, or 260 ns per query - **Optimized classic implementation:** (which I was taught) 4.452 seconds, or 150 ns per query (75% faster than classic) - **Bottom-up implementation:** 1.914 seconds, or 64 ns per query (133% faster than optimized) - **Novel parallel implement...

Full text and comments »

Register for the Montgomery Blair Informatics Tournament (mBIT) 2020 Fall Round! If you are interested in participating in the **Montgomery Blair Informatics Tournament (mBIT)**, which will be held online from [12:00-4:00 PM EST](https://www.timeanddate.com/worldclock/fixedtime.html?msg=Montgomery+Blair+Informatics+Tournament+%28mBIT%29+Fall+2020+Round&iso=20201114T12&p1=263&ah=4) on **Saturday, November 14 (11/14/20)**, please register at https://mbit.mbhs.edu/. The contest will be hosted on our personal servers at https://mbit.live/. All problems were written by the [Montgomery Blair HS Computer Team](https://mirror.codeforces.com/ratings/organization/2457), including [user:12tqian,2020-10-28], [user:gabrielwu,2020-10-28], [user:galen_colin,2020-10-28], [user:smax,2020-10-28], [user:meiron03,2020-10-28], [user:Blastman,2020-10-28], [user:czhang2718,2020-10-28], and [user:csytrn,2020-10-28]. Special thanks to [user:balbit,2020-11-12] for spending hours test solving our hardest problems! mBIT is split into two divisions: **Standard** and **Advanced**. Teams may choose ...

Full text and comments »

Montgomery Blair Informatics Tournament 2021 Spring Round (Registration live!) **Competitors can join our Discord server [here](https://discord.gg/CuWRkC8pG5)**. The [Montgomery Blair HS Computer Team](https://www.mbhscompteam.org/) is proud to present the fourth iteration of the semi-annual **Montgomery Blair Informatics Tournament (mBIT)**, which will be held online from [10:00 AM — 2:00 PM EDT](https://www.timeanddate.com/worldclock/fixedtime.html?msg=Montgomery+Blair+Informatics+Tournament+%28mBIT%29+2021+Spring+Round&iso=20210612T10&p1=263&ah=4) on **Saturday, June 12 (6/12/21)**. If you are interested in competing, please register at https://mbit.mbhs.edu/. The contest will be hosted on our personal servers at https://mbit.live/. All problems were written by the Montgomery Blair Computer Team, including [user:12tqian,2021-01-01], [user:gabrielwu,2021-04-01], [user:galen_colin,2021-05-14], [user:smax,2021-05-14], [user:meiron03,2021-05-14], [user:Blastman,2021-05-14], [user:alien_lover,2021-05-14], [user:czhang2718,2021-06-05], and [user:csytrn,2021...

Full text and comments »

Results and Editorial for mBIT 2021 June Round **UPD: Editorials have been released!** Thank you to everyone who participated in the mBIT Spring 2021 competition today! All of the information on this blog post is also available in our [archive](https://mbit.mbhs.edu/archive/2021s/), which includes the full leaderboard. Problems and Editorials ================== Test your solutions on our Codeforces Gyms: [Standard](https://mirror.codeforces.com/gym/103110), [Advanced](https://mirror.codeforces.com/gym/103109) - [Standard problems](https://mbit.mbhs.edu/archive/2021s/standard.pdf) / [Standard solutions](https://mbit.mbhs.edu/archive/2021s/standard_editorial.pdf) - [Advanced problems](https://mbit.mbhs.edu/archive/2021s/advanced.pdf) / [Advanced solutions](https://mbit.mbhs.edu/archive/2021s/advanced_editorial.pdf) Results ================== First, we would like to congratulate the team **Texas** _(Adam Bertelli, Dilhan Salgado, Zack Lee)_ for being the first team to find all of the Among Us references hidden in the problems! Wi...

Full text and comments »

mBIT 2025 Editorial Thank you to everyone who competed in mBIT 2025! It was a record breaking year for us with 84 in-person participants and 135 online participants. We hoped you guys enjoyed it as much as we did. We tried hard to make the problems fun and interesting for as wide of a skill gap as possible. In fact, this year's competition had an in-person team of middle schoolers that was unfamiliar with for loops, and an online team with all three participants in the top 15 in the world in codeforces. We are glad to contribute to all niches of the computer science community: beginner and advanced, local and global. Thank you all for your enthusiasm. Congratulations to the winners: **Online Advanced:** - 1st place — HoMaMaOvo — Masaki Nishimoto, Riku Kawasaki, Yui Hosaka - 2nd place — mathforcesbox — Brian Xue, Bing-Dong Liu, Alex Chen - 3rd place — bluepuppygreenturtle — Rain Jiang, Kai Jiang **Online Intermediate:** - 1st place — NULP Lega...

Full text and comments »

Montgomery Blair Informatics Tournament (mBIT) Spring 2022 Round **Reminder that the contest starts in 10 minutes!** <div style="text-align: center;"> <img src="https://i.ibb.co/YyrtJ2w/Screenshot-2022-04-23-145543.png" width="50%" class="center"> </div> The [Montgomery Blair HS Computer Team](https://compteam.mbhs.edu/) is excited to present the fifth edition of **Montgomery Blair Informatics Tournament (mBIT)**, which will be held online from [1:00 PM &mdash; 4:00 PM EDT](https://www.timeanddate.com/worldclock/fixedtime.html?msg=mBIT+Spring+2022&iso=20220522T13&p1=263&ah=3) on **Sunday, May 22 (05/22/22)**. Note that the contest is 3 hours long this year. If you are interested in competing, please register at [https://mbit-live.mbhs.edu/](https://mbit-live.mbhs.edu/). All problems were written by the Montgomery Blair Computer Team, including [user:csytrn,2022-04-23], [user:czhang2718,2022-04-23], [user:-DanTheMan-,2022-04-23], [user:gabrielwu,2022-04-23], [user:jh0, 2022-05-08], [user:nachoz,2022-04-23], and [user:susp,2022-04-23]. S...

Full text and comments »

Results and Editorial for mBIT 2020 November Round Thank you to everyone who participated in the mBIT Fall 2020 competition today! All of the information on this blog post is also available in our [archive](https://mbit.mbhs.edu/archive/2020f/), which also includes the full leaderboard. Problems and Editorials ================== Test your solutions on our Codeforces Gyms: [Standard](https://mirror.codeforces.com/gym/102859), [Advanced](https://mirror.codeforces.com/gym/102824) - [Standard problems](https://mbit.mbhs.edu/archive/2020f/standard.pdf) / [Standard solutions](https://mbit.mbhs.edu/archive/2020f/standard_editorial.pdf) - [Advanced problems](https://mbit.mbhs.edu/archive/2020f/advanced.pdf) / [Advanced solutions](https://mbit.mbhs.edu/archive/2020f/advanced_editorial.pdf) Results ================== We are pleased to announce the winners! ### Advanced Division Winning Teams: 1. **Zagreb Oblutci** (HS team) &mdash; _Dorijan Lendvaj (XV. gimnazija Zagreb), Krešimir Nežmah (XV. gimnazija Zagreb), Patrick Pavić (XV. gimnaz...

Full text and comments »

Register for the Montgomery Blair Informatics Tournament 2020 Online Round! If you are interested in participating in the Montgomery Blair Informatics Tournament, which will be held **online** from [1:00-4:00 PM EDT](https://www.timeanddate.com/worldclock/fixedtime.html?msg=Montgomery+Blair+Informatics+Tournament+2020+Online+Round&iso=20200607T13&p1=263&ah=3) on **Sunday (6/7/20)**, please register at https://mbit.mbhs.edu/. Teams of up to 4 are allowed! Anyone can compete, but only teams of US high school (or middle school) students can win Amazon gift cards for prizes: - $50 per person for 1st place in Advanced Division - $25 per person for 1st place in Standard Division, 2nd place in Advanced Division, and 3rd place in Advanced Division If you want to get a sense of what mBIT problems are like, take a look at the problems from our contest last November: - [Rookie (Standard) problems](https://mbit.mbhs.edu/archive/2019/rookie.pdf) | [Rookie solutions](https://mbit.mbhs.edu/archive/2019/rookie_editorial.pdf) | [Test Rookie solutions here](https...

Full text and comments »

Montgomery Blair Informatics Tournament 2025 And... We're back! The [Montgomery Blair HS computer team](https://compteam.mbhs.edu/) is excited to present the seventh edition of the **Montgomery Blair Informatics Tournament (mBIT)** &mdash; mythology edition!  Just like last year, we will be holding the competition in a dual format. We will have an in-person competition at [Montgomery Blair High School](https://maps.app.goo.gl/HLt87qKPKiH9Zock8) open to middle school and high schoolers, and an online mirror hosted here on Codeforces and open to everyone. **Details** - Sunday, June 1st, 2025 - In-person event: 10 AM &mdash; 3:30 PM EST - Competition time: [11 AM &mdash; 2 PM EST](https://www.timeanddate.com/worldclock/fixedtime.html?msg=Montgomery+Blair+Informatics+Tournament&iso=20250601T11&p1=263&ah=3) - Teams of up to three - Three divisions - $800+ total prize pool plus t-shirts For the first time, we will be offering three ...

Full text and comments »

Crafting Farmer John — My USACO Problemsetting Experience Hello Codeforces! If you've somehow been living under a barn, [USACO](https://usaco.org/) is the largest online competitive programming contest for the USA high school students. As I myself am a USA high school student about to graduate, I'd like to reflect on my experience with contributing problems to USACO. By the way, I don't select problems that end up on each contest &mdash; I just contribute possible candidates. Also, I guess this is inspired by [user:xiaowuc1,2025-01-30]'s [blog](https://mirror.codeforces.com/blog/entry/113687), who also used to be a pretty active USACO problemsetter. The difficulty column is purely based on **my own opinion**. <table> <thead> <tr> <th> # </th> <th> Problem </th> <th> Contest </th> <th> Difficulty </th> <th> Comments </th> </tr> </thead> <tr> <td> 1 </td> <td> <a href="https://usaco.org/index.php?page=viewproblem2&cpid=1255">Circular Barn</a> </td> <td> Silver, 2022 December<...

Full text and comments »

Montgomery Blair Informatics Tournament 2024  The [Montgomery Blair HS computer team](https://compteam.mbhs.edu/) is excited to present the sixth edition of the **Montgomery Blair Informatics Tournament (mBIT)**! The contest will be held both in-person at Montgomery Blair High School and online right here on Codeforces! For space reasons, in-person is only available for pre-college participants. The contest will take place from [11:00 am &mdash; 3:00 pm EDT](https://www.timeanddate.com/worldclock/fixedtime.html?msg=mBIT+2024&iso=20240608T11&p1=263&ah=4) on Saturday June 8th. The competition is for **teams of up to 4 competitors.** Anybody may compete &mdash; in the past, mBIT has drawn both complete beginners and world class participants. The competition is split into two divisions: Standard (recommended for rating <= 1900) and Advanced (recommended for rating > 1900) to support all levels. All problems were written by the Montgomery Blair Compute...

Full text and comments »