Um_nik's blog

By Um_nik, 6 years 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

| Write comment?
»
6 years 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!

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Yes True but helping when it is not good ROT to invetigate on a unnecessary problem is not doing hard work for you. one should understand when it is an irritating problem and when its not Will that investigation be useful for anther problem Most likely not. Is that probelm teaching you differencebetween set and multiset ? Most likely its a Skind I don not bother even checking its true or not Thats what I did I Ignored Problem and Moved to next One needs to know when It is Skind and one its not for them If enough people say its a skind, atleast problem writer will understand its a skind somebody need to tell right? If everyone stays to be coomfortable in accepting the uncomfortable then people forget to distingusih what is comfortable and what is not and what is good and what is bad when you have only both you will recognize the value of other

»
6 years ago, # |
  Vote: I like it +49 Vote: I do not like it

So, what's the point?

»
6 years 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

»
6 years 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? :)

  • »
    »
    6 years 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...

  • »
    »
    6 years 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.

»
6 years 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.

»
6 years 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".

»
6 years ago, # |
  Vote: I like it -82 Vote: I do not like it

The new bredor?

»
6 years 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.

»
6 years 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.

»
6 years 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.

  • »
    »
    6 years 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.

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

I belong to a doomed community of supposedly smart people.

  • »
    »
    6 years 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.

»
6 years 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.

»
5 years ago, # |
  Vote: I like it -50 Vote: I do not like it

up

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

    left

  • »
    »
    5 years 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.

»
2 years ago, # |
  Vote: I like it -46 Vote: I do not like it

Most of the problem statements are unclear.

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

fantastic!

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

thanks a lot

»
12 months ago, # |
  Vote: I like it -9 Vote: I do not like it

Everyone is so good, someone can give me some tips on learning programming,pls

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

冒泡

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi,

This might not be the best question, but can anyone please explain how to solve the "Scheduled Checking" problem mentioned in the examples?

I understand the reduction provided by the author. I have tried some approaches to solve the problem but have made no progress in a while.

My only idea that could have worked was to create the bi-partite graph consisting of vertices on the left hand and simple cycles on the right (as explained by the author). Then, run a maximum matching algorithm on this graph. Remove the edges in the matching from the graph, increment the answer by 1, and then repeat until all the edges have been covered.

I have a couple of questions:

  1. "After that reduction it is kinda known problem", which known problem is this ?
  2. Do I need to generate the entire bipartite graph as defined above? The number of cycles in a complete graph with 14 nodes will be of the order of 14!, so I don't think it's even possible to generate the entire graph.

Any advice would be greatly appreciated.

Thanks

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

    "After that reduction it is kinda known problem", which known problem is this ?

    Edge coloring.

    Do I need to generate the entire bipartite graph as defined above? The number of cycles in a complete graph with 14 nodes will be of the order of 14!, so I don't think it's even possible to generate the entire graph.

    No. The big bipartite graph is only theoretical.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks for your suggestions