xiaowuc1's blog

By xiaowuc1, 2 weeks ago, In English

Hi all,

The final contest of the 2023-2024 USACO season will run from March 15th to March 18th. Good luck to everyone! Please wait until the contest is over for everyone before discussing anything contest-related (including but not limited to your scores or anything about the problems).

For those unfamiliar with the USACO contest format, please refer to the contest instructions and rules. We provide a short FAQ but folks should read all the rules carefully.

I have a question about the contest. Where do I ask it?

Email the contest director via the instructions above. Do not post anything publicly about the questions (including but not limited to your scores, how you felt about the problems, any content of the problems, etc) until after the contest is over for everyone. Do not DM me or anyone else affiliated with USACO, only the contest director can assist you. The contest director does not monitor Codeforces, this blog post is merely a courtesy to inform other people of the contest.

When can I enter the contest?

The contest will open on March 15th.

If I submit multiple programs, which one gets evaluated?

Only the last submission will be evaluated for official scoring purposes.

Can I use prewritten code / templates?

No.

Can I use AI tools during the contest including but not limited to ChatGPT and Copilot?

No.

Am I allowed to use outside resources during the contest?

You may only refer to language documentation.

Can I solve problems in Rust?

No, the only languages supported are C, C++, Java, and Python. Consult the instructions for language-specific technical details.

Will Rust support be added?

Probably not. Petition IOI to add Rust support first.

Full text and comments »

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

By xiaowuc1, 7 weeks ago, In English

Hi all,

The third contest of the 2023-2024 USACO season will run from February 16th to February 19th. Good luck to everyone! Please wait until the contest is over for everyone before discussing anything contest-related (including but not limited to your scores or anything about the problems).

For those unfamiliar with the USACO contest format, please refer to the contest instructions and rules. We provide a short FAQ but folks should read all the rules carefully.

Note: The USACO website has been switched over to HTTPS and some other upgrades have happened since the last contest.

I have a question about the contest. Where do I ask it?

Email the contest director via the instructions above. Do not post anything publicly about the questions (including but not limited to your scores, how you felt about the problems, any content of the problems, etc) until after the contest is over for everyone. Do not DM me or anyone else affiliated with USACO, only the contest director can assist you. The contest director does not monitor Codeforces, this blog post is merely a courtesy to inform other people of the contest.

When can I enter the contest?

The contest will open on February 16th.

If I submit multiple programs, which one gets evaluated?

Only the last submission will be evaluated for official scoring purposes.

Can I use prewritten code / templates?

No.

Can I use AI tools during the contest including but not limited to ChatGPT and Copilot?

No.

Am I allowed to use outside resources during the contest?

You may only refer to language documentation.

Can I solve problems in Rust?

No, the only languages supported are C, C++, Java, and Python. Consult the instructions for language-specific technical details.

Will Rust support be added?

Probably not. Petition IOI to add Rust support first.

Full text and comments »

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

By xiaowuc1, 2 months ago, In English

NOTE: The USACO website has been targeted by a DDoS attack and may be down for the duration of the contest.

Hi all,

The second contest of the 2023-2024 USACO season will run from January 26th to January 29th. Good luck to everyone! Please wait until the contest is over for everyone before discussing anything contest-related (including but not limited to your scores or anything about the problems).

For those unfamiliar with the USACO contest format, please refer to the contest instructions and rules. We provide a short FAQ but folks should read all the rules carefully.

I have a question about the contest. Where do I ask it?

Email the contest director via the instructions above. Do not post anything publicly about the questions (including but not limited to your scores, how you felt about the problems, any content of the problems, etc) until after the contest is over for everyone. Do not DM me or anyone else affiliated with USACO, only the contest director can assist you. The contest director does not monitor Codeforces, this blog post is merely a courtesy to inform other people of the contest.

When can I enter the contest?

The contest will open on January 26th.

If I submit multiple programs, which one gets evaluated?

Only the last submission will be evaluated for official scoring purposes.

Can I use prewritten code / templates?

No.

Can I use AI tools during the contest including but not limited to ChatGPT and Copilot?

No.

Am I allowed to use outside resources during the contest?

You may only refer to language documentation.

Can I solve problems in Rust?

No, the only languages supported are C, C++, Java, and Python. Consult the instructions for language-specific technical details.

Will Rust support be added?

Probably not. Petition IOI to add Rust support first.

Full text and comments »

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

By xiaowuc1, 4 months ago, In English

Hi all,

The first contest of the 2023-2024 USACO season ran from December 15th to December 18th. Good luck to everyone! Please wait until the contest is over for everyone before discussing anything contest-related (including but not limited to your scores or anything about the problems).

There are some new rules regarding the platinum division of USACO, please refer to the website regarding the updates, especially if you are trying to be invited to the USACO training camp.

For those unfamiliar with the USACO contest format, please refer to the contest instructions and rules. We provide a short FAQ but folks should read all the rules carefully.

I have a question about the contest. Where do I ask it?

Email the contest director via the instructions above. Do not post anything publicly about the questions (including but not limited to your scores, how you felt about the problems, any content of the problems, etc) until after the contest is over for everyone. Do not DM me or anyone else affiliated with USACO, only the contest director can assist you. The contest director does not monitor Codeforces, this blog post is merely a courtesy to inform other people of the contest.

