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

×

BGQRS - Unofficial Editorial

4
2

Hi,

I want to share my detailed editorial to BGQRS problem from October Long. I used approach which barely fits time limit, but it illustrates a nice useful method that can be used to deal with these kind of query problems.

I posted the editorial on my blog (there is a better math syntax available there):

Unofficial Editorial: Big Queries from Codechef October Long 2016

I hope you like it :)

asked 17 Oct '16, 15:08

pkacprzak's gravatar image

5★pkacprzak ♦♦
74485097
accept rate: 12%

edited 20 Oct '16, 15:01

admin's gravatar image

0★admin ♦♦
19.7k350498541

Sqrt Decomposition is a nice trick and can help to solve many problems. Thanks for sharing!!
Can you suggest some good problems to start mastering this trick?

(17 Oct '16, 16:08) ankurverma19944★
2

@ankurverma1994 I added one bonus problem at the bottom of the editorial. It is perhaps the most classical one you can get.

(17 Oct '16, 16:11) pkacprzak ♦♦5★

And Why did you choose KMax as 20? Thanks

(18 Oct '16, 10:04) vishveshcoder4★

@vishveshcoder As you can see, I set K (the initial size of a block) to be max(20, sqrt(n)). The constant 20 is chosen arbitrary. I did it in order to avoid extremely small blocks when sqrt(n) is small. Notice that later I set num_of_blocks = N / K. However, I think that you can just write K = sqrt(n) and everything should work just fine.

(18 Oct '16, 18:19) pkacprzak ♦♦5★

My solution

is O(N log N) too with Segment Tree and Lazy Propagation, pass in 0.71 s.

link

answered 09 Nov '16, 13:42

eteruel's gravatar image

3★eteruel
11
accept rate: 0%

Answer is hidden as author is suspended. Click here to view.

answered 23 Oct '16, 01:12

saksham2405's gravatar image

5★saksham2405
(suspended)
accept rate: 0%

Here is my solution which uses single segment tree. It uses oops to further simplify the problem.Solution link

link

answered 23 Oct '16, 00:31

nikil_agar's gravatar image

4★nikil_agar
29
accept rate: 0%

little complex.. :)

link

answered 19 Oct '16, 02:35

rohitangira's gravatar image

2★rohitangira
939
accept rate: 0%

codechef is very slow in updating editorials

link

answered 18 Oct '16, 14:47

akki28's gravatar image

4★akki28
783
accept rate: 10%

can anyone suggest mistakes in my link text solution please??

And Why do we need to store the ex2,ex5,lz2,lz5?? can anyone please explain??

link

answered 18 Oct '16, 13:19

tejaram15's gravatar image

2★tejaram15
212
accept rate: 0%

16

Here is comparatively short and clean implementation of O (n lg n) solution based on segment-tree approach passed in 0.52 seconds. solution

link

answered 18 Oct '16, 12:26

anshal21's gravatar image

4★anshal21
6068
accept rate: 7%

I have tried to implement the Lazy Propagation on a Segment Tree to fetch the queries and update the values in O(logN). But my solution wasn't accepted. Can someone help me out with where am I going wrong? PS: My code gives the correct output for the given test case and some random test cases. Here is my code.

link

answered 17 Oct '16, 18:21

cyber_warrior's gravatar image

3★cyber_warrior
12
accept rate: 0%

8

As your solution is too lengthy I can not read it completely but the thing is that your propagation of updates is not correct , for the test case-
1
7 6
1 2 3 4 5 6 7
1 2 6 5
2 2 7 1
1 2 5 2
3 1 4
3 3 7
3 2 6

your codes output is "6" but it should be "2" so simulate your codes working on this test case and you will know the mistake.

(22 Oct '16, 13:22) anshal214★

You should see my solution if you are not very good in segment tree . good and easy solution to understand . i used basic concept (as zscoder described power of 2 and 5) . you can easily understand hows lazy working
Solution

link

answered 17 Oct '16, 17:26

yb4singh's gravatar image

4★yb4singh
1215
accept rate: 0%

My solution is $\mathcal O(n \lg n)$ and passed in $0.47$ seconds with some preprocessing. Idea is same as @zscoder described.

link

answered 17 Oct '16, 16:18

nirjhor's gravatar image

6★nirjhor
812
accept rate: 0%

The Intended solution was i think uses Segment tree or similar binary data structure.

The takeaway from the problem was to learn how two lazy fields propagate down the tree during queries.
One lazy term was for the Multiplying a number to a node and then marking its children lazy(if they exist) and one lazy term was for resetting the node to a new sequence which was nothing but a factorial multiplied by a number and mark the children lazy for reset.

While propagating a reset update you can ignore the child's previous lazy terms(both), convince yourself here. For propagating "multiplication" update if you encounter a node having reset lazy field then first reset the node from its reset lazy field, mark its child lazy for reset and then do a update query on this node.

For double-lazy propagation to work, in my opinion, there should be at least one reset update of some kind, because reset update tells us that we can ignore the child previous lazy terms and set them according to the new update, irrespective of the child node history, as it is a reset update. If you don't have a reset update, then after some queries you will notice that some nodes contain both the lazy terms and you would not be able to distinguish which one to apply first and usually the order in which they are applied would matter and would yield different result, unless you suggest me some two different good operation whose order of application yields the same result(then that would make a good codechef long challenge problem :P)

REFERENCE SOLUTION

[EDIT]
A similar question that you can try is SEGSQRSS, although the test cases are very weak and you can get AC without lazy propagation, but then its just a waste of time. Do try that.

link

answered 17 Oct '16, 16:00

ashwanigautam's gravatar image

3★ashwanigautam
187213
accept rate: 0%

edited 17 Oct '16, 16:09

I tried to solve using same approach. I am getting WA. Please help. :)

https://www.codechef.com/viewsolution/11867542

(17 Oct '16, 16:15) dushsingh19954★

there is no need for a boolean(type2, in you code) to tell us whether reset is necessary or not. Notice you can simply set tree[node].st = -1 (for example) to indicate this node doesn't require reset operation. Our solution are two much similar.. hope we don't find ourself in plagiarism :P (LOL). couldn't find the bug Yet.

(17 Oct '16, 17:27) ashwanigautam3★

Nice. Though Sqrt Decomposition is viable here, I have an alternative solution using Lazy Propogation on Segment Tree.

The only "hard" query here is the second one. However, if you store :

  1. The largest power of $2$ and $5$ that divides the product of the segment
  2. A boolean denoting whether a lazy update is needed
  3. The type of update that has to be applied (either a range multiplication or reset)
  4. The ends of the segment $[l, r]$
  5. $ex2, ex5$ denoting that we should multiply the range by $2^{ex2}$ and $5^{ex5}$
  6. The endpoints of the current type $2$ query that needs to be propogated
  7. $laz2, laz5$ denoting the largest power of $2$ and $5$ of $y$ in a type $2$ query.

AC Solution

link

answered 17 Oct '16, 15:45

zscoder's gravatar image

6★zscoder
62813
accept rate: 6%

Sure, also noticing that the second query can be transformed to first assigning sequence 1,2,.. and then multiply it by Y can help a lot while handing that query. Lazy Propagation is something closer to the intended solution. Using sqrt blocks was too tempting for me, so I went for it - I see that we have similar run times, did you need to optimize your solution?

(17 Oct '16, 15:54) pkacprzak ♦♦5★

you sure the largest ?

(17 Oct '16, 16:02) ashwanigautam3★
2

@pkacprzak My solution passed without fastio too, but fastio is slightly faster.

(17 Oct '16, 16:11) zscoder6★

Nice editorial or I would say article.

I have added my editorial/explanation to the same problem. The Update and Query range complexity for my solution is O(ln(N)). It runs in .77 seconds in java. You can see the same in my solution.

link

answered 17 Oct '16, 15:16

ashok1113's gravatar image

4★ashok1113
913
accept rate: 0%

edited 17 Oct '16, 15:21

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:

×15,630
×20
×9

question asked: 17 Oct '16, 15:08

question was seen: 6,186 times

last updated: 09 Nov '16, 13:42