When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

xiaowuc1's blog

By xiaowuc1, 12 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
  • Vote: I like it
  • +56
  • Vote: I do not like it

»
12 months ago, # |
  Vote: I like it +34 Vote: I do not like it

I think it would be cool if codeforces added a section in profile page for written problems

  • »
    »
    12 months ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    Maybe it's hard to connect problems with authors, but it's cool

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      I believe it could be implemented if each problemsetter is given the rights to link problems which he created. I'm unsure whether there would be trolls or not.

»
10 months ago, # |
  Vote: I like it +44 Vote: I do not like it

criticism

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved Power of Divisors by clearing out the $$$N=1$$$ and the $$$N=p^2$$$ case, and then checking the rest in $$$O(N^{1/3}\log\log N)$$$ time since the rest have more than 3 divisors. Seems like I went just too far.

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm not sure what you mean by "math riddle of sorts", but Allergen Testing is the same as TCO 2014 3B Easy.