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

×

November Lunchtime Editorials

6
2

Hello Guys...

This time I'm not posting any editorial because of an unavoidable reason (not being able to solve any problem complete :( ), but i still invite you all to share your approach for any of the four problems.

Even then, some of the users have shared their approaches for various problems, which are mentioned below:

SMRSTR

This problem has been discussed at here by @vipin_bhardwaj

SHUFFL

This problem has been discussed here by @aayushkapadia

L-R Queries using sqrt decomposition by @avi224

Break the array into blocks of size $\sqrt{N}$ and then use a $map$ containing frequencies of numbers in each block. For update, remove $A[l]$ from the block containing index $l($ $i.e.$ $l/block\_size)$ by decreasing its frequency and then add $y$ to it.

The key to solving the problem is to notice that we have to minimize the quadratic expression $(x-A[l])*(x-A[r])$ such that $x=A[m]$ and $l\le m \le r$. Note that the global minimum occurs at $x_0=0.5*(A[l]+A[r])$. We have to find this $A[m]$ nearest to $x_0$. This can be done using binary search (lower_bound() function in c++) on the frequency maps.

For query, just iterate from $l$ onwards and calculate normally until you find the start of a block. Iterate through every block as long as index $r$ is outside the block, and find the nearest $A[m]$. After the last block, calculate normally until index $r$ is reached.

The preprocessing part takes $O(N*log(N))$ and complexity is $O(\sqrt(N)*log(N))$ per query.

Refer to solution here

STRQUER

All credits to @mgch, the setter of this problem. (I can call this one as Official Editorial) (Copied from answers)

Hi, let me explain the 4th problem. let's make a couple observations:

1.If we have two connected segments that have a common part $[a..b] [x..y]$, we can create two segments that have no common part with connections between their first and second ends respectively.

