2022/11/1
https://codeforces.com/blog/entry/106346
On "is this greedy or DP", forcing and rubber bands
reading other people's thought processes
They look at the constraints or use some other, usually misguided, intuition to tell whether it is DP, greedy, or something else.
If you still want to ask however, a better wording would be "do you know of any solution using X"?
Not greedy does not imply DP
High-rated users can sometimes make it worse
however much easier to solve it by knowing only the stuff you didn't tell me — I could probably come up with the DSU portion myself.
Very few hard problems can be solved directly using greedy, DP or any common algorithm.
but you can't solve most problems by simply deciding to use greedy
Instead, what you should do is try to understand this structure
I mean really understand it. Not understand the words in the statement, understand what's going on inside
Gather observations,Maybe even forget for the moment what the problem is asking for and try to understand the situation in general.
A note about the word 'observation'
"Observation" is one of these words that has a somewhat specific meaning in mathematics. It might be a little different from the everyday usage you are familiar with.
You come up with some fact through a chain of reasoning. This chain of reasoning is called a proof. Usually, if you find an observation, you already know the proof.
The essence, the idea of the solution is somewhere else
you need to find and prove some equivalent condition and you have to rephrase the problem into something that you can actually make an algorithm out of.
How to exactly come up with this transformation and how to use DP for the new problem are beyond the scope of this blog, but I think this perfectly illustrates the "two-phase" thought process.
1.Gather observations, understand what's really going on, convert the problem into something you can make an algorithm out of.
2.Solve the new and simpler problem directly, with DP, greedy or some classical algorithm.
By the way, this is a very common technique in problems like "you are given operations X and Y, can you make t starting from s/what is the lexicographically smallest t you can make from s/how many different t can you make from s".
1.You identify some invariant, something that doesn't change when you apply the operation.
2.You prove, using some construction, that anything satisfying this invariant is actually reachable.
In all problems I have shown, there are essentially two parts to the solution.
1.Deeply understanding the problem, familiarizing yourself with the situation, making observations, reductions, rephrasing the problem.
2.Actual computation, often in a relatively standard way, possibly a greedy algorithm or DP.
Of course, this picture is simplified. In practice, the steps are very much intertwined, and it is usually hard to write down the two phases so explicitly separately. But the general idea stays the same. Doing greedy or DP happens at the end of your thought process, not at the beginning of it.
2022/11/1
https://codeforces.com/blog/entry/62730
How to read problem statements
The result of reading the statement is usually pure math model. If story helps to build correct understanding, you can keep it, but still try to discard as many unnecessary details as possible.
Imagine you want to tell the problem to someone else. What parts you want to tell? (According to my PM, this rule won't help you).
Shorter = better.
Simpler = better.
Limitations are part of problem statement. Especially small limitations, because for small data you can try all the possibilities.
Samples are part of problem statement. After building math model, check that you model working correct on samples, at least on small samples where you can check everything fast.
Notes are part of problem statement.
Try to find familiar patterns, maybe objects you already know something about. If you are given some connected graph with exactly one simple path between each pair of vertices, it's called tree. 4 letters instead of 12 words, see?
Try even harder to spot something strange, something you not expecting. That probably will be the cornerstone of the problem.
If there is some part of the statement you don't like, try to change that to something you like. Start with understanding the object, then simplify it. There are some problems which can be completely solved by this technique.
If the model you get is very big, try to split it into some pieces. It would be great if pieces are independent, like 'solve problem1, then use its answer as input to problem2 and so on'.
On first stages it can be useful to write your new statement. On paper. By hand.
Problemsetters do not write random things in statements. But why would you believe me, since I'm a bad problemsetter? I don't know, maybe you shouldn't.
阅读语句的结果通常是纯粹的数学模型。若故事有助于建立正确的理解，你们可以保留它，但仍要尽可能多地丢弃不必要的细节。
想象一下，你想把这个问题告诉别人。你想说什么？（根据我的PM，这条规则对你没有帮助）。
越短越好。
更简单=更好。
限制是问题陈述的一部分。特别是小的限制，因为对于小数据，你可以尝试所有的可能性。
样本是问题陈述的一部分。建立数学模型后，检查您的模型在样本上是否正确工作，至少在小样本上，您可以快速检查所有内容。
注释是问题陈述的一部分。
试着找到熟悉的模式，也许是你已经了解的对象。如果给定某个连通图，在每对顶点之间只有一条简单路径，则称为树。
4个字母而不是12个单词，看到了吗？
更努力地发现一些奇怪的东西，一些你想不到的东西。这可能是问题的基石。
如果陈述中有你不喜欢的部分，试着把它改成你喜欢的部分。
从理解对象开始，然后简化它。有一些问题可以用这种技术完全解决。
如果你得到的模型很大，试着把它分成几块。如果各个部分是独立的，比如“解决问题1，然后将其答案用作问题2的输入，等等”，那就太好了。
在第一阶段，编写新语句可能很有用。在纸上。手工
问题解决者不会在语句中随意写东西。但既然我是一个糟糕的问题解决者，你为什么会相信我？我不知道，也许你不应该。
You don't have to read "solution" parts, but I warn you that my concept of reading statements works. I mean, "statement" parts will often contain huge hints to solution.“语句”部分通常包含解决方案的巨大提示
2022/11/2
https://codeforces.com/blog/entry/20548
How to come up with the solutions: techniques
Technique 1: "Total Recall"
remember some similar problems that you had to solve
you can use your experience of solving a similar problem to solve this one
Technique 2: "From Specific to General"
尝试解决一些（或多个）具体案例，然后尝试将其概括为主要问题的解决方案。这样的具体案例可以被视为问题的简化，也就是说，我们可以根据以下原则进行推理：“如果我不知道如何解决一个复杂的问题，我想我会简化它并找到简化版的解决方案”。
常见的简化示例（具体案例）：
你有一棵树的问题。考虑其变体，其中树退化为路径；
这个问题有权重吗？考虑一个变型，其中所有权重都等于一或任意数，或者只有两个不同的权重（依此类推）。
请注意，特定案例的解决方案几乎总是不比一般案例的解决方法简单，因此您需要尝试找到一个尽可能简单有效的解决方案。
Technique 3: "Bold Hypothesis"大胆假设
try to prove it — it may either work out well or give you an idea of how to disprove it. Do test the hypothesis on a wide set of tests as it would be a pain to waste time on implementing a solution based on a hypothesis and only after that disprove the hypothesis.
Examples:
the solution always exists;
item the number of states isn't large.
Technique 4: "To solve a problem, you should think like a problem"要解决问题，你应该像问题一样思考
Try to process some small samples on your own. If the problem is about a game, play it. Sometimes I try to visualize a process or a model for better understanding. It's a little like how movies show the way scientists think. Try to think in images, imagine the solution, see it unfolding.
将一个过程或模型可视化
试着用图像思考，想象解决方案，看到它的展开
Technique 5: "Think together"
Sometimes your teammates will pick up ideas and develop them and this strategy can get you through the problem.
Technique 6: "Pick a Method"
选择了一种方法后，假设问题是用这种方法解决的，试着思考解决方案
尝试使用可以以任何方式应用于问题的流行算法或方法
Technique 7: "Print Out and Look"
In order not to keep the computer busy, a good strategy is to print out the acquired results and meditate this time on the print outs.
为了不让计算机忙碌，一个好的策略是打印出所获得的结果，并在打印结果上思考这一次。
Sometimes it is a good idea to print not only the answer, but also some extra information, such as a manner of acquiring a solutions.
有时，不仅打印答案，还打印一些额外的信息，例如获取解决方案的方式，这是一个好主意。