### Um_nik's blog

By Um_nik, 3 years ago,

But Um_nik, we all know how to read, we have our whooping 2 month of experience! Oh, my sweet summer child, my experiments show that many people with kinda cool achievements like medals on ROI don't know how to read statements. But don't worry, I'll teach you. Well, probably you won't understand anything, because you didn't try to understand anything in your life, you expect all hard work to be done for you by someone else. Let's start!

# Basic rules

• 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.

# Some examples

I'll use Timus for almost all examples. If you see statement in Russian and you don't want to, there is a language switch in upper-left corner.
Assumed workflow: read the statement on Timus, try to understand and simplify it using the rules above. 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.
In most cases I won't write step-by-step explanations how I get the final version. You can say that that's not how teaching works. I can say that you don't want to study. I'll win, because that's my blog.

Statement
Solution

Magic Programmer

Statement
Solution

Scheduled Checking

Statement
Solution

Work for Robots

Statement

Coffee and Buns

Statement

# Harder examples

Now I'll try to explain something.

GOV-internship 2

Statement
Solution

Martian Plates

Statement

Winnie the Pooh

Statement

Titan Ruins: Serial Control

Statement
Solution

Statement

# Different math models will lead you to different solutions

Well, only if you have some patterns of how you should solve problems. And you should have them, patterns are good, they're the fastest way to solve problems.

Empire Strikes Back

Statement and Solution
Statement and Solution 2

# Eliminating things you don't like can solve the problem

Last example in this blog will be not from Timus, it is 2016 Yandex.Algorithm Round 3, Problem F, shout-out to Endagorion for creating such pearl.

Problems visible only to participants, so I'll give already simplified problem statement here:

Given a tree, all vertices are initially white. Two players, Red and Blue, take turns coloring white vertices (surprise) red and blue. The game ends when there are no white vertices left. The score of the game is CR - CB, where CR is a number of connected components on red vertices, and CB is a number of connected components on blue vertices. Red wants to maximize the score, Blue wants to minimize it. Find the score if both play optimally. n ≤ 2·105.

Solution

• +381

 » 3 years ago, # | ← Rev. 3 →   +167 Well, probably you won't understand anything, because you didn't try to understand anything in your life, you expect all hard work to be done for you by someone else. Let's start! Such an inspiring introduction!
 » 3 years ago, # |   +49 So, what's the point?
 » 3 years ago, # |   -35 Yeah I believe Problem statement should be short simple and precise...butsome problem setter are more literature lover than CPer
•  » » 3 years ago, # ^ |   -16 Hi sguu
•  » » » 3 years ago, # ^ |   -31 Hiii :D
 » 3 years ago, # | ← Rev. 2 →   +69 Problemsetters do not write random things in statements. This reminds me of AIM Tech Round 5 and 1028G - Guess the number, where M = 10004205361450474 was chosen to be exactly maximum value for which the answer in 5 queries can be found. To disguise this they chose constraints like n = 132674 in other problems.By the way, did some problemsetters try to troll participants relying on this fact too much by adding many random things into statements? :)
•  » » 3 years ago, # ^ |   +89 If you only knew how many random things by problemsetters I've deleted from statements...
•  » » 3 years ago, # ^ |   0 If you are really cool (not me, I understand it only after the contest), those limits could be a hint that for one of the problems it is not random.
•  » » 17 months ago, # ^ |   -10 the god has spoken
 » 3 years ago, # | ← Rev. 2 →   +7 By the way, another advice is to read the statements carefully. Sometimes I failed some Div.1 A problems because I misread the statements and thought of a different problem, that was much harder, maybe even unsolvable in the given constraints.
 » 3 years ago, # |   +60 Please create a blog "How to admit my mistakes, and not be a d*ck".
 » 3 years ago, # |   -82 The new bredor?
 » 3 years ago, # |   +18 Why this is not added to the front page?... it seems the organization is interfering again, don't worry Um_nik, I'll try to broke the convergence again.
 » 3 years ago, # |   +16 This post was actually very helpful to me. So thank you for this.
 » 3 years ago, # |   +45 I'm not sure about others, but let me give you two examples why/how one can feel a statement unclear or hard to read.In the "Networking the "Iset" problem, there is a line "it was decided that only the links that are required to make a connected network will be installed". Now one can interpret this sentence in two ways: a) "only the bridges of the graph will be installed" b) the one you mentioned. And you can not blame the group of people who interpreted it as a, can you? Yah, may be after reading the remaining part of the statement/sample it will become clearer, but the author should have used better sentence here.In the short statement of "Magic Programmer", you wrote "each vertex has some subset of universe of size m". How should one read it? (subset of (universe of size m)) or ((subset of universe) of size m)? Similarly read this sentence from Div2-C: "For any two different colors a, b union of set of rooks of color a and set of rooks of color b is connected if and only if this two colors harmonize with each other." I had to read this sentence a few times to understand exactly what the author meant. Because this is a crucial line, and misunderstanding means solving wrong problem. Just look at how many "of"s are there in this sentence making this whole sentence very complicated. The author should have rewritten the sentence, may be splitting it into simpler sentences, or may be introducing some abstract concept.I agree people send stupid clars, I do get angry when I get those. But sometime people really struggle to understand and I tried to give you couple of such examples. On different note, I personally struggled a lot to read Div1-D of this contest. I am skipping explaining the reason to not make the comment long, but if you want I can explain why.
•  » » 3 years ago, # ^ |   +7 Please do. You can do it in PM if you want.I also agree about some issues you mentioned, but I think that if the problem statement is big, it is a good idea to read it once to grasp overall ideas, what is connected with what, and then read it second time to understand details. Also reading key statements 3-4 times spends 1 minute and saves 10 minutes later.
 » 3 years ago, # | ← Rev. 3 →   -21 I belong to a doomed community of supposedly smart people.
•  » » 3 years ago, # ^ |   +33 Second sentence in your disjoint union article is exactly what I want. Symmetric difference has nothing to do with this problem.It is so funny to look at people who can't read blog about reading problem statements. But, sadly, not unexpected.
•  » » » 3 years ago, # ^ |   +10 lol you're right. point made. :)
 » 3 years ago, # |   -10 I see the hard work you do for community. Thank you! for writing the post for us. This is actually very helpful for me.
 » 2 years ago, # |   -50 up
•  » » 2 years ago, # ^ |   +64 left
•  » » 2 years ago, # ^ | ← Rev. 2 →   +23 Please next time when you will make contest with two different problems with similar statement do not give them the same name. Better describe difference between them in problem name.
 » 10 months ago, # |   0 It's very helpful
 » 8 months ago, # |   -8 First of all thank you for the article!May I ask you a question regarding a Work for Robots task? You wrote:Count the number of complete subgraphs. Nice and easy.I tried to solve it using Bron-Kerbosch algorithm (I found all maximal cliques, then count), but the thing is that there are many overlaps between the cliques, which makes it hard (at least for me) to count the number of distinct complete subgraphs. Am I missing something? Could you please point me in the right direction? Thanks.