When can I enter the contest?

The contest will open on December 15th.

If I submit multiple programs, which one gets evaluated?

Only the last submission will be evaluated for official scoring purposes.

Can I use prewritten code / templates?

No.

Can I use AI tools during the contest including but not limited to ChatGPT and Copilot?

No.

Am I allowed to use outside resources during the contest?

You may only refer to language documentation.

Why didn't I get an email from USACO when I registered my account?

Follow the directions on the USACO website regarding Gmail Delivery Issues to contact the contest director.

Can I solve problems in Rust?

No, the only languages supported are C, C++, Java, and Python. Consult the instructions for language-specific technical details.

Will Rust support be added?

Probably not. Petition IOI to add Rust support first.

Full text and comments »

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

By xiaowuc1, 9 months ago, In English

I was motivated to write this blog post after reading this blog post about possible precision issues in output and requiring printing a rounded answer exactly instead of printing an answer within a tolerance. This blog post feels somewhat related insofar as that it has an issue with floating point numbers, and also a doubt as to the correctness of the underlying data. Alternatively, someone can find the mistake in my logic.

The problem in question is Rationalization which asks to find a positive rational $$$\frac{A}{B}$$$ that is within a range $$$[C-F, C+F]$$$. Among all such fractions, minimize $$$A$$$, and among all such with minimal $$$A$$$, minimize $$$B$$$. The judge data guarantee that $$$1 \le A, B < 10^6$$$.

My solution path is as follows: If $$$C-F \le \frac{A}{B} \le C+F$$$, then $$$B(C-F) \le A \le B(C+F)$$$. Therefore, we can just check all $$$B$$$ in increasing order and find the smallest $$$B$$$ where $$$[B(C-F), B(C+F)]$$$ contains some integer, and the smallest such integer should be our $$$A$$$.

Now, $$$C$$$ and $$$F$$$ are floating-point numbers, so in order to make sure that we can represent $$$C-F$$$ and $$$C+F$$$ exactly, we scale them up by powers of 10 until they are exactly integers. Fortunately, we're guaranteed that these numbers are written in decimal form.

Some poorly written Python code

This gets 60 points on Kattis with a WA verdict on the final subtask, so it does print something which is deemed incorrect (as opposed to printing nothing or printing a value of $$$A$$$ that is too large and getting RTE). Since the solution does pass the first two subtasks, I am reasonably confident that it is not completely wrong. I presume that the second subtask is meant to admit solutions that have precision issues by representing values using floating point values (perhaps by scaling each of the floating point values directly by $$$B$$$), though I haven't bothered to experiment much there.

I do have a weak prior that some Kattis problems with floating point numbers do something incorrect — for example, for this problem, all reference solutions say that three points are collinear if and only if the turn would be at most $$$10^{-9}$$$ degrees, as opposed to checking collinearity exactly.

Because of this prior, I'd like to identify the test case to see where I went wrong. Sadly, I can't find the input data for this problem, so I'm stuck trying to find a bug in my solution/logic or conclude the test data are wrong. I'd just like to ask the author for test case 77 to verify it by hand. In the interim, I might be able to get the test case in a few hours if I can find a way to AC the first 76 cases and differentiate that I'm in test case 77. (Kattis only allows 10 submissions within a 10 minute window.)

Alternatively, did I go wrong somewhere?

Update 1: Test case 77 has c = 7.80212 and f = 0.0000000684. I wrote a slow program that seems to generate the same output as what my program prints.

More Python code

This fraction is not equal to either of $$$C-F$$$ and $$$C+F$$$.

Update 2: jeroenodb was able to AC the problem and with his solution we were able to prove that the test data are indeed incorrect. I have contacted Kattis to try to get this rectified.

Full text and comments »

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

By xiaowuc1, 10 months ago, In English

The 19th round of the first Universal Cup is happening the weekend of June 3rd. The contest is based on the North America Championship, which will take place in Florida on May 29th, 2023. The top 51 teams in North America will be competing for qualification to World Finals.

As always, there are three time windows for you to join:

  • June 3rd 13:00 — 18:00 (UTC +8)
  • June 3rd 19:00 — 24:00 (UTC +8)
  • June 4th 02:00 — 07:00 (UTC +8)

Please note that you can see two scoreboards in DOMjudge. The 'Local Scoreboard' shows the standings ONLY IN THE CURRENT TIME WINDOW. And the 'Combined Scoreboard' shows all participants, including the onsite participants, and the cup participants in the previous time windows.

Special note: The North America Championship intends on running an open contest in parallel to the contest. Teams that compete in the open contest can request to have their results merged into the combined scoreboard. Teams that intend on competing in the Universal Cup stage should not look at the problems or attempt to solve them in the mirror.

Contest link: https://domjudge.qoj.ac/

Universal Cup Scoreboard: https://qoj.ac/ucup/scoreboard

About Universal Cup:

Universal Cup is a non-profit organization dedicated to providing trainings for competitive programming teams. Up to now, there are more than 600 teams from all over the world registering for Universal Cup.

A more detailed introduction: https://codeforces.com/blog/entry/111672

