SuperJ6's blog

By SuperJ6, history, 3 months ago, In English

This is something I think for a long time now, and some comments today make me explicitly share it.

The phrase "ad-hoc" is vaguely attributed to any problem that does not incorporate a "standard technique", where it's hard to put it in some big category on a problem bank.

However, in competitive programming there are many "standard techniques" that you will not find in a textbook. Some of them are still sometimes stated as "standard", but many are often attributed as "pure logic", yet it is a logic that can only be placed in beginner problems because it appears so often.

Let's take today's 1965B - Missing Subsequence Sum. This is a type of problem I think many beginners will call "ad-hoc", and even some advanced participants will claim as "just logic/trying stuff". Yet, such problem as this boils into two parts: create all of lower sum, create all of higher sum same way, how do you create all of such sum? Any advanced participant has actually come across many problems like this (i wanted to put many but too lazy to find) that are applying essentially same idea, but I do not think they're ideas that you immediately come to with no experience in cs domain. However, it's hard to put a name and a bit more flexible in presentation, so we often just pretend such problems do not fall in a category, even though they clearly do.

If you've done enough problems and think hard enough, you can classify almost every problem as using the same sort of sequence/combination of steps as a dozen others. And then low level participants get this false information that they are just plain not as good at logic, while there are also many hidden prerequisite ideas that make a problem easier.

I wonder, why are "hidden ideas" ok to be reused over and over as long as it's hard to pinpoint a name to them, but any idea that is well named is usually too hard for beginners and too standard for advanced?

What's the point?

