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

×

PAINTBOX - editorial

PROBLEM LINK:
Practice
Contest

Author: Pankaj Jindal, Piyush Kumar
Tester: Sergey Kulik
Editorialist: Aman jain

DIFFICULTY:

Medium

PREREQUISITES:

Set, Segment Tree

PROBLEM:

Given a array $A$ of size N each filled with a color with value $A_i$. There are $Q$ queries, each query update color of box at position $Pos_i$ with color $Col_i$. For each query you need to find number of ways to select $W$ adjacent boxes of same color from total of $N$ boxes.

QUICK EXPLANATION:

Maintain a set of starting indices of color segments. Now on each query there are three possibilities, either we assign the same color, so no change to the array, or we have an update that breaks a continuous segment of colors, or an update that joins two continuous segments, each of which can be done in $O(log(N))$. Update your answer for the query and correspondingly update set of starting indices of color segments.

EXPLANATION:

Let's start with easy constraints. Let say you have a color segment of length $L$, then number of ways to select $W$ adjacent boxes from this segment would be $max(0,(L-W+1))$. Now if you have sequence of segments say, $s1s2s3s4$, then number of ways to select $W$ boxes would be sum of number of ways for each segment i.e. $\sum{max(0,L_i-W+1)}$. Complexity of this solution would be $O(N*Q)$, this works within time-limit for first sub-task but will fail on main task.

To solve hard part efficiently, we can store the result of the query for the input string in $ans$ and maintain set that store starting indices of color segments. After each query operation we need to insert or erase indices from set accordingly.
If you analyse closely you will find that each update operation looks like:
a) if update operation, does not change the state of boxes from current state, then there will be no change in answer to this query.
b) state change can be described as, $......s_a c1 s_b......$ to $......s_a c2 s_b......$, where $s_a$ is segment to the left and $s_b$ segment to the right of update position $pos_i$, with box color changed from $c1$ to $c2$.

Following cases possible (assuming 0 based indexing):
1) $pos_i$ is 0 and $c1$ lies in $s_b$ i.e. same in color to $s_b$, after the operation splitting takes place and $ans = ans - ways(len(s_b)+1) + ways(len(1)) + ways(len(s_b))$, here ways(l) means number of ways to get $W$ adjacent boxes from segment of length $l$.
2) $pos_i$ is 0 and $c1$ does not lies in $s_b$, after updation $c2$ lies in $s_b$, so merging takes place. $ans = ans - ways(1) - ways(len(s_b)) + ways(len(s_b)+1)$.
3) $pos_i$ is 0 and $c1$ and $c2$ both does not lie in $s_b$, no change in answer.
4) $pos_i$ is $N-1$ and $c1$ lies in $s_a$, after the operation splitting takes place and $ans = ans - ways(len(s_a)+1) + ways(len(1)) + ways(len(s_a)).$
5) $pos_i$ is $N-1$ and $c1$ does not lies in $s_a$, after updation $c2$ lies in $s_a$, so merging takes place. $ans = ans - ways(1) - ways(len(s_a)) + ways(len(s_a)+1).$
6) $pos_i$ is $N-1$ and $c1$ and $c2$ both does not lie in $s_a$, no change in answer.
7) for rest of the cases $pos_i$ lies in between 0 and $N-1$, $s_a = s_b$, i.e. same in color and $c1$ lies in $s_a$, now splitting takes place, $ans = ans - ways(len(s_a)+1+len(s_b)) + ways(len(s_a)) + ways(1) + ways(len(s_b))$.
8) $s_a = s_b$, $c1$ does not lies in $s_a$, $c2$ lies in $s_a$, $ans = ans - + ways(len(s_a)) - ways(1) - ways(len(s_b)) + ways(len(s_a)+1+len(s_b)).$
9) $s_a = s_b$, $c1$ and $c2$ does not lies in $s_a$, no change in answer.
10) $s_a != s_b$, $c1$ lies in $s_a$ and $c2$ lies in $s_b$, $ans = ans - ways(len(s_a)+1)+ways(len(s_a))-ways(len(s_b))+ways(len(s_b)+1)$.
11) $s_a != s_b$, $c1$ lies in $s_a$ and $c2$ does not lie in both, $ans = ans - ways(len(s_a)+1) + ways(1) + ways((len(s_a))$.
12) $s_a != s_b$, $c1$ lies in $s_b$ and $c2$ lies in $s_a$, $ans = ans - ways(len(s_b)+1)+ways(len(s_b))-ways(len(s_a))+ways(len(s_a)+1)$.
13) $s_a != s_b$, $c1$ lies in $s_b$ and $c2$ does not lie in both, $ans = ans - ways(len(s_b)+1) + ways(1) + ways((len(s_b))$.
14) $s_a != s_b$, $c1$ does not lies in both $s_a$ and $s_b$, $c2$ lies in $s_a$, $ans = ans - ways(1)-ways(len(s_a))+ways(len(s_a)+1)$.
15) $s_a != s_b$, $c1$ does not lies in both $s_a$ and $s_b$, $c2$ lies in $s_b$, $ans = ans - ways(1)-ways(len(s_b))+ways(len(s_b)+1)$.
16) $s_a != s_b$, $c1$ and $c2$ does not lies in both $s_a$ and $s_b$, no change in answer.