2.It gives us next idea(let's sort our set, and divide it into connected groups), but if the size of a connected $group \ge 4$ we can split into two groups of sizes $[group/2]$ and $group-[group/2]$, the answer will be smaller, and every number will be connected.

3.Let we have order of set $A[1..N], DP[1..i]$ - the minimal cost to connect prefix A[1..i],

DP$2$ = A$2$ - A$1$

DP$3$ = A$3$ - A$1$

DP[x] = min(DP[x - 3] + A[x] - A[x - 2], DP[x - 2] + A[x] - A[x - 1]),

we checking where to connect x $\implies$ to x-1, or to x-2.

Let's rewrite that $DP, DP[i][j]$ denotes connection of the prefix $1..i, j=0$ denotes that $i$ is connected to $1..i-1, j=1$ denotes that $i$ should be connected to $i+1$.

$DPi = DP[i-1][0], DP[i][0] = min(DP[i-1][0],DPi-1)+A[i]-A[i-1]$, for $i \ge 3$.

But how to maintain add/erase queries? Let's make one more observation we can keep DP for the segment $l..r$ in a similar way:

$ DP[l..r][i][j] (r-l\ge1)$ denotes minimal value to connect everything in the segment $l..r$, if $i=1$, $l$ should be connected to $l-1$, otherwise it's connected to the segment $l..r$.

If $j=1$, $r$ = should be connected to $r+1$, otherwise connected to the segment $l..r$.

For $r-l==1$ and $r-l==2$ better to recalculate DP with hands.

For $r-l \ge 3$, we can split segment into to $l..m$, and $m+1..r$, and recalculate $DP[l..r][x][y]$ as $min(DP[l..m][x][i] + DP[m+1..r][j][y] + (1 - i) * (1 - j) * (A[m + 1] - A[m]))$.

Only in one case we don't need to take $A[m+1]-A[m]$, if $A[m]$ is connected to $l..m$ and $A[m+1]$ is connected to $m+1..r$. We need to add some data structure for the solution, we can use cartesian tree/splay tree, but it's very painful to write that, (I did it, I know what I'm saying about :) )

Let's use implicit segment tree(also, we can read all queries, compress the values and use normal segment tree) and for each node to save ($min$ and $max$ on the segment in the segment tree, $dp2$ and other things), after that we can combine two segments into one, by operations as described above.

We have a solution with complexity $O(Q log N)$ but with huge constant around $(~log N)$. My solution with cartesian is very hard to understand, you can write yours, maybe my debugging solution will help understand what's going on: https://pastebin.com/PuFTvuNy

And i hope you guys would like to share your approach as always. :)

This question is marked "community wiki".

asked 25 Nov, 23:59

taran_1407's gravatar image

5★taran_1407
2.2k622
accept rate: 22%

edited 04 Dec, 04:37

1
(26 Nov, 00:24) aayushkapadia6★

Well this time , both of us missed the contest.

(27 Nov, 21:58) trashmaster3★

I didn't miss contest, it went badly for me (my worst till now) :)

(27 Nov, 23:28) taran_14075★

@vijju123, pleaseeee have a look at the formatting of LRQUER editorial.... I tried to use latex feature, but couldn't...

Help!!

(04 Dec, 04:39) taran_14075★

@taran_1407 please elaborate the observation 2 in the last question!

(04 Dec, 18:26) pk3012★
1

@pk301, i have added an explanation in answers.

(04 Dec, 18:52) taran_14075★
showing 5 of 6 show all

Here is my LRQUER solution.

$(A_M-A_L)*(A_R-A_M) = (A_R+A_L)*A_M-A_M^2-A_L*A_R$. The last term is constant, so it doesn't matter. You are looking for maximum of $(A_R+A_L)*A_M-A_M^2$ thus minimum of $A_M^2-(A_R+A_L)*A_M$. You can notice, that $A_M^2-(A_R+A_L)*A_M = (A_M-\frac{A_R+A_L}{2})^2-(\frac{A_R+A_L}{2})^2$. The second term is constant, so it doesn't matter. Thus you are looking for minimum of $(A_M-\frac{A_R+A_L}{2})^2$ which is the same as minimum of $\left|A_M-\frac{A_R+A_L}{2}\right|$, so you need to find the element with minimum absolute difference from $\frac{A_R+A_L}{2}$.

In a node store all the array numbers in a multiset, which are below the node.

This segment tree has $N*\log{N}$ space complexity, which fits in ML for $N \leq 10^5$. Building the segment tree can be done as usually, you have to merge the two children's sets in a node.

When updating, you can erase the old value from the set, and insert the new one. It takes $O(\log{N})$ to update a node, and you have to update $O(\log{N})$ nodes, so overall updating is $O(\log^2{N})$.

When querying, you can go through the $O(\log{N})$ nodes which contains the values of the segment. At each node, you can do a lower_bound on the set for $\frac{A_L+A_R}{2}$, and thus check the elements closest to it. It takes $O(\log{N})$, so overall query is $O(\log^2{N})$.

This results in $O(Q\log^2{N})$ time complexity.

link

answered 26 Nov, 00:47

bazsi700's gravatar image

6★bazsi700
3057
accept rate: 9%

edited 26 Nov, 00:49

that multiset idea was really cool :)

i have done the same but used sqrt decomposition for handing that(using vectors) but this was really awesome !

thanks for sharing this :)

(26 Nov, 07:53) pk3012★

we don't have multiset in java any suggestion for this case

(26 Nov, 10:51) ayush2013★
1

@ayush201 You could use a Map and store the count of each element. It should have the same complexity.

(26 Nov, 15:01) bazsi7006★

@bazsi700 - https://www.codechef.com/viewsolution/16378208 i have implemented similar approach here, but it is timing out can you have a look why?

(26 Nov, 18:13) divyansh_gaba75★

@divyansh_gaba7 The problem is you use std::lower_bound in query, which is $O(N)$ on sets. You should use std::set::lower_bound which runs $O(\log{N})$, thus replace lower_bound(t[l].begin(),t[l].end(),m) by t[l].lower_bound(m).

I faced the same problem once, and posted a blog about it on CF, where I got explanation for it: http://codeforces.com/blog/entry/55450

(26 Nov, 18:35) bazsi7006★

how could this brute force solution can get 100% AC https://www.codechef.com/viewsolution/16379351

