Блог пользователя FiniteMoves

Автор FiniteMoves, 3 месяца назад, По-английски

How to approach problems , how to think in problems like : Construct a permutation having some particular property ?

  • Проголосовать: нравится
  • -3
  • Проголосовать: не нравится

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

You can watch this video which i made for solving this prolems.

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

There are several ways, at least that I've learned and that I'm practicing right now.:

1) Pay attention to the topic of the task (if the task has bitmasks or a hint of sorting, etc.)

2) If a formula is given, try to describe it in more detail, perhaps to bring it to a different form (for example, if it is necessary that the property $$$a_{i}*a_{j} = i*j$$$ is fulfilled, then this can be reformulated as $$$\frac{a_{i}}{i} = \frac{j}{a_{j}}$$$). Or, if the formula for the sum is given, the products should be painted in a row and see what can be reduced, which properties are fulfilled.

3) If a property is set (for example, a[i] + a[j] must be even for some j), then you need to try to consider what invariants this property has, i.e. what is ALWAYS preserved regardless of the choice of the value or , or under what circumstances, in principle, this property holds.

4) If bitmasks or a hint of them are specified, try to first consider parity (the lowest bit and how it changes depending on the design), then see if there are any bits that ALWAYS remain the same (the same invariant), and so on.

5) If something from the category "You will need to perform 0+1\k\n operations of the form ..." is set, then it is worth looking at what this operation does and changes in general, consider it with a small example, and then try to generalize

6) If nothing comes to mind at all, there is a radical, but often good way — in Python to generate all the permutations for n = 1, ..., 10 and then select only those that satisfy the condition, output them to the console. And you can often see a pattern that only needs to be implemented. (I don't like such tasks, simply because the whole solution is guessing. And when you look at the Editorial, they just say "One of the possible ways to build a permutation is [n, 1, n — 1, 2, ..., ]" which makes you feel like an idiot).

7) Solving tons of tasks with the tag "constructive". Only 2100+ can solve these problems for the reason of "Oh, I've seen something like this before" and not come up with a solution from scratch, but simply reproduce identical ideas. I declare that it works because I solve various simple tasks according to this principle, just because I really often come across something that I have already seen before. Although I am still very young and I have only ~ 1200 solved tasks from different platforms and tasks for constructive 1400+ are often difficult for me.

I know that my rating right now is not such that I can guarantee that it always works, but at least it helps me and I try to do it that way.