Register a new team: https://ucup.ac/register (the registration request will be processed before each stage)

Results of the past stages: https://ucup.ac/results

Terms: https://ucup.ac/terms

Ratings: https://ucup.ac/rating

Full text and comments »

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

By xiaowuc1, 12 months ago, In English

Hi all,

The final contest of the 2022-2023 USACO season will be running from March 24th to March 27th. Good luck to everyone! Please wait until the contest is over for everyone before discussing anything contest-related (including but not limited to your scores or anything about the problems).

For those unfamiliar with the USACO contest format, please refer to the contest instructions and rules. We provide a short FAQ but folks should read all the rules carefully.

I have a question about the contest. Where do I ask it?

Email the contest director via the instructions above. Do not post anything publicly about the questions (including but not limited to your scores, how you felt about the problems, any content of the problems, etc) until after the contest is over for everyone. Do not DM me or anyone else affiliated with USACO, only the contest director can assist you. The contest director does not monitor Codeforces, this blog post is merely a courtesy to inform other people of the contest.

When can I enter the contest?

The contest will open on March 24th.

If I submit multiple programs, which one gets evaluated?

Only the last submission will be evaluated for official scoring purposes.

Can I use prewritten code / templates?

No.

Am I allowed to use outside resources during the contest?

You may only refer to language documentation.

Why didn't I get an email from USACO when I registered my account?

Follow the directions on the USACO website regarding Gmail Delivery Issues to contact the contest director.

Can I solve problems in Rust?

No, the only languages supported are C, C++, Java, and Python. Consult the instructions for language-specific technical details.

Will Rust support be added?

Petition IOI to add Rust support first.

Full text and comments »

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

By xiaowuc1, 13 months ago, In English

Hi everyone! I have been inspired by recent events to write this blog post. This list is not comprehensive, but mostly because I do not keep detailed logs of problems I have written.

There are a few things you will notice after reading through these problems. In no particular order:

  1. Most of these problems are not "high-quality" — they would never see the light of day on a CF round for example. This is mostly due to my lack of skill in generating "high-quality" problems. You'll see that a lot of my problems are generated from observing real-life events and then constructing problems out of those scenarios. There are many ideas that have been proposed and thrown into the void because they were worse. I think there are a couple problems in this list that are actually good problems, but most of them I am not particularly proud of.
  2. The difficulties on these problems generally lean easy, and the problems almost always lean standard. My problemsetting ideology for contests is to set the easiest possible problem to get the desired results. This frequently results in problems where the idea is very straightforward, but maybe obfuscated in a minor way. This is also because most of my problem setting is for my local regional contest, where there are two divisions and because people love to propose hard problems, I get to fill in the gap with easy problems.
  3. I like to embed random references into my problems. They don't mean anything in particular, but, for example, people who are friends with me on Facebook know that I upload quarterly photo albums and the album name is usually a song that I enjoyed listening to that quarter. I'm a nostalgic person.
  4. It turns out a bunch of the problems I wrote have appeared in very similar forms before. Any such problems I am aware of are labeled as such. Please include more examples in the comments.
  5. I'm probably not done authoring problems. I expect a lot of criticism in the comments.
