alpha_1001's blog

Is there any general way...!
By alpha_1001, history, 3 years ago, In English

Is there any general way of approaching any problems like this...

Suppose, Given two arrays A and B, we have to select any subsequence of A, which satisfies the given properties (XYZ) having minimum or maximum value.

Suppose any selected subsequence of A is S = {A_i1, A_i2, A_i3, ..., A_ik} which satisfy the given properties (XYZ), then the value of Subsequence S is V = {B_i1 @ B_i2 @ B_i3 @ ... @ B_ik}, where @ is any function.

Our goal is to minimize or maximize or ..., the value V of subsequence S.

P.S.: Share any resources related to this, if any.

Problem 1 : 510D - Fox And Jumping

Share your own way to solve problems like this.

P.S.: Comments some more related problems, if you know.

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

Comments Comments (3)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by alpha_1001 (previous revision, new revision, compare).

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

Generally, the answer to such questions is "no, there is no general way" or if there is one, it will be very vague.. Because the goal of CP problems is to be interesting for participants and thus, authors try to make every problem somewhat unique, striving to contain some new idea never seen before. This is in contrast to school exam problems (where usually, a fixed set of techniques is tested) or real-life problems (where certain types of things just happen to come up more often).

The simplest general way to solve such problems is DP, defining $$$\mathrm{dp}[i][j]$$$ to be the best (minimum, maximum, ...) way to pick a subsequence from the positions $$$1 \ldots i$$$ such that the @ of the picked subsequence is $$$j$$$. But this is usually not good enough, because the number of states will become too big. And it will be even worse because we usually need to add some states to satisfy the constraints (XYZ).

The way to solve these problems is instead to make observations about the constraints you're given and about the @ and piece them together. In every problem, they will be a bit different, but in CP, this means that the solutions might be a lot different, because most of the time, solutions use some specific property of the XYZ.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    For example, in your problem the solution is:

    1. Notice that the condition is equivalent to the fact that the gcd of the items you pick must be 1. This actually is a standard observation.
    2. Pick one number to put in the solution (try all variants).
    3. Notice that the number only has up to 9 prime factors; you can replace each element with a bitmask saying which of these prime factors it has, and must pick the other numbers such that their bitwise and is 0.
    4. Use some bitmask dp to solve the problem.

    Notice that in step 3, we are already at a unique situation that wouldn't be possible if the "XYZ" constraint in the problem was different. In other problems like this, you wouldn't have this property of "we can consider numbers as bitmasks of length 9" and would instead have a completely different property, and the solution will also be completely different. For example, the other problem here, Jelly, has a very different idea.

    → Reply