(26 Nov, 21:39) ayush2013★

@bazsi700 can you please tell why you have added .01 in (a[l] + a[r])/2.0

(27 Nov, 20:06) vipin_bhardwaj4★
1

@vipin_bhardwaj To avoid double precision issues. The sum of $A_L$ and $A_R$ may be odd, this is why we need double, but double can have precision issues, so you can't use = sign on doubles.

E.g. if you have this code: double x = 2; x = (x*5)/2;

then probably x == 5 expression will be false, because x will be something like 4.999999 or 5.0000001.

That's why you should always compare doubles with an error, which I chose 0.01.

(27 Nov, 21:32) bazsi7006★

Wow... please tell me this one also let a[l] + a[r] = 5 than we will be finding value in array which is closer to 2 or 3, what should we choose.

(27 Nov, 23:32) vipin_bhardwaj4★
1

I used (l+r)/2 for floorkey and (l+r+1)/2 for ceilkey, no messing with double.

(27 Nov, 23:57) taran_14075★

@bazsi700 ooo that's an interesting catch. Thank you very much mate! Highly appreciated.

(28 Nov, 02:11) divyansh_gaba75★

That thing was hard af to debug. I cant believe I missed that. set lowerbound and normal lowerbound. The more you know about STL XD

(28 Nov, 02:13) vijju123 ♦4★

@vijju123 It took me 2 hours of thinking and googling to find it out. Glad to share it with others, and spare their time :P

@taran_1407 There wasn't too much messing

(28 Nov, 02:25) bazsi7006★

@vijju123 - Sorry xD i will try to put more readable code with some documentation before asking for help next time. Thank you for your efforts! and thanks bazsi once more.

(28 Nov, 02:29) divyansh_gaba75★
showing 5 of 14 show all

$LRQUER(Prerequisite:$ $Square-root$ $decompositon$, $binary$ $search$, $STL$ $map)$

I solved LRQUER using $square-root$ $decomposition$. Break the array into blocks of size $\sqrt{N}$ and then use a $map$ containing frequencies of numbers in each block. For update, remove $A[l]$ from the block containing index $l($ $i.e.$ $l/block\_size)$ by decreasing its frequency and then add $y$ to it.

The key to solving the problem is to notice that we have to minimize the quadratic expression $(x-A[l])*(x-A[r])$ such that $x=A[m]$ and $l\le m \le r$. Note that the global minimum occurs at $x_0=0.5*(A[l]+A[r])$. We have to find this $A[m]$ nearest to $x_0$. This can be done using binary search (lower_bound() function in c++) on the frequency maps.

For query, just iterate from $l$ onwards and calculate normally until you find the start of a block. Iterate through every block as long as index $r$ is outside the block, and find the nearest $A[m]$. After the last block, calculate normally until index $r$ is reached.

The preprocessing part takes $O(N*log(N))$ and complexity is $O(\sqrt(N)*log(N))$ per query.

My solution

Feel free to ask in case of any doubts :)

link
This answer is marked "community wiki".

answered 26 Nov, 00:17

avi224's gravatar image

5★avi224
1528
accept rate: 25%

edited 26 Nov, 17:31

Mate, shouldn't the expression be (x-A[l])*(A[r]-x)??

(26 Nov, 00:22) taran_14075★

Ya, we had to maximise that. So, I took the negative and minimized it. It was a bit clearer.

(26 Nov, 00:24) avi2245★

Oh.. :) missed that...

(26 Nov, 00:25) taran_14075★

I think your link is broken. Can you please fix it.

(26 Nov, 00:30) aayushkapadia6★

I've fixed it :)

(26 Nov, 00:33) avi2245★
1

During contest, I first thought of this solution only. But I thought time complexity will be too much. So as your time complexity is O(TQsqrt(N)log(N)) and let T=2 and N=Q=1e5. So that summation is less than 2e5. Then 2 X 1e5sqrt(1e5)log(1e5) comes out to be roughly 1e9. I thought that 1e9 will not work in 4 sec. Nice to see it worked. I coded segment tree during contest to remove sqrt factor and place logN factor. So my solution is O(QNlogNlogN). My solution for segment tree : https://www.codechef.com/viewsolution/16370436

