English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Consider a variant of Tetris played on a board of width $w$ and infiniteheight, where the pieces are axis-aligned rectangles of arbitrary integerdimensions, the pieces can only be moved before letting them drop, and a rowdoes not disappear once it is full. Suppose we want to follow a greedystrategy: let each rectangle fall where it will end up the lowest given thecurrent state of the board. To do so, we want a data structure which can alwayssuggest a greedy move. In other words, we want a data structure which maintainsa set of $O(n)$ rectangles, supports queries which return where to drop therectangle, and updates which insert a rectangle dropped at a certain positionand return the height of the highest point in the updated set of rectangles. Weshow via a reduction to the Multiphase problem [P\u{a}tra\c{s}cu, 2010] that ona board of width $w=\Theta(n)$, if the OMv conjecture [Henzinger et al., 2015]is true, then both operations cannot be supported in time $O(n^{1/2-\epsilon})$simultaneously. The reduction also implies polynomial bounds from the 3-SUMconjecture and the APSP conjecture. On the other hand, we show that there is adata structure supporting both operations in $O(n^{1/2}\log^{3/2}n)$ time onboards of width $n^{O(1)}$, matching the lower bound up to a $n^{o(1)}$ factor.

How Fast Can We Play Tetris Greedily With Rectangular Pieces?