# Date Problem Contest Comments
1 November 2014 Salary Inequity 2014 ACM-ICPC Pacific Northwest Regional This was the first problem I ever wrote for a contest. I didn't actually know the phrase "Euler tour" at this point in time but I was doing some other problem about preorder traversal of a tree and was inspired to write this problem.
2 December 2014 Marathon (Bronze) USACO December 2014 N/A
3 December 2014 Marathon (Silver) USACO December 2014 N/A
4 December 2014 Marathon (Gold) USACO December 2014 I don't remember which problem idea came first but at the time I really wanted to try to have the problem span all three divisions. I speculate the bronze problem got written first because I was trying to help fill in bronze problems, and then the silver and gold problems were "extensions" of some sort.
5 January 2015 Meeting Time (Bronze) USACO January 2015 N/A
6 January 2015 Meeting Time (Silver) USACO January 2015 I don't recall this problem at all. It seems more obvious here that the bronze problem came first and the silver extension followed.
7 January 2015 Cow Rectangles (Gold) USACO January 2015 Contrary to what one might think based on my problemsetting history so far, I actually did not see the segment tree solution to this problem. This problem has probably appeared before?
8 February 2015 Cow Hopscotch (Bronze) USACO February 2015 N/A
9 February 2015 Cow Hopscotch (Silver) USACO February 2015 N/A
10 February 2015 Cow Hopscotch (Gold) USACO February 2015 Many people know me as publicly denouncing BITs as a data structure that is not worth using, and to use segment trees instead because they're more robust. Yes, I'm a hypocrite.
11 November 2015 Airports 2015 ACM-ICPC Pacific Northwest Regional This problem was motivated by me sitting on an airplane that was stuck on the tarmac for two hours as I watched planes alternate in departing and arriving from the airport, and I thought about how efficient airlines are at reusing planes.
12 November 2015 Complexity 2015 ACM-ICPC Pacific Northwest Regional (We needed some easy problems, part 1.)
13 November 2015 Egg Drop 2015 ACM-ICPC Pacific Northwest Regional (We needed some easy problems, part 2.)
14 November 2015 Magic Trick 2015 ACM-ICPC Pacific Northwest Regional (We needed some easy problems, part 3.) Division is hard.
15 November 2015 Triangle 2015 ACM-ICPC Pacific Northwest Regional I was asked to write an easy problem. On the actual contest, we provided a diagram of a square being cut diagonally in half. It turns out this problem is hard.
16 December 2015 Breed Counting (Silver) USACO December 2015 I don't recall if we set template problems this contest because it was the first four-division contest, but I am not proud of this problem.
17 December 2015 Counting Haybales (Platinum) USACO December 2015 I don't recall if we set template problems this contest because it was the first four-division contest, but I am extremely not proud of this problem.
18 March 2016 Diamond Collector (Bronze) USACO US Open 2016 I don't recall this problem at all.
19 March 2016 Diamond Collector (Silver) USACO US Open 2016 I don't recall this problem at all.
20 November 2016 Alphabet 2016 ACM-ICPC Pacific Northwest Regional I like to set problems with TopCoder-style bounds. By this point, you have probably noticed my propensity for setting extremely standard problems.
21 November 2016 Equality 2016 ACM-ICPC Pacific Northwest Regional This is what happens when you ask me to try to write a very easy problem.
22 November 2017 Forbidden Zero 2017 ACM-ICPC Pacific Northwest Regional We needed an easy problem.
23 November 2016 Illumination 2016 ACM-ICPC Pacific Northwest Regional I really wanted to set a 2-SAT problem for some reason. This one seems a little forced in hindsight. I think at the time, 2-SAT in book code was not quite in the meta which means that this idea was especially mean, though I felt that most people had SCC in their book code so they could just do the reduction themselves.
24 November 2016 Mismatched Socks 2016 ACM-ICPC Pacific Northwest Regional In 2016, I did not like to wear matching socks. This was mostly because holes developed in half of them.
25 November 2017 Odd Palindrome 2017 ACM-ICPC Pacific Northwest Regional At work I had to write questions for a Python Bee. This was one of the meaner questions that got reused for regionals.
26 November 2016 Paint 2016 ACM-ICPC Pacific Northwest Regional This feels like the sort of DP problem that was really popular on USACO a long time ago.
27 November 2016 Three Square 2016 ACM-ICPC Pacific Northwest Regional This is the sequel to Triangle. I wrote a version called TwoSquare that was originally intended for division 2, and this was intended for division 1. This ended up in division 2 and TwoSquare got scrapped, and people got destroyed.
28 November 2017 Hopscotch 2017 ACM-ICPC South Central Regional This could plausibly be a sequel to the Cow Hopscotch problem. I think I wanted to set a problem that wasn't really a 2D data structures problem even though it looks like it should be one.
29 December 2017 Barn Painting (Gold) USACO December 2017 I think I wanted to force some sort of 3-coloring problem for some reason, I don't recall why this problem was phrased this way.
30 November 2018 Coprime Integers 2018 ACM-ICPC Pacific Northwest Regional I authored so many problems this year that it feels like I tried to force filling in some gap that I perceived in the topic distribution.
31 November 2018 Exam 2018 ACM-ICPC Pacific Northwest Regional This was inspired by some real life incident, though I don't recall what true/false Buzzfeed quiz was involved.
32 November 2018 Goat Rope 2018 ACM-ICPC Pacific Northwest Regional I wanted to write a problem on goat ropes based on a similarly named problem in 2013.
33 November 2018 Liars 2018 ACM-ICPC Pacific Northwest Regional I originally wanted this problem to require a linear time solution, I'm not sure why we ended up nerfing this to quadratic time.
34 February 2019 Painting the Barn (Silver) USACO February 2019 I can't believe this problem was approved for use in a contest. I can believe I proposed it, because I think at around this time I was trying to claim that prefix sums were "hard enough for Silver."
35 February 2019 Painting the Barn (Gold) USACO February 2019 This problem seems better.
36 November 2019 Even or Odd? 2019 ICPC Pacific Northwest Regional I did not propose the problem with these bounds. That is a story that can be inferred from other things I have written on CF.
37 November 2019 From A to B 2019 ICPC Pacific Northwest Regional I swear this problem is unoriginal but none of us could find this on Codeforces. I fully expect someone to link this problem in the comment section.
38 November 2019 Rainbow Strings 2019 ICPC Pacific Northwest Regional Someone wanted a sequel to rainbow graph. I forced the rainbow idea but that was it.
39 December 2019 Cow Gymnastics (Bronze) USACO December 2019 I guess bronze really needed an easy problem? I think I proposed this problem back in 2015 and it only got used now.
40 January 2020 Race (Bronze) USACO January 2020 This and Loan Repayment were two of my most infamous USACO problems. It feels like I wanted to bait people into doing a lot of math.
41 January 2020 Loan Repayment (Silver) USACO January 2020 I think I wanted to propose the easiest possible hardest "binary search" problem feasible to be used in Silver. I think it succeeded.
42 February 2020 Triangles (Silver) USACO February 2020 I don't remember proposing a harder version of this problem.
43 December 2020 Daisy Chains (Bronze) USACO December 2020 I thought we required $$$\mathcal{O}(N^2)$$$ for this... guess not.
44 December 2020 Sleeping Cows (Platinum) USACO December 2020 This problem has appeared before. Can you find the source?
45 January 2021 Even More Odd Photos (Bronze) USACO January 2021 This problem title sounds like something I would say out loud and find unreasonably funny.
46 January 2021 Uddered but not Herd (Bronze) USACO January 2021 I feel like this is inspired by the alphabet problem from a few years ago?
47 January 2021 Uddered but not Herd (Gold) USACO January 2021 I wasn't responsible for this one.
48 March 2021 Ant Typing 2020 ICPC Pacific Northwest Regional Definitely trying to force a lot of brute-force problems.
49 March 2021 Exam Manipulation 2020 ICPC Pacific Northwest Regional The COVID year, where we thought we needed a lot of problems to saturate keyboard time.
50 March 2021 Exciting Tournament 2020 ICPC Pacific Northwest Regional This problem has appeared before. Can you find the source?
51 March 2021 Kangaroo Party 2020 ICPC Pacific Northwest Regional Was this motivated by an old APIO problem? I no longer recall.
52 March 2021 Longest Common Subsequence 2020 ICPC Pacific Northwest Regional I really liked this problem, though I am still convinced it is completely unoriginal.
53 March 2021 Magic Trick 2020 ICPC Pacific Northwest Regional This was motivated by an IRL trick someone played on someone else.
54 March 2021 Missing Number 2020 ICPC Pacific Northwest Regional This problem looks vaguely familiar...
55 March 2021 Rainbow Numbers 2020 ICPC Pacific Northwest Regional This is continuing on the theme of rainbow problems, except because I'm trying to force rainbow as a theme the problems get worse and worse.
56 March 2021 Rating Problems 2020 ICPC Pacific Northwest Regional Yep, this is how we internally rate problems. I rated this problem a 0... it got an average of 0.60.
57 March 2021 Reconstruct Sum 2020 ICPC Pacific Northwest Regional Somehow the test data for this problem were weak, but I don't remember who prepared the data for this problem or why I was too lazy to write the obvious WA.
58 April 2021 Laptop Sticker 2021 North America Division Championships This was originally a division 2 problem that was a carryover to NADC. I'm honestly surprised we used it at NADC.
59 April 2021 Longest Common Substring 2021 North America Division Championships Originally, I wanted this problem to be used in division 2 and Longest Common Subsequene to be used in division 1. Good thing it wasn't used in division 2?
60 August 2021 수학은 체육과목 입니다 3 UCPC 2021 Preliminary I was tasked with trying to write an easy and accessible problem. This was too hard.
61 August 2021 항체 인식 UCPC 2021 Preliminary I was tasked with trying to write a slightly less easy problem. This was also too hard.
62 August 2021 스키장 UCPC 2021 Preliminary I was tasked with trying to write a slightly less easy problem. This one was fine. It's worth noting that all of these problems were translated on my behalf, and I know zero Korean.
63 August 2021 Cleaning Robot 2021 North American Championship Inspired by watching my roommates' Roomba fail to clean.
64 August 2021 Contest Construction 2021 North American Championship Inspired by watching us try to construct a contest with a reasonable difficulty curve, and completely failing to do so.
65 August 2021 Mountainous Palindromic Subarray 2021 North American Championship This problem has appeared before. Can you find the source?
66 August 2021 You Be The Judge, Again 2021 North American Championship Inspired by its predecessor in NADC.
67 December 2021 Lonely Photo (Bronze) USACO December 2021 This problem was motivated by an unfortunate photo I saw being taken.
68 December 2021 Walking Home (Bronze) USACO December 2021 In 2018 someone had an argument with me about the fastest way to navigate from point A to point B in SF by walking along certain turning paths. I don't remember the outcome but this problem came out of it.
69 December 2021 Connecting Two Barns (Silver) USACO December 2021 I think I wanted to write some sort of minimum spanning tree problem but somehow wrote this instead?
70 March 2022 Double Password 2021 ICPC Pacific Northwest Regional I think this is motivated by watching someone backdoor some combination lock.
71 March 2022 Fail Them All! 2021 ICPC Pacific Northwest Regional This problem was originally named Exam Manipulation.
72 March 2022 Rise and Fall 2021 ICPC Pacific Northwest Regional This problem was originally named Rainbow Numbers.
73 March 2022 Scaling Recipe 2021 ICPC Pacific Northwest Regional I didn't learn my lesson about division being hard.
74 March 2022 Tree Hopping 2021 ICPC Pacific Northwest Regional I solved this problem and decided writing a verifier for this would make a reasonable problem.
75 February 2022 Phone Numbers (Platinum) USACO February 2022 I only proposed the idea for this problem, I wasn't able to solve it. This problem is actually inspired by rhythm games.
76 March 2022 Alchemy (Bronze) USACO US Open 2022 This problem idea was forced by a certain song.
77 February 2023 Advertising ICPC 2022 ICPC Pacific Northwest Regional This problem has appeared before. Can you find the source?
78 February 2023 Alchemy 2022 ICPC Pacific Northwest Regional 2022 NA ICPC Regionals problem themes this year were a bunch of songs. This problem was much harder than I thought it would be. Maybe it's because of the TopCoder-esque bound?
79 February 2023 Champernowne Count 2022 ICPC Pacific Northwest Regional I feel like I've seen this problem before.
80 February 2023 Counting Satellites 2022 ICPC Pacific Northwest Regional This problem has appeared before. Can you find the source? Incidentally, this was my favorite song of 2022.
81 February 2023 Fading Wind 2022 ICPC Pacific Northwest Regional With the problem theme being forced, this was the first idea I could come up with.
82 February 2023 Restaurant Opening 2022 ICPC Pacific Northwest Regional This problem isn't named after a song.
83 February 2023 Streets Ahead 2022 ICPC Pacific Northwest Regional This problem also isn't named after a song. It is a reference to a certain TV show though.
84 February 2023 Sun and Moon 2022 ICPC Pacific Northwest Regional With the problem theme being forced, this was the natural problem to propose.
85 May 2023 Allergen Testing North America Championship 2023 I was not able to find this problem beforehand, but it seems to have been presented in an alternate format as a math riddle of sorts. This problem was intended to be among the easier half of problems on NAC.
86 May 2023 A Tree and Two Edges North America Championship 2023 This problem was designed to be at the difficulty of problems that would gate qualification to WF from North America. It's a relatively standard test of graph theory fundamentals that requires a decent amount of implementation or having all the primitives you want in your book code.
87 May 2023 Four Square North America Championship 2023 This was the sequel to Three Square. The time limit of 4 seconds, though an accident originally, was intentional (and yes, some team did get TLE on it in contest.)
88 May 2023 Power of Divisors North America Championship 2023 For some reason, I had this idea in my head that some NA teams consider pollard-rho to be something essential to know for ICPC competitions. This problem is a response to it, as a problem that does not require any high-powered number theory and can be solved with some observation and just trial division.
89 September 2023 Contest Advancement North America Qualifier 2023 Written shortly after NAC was announced. It was not a popular idea.
90 September 2023 Digit Translation North America Qualifier 2023 I'll give you one guess what the inspiration of this problem is.
91 September 2023 Don't Hunger Together North America Qualifier 2023 I don't play this game.
92 September 2023 Garden of Thorns North America Qualifier 2023 I also don't play this game.
93 September 2023 ICPC Team Generation North America Qualifier 2023 Inspired by real-life events.
94 September 2023 Is Y A Vowel? North America Qualifier 2023 Do you add the letter 'u' to words randomly?
95 September 2023 Lines Per Hour North America Qualifier 2023 Inspired by real-life discussion around how contests should work.
96 September 2023 Magnesium Supplementation North America Qualifier 2023 N/A
97 September 2023 Missing Number North America Qualifier 2023 I guess this is the hard mode of a problem I wrote before.
98 September 2023 Water Journal North America Qualifier 2023 N/A