(26 Nov, 00:41) aayushkapadia6★

Can you explain how the frequency map is constructed?

(26 Nov, 01:44) ramini3★

@ramini For each block, we use a map maintaining the frequency of all (distinct) elements in that block.

(26 Nov, 09:56) avi2245★

@avi224 u take vector<map<int,int>> why int as constraint of A[i]<=10^9?please explain

(26 Nov, 15:01) prince3674★

@prince367 The A[i]'s are the keys of the maps. The way data is stored in maps is different. If I insert 10^9 into the map, it goes to the first instead of the 10^9 th position as it would do for arrays.

(26 Nov, 16:22) avi2245★
4

Btw, if you'll use https://en.wikipedia.org/wiki/X-fast_trie you can update your solution theoretically to O(Q sqrt (N log log N)), I don't how it goes practically, next and previous elements can be found in time O(log log N), but insert/erase in O(log N)

(26 Nov, 16:32) mgch7★
showing 5 of 11 show all

Hi, let me explain the 4th problem. let's make a couple observations:

1.If we have two connected segments that have a common part $[a..b] [x..y]$, we can create two segments that have no common part with connections between their first and second ends respectively.

2.It gives us next idea(let's sort our set, and divide it into connected groups), but if the size of a connected $group \ge 4$ we can split into two groups of sizes $[group/2]$ and $group-[group/2]$, the answer will be smaller, and every number will be connected.

3.Let we have order of set $A[1..N], DP[1..i]$ - the minimal cost to connect prefix A[1..i],

DP[2] = A[2] - A[1]
DP[3] = A[3] - A[1]
DP[x] = min(DP[x - 3] + A[x] - A[x - 2], DP[x - 2] + A[x] - A[x - 1]),

we checking where to connect x $\implies$ to x-1, or to x-2.

Let's rewrite that $DP, DP[i][j]$ denotes connection of the prefix $1..i, j=0$ denotes that $i$ is connected to $1..i-1, j=1$ denotes that $i$ should be connected to $i+1$.

$DP[i][1] = DP[i-1][0], DP[i][0] = min(DP[i-1][0],DP[i-1][1])+A[i]-A[i-1]$, for $i \ge 3$.

But how to maintain add/erase queries? Let's make one more observation we can keep DP for the segment $l..r$ in a similar way:

$ DP[l..r][i][j] (r-l\ge1)$ denotes minimal value to connect everything in the segment $l..r$, if $i=1$, $l$ should be connected to $l-1$, otherwise it's connected to the segment $l..r$.

If $j=1$, $r$ = should be connected to $r+1$, otherwise connected to the segment $l..r$.

For $r-l==1$ and $r-l==2$ better to recalculate DP with hands.

For $r-l \ge 3$, we can split segment into to $l..m$, and $m+1..r$, and recalculate $DP[l..r][x][y]$ as $min(DP[l..m][x][i] + DP[m+1..r][j][y] + (1 - i) * (1 - j) * (A[m + 1] - A[m]))$.

Only in one case we don't need to take $A[m+1]-A[m]$, if $A[m]$ is connected to $l..m$ and $A[m+1]$ is connected to $m+1..r$. We need to add some data structure for the solution, we can use cartesian tree/splay tree, but it's very painful to write that, (I did it, I know what I'm saying about :) )

Let's use implicit segment tree(also, we can read all queries, compress the values and use normal segment tree) and for each node to save ($min$ and $max$ on the segment in the segment tree, $dp[2][2]$ and other things), after that we can combine two segments into one, by operations as described above.

We have a solution with complexity $O(Q log N)$ but with huge constant around $(~log N)$. My solution with cartesian is very hard to understand, you can write yours, maybe my debugging solution will help understand what's going on: https://pastebin.com/PuFTvuNy

link
This answer is marked "community wiki".

answered 26 Nov, 15:17

mgch's gravatar image

7★mgch
210514
accept rate: 12%

edited 26 Nov, 16:14

vijju123's gravatar image

4★vijju123 ♦
11.3k1316

2

Hey misha, I edited your answer a little to give some formats (Decent formatting + Decent explanation= Profit :p ). Please have a look in case you find concern. :)

(26 Nov, 16:13) vijju123 ♦4★

@vijju123 Oh my god, it's awesome!! Thanks for your work!)

(26 Nov, 16:16) mgch7★
1

You're welcome :D :)

(26 Nov, 16:24) vijju123 ♦4★
1

@vijju123 please profit by editing mine too :P

(26 Nov, 16:24) avi2245★
1

Done. Please have a look and verify :)

