Um_nik's blog

By Um_nik, 13 months ago, In English,

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.

Networking the "Iset"

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

Coolest trick of reading statements

Zamkadye

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
 
 
 
 
  • Vote: I like it
  • +381
  • Vote: I do not like it

»
13 months ago, # |
Rev. 3   Vote: I like it +167 Vote: I do not like it

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!

»
13 months ago, # |
  Vote: I like it +49 Vote: I do not like it

So, what's the point?

»
13 months ago, # |
  Vote: I like it -35 Vote: I do not like it

Yeah I believe Problem statement should be short simple and precise...

butsome problem setter are more literature lover than CPer

»
13 months ago, # |
Rev. 2   Vote: I like it +69 Vote: I do not like it

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? :)

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

    If you only knew how many random things by problemsetters I've deleted from statements...

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

    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.

»
13 months ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it

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.

»
13 months ago, # |
  Vote: I like it +60 Vote: I do not like it

Please create a blog "How to admit my mistakes, and not be a d*ck".

»
13 months ago, # |
  Vote: I like it -82 Vote: I do not like it

The new bredor?

»
13 months ago, # |
  Vote: I like it +18 Vote: I do not like it

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.

»
13 months ago, # |
  Vote: I like it +16 Vote: I do not like it

This post was actually very helpful to me. So thank you for this.

»
13 months ago, # |
  Vote: I like it +45 Vote: I do not like it

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.

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

    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.

»
13 months ago, # |
Rev. 3   Vote: I like it -21 Vote: I do not like it

I belong to a doomed community of supposedly smart people.

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

    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.

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

I see the hard work you do for community. Thank you! for writing the post for us. This is actually very helpful for me.

»
4 months ago, # |
  Vote: I like it -50 Vote: I do not like it

up

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

    left

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it +23 Vote: I do not like it

    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.