Full text and comments »

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

By xiaowuc1, 13 months ago, In English

When preparing the problems for the February 25th NA ICPC regionals, we had some discussion around how lists should be formatted when given as input to contestants.

The primary argument motivating some design decisions was consistency — namely that all lists should be formatted the same way, where a list should be expressed by starting with the length of the list, $$$n$$$, and then writing $$$n$$$ lines, one item per line.

This is pretty standard and for most problems, this is the convention that most problems use for most lists. The main counterexample to this case seems to be when the list is a list of integers. A lot of problems, when confronted with a list of $$$n$$$ integers, will write out the list as one line of $$$n$$$ space-separated integers. This seems to be the meta for most contests, though I have not looked very carefully at this so this assumption may be wrong. NA ICPC is one of the contests that generally follows line-delimited lists of integers.

Here's my question to the competitive programming community at large — as a contestant, how do you feel about input formatting of this form?

  • Consistency is the most important thing, so all lists should be written as $$$n$$$ followed by $$$n$$$ lines, one per object.
  • Consistency is not that important. For complicated lists where the object is not just a single string or an integer, I prefer lists to be written as $$$n$$$ followed by $$$n$$$ lines, one per object. However, for lists of integers or strings, I prefer $$$n$$$ on one line followed by another line with $$$n$$$ space-separated tokens.
  • Consistency is not that important, and I don't care how lists of $$$n$$$ integers are written, since I'll just read them the same way no matter what.
  • I don't believe that lists by default should be written as $$$n$$$ followed by $$$n$$$ lines, one per object.