(26 Nov, 16:51) vijju123 ♦4★

@mgch can you please elaborate 2nd observation a little more?

(02 Dec, 10:21) pk3012★
showing 5 of 6 show all

@skpro19, for the 3rd problem SHUFFL you just have to apply the operations in reverse. I'll explain this straightforward solution by @heart_blue: 16365417. Consider 0-based indexing, so what the problem says odd index will be even index now and vice versa.

In the end the array size is $2$, and the two elements are at indices $0$ and $1$. We want to trace back where there elements were in the previous array state, and repeat that $M/2-1$ times.
Consider the general case. Let current array size be $2i$, and some index we want to track back be $a$. Then to do reverse of the merge, we split the array into left and right halves. If $a \ge i$, it means it lies in the right half, and we adjust it to $a-i$, otherwise we leave it as is. Now this half array of size $i$ was obtained after deleting an element, so before deletion its size was $i+1$. Which means the deleted element was at $\lfloor(i+1)\ x/y\rfloor$. So if $a \ge $ this deleted index, $a$ was originally $a+1$. Next we have to do the reverse of the even-odd split. Notice that any even index $e$ becomes $e/2$ and any odd index $o$ becomes $(o-1)/2$. We are doing the reverse, so if $a$ is now in the left half that means it came from an even index and should be updated to $2a$, and if in the right half it should become $2a+1$.

Hopefully the explanation is clear. If not, working out a few steps on paper helps. If that too fails, feel free to ask below :)

link

answered 26 Nov, 09:48

meooow's gravatar image

5★meooow ♦
5.5k411
accept rate: 47%

edited 26 Nov, 09:55

Here, im going to explain the second observation in @mgch's solution.

Take an example, given a set {a,b,c,d} (assume a< b< c< d for sake of simplicity)

Let us assume that a group of 4 leads to optimal solution.

Then the cost of above set will be |b- a| + |c - b| +|d -c|.

But, another possible arrangement is to connect a with b and c with d, creating two groups {a,b} and {c, d}

In this arrangement, cost will be |b-a| + | d-c|

This way, cost of second arrangement is less than cost of first arrangement by |c-b|.

This contradict our assumption that a group of 4 can result in optimal solution.

So, optimal solution contains only groups of 2 and 3 (only 1 group of 3 in case size of given set is odd).

Hope it makes everything clear.

link

answered 04 Dec, 18:48

taran_1407's gravatar image

5★taran_1407
2.2k622
accept rate: 22%

@taran_1407 thanks a lot!

one more thing please...it is written : "(min and max on the segment in the segment tree, dp[2][2], dp[2][2] and other things)". What is the need to store min and max? We can calculate dp values by hand at base level and thus can combine them to get answrs for higher level. so, what is the need for them?

and last thing i have understood how to add elements(just add a node at last) but how to support erase operations? is min and max is something that requires for this one?

(04 Dec, 20:15) pk3012★

Mate, i haven't myself implemented the solution yet. I knew about 2nd observation, so i wrote the proof here...

(04 Dec, 22:24) taran_14075★

okay thanks taran but one request if you implement it in future please provide the solution link.

(05 Dec, 13:08) pk3012★

If i implement, i will post solution link.

(05 Dec, 17:33) taran_14075★

Why is this solution failing in first subtask even though I used long where it is needed. After that I used long for all the variables where they won't even overflow as they were given in constraint as 1<=Ai, Y<=10e9. The same solution with every variable's data type set as long even where it is not needed is passing here. Please explain.