I wish there are three things people would do:

  1. It would be great if problems were better classified, and more of these ideas that are standard to experienced participants yet never explicitly written as a technique were named in a huge list with examples.
  2. I wish coordinators would stop gearing problems towards ones that are 1 or 2 shot killed with "hidden ideas". This is just as boring as solving many variations with minimal different thinking of the same data structure or shortest path. Either get rid of all problems that are using same combination of ideas as previous, or allow combinations of known ideas as easier problems but increase the domain knowledge past what can be described to elementary school student (just because it can described in simple terms doesn't mean it's any easier to come up with, it just means it's boring with an illusion of more accessible).
  3. Stop blindly praising problems that don't use higher level domain knowledge but are not an exact replica for being "pure logic of ad-hoc". Almost no problems in contest actually has much new thinking, it is just different rehashes of ideas that are more exclusive to better participants because you won't find them in a textbook.

How does this affect your practice?

Same as I put in my practice blog, don't believe some ideas are impossible pre-reqs you must have read while others are just pure logic you always come up with from scratch. All these ideas are the same, just focus on what is similar and different between problems in practice and what are similar hints toward a mindset across problems you solve.

My Challenges

Can you list some of these "hidden techniques" that you see most often?

Also, can you post a problem that is actually "ad-hoc", ie that others cannot find 20 similar problems before it with the same "hidden ideas"?

Full text and comments »

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

By SuperJ6, history, 3 months ago, In English

I believe this is the CM-M way of falling into forcing rubber bands blog.

I think I almost never fall into the trap of saying "is this greedy" "is this dp" "is it dijkstra" etc. Yet, I still tunnel vision and end up not solving easy problems compared to my practice. Why?

I believe the trap I and many others fall into is that they believe at some point in contest that a problem will be satisfying to solve.

Particularly to me, once I get to some problem level I don't always solve, I first naively believe there will be some reduction or insight that is interesting to me where I believe not anyone can come up with it (probably for some ego reasons). While I then get the main insights, I will end up overcomplicating putting things together or miss a final simplification step as it seems before the last step the problem would still seem cool to me. However, when I don't get it, shortly after contest reality will strike and I realize the reduction is so simple that anyone from primary school would eventually get it if they thought about the problem very long (this doesn't necessarily mean it's easy, but rather that it's hard to miss given enough time and focus and requires minimal background).

Practice is when to try to solve satisfying problems that will increase your thinking capability, contest is often only enough time to get what is easy in hindsight. The exception is through luck/skill you are able to properly always think stupid until it no longer works, but you never are sure when it won't work and chances are you just aren't thinking stupid enough.

If you too are always seeing a problem is unsatisfying in hindsight from contest, tell yourself more consciously when you are taking longer than 30 minutes or the ideas are seeming longer than 30 lines of code to think stupider. Because 90% of time that problem you're stuck on is not one your stuck because it will be satisfying, but because you believed it will be.

Full text and comments »

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

By SuperJ6, 13 months ago, In English

I often want to find problems I did in my submissions tab (or stalking others) sorted by similar things like tags or rating as problemset tab. Is there anything for sorting problems by these features or at least displaying rating/tags besides submissions? If not I might make one, but would prefer to not have to do any work...

Full text and comments »

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

By SuperJ6, 14 months ago, In English

Are you a US student training for USACO and currently high bronze/low silver level? Are you very determined to get better at competitive programming?

I am willing to tutor 1 person for free (with probably 2-3 live meetings per week) if you are able to do a minimum of 2 (but preferably 3+) problems at your skill level per day for next year and post all solutions on github for proof. You can have one mess up day per month, including during school year, otherwise I will stop deal immediately. If this interests you and you want a chance to be chosen, please link a new github repo/folder under this post that will contain all your solutions from one of next few days onward and I will choose from there based on who practices the most, preferably following close to my practice guide. I want someone who scored close to range of 333 on bronze to 333 on silver, but it is not strict. Must be elligible for IOI through US next year and < gold tho (if no one signs up that meets requirements I'll pick from gold tho). I am busy until June 1st (finals rip), I will select and start working with them then.

For perspective I am a previous USACO camper and tutored last USACO season and got a few people to plat and one to camp. This year I want to work with someone and see if I can get them to IOI from minimum prior experience in one year, but it won't work if they aren't dedicated enough. If they follow through, we should get roadmap to IOI from their github :).

If you aren't chosen but still want tutoring and are silver+/pupil+ skill level (gold is most fun for me tho), I do $60/h (with possible negotiation), and for paid you don't need to be US student. You can read my methodology here, but I also do silver now. Contact me on discord at "megumikatou" for info. I won't start until June 1st for this either (and may take while to respond on discord until then). Though tutoring might help improve faster, it is not necessary for success. Just follow my practice guide to get gud.

Addition: I will also maybe take another person who is gold+ under same conditions, because I wonder how different outcome would be. I am not sure if I will have enough time/money though and can't do a ton for free. However still post github and say that you are gold+ if you want a chance (like 50%).

Update on Chosen People: My top choice to select is SriniV, and I will begin meeting twice per week with him. However, since I have a bit more time now, I will also meet with InfinitePath, SwayamSahoo11742, and hazzlek (from gold) once per week. All of these will probably be 1h each meeting, please contact me on discord if you were chosen.

However, realize I am doing this for free and this is a lot of my time, so it is unlikely I will maintain all these people permanently, and for sure will not select more people for free. I hope to maintain probably two for entirety of next year based on who seems to have most potential. I will update on progress occasionally if their results are interesting :).

But for now, congrats to these individuals for working hard and hope they continue to do so and with help they can achieve highest levels possible! If you weren't chosen however, continue to work hard, if you continue the practice rate I specified and are diligent on doing problems at a hard level you will likely at minimum make platinum without any tutoring anyway. Good luck!

Full text and comments »

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

By SuperJ6, 14 months ago, In English

This is a slight tweak of a practice guide I wrote a while ago on USACO reddit since I thought it could be helpful to people here. Some USACO specific sections or extra clutter I left out here that aren't needed for a general audience. This should cover all general cp advice I have so I never have to retype.

Introduction

This is a post on how I believe is the best method to practice modern day competitive programming based on my experiences. I assume you already have some knowledge and know simple things like binary search and dfs/bfs, but read the footnote if you are complete beginner (never code, solved <50 problems, div2 A/B too difficult, grey or stuck low pupil).

First, a quick tl;dr of the practice strategy before a bunch of specifics and explanation:

In short, mostly you only need to use codeforces (no matter what contest you're training for), find a rating range where you can solve around ~30-40% of the time on your own, and just grind down the problem set tab in reverse order of id (the default sorting). Also take part in every live contest you can, and virtual any live contests you miss.

Also, if your primary goal is some goal outside of codeforces (let's say USACO, but could replace with any OI or if ICPC replace instance of OI with ICPC) Approximately once per week (probably on each weekend), I recommend you virtual an OI contest then upsolve the ones you understand the editorial for after. This should be old USACO contests until you finish all in the past 5 or so years, then use OI checklist to find new contests. Make sure you go for subtasks just as you would in real contests when doing so.

Some parts of this method may seem strange to you, so I'll explain in more detail and comment on why I believe it is the best method, and give some proof. If you're too lazy to read all of it, the most important parts of this article are bolded. Also, I am assuming you are able to practice somewhat regularly (at least a few days of practice done each week for multiple months), and this practice is unlikely to work if you don't. However if you really want to improve fast, ideally practice should be daily, no breaks.

Full text and comments »

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

By SuperJ6, history, 17 months ago, In English

What are some examples of surprisingly similar problems across different contests on codeforces?

Full text and comments »

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

By SuperJ6, history, 2 years ago, In English

Inspired by tmw's cses stream, I will do livestream solving Yosupo Library problems. I will start around 4am UTC, maybe slightly later, and I will probably go for around 6 hours, but maybe longer.

Here is the link: Yosupo Livestream Link

Hope to see you there! Also I will probably do more cf virtual livestreams in the future.

Full text and comments »

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

By SuperJ6, history, 4 years ago, In English

I'm wondering if anyone knows where I can find the Chinese training camp papers. I see them referenced sometimes and would love to be able to read them. This link seems to have had them but the downloads no longer work. English would be even better but I'm fine with Chinese (I'm fluent in google translate).

Full text and comments »

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

By SuperJ6, history, 4 years ago, In English

I was wondering if there is any data structure for supporting editing elements, querying elements, and sorting sub-arrays, faster than the naive implementation.

For example, consider the starting array [3, 5, 2, 6, 9, 5, 1]. For a query, you want to sort the subarray between indices 1 and 5 (0 index inclusive). You are left with resulting array [3, 2, 5, 5, 6, 9, 1]. Now you want to query for element at index 4, which you print 6. Now query to change index 4 to 3 and query to print it, and you print 3.

Essentially you are supposed to maintain idea you are sorting so that you print correct element at index, but you don't want to actually sort the whole subarray every time obviously.

I thought I remembered hearing something about this, but can't find any resources so maybe i just made the idea it's possible up.

Full text and comments »

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

By SuperJ6, history, 4 years ago, In English

Hi y'all, I am wondering if you could give me some resources, I have been stuck for so long and need to learn your secrets.

Jk I know how to google and,2020-04-08 stalk reds

I am wondering how many of you were low rated and naive and once asked a question like this in a cf blog or similar, and are now what you would be what you consider good at cp.

I am curious because I'm convinced anyone who can't perform google searches can't become good at cp, and I've seen many blogs asking for help like this while barely solving any problems or trying to figure out for themselves, yet I don't think those blogged helped them improve as I don't recall anyone like that ever getting up to expert.

If you once asked for help without starting and are now successful, please tell me, as I am eager to see if I can be proved wrong.

Also my important tip to beginners is get good at googling and reading solutions while thinking how you could think of it on your own, that is the only two skills you really need to improve.

Full text and comments »

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