I also want to ask a similarly related question — as a contestant, have you thought about consistency of input formats in programming contests?

  • Yes, and it bothers me when contests are internally inconsistent with regards to reading until EOF or a sentinel, or having a prespecified $$$n$$$.
  • Yes, and it bothers me when different contests follow different formats.
  • Yes, but I don't really care.
  • No.

Full text and comments »

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

By xiaowuc1, 13 months ago, In English

Hi all,

The third contest of the 2022-2023 USACO season will be running from February 24th to February 27th. Good luck to everyone! Please wait until the contest is over for everyone before discussing anything contest-related (including but not limited to your scores or anything about the problems).

For those unfamiliar with the USACO contest format, please refer to the contest instructions and rules. We provide a short FAQ but folks should read all the rules carefully.

I have a question about the contest. Where do I ask it?

Email the contest director via the instructions above. Do not post anything publicly about the questions (including but not limited to your scores, how you felt about the problems, any content of the problems, etc) until after the contest is over for everyone. Do not DM me or anyone else affiliated with USACO, only the contest director can assist you. The contest director does not monitor Codeforces, this blog post is merely a courtesy to inform other people of the contest.

When can I enter the contest?

The contest will open on February 24th.

If I submit multiple programs, which one gets evaluated?

Only the last submission will be evaluated for official scoring purposes.

