Back to School '24

Welcome back everyone! We hope you enjoy the Back to School '24 contest!

The problem setters are NK, 876pol, and Riolku.

Special thanks to X_Ray, Trentium, SuperClash, Josh, dxke02, and Rebirth for testing and feedback on problems!

This contest will be rated for participants with a rating under 2400.

Before the contest date, you may wish to check out the tips and help pages.

You will have 3 hours to complete the contest. After the contest window begins, you may begin at any time. Once you enter the contest, your personal timer will start counting down, and you will be able to submit until 3 hours from when you started, or until the hard deadline (00:00:00 EDT of September 9th), whichever comes first.

After joining the contest, you proceed to the Problems tab to begin.

Here are the parameters of the contest:

Some problems offer partial marks in the form of subtasks.
Number of problems: 6, full feedback (you will see the results of your submissions instantly).
Scoreboard will be hidden, until your window is over. Divulging the contents of the scoreboard to participants who have not finished their window is an offence, the punishments of which are listed below.
Number of submissions allowed per problem: 50.
Ties will be broken by the maximum submission time that increased score with no penalties for multiple submissions.
Problems will be approximately increasing in difficulty. Reading all of the statements is recommended.
Rated for opening the contest. Being able to read the problems will cause the contest to be rated.
Checkers: unless otherwise specified, standard.
It is guaranteed that all problems will be solvable with C++.

We have listed below some advice as well as contest strategies:

Remove all extra debugging code and/or input prompts from your code before submitting. The judge is very strict — most of the time, it requires your output to match exactly.
Do not pause program execution at the end. The judging process is automated. You should use stdin / stdout to perform input / output, respectively.
Python users are recommended to use PyPy 2/3 over Python 2/3 when submitting.

Clarification requests for the contest must be routed through the clarification system provided on DMOJ and not through other channels, including but not limited to Discord and Slack. Furthermore, all clarification requests will be handled the way they normally are in IOI. Note that, in particular, clarification requests must come in the form of yes/no questions.

Due to rampant issues with cheating on contests that have happened recently, any suspicious behaviour during the contest window may result in your rating being impacted negatively. Such behaviour includes but is not limited to:

Divulging the contents of the scoreboard to participants who have not finished their window.
Registering for the contest with at least two accounts.
Participating in the contest with an account that is not your primary account.
During the contest window, talking about the contest in more detail than answering a yes/no question about whether one participated in the contest. This includes but is not limited to posting spoilers about the contest and public speculation of the contest.
Attempting to exploit bugs in the platform to subvert the constraints of the contest.
Attacking the judge infrastructure, other contestants, or contest personnel within or after your window.

Punishments may include performance being unrated or, for more serious infractions, being forcibly ranked at the bottom of the scoreboard.

At the end of the contest, you may comment below to appeal a judging verdict. In the case of appeals, the decision(s) of DMOJ staff is final.

Problems

Problem	Points	AC Rate	Users	Editorials
Back to School '24 P1 - Kicking	5p	33.2%	295	Editorial
Back to School '24 P2 - Cheating	10p	24.7%	201	Editorial
Back to School '24 P3 - Tournament	12	34.2%	135	Editorial
Back to School '24 P4 - Candidates	15p	16.1%	63	Editorial
Back to School '24 P5 - Snitching	15p	12.0%	55	Editorial
Back to School '24 P6 - Rex	20p	17.3%	19	Editorial

Comments

1

farmersrice commented on Sept. 10, 2024, 2:31 a.m.

P5 is nice, but why is the time limit so strict? Very difficult to pass with $(N + Q) \sqrt{N}$ ~(N + Q) \sqrt{N}~, especially at 5e5, that's 0.7e9 which is insane for 3s. I see many submits with sqrt solutions timing out, some in contest. I don't think there's any solution which could be cheesed even if $N, Q \leq 2 \cdot 10^5$ ~N, Q \leq 2 \cdot 10^5~ . My first sqrt solution was unable to be optimized within the TL despite many attempts until I implemented a different sqrt solution. Would love to know the reasoning behind this decision.

5
NK commented on Sept. 10, 2024, 10:08 p.m.
Firstly, I apologize for any difficulties you or others faced with P5. However, I believe the time limit is justifiable for few reasons:

Depending on the language and implementation, it can be extremely fast. During testing, several solutions took only 0.5-0.7 seconds on their maximum test cases, which is about six times faster than the time limit.

During testing, there were also extremely fast $\sqrt{N}\log{N}$ ~\sqrt{N}\log{N}~ solutions that passed with lowered constraints. In fact, constraints were originally set to be $N, Q \le 2 \cdot 10^5$ ~N, Q \le 2 \cdot 10^5~ (with a different TL), but this proved too lenient to differentiate from $\sqrt{N}$ ~\sqrt{N}~. (Additionally, an extremely optimized solution [written by X_Ray orz] made us consider an even lower time limit. However, due to similar concerns as yours, we decided against it.) 

Overall, while I sympathize with you, I stand by the decision. Allowing solutions without the intended time complexity to pass would not have been ideal. Also, I believe this problem can help people understand the power of a good constant factor, as even I was surprised by how fast the algorithm could be. I do not want to clog up the DMOJ comment system with more lengthy explanations, so if you want to discuss further, please join the DMOJ Discord. You can find me there as well. Thanks for participating!

3

X_Ray commented on Sept. 11, 2024, 3:05 p.m. ← edited →

For some additional context for those who are curious, the optimized solution replaced the $\log(N)$ ~\log(N)~ factor with a $\log(\log(N))$ ~\log(\log(N))~ factor (using noimi's FastSet/vEB Tree to support insert, delete, and findMin in $\mathcal{O}(\log(\log(N)))$ ~\mathcal{O}(\log(\log(N)))~ time), which managed to pass with 2.5/3s.

4

leoliu93233 commented on Sept. 2, 2024, 4:30 a.m.

noooooooooooo not school :(

2

Patricc commented on Aug. 29, 2024, 8:54 p.m.

Man I love NK

7

htoshiro commented on Aug. 29, 2024, 4:31 p.m.

the drought is finally over and the thirst is cured

thank you SO SO SO SO MUCH NK an d876pol

5

ostrichthattypes commented on Sept. 1, 2024, 11:59 p.m.

nerd

7

kevlu8 commented on Sept. 2, 2024, 1:54 a.m.

i concur with this slander of htoshiro, as it is very much needed and necessary given the mental trauma he has inflicted upon me

-4

htoshiro commented on Sept. 2, 2024, 12:14 p.m.

would've been better if it was called back to spring break

0

HisMonDon commented on Sept. 1, 2024, 3:08 p.m.

ok lucas

13

weewoo14 commented on Aug. 29, 2024, 2:16 p.m.

NK and 876pol the 🐐s

thanks for the rated contest!