You are not logged in. Please login at www.codechef.com to post your questions!

×

Editorial for SHMIRZ - PELT2019

Problem Setter: xodiac

Difficulty: Medium-Hard

Prerequisites: Square root decomposition, Convex Hull Trick

Explanation:

Question is to find maximum chocolates in exchange of x coins. Given a set of lines of form Y=A*x+B, the question is to find the maximum value of Y for a given x. We will use Convex Hull Trick to find the maximum value of Y i.e chocolates. Divide the array into sqrt(n) blocks . We will maintain a CHT for each block.

For query 1 : To remove an element you can find the block in which the element is present in sqrt(n) time. It will take an order of sqrt(n) time to remove the element from that block as the size of each block is sqrt(n) . Similarly, for inserting an element it will take order of sqrt(n) time . After removing and inserting an element we will need to update the CHT for corresponding blocks. It will take sqrt(n)log(sqrt(n)) time to rebuild the CHT for corresponding blocks . We will need to rebuild the whole square root decomposition after sqrt(n) queries of type one as in worst case it may be possible that the number of elements in a block becomes equal to n. If we rebuild then the number of elements in a block will not exceed 2sqrt(n).

For query 2 : To answer the query of second type we will iterate the blocks which lies completely between the given range [L,R] and brute force for starting and ending blocks. It will take sqrt(n)*log(sqrt(n)) time .

So the overall complexity will be qsqrt(n)log(n)

Author’s Solution: click here
Tester’s Solution: click here

asked 11 Jan, 18:39

panik's gravatar image

5★panik
1166
accept rate: 7%

edited 11 Jan, 18:47

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,236
×151
×81
×32
×10
×2
×2

question asked: 11 Jan, 18:39

question was seen: 76 times

last updated: 11 Jan, 18:47