Can I use prewritten code / templates?

No.

Am I allowed to use outside resources during the contest?

You may only refer to language documentation.

Why didn't I get an email from USACO when I registered my account?

Follow the directions on the USACO website regarding Gmail Delivery Issues to contact the contest director.

Can I solve problems in Rust?

No, the only languages supported are C, C++, Java, and Python. Consult the instructions for language-specific technical details.

Will Rust support be added?

Petition IOI to add Rust support first.

Full text and comments »

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

By xiaowuc1, 14 months ago, In English

Hi all,

The second contest of the 2022-2023 USACO season will be running from January 27th to January 30th. Good luck to everyone! Please wait until the contest is over for everyone before discussing anything contest-related (including but not limited to your scores or anything about the problems).

For those unfamiliar with the USACO contest format, please refer to the contest instructions and rules. We provide a short FAQ but folks should read all the rules carefully.

I have a question about the contest. Where do I ask it?

Email the contest director via the instructions above. Do not post anything publicly about the questions (including but not limited to your scores, how you felt about the problems, any content of the problems, etc) until after the contest is over for everyone. Do not DM me or anyone else affiliated with USACO, only the contest director can assist you. The contest director does not monitor Codeforces, this blog post is merely a courtesy to inform other people of the contest.

When can I enter the contest?

The contest will open on January 27th. A link to the contest will be posted here shortly after the contest opens.

If I submit multiple programs, which one gets evaluated?

Only the last submission will be evaluated for official scoring purposes.

Can I use prewritten code / templates?

No.

Am I allowed to use outside resources during the contest?

You may only refer to language documentation.

Why didn't I get an email from USACO when I registered my account?

Follow the directions on the USACO website regarding Gmail Delivery Issues to contact the contest director.

Can I solve problems in Rust?

No, the only languages supported are C, C++, Java, and Python. Consult the instructions for language-specific technical details.

Will Rust support be added?

Petition IOI to add Rust support first.

Full text and comments »

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

By xiaowuc1, 16 months ago, In English

Hi all,

The first contest of the 2022-2023 USACO season will be running from December 16th to December 19th this weekend. Good luck to everyone! Please wait until the contest is over for everyone before discussing anything contest-related (including but not limited to your scores or anything about the problems).

For those unfamiliar with the USACO contest format, please refer to the contest instructions and rules. We provide a short FAQ but folks should read all the rules carefully.

I have a question about the contest. Where do I ask it?

Email the contest director via the instructions above. Do not post anything publicly about the questions (including but not limited to your scores, how you felt about the problems, any content of the problems, etc) until after the contest is over for everyone. Do not DM me or anyone else affiliated with USACO, only the contest director can assist you. The contest director does not monitor Codeforces, this blog post is merely a courtesy to inform other people of the contest.

When can I enter the contest?

This contest runs until December 19th, 23:59 UTC-12 and is four hours long. The URL for the contest page can be found here.

If I submit multiple programs, which one gets evaluated?

Only the last submission will be evaluated for official scoring purposes.

Can I use prewritten code / templates?

No.

Am I allowed to use outside resources during the contest?

You may only refer to language documentation.

Why didn't I get an email from USACO when I registered my account?

Follow the directions on the USACO website regarding Gmail Delivery Issues to contact the contest director.

Can I solve problems in Rust?

No, the only languages supported are C, C++, Java, and Python. Consult the instructions for language-specific technical details.

Will Rust support be added?

Probably not. Petition IOI to add Rust support first.

Full text and comments »

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

By xiaowuc1, 2 years ago, In English

Hi all,

The final contest of the 2021-2022 USACO season will be running this weekend. Good luck to everyone! Please wait until the contest is over for everyone before discussing anything contest-related (including but not limited to your scores or anything about the problems).

Full text and comments »

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

By xiaowuc1, 2 years ago, In English

Is there a released PDF of the problem statements? The published link on the website 404's, it is possible to download the full Polygon package and get TeX statements that way but it does seem bad to have links on the website that are 404'ing.

