papa-ka-para's blog

need help in upsolve.

By papa-ka-para, history, 12 months ago, In English

Hi all,

I am trying to upsolve this problem. https://mirror.codeforces.com/contest/1699/problem/E

Can someone please help me understand the first two paragraphs of the editorial ?

How to build the DP solution that is mentioned in the paragraph-2 ?

How to do it in O ( vmax * log vmax * log vmax ) ?

Thanks in advance.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
12 months ago, # |
← Rev. 3   Vote: I like it -6 Vote: I do not like it

I think the solution in the editorial is overkill. My solution:

  • You want to write all values as products of integers in $$$[i, j]$$$, where $$$j-i$$$ is the smallest possible.
  • For each $$$i$$$, you want to find the smallest $$$j$$$. If $$$i$$$ increases, $$$j$$$ increases, so you can use two pointers and try to answer "can you write all values only using $$$[i, j]$$$?". After processing $$$[i, j]$$$, you must be able to process either $$$[i, j+1]$$$ or $$$[i+1, j]$$$ fast.
  • Let $$$f(x)$$$ be $$$1$$$ if you can write $$$x$$$ using $$$[i, j]$$$, $$$0$$$ otherwise. The transition from $$$[i, j]$$$ to $$$[i, j+1]$$$ is $$$f(k(j+1))$$$ |= $$$f(k)$$$ for all $$$k$$$ from $$$1$$$ to $$$m/(j+1)$$$ (similar to adding $$$j+1$$$ to a knapsack with product instead of sum).
  • Removing $$$i$$$ from the knapsack is possible if you let $$$f(x)$$$ be the number of ways to write $$$x$$$, modulo a random prime (instead of $$$0$$$ or $$$1$$$). For example, see abc321_f.

The complexity is $$$O(n + m \log m)$$$, because each $$$i$$$ is added and removed from the knapsack at most once.

→ Reply