link

answered 26 Nov, 03:45

vatsalsura's gravatar image

4★vatsalsura
1417
accept rate: 10%

1

Replied on your post. :) Data types int vs long.

(26 Nov, 03:53) taran_14075★

How do we solve the 3rd and the fourth question?

link
This answer is marked "community wiki".

answered 26 Nov, 07:13

skpro19's gravatar image

3★skpro19
0
accept rate: 0%

Can any one help me with the problem SMRSTR, I'm getting either 75 points or 25 points, I could not make it to 100.. Here is the link to my solution link to my solution

link

answered 26 Nov, 11:44

arun_001's gravatar image

4★arun_001
11
accept rate: 0%

Probably the problem is with double precision. However you don't need to precalculate the division into a double, because you can perform standard division each time which takes floor operation anyways.

(26 Nov, 19:54) bazsi7006★

@bazsi700 , when I change the datatype to double, it is passing 1st test case but when I change it to long double it is passing only 2nd test case, why?(isn't first test case a sub set of 2nd) I just want to know what's happening behind..

(26 Nov, 20:01) arun_0014★

Can anyone tell me why my solution for problem LRQUER is giving wrong answer on subtask #2 but correct answer on subtasks #1 and #3. https://www.codechef.com/viewsolution/16377252

link

answered 26 Nov, 13:31

akash_321's gravatar image

3★akash_321
242
accept rate: 0%

@arun_001 your solution for SMRSTR was almost correct except if input element becomes zero. Divide by zero can't be possible hence avoid dividing by input.Here is what I have changed slightly in your code and got A.C: https://www.codechef.com/viewsolution/16377847

link

answered 26 Nov, 15:27

lunchcook's gravatar image

3★lunchcook
11
accept rate: 0%

edited 26 Nov, 17:48

@lunchcook , firstly thank you for the reply, but it is clear that 1 ≤ Xi, Di ≤ 10e9, how "was almost correct except if input element becomes zero. Divide by zero can't be possible hence avoid dividing by input" is possible?

link

answered 26 Nov, 19:44

arun_001's gravatar image

4★arun_001
11
accept rate: 0%

@vijju123, could you please tell me : Have ratings for November Lunchtime been updated ?

link

answered 26 Nov, 21:15

swarnabja19's gravatar image

3★swarnabja19
536
accept rate: 11%

No, Rating are updated only upto November Cook Off.

(26 Nov, 21:30) taran_14075★

Okay, @taran_1407 , thanks a lot :)

(26 Nov, 21:46) swarnabja193★

For SMRSTR, you could use a language which supports large integer values (python or Java).

link

answered 26 Nov, 22:27

captaindavinci's gravatar image

4★captaindavinci
363
accept rate: 33%

In the solution of the 4th question, I do not understand, how he has defined the dp states.

link
This answer is marked "community wiki".

answered 02 Dec, 03:31

skpro19's gravatar image

3★skpro19
0
accept rate: 0%

Did you read @mgch 's answer?

(02 Dec, 12:21) vijju123 ♦4★

@vijju123 which one?

(04 Dec, 04:15) skpro193★

@pk301, how did you solve it?

(04 Dec, 04:32) skpro193★

@skpro19 i didn't able to solve it for 100 but with a dp approach i get 27

(04 Dec, 18:23) pk3012★

@skpro19 if you get the logic then please explain it. it will be a great help :)

(04 Dec, 18:24) pk3012★

@pk301, are you on codeforces?

(04 Dec, 19:31) skpro193★
(05 Dec, 14:07) pk3012★

@pk301 username?

(06 Dec, 02:20) skpro193★

@skpro19 pk845

(07 Dec, 21:43) pk3012★
showing 5 of 9 show all

can anyone please explain the second observation in the @mgch's answer

link

answered 02 Dec, 17:43

pk301's gravatar image

2★pk301
2407
accept rate: 15%

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:

×12,344
×87
×41
×27
×24
×19

question asked: 25 Nov, 23:59

question was seen: 2,769 times

last updated: 07 Dec, 21:43