(Incidentally, will this contest get uploaded to the CF gym? I recall old Northern subregionals being uploaded but don't seem to see this one either.)

Full text and comments »

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

By xiaowuc1, 2 years ago, In English

Hi all,

The third contest of the 2021-2022 USACO season will be running from February 25th to February 28th this weekend. Good luck to everyone! Please wait until the contest is over for everyone before discussing anything contest-related (including but not limited to your scores or anything about the problems).

Full text and comments »

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

By xiaowuc1, 2 years ago, In English

Hi all,

The second contest of the 2021-2022 USACO season will be running from January 28th to January 31st this weekend. Good luck to everyone! Please wait until the contest is over for everyone before discussing anything contest-related (including but not limited to your scores or anything about the problems).

Full text and comments »

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

By xiaowuc1, 2 years ago, In English

Hi all,

The first contest of the 2021-2022 USACO season will be running from December 17th to December 20th this weekend. Good luck to everyone! Please wait until the contest is over for everyone before discussing problems here.

Edit 1: The contest is live now! Please read the contest rules carefully, especially regarding how to ask clarifications or contact the contest organizers. Do not spoil anything (including but not limited to your scores or anything about the problems) about the contest until the end of the contest (four hours after the stated deadline of the contest).

Edit 2: Results have been released.

Full text and comments »

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

By xiaowuc1, 3 years ago, In English

On szkopul, I'm seeing problem statements where the \n character appears instead of actual newlines, even in sample input/output. Other non-ASCII characters appear to be written in escaped format also instead of rendered properly.

I'm curious if this is a local issue for just myself and, if not, if anyone has a good short-term fix for this.

Full text and comments »

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

By xiaowuc1, 3 years ago, In English

Problem statement

This problem looks like a fairly standard tree DP problem, I won't spoil the solution in case people want to think about it.

However, the reason why this problem is interesting (or perhaps extremely painful) is that the memory limit is 32MB. Given that $$$N$$$ can be 1.5 million, this means you're not even allowed to store $$$6N$$$ 32-bit integers.

Therefore, it seems that the main challenge of this problem is to be able to fit everything inside such a tight memory limit. Notably, I've gotten MLE just trying to read in the input and trying to get the tree stored in a representation that makes it possible for me to start working on the DP part of the problem.

In the modern era, memory limits are no longer this tight, but a lot of problems on szkopul retain these tight memory limits which occasionally makes it an interesting (or perhaps extremely painful) challenge to figure out how to fit things in the memory limit.

What's intended here? I asked about this problem in the AC server and got some advice with things such as relabeling the tree with ETT or simulating DFS without an explicit stack. It feels like the authors intended for some precise $$$5N + \mathcal{O}(1)$$$ memory solution and it's a little alarming that I can't even get beyond "read the input and come up with some representation for the tree" without getting MLE.

Full text and comments »

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

By xiaowuc1, 3 years ago, In English

Hi all,

The final contest of the 2020-2021 USACO season will be running this weekend. Good luck to everyone! Please wait until the contest is over for everyone before discussing problems here.

Full text and comments »

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

By xiaowuc1, 3 years ago, In English

Hi all,

The third contest of the 2020-2021 USACO season will be running from February 26th to March 1st this weekend. Good luck to everyone! Please wait until the contest is over for everyone before discussing problems here.

Full text and comments »

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

By xiaowuc1, 3 years ago, In English

Hi all,

The second contest of the 2020-2021 USACO season will be running from January 22nd to January 25th this weekend. Good luck to everyone! Please wait until the contest is over for everyone before discussing problems here.

Edit 1: The contest is now live! Please do not spoil anything about the contest publicly until the contest is over for everyone, and please report any issues with the contest directly to the contest administrator via the instructions instead of posting them here.

Full text and comments »

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

By xiaowuc1, 3 years ago, In English

Hi all,

The first contest of the 2020-2021 USACO season will be running from December 18th to December 21st this weekend. Good luck to everyone! Please wait until the contest is over for everyone before discussing problems here.

Edit 1: The contest is now live! There are new changes to how USACO contests are run — the most notable change is that I/O is no longer done via files. Please consult the official rules for all the changes.

Edit 2: Although the contest window is almost over, please do not discuss the contest until everyone has finished it. The contest window should close four hours after it officially ends since folks who join at the last minute purportedly still get a full window, in which case the contest ends at this time.

Edit 3: The contest is officially over — hope everyone enjoyed the contest! Results should hopefully be ready by the end of the week.

Edit 4: Results are out!

Full text and comments »

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

By xiaowuc1, 4 years ago, In English

Hi all,

The final contest of the 2019-2020 USACO season will be running from March 27th to March 30th. Good luck to everyone! Please wait until the contest is over for everyone before discussing problems here.

Full text and comments »

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

By xiaowuc1, 4 years ago, In English

The 2020 ICPC North America Championship 2020 is today!

The 60 best teams from North America will compete for the title of North America Champions, a trophy and also an opportunity to represent North America at the ICPC World Finals 2020 in Moscow, Russia! Join us for a live broadcast or just follow the contest through all the possible links below.

Today's live broadcasters will be ecnerwala, scott_wu, tehqin, and xiaowuc1. Live commentary will start at 10 AM EST!

Official Website: https://nac.icpc.global/

Hashtag: #icpcnac2020

Discord: https://discord.gg/FpJfBHS

Mirror contest: https://open.kattis.com/contests/nac20open

Scoreboard: http://nac.icpc.global/scoreboard/

Live broadcast: https://www.youtube.com/channel/UC6-6qLP8Fubg5F3r4tfbosw and https://www.twitch.tv/icpclive

Twitter: https://twitter.com/IcpcNac

Facebook: https://www.facebook.com/na.icpc.io

Flickr: https://www.flickr.com/photos/187051365@N06/

Full text and comments »

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