COMPLEXITY:

Each query operation requires insertion, deletion of elements from set and answer update, all can be done in $O(log(N))$. For $Q$ queries, overall complexity would be $O(Q*log(N))$.

ALITER:

Tester Sergey also suggested that above problem can be solved using Segment Tree, which would be much modular approach than handling many cases. HINT: For each node of segment tree stores length of color segment from left and length of color segment from right, color of left and right segment and ans for query for segment range. Update these values accordingly on each query operation.
If you are not able to solve the problem using Segment Tree, go through Sergey code in refernces.

AUTHOR'S, TESTER'S and Editorialist's SOLUTIONS:
author
tester
editorialist

This question is marked "community wiki".

asked 26 Mar '15, 20:47

amanjain110893's gravatar image

4★amanjain110893
561412
accept rate: 0%

edited 16 Jun '15, 11:27

vicky002's gravatar image

1★vicky002 ♦♦
2561314


My Solution

Let us first group the numbers from left to right according to their colors. Then each update will either break a group into more groups or it will merge some groups. We can maintain the groups using sets. Checking whether current update will break or merge can be decided on the basis of previous and next segment of current segment.

link

answered 29 Mar '15, 02:47

dpraveen's gravatar image

4★dpraveen ♦♦
2.5k53137170
accept rate: 20%

edited 29 Mar '15, 02:52

I thought of same solution as djpraveen. It is much more simple . Surprised to see the problem as "medium"

link

answered 29 Mar '15, 14:15

dreamplay's gravatar image

4★dreamplay
1485
accept rate: 0%

@djpraveen how exactly would you implement this?

The merging of sets is not fast enough for the problem size. It is linear from what I know. If you implement it using disjoint set-forest we can indeed get merging faster. But then breaking is much more of a hassle.

Even after that, I do not understand how you would answer each query as then we would need to go over the size of each set to compute the answer. (I think we might be able to do it locally by changing the total when we modify a set)

Please be a bit more clear in your answer.

Thanks.

link

answered 01 Apr '15, 08:43

epsilon_0's gravatar image

4★epsilon_0
4527
accept rate: 0%

Here's how I did it. The problem boils down to tracking the sizes of the runs. To do this, I maintain the set of breakpoints between the runs. So if the string is

RRBBBRRBR

I would store

0,2,5,7,8,9

Note that each color update will only modify a constant number of breakpoints. Also, in order to calculate the sizes of the runs from the breakpoints, I need to be able to go to the next and previous breakpoint easily. We can use two different data structures. One is a list, but maintaining a sorted list is O(N) time. So use a TreeSet instead which can do add/remove/next/prev in O(log(n)) time.

(01 Apr '15, 10:33) abeliangrape3★

The problem is a pretty standard segTree problem when looked from the perspective of tester @sergey . The problem should be rated as easy or easy-medium.

link

answered 01 Apr '15, 12:41

gvaibhav21's gravatar image

7★gvaibhav21
947210
accept rate: 25%

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:

×2,595
×1,755
×160
×70

question asked: 26 Mar '15, 20:47

question was seen: 2,173 times

last updated: 16 Jun '15, 11:27