Шестоугао
Аутор: Никола Милосављевић
Текст и тест примери: Алекса Милисављевић
Тестирање: Павле Мартиновић
Анализа решења: Алекса Милисављевић
Прва ствар коју треба да приметимо је да услов да је фигура шестогао и да има странице паралелне ивицама матрице заправо значи да је у питању фигура која се добија тако што из правоугаоника избацимо мањи правоугаоник који је такав да им се тачно један ћошак поклапа.
Решење када N \leq 5
У овом подзадатку можемо да фиксирамо сваки шестоугао, проверимо да ли је он леп и прерачунамо одговор за сваку подматрицу. Различитих шестоуглова има О(N^6), док различитих подматрица има O(N^4). Због тога, ово решење ради у временској сложености О(N^{10}).
Временска сложеност је О(N^{10}), а меморијска O(N^4).
Решење када A = 8, Q \leq 10
Приметимо да су шестоуглови са обимом 8 управо квадрати димензија 2 \times 2 из којих је избачен један ћошак. Таквих шестоуглова има O(N^2) у матрици. У сваком упиту можемо да итерирамо кроз целу подматрицу и израчунамо збир бројева у сваком лепом шестоуглу.
Временска сложеност је O(Q \cdot N^2), а меморијска је O(N^2).
Решење када N \leq 50, Q \leq 10
За решавање овог подзадатка морамо детаљније да размотримо када тачно избацивањем мањег правоугаоника из већег настаје леп шестоугао.
Претпоставимо да смо имали правоугаоник димензија w \times h и да смо из једног његовог ћошка избацили правоугаоник димензија p \times q. Посматрајмо два случаја:
- Први случај: w \neq h, тј. оргинални правоугаоник није квадрат. Без умањења општости, претпоставимо да w > h. Шестоугао који настаје брисањем правоугаоника има странице дужина w, h, w-p, q, p, h-q. Како w \neq h и како у шестоуглу, да би био леп, свака дужина мора да се јавља барем два пута , то мора да важи w = w-p или w = q или w = p или w = h-q. Међутим, како важи p, w-p < w и q, h-q < h < w , то овај случај није могућ, тј. шестоугао мора бити квадарат.
- Други случај: w = h. Уведимо a = w = h. Шестоугао који настаје брисањем правоугаоника има странице дужина a, a, a-p, q, p, a-q. Како свака дужина мора да се јавља барем два пута, то разликујемо следећа два случаја: p = q и p = a - q. Додатно, приметимо да је обим овог шестоугла управо a + a + a - p + q + p + a - q = 4a, тј. a = \frac{A}{4}.
Дакле, да би шестоугао био леп, он мора да настане тако што се из квадрата странице a = \frac{A}{4} избаци правоугаоник димензија p \times q, за које важи p = q или p + q = a. Приметимо да у почетној матрици квадрата странице a има (N-a+1)^2, а за сваки од њих постоји 4(a-1) правоугаоника које можемо да избацимо да би добили леп шестоугао. Дакле, укупно постоји O(N^3) лепих шестоуглова у матрици.
Користећи ову информацију, лако можемо да решимо подзадатак. У сваком упиту, прођемо кроз све лепе шестоуглове. Ово је најлакше урадити тако што прво фиксирамо горњи леви ћошак квадрата из којег бришемо правоугаоник, затим странице правоугаоника и коначно један од четири ћошка квадрата који се поклапа са правоугаоником.
Временска сложеност је O(Q N^3), а меморијска је O(N^2).
Решење када N \leq 50
Овај задатак захтева да мало поправимо решење из претходног. Кључно је приметити да за сваки горњи леви ћошак квадрата из којег избацујемо правоугаоник можемо да израчунамо леп шестоугао који настаје са највећим збиром. Ово запамтимо за свако поље. Потом у сваком упиту прођемо кроз сва поља која су кандидати за горњи леви ћошак правоугаоника и на тај начин пронађемо леп шестоугао са највећим збиром који се потпуно налази у подматрици из упита.
Временска сложеност је O(Q N^2), а меморијска је O(N^2).
Решење када А = 8
За решења овог подзадатка је неопходна техника sparse tabela.
Прво у помоћној матрици b[i][j] запамтимо леп шестоугао са највећим збиром који је настао тако што смо квадрату коме је горње лево поље управо (i,j) склонили један ћошак.
У помоћној матрици sparse[i][j][k], прерачунамо максимуме свих лепих шестоуглова који настају од квадрата димензија 2 \times 2 којима је горњи леви ћошак на неком од поља из скупа \{(i,j),(i,j+1),...,(i,j+2^k-1)\}. За ову матрицу је лако наћу рекурзивну формулу:
sparse[i][j][0] = b[i][j],
sparse[i][j][k] = max(sparse[i][j][k-1],sparse[i][j+2^(k-1)][k-1])
На основу ове матрице, можемо да одговарамо на упите у временској сложености O(N). Нека је k највећи број такав да је 2^k \leq r-l. Да би одговорили на упит, прођемо кроз сваки ред i у интервалу [u,d-1] и за сваки од њих израчунамо вредност max(b[i][l][k],b[i][r-2^k][k]) (на овај начин смо узели максимум свих лепих шестоуглова којима је горњи леви ћошак у реду i). Максимум од свих тих вредности је одговр на упит.
Временска сложеност је O(N^2 \log N + Q N), а меморијска O(N^2 \log N) (ако памтимо увек само резултате претходног кола).
Главно решење
За главно решење, неопходно је генерализовати идеју из претходног подзадатка, коришћењем опсервације о томе какав правоугаоник морамо да избацимо да би добили леп шестоугао. У матрици b[i][j] запамтимо максимум свих лепих шестоуглова који су настали тако што смо избацили неки правоугаоник из квадрата којем је горње лево поље (i,j). Потом рачунамо и користимо табелу на сличан начин као у претходном подзадатку.
Временска сложеност је O(N^3 + Q N), а меморијска O(N^2 \log N).
Задатак је било могуће решити и у бољој временској сложености O(N^3 + N^2 \log^2 N + Q), коришћењем дводимензионалних табела, али то није било потребно за максималне поене.