FeiWuLiuZiao's blog

Is this rigorous
By FeiWuLiuZiao, history, 5 weeks ago, In English

This is my solution for 2040E - Control of Randomness. It passed the tests, but I’m not sure whether deriving the DP formula in this way (splitting the min, solving the equation, and then putting the min back) is rigorous.

More formally, if we have $$$x_0$$$ is the only number that satisfies $$$x_0=f(x_0)$$$, and so do $$$x_1$$$ and $$$g(x_1)$$$, can we say that $$$x=h(f(x),g(x))\Leftrightarrow x=h(x_0,x_1)$$$? What if $$$h(x,y)=\min(x,y)$$$?

This (used ChatGPT to translate)
Solution (original Chinese ver)
  • Vote: I like it
  • +32
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Or, what's the more basic logic behind this

→ Reply
»
5 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I have misread the constraints that $$$q = 3e5$$$ and did the same in the contest ToT 295629246

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

    when i'm vping this i just couldn't understand why isn't $$$q\le 2\times 10^6$$$ lol

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

    what's the problems with her eyes?

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

Please formulate a mathematically sound and logical query with everything correctly defined, I cannot understand what you actually tried to ask

However, what I suspect you want is the following: suppose we are in a state, now we must decide to pay coin or not. If we pay coin, then we leave and all is good. Otherwise, we could come back to the same place after one random step. Now it seems that we have to decide to pay or not yet again, but this is not necessary as the process is Markov/Stateless/Memoryless, nothing actually changed between the first time or later time you arrived (the total sunk cost did change, but you are only asking for expected cost, so it does not affect the expected cost. Note however if you are asking for probability of total cost <=k then it will change). This means you either always pay or never pay at this exact state, giving why the DP is valid.

The rearrangement could seem surprising in a dp but that is just a general equation solving in a random (here, markov chain) process.

→ Reply
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    what to do to gain this math formulation skills?

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

    thank you for introducing the Markov chain (✿◠‿◠)

    → Reply
»
5 weeks ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

upd:

For all $$$h(x,y)$$$, this doesn't always hold. For example:

$$$ f(x)=2x-1\\ g(x)=114514\\ h(x,y)=2^x $$$

then we have $$$x_0=1,x_1=114514,h(x_0,x_1)=2,h(f(2),g(2))=8$$$, so $$$h(x_0,x_1)$$$ is not a fixed point of $$$h$$$.

however, if we have $$$\forall x,y:h(x,y)=x\lor h(x,y)=y$$$, like $$$h(x,y)=\min(x,y)$$$, we can say that $$$x_0,x_1$$$ are the only possible fixed points.

let's define $$$A:=\{x\mid h(f(x),g(x))=f(x)\},B:=\{x\mid h(f(x),g(x))=g(x)\}$$$, then if $$$x\in A$$$, the fixed point of $$$h(f(x),g(x))=f(x)$$$ should be $$$x_0$$$. else if $$$x\in B$$$, it should be $$$x_1$$$. now, $$$x_0,x_1$$$ are the only possible fixed points for $$$h$$$. what we need to do is to check if $$$h(x_0,g(x_0))=x_0$$$ and $$$h(f(x_1),x_1)=x_1$$$.

thanks to my classmate MasCotangent for math helping :)

→ Reply