Duelist1234's blog

Sometimes it is really about observation
By Duelist1234, history, 8 months ago, In English

A few days ago i stumbeld upon a 1200 which gave me a headache 1822D - Super-Permutation , and just now i solved it. What i want you to do is look at this problem and try figuring it out , then read the rest of this post.

The way i solved it , and what i believe to be the easiest way of solving it looking at last test case and finding the pattern, after this you should be all set , the implementation is really easy.

This problem taught me that i really need to observe the test cases more , even if there is really only one useful test case.

Enjoy the rest of your day.

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

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

For such questions i generally write brute force and observe the pattern like here it was n 1 n-2 3.... and so on

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

A very similar problem appeared on the Junior Bosnian Mathematical Olympiad. link

Translation:

Let $$$n$$$ be a natural number and let $$$a_1, a_2, ... , a_n$$$ be natural numbers from the set $$$(1,2,...,n)$$$, where each one of those numbers appears exactly once. Is it possible that the numbers $$$a_1, a_1 + a_2, ..., a_1 + a_2 + ... a_n$$$ all have different residues upon division with $$$n$$$ if: a) $$$n = 7$$$; b) $$$n = 8$$$?

→ Reply
»
8 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I do agree observation is important in many cases. However, I don't think you should consider a constructive problem "observation" or "finding the pattern" when you can't solve it; In fact, I think the other situation is you're not familiar with something related to the problem. (At least, I don't think the problem you mentioned above is all about observation, for I've come up with the construction almost instantly without looking around for too much, so maybe you're just not familiar with the nature of permutation and modulars)

Anyway, good luck on practising your observation skills XD

→ Reply
»
8 months ago, # |
  Vote: I like it +3 Vote: I do not like it

My brother in christ. This is not what people mean with "make observations about the problem".

https://codeforces.net/blog/entry/106346

In most problems, you are presented with some structure (broadly speaking). In a harder problem, you can't directly calculate the thing you are asked to. 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. There will be examples below.

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.

Making observations generally doesn't mean looking at input/output pairs and noticing patterns. It can mean that in some problems (for example, in game problems with just 2 parameters, you can often brute-force and notice the pattern) but it is not what it means in general.

Really, an observation is like a little theorem. 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.

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

    nicely explained , i have one question ,how to come up observations faster? i go through the same process you mentioned to solve problems, but the thing is i am very slow, also it's not like i lack practice in this method or anything. the chain of reasoning you mentioned ,, it takes me lot of time to go through that and arrive at useful observations about the problem and by that time the contest is over.

    → Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

That's not an observation. It's a hack for sometimes solving problems in a contest. It's a useful hack and is also a way of ACing the problem but you can't put every constructive problem in the same category. (as many problems have multiple valid outputs)

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for educating us

→ Reply