Unofficial Editorials October Long Challenge (Part 3)

Hello Guys

This is the part 3 of three posts of unofficial editorials for October Long Challenge.

For Solutions of problems PERFCONT, MEX and/or CHEFCOUN, click here.

For Solutions of problems CHEFGP and/or MARRAYS, click here

This post has editorials for problems CHEFCCYL and SHTARR

Problem CHEFCCYL

Problem Dificulty:Medium

Prerequisites: Sum Arrays would be enough :slight_smile:

Problem Explanation

Find the smallest distance from Vertex v1 of Cycle c1 to Vertex v2 of Cycle c2, given a set of cycles, being ith cycle connected to (i-1)th and (i+1)th cycle by an edge.

Edges are weighted and bidirectional.

Solution

Subtask 1:

Since N, Q <= 10^3, it allows the simplest solution to pass, running dijkstra algorithm for every query. Each query takes O(N) time, resulting in overall complexity (NQ).

Clearly, this solution will fail grossly for remaining subtasks.

First defining Connecting edges : The edges which connects the cycles with each other.

Let us solve a simpler version of this problem first.

Given a cycle with N nodes, ith node being connected to two adjacent nodes, find the smallest distance.

N = 5.

dist 5 - 1 = 7

dist 1 - 2 = 3

dist 2 - 3 = 4

dist 3 - 4 = 5

dist 4 - 5 = 6

//I am used to writing sum array code this way only. Actual order of weight will be given as 3,4,5,6,7. Adjustment has been made to store array as last element, first element , 2nd, 3rd and so on…

For Every node, there are exactly two paths to visit other node. eg. node 3 can be visited from node 1 through path 1-2-3 (weight 3+4 = 7) or 1-5-4-3 (7+6+5 = 18).

Now, consider array {7, 3, 4, 5, 6, 7, 3, 4, 5, 6} // distance edge weights in serial order

generate sum array of above, say S = {0, 7, 10, 14, 19, 25, 32, 35,39,44,50 };

Now, distance from from 1 to 3

(1st path) = S{3} - S{1} = 14-7 = 7

(2nd path) = S{1 + N} - S{3} = S{1+5}-S{3} = 32-14 = 18 //N is number of nodes in given cycle.

//using curly brackets due to formatting issues

Required distance = Min(7,18) = 7

Seems magic… ryt?? :)…

So now we can calculate the smallest distance from one node to another in

Be Sure you thoroughly understand the above solution before proceeding.

Now, the Second sub-problem is…

Given the edge weights between cycles, find the distance between two cycles…

Consider example N = 4 (Number of cycles here)

dist 4 - 1 = 7 // connecting edges between cycles, given after cycles, but before queries in input of problem

dist 1 - 2 = 3

dist 2 - 3 = 4

dist 3 - 4 = 5

Here too, the same technique. :slight_smile:

Say we are asked to find distance of Vertex v1 if Cycle c1 to Vertex v3 of Cycle c3, total cycles being 4, We need to consider exactly two paths, one from Cycle c1 to Cycle c3 through c2, other one through c4.

Consider array {7,3,4,5,7,3,4,5}

Sum array {0,7,10,14,19,26,29,33,38}

distance C1 to C3

through C2 = S{C3}-S{C1} = 14-7 = 7

through C4 = S{C1+N} - C{C3} = 26-14 = 12;

Main Problem

If we consider path of any vertex in cycle c1 to any vertex if cycle c3, we need to add the weight of connecting edges C1-C2 and C2-C3, which can be added as above.

But we also need to consider the distance traveled within cycle c2, from end point of connecting edge from C1 to c2

to start point of connecting edge between cycle C2 and C3.

This can be calculated using the same technique, just constructing the sum array from base array. ( :smiley: )

The values in base arrays are {

{0} = dist between (end point of connecting edge between Nth cycle and 1st cycle) to (src point of connecting edge between 1st cycle and 2nd cycle)

{1} = dist between (end point of connecting edge between 1th cycle and 2nd cycle) to (src point of connecting edge between 2nd cycle and 3rd cycle)
}

Let us denote this as Cycle weight.

Thus, Required Distance from Vertex v1 of Cycle c1 to Vertex V2 of Cycle is

** Minimum of following two**

** (path 1) dist(v1 to end-point of connecting edge within (cycle c1 and c1+1) ) + E{c2}-E{c1} + V{c2-1} -V{c1} + dist( v2 to end point of connecting edge between cycle c2-1 and cycle c2)

(path 2) dist(v1 to end-point of connecting edge within (cycle c1 and c1-1) ) + E{c1+N}-E{c2} + V{c1+N-1} -V{c2} + dist( v2 to end point of connecting edge between cycle c2 and cycle c2+1) **

I know the solution is a bit complex, but I guarantee you, it’s worth it. :slight_smile:

Here’s a link to my


[4]


# Problem [SHTARR][5]
# 
### Problem Dificulty:Medium
# 
### Prerequisites: Square-root Decomposition, binary search
# 
#### Problem Explanation
# 
Given an array A, perform two types of queries
 1. i X increase A[i] by X
 2. i L R count number of values staring from ith position in array such that A[j]>=L and A[j] is greater than maximum value between from A[i] to A[j-1] and maximum value between A[i] to A[j-1] < R

**Be sure to understand the second query, whether You need to read it 1 time, 2 time, 10^2 time of 2^10 time :D**
## Solution
# 

### A Naive Solution
# 
Create int[] next Next Greater Element Array from [here][6]

_for update_

update value in array

recreate the whole next array

_for query_
{
start from ith value, 

long x = i;

int count = 0
while(a[x] < L)x = next[x]; // to exclude values smaller than L
while(A[x] < R){

count++;

x = next[x];

}

count++; // because last value >= R
}

**Note: Above is just an overview of naive solution. Forgive me for errors if there are. :)**

The above solution performs both update and query in O(N) time in worst case, giving overall complexity O(NQ) which will exceed Time limit.

**Efficient Solution**

Have a read at one of my answer to a similar problem here.

Now, The idea of SQRT decomposition is to divide the given array into sqrt(N) blocks and solving queries as well as updates in O(sqrt(N)) time.

Please refer to my 

7 to follow explanation.

Now, every block is an unsorted array.

Sub-problem: We need to find number of values greater than X, which are strictly increasing.

For example: Say the ith block contains values {2,5,8,4,6,9}

So the list[i] will only store {0, 2,5,8,9} and size[i] = 5 // 0 is added to terminate binary search, as explained below

If Block contains values {2,5,4,6,8,9}, the list[i] will contain {0,2,5,6,8,9} and size[i] = 6.

The idea here is that, now if we need to find number of values greater than X which are greater than all previous values, we just need a binary search to find such a value.

for Block {2,5,8,4,7,9}, if we need to find values greater than 6

binary search will search within list {0,2,5,8,9} and return 3.

List stores the elements in above form.

The max array store the maximum value in a block. The size array store the size of list made from each block.

If you have understood all this, you should be able to solve the problem yourself

Now, we build blocks in this way, creating list, storing size and max value. (build function in my code)

**Now, for Update operation i, X **

int blockNo = i/len;

A[i] += X; //updated value in array;

updateBlock(blockNo); //updated the list

Now, for query operation i, L,R

let Long prev = L-1;

blockNo = i/len;

loop in first block{

if(a[j] > prev){

count++;

prev = a[j];
}

if(prev>=R)return count;//in case all the required values are within current block
}

for(int block = blockNo+1; block < len; block++){

if(max[i] > prev && max[i] < R){ //middle blocks

count += size[i] - binarysearch(i, prev)//preform search for index of value greater than prev in ith list and add number of elements greater than prev

prev = max[i]

}else if(max[i] <= prev)continue; // blocks in which no value is greater than prev
else{

//last block, because it contains a value greater than R

We search manually // or create another binary search to find index having value equal or greater than X, as in my code.

loop in current block{

if(a[j] > prev){

count++;

prev = a[j];
}

if(prev>=R)return count;//count is the required answer of query.
}

break;

}

return count; // in case max (array from a[i] to a[n-1]) < R

}

I also got 10 points in Lucky Edge problem using Brute-force solution, but it’s better to have a look at official solution of remaining problems, as i myself will :)…

Keep coding. Feel Free to ask anything…

5 Likes

Isn’t the SHTARR soln O(Q*root(N)*log(N))?
How did that fit in the time limit? I thought of a similar soln but did not implement it as I was sure it would time out. Did you make any optimizations?

1 Like

@taran_1407 why you have taken list as 2 d array and you have called update block in build().what is it’s purpose and what basically updateblock() is doing and while looping in updateblock() why you are taking the min of (i+1*len , N).can you please clarify me a bit.

&& " Have a read at one of my answer to a similar problem here."
Here the link of here is not working . can u please update it as i want to read your previous answer also.

Could someone upvote me please ? Would like to ask questions.

1 Like

Mate

The time complexity is O(Qsqrt(N)log(sqrt(N)) because we perform binary search within one block of size sqrt(N)

Second thing, many blocks go unchecked because of max array. In case prev value ia already greater than the maximum value in block…

Third thing, binary search on a single block is even faster than O(log(sqrt(N)) as binary search is performed in list[i] which contain only selected elements from block, thus size of list[i] < sqrt(N) ( size = sqrt(N) if and only if all elements in block are sorted, which i doubt :smiley: )…

Hope this clarifies…

Feel free to ask anything… :slight_smile:

1 Like

OMG! I feel stupid now. I was so frustrated by the time I came up with it that I thought “ye bhi nahi chalega”.

Thanks for clarifying it in such a clean way :slight_smile:

No problem :slight_smile:

About my previous answer, the link was

http://discuss.codechef.com/questions/112763/tricky-how-do-i-find-the-first-element-in-an-unsorted-array-which-is-greater-than-or-equal-to-a-given-value-x-in-olog-n

But i dont know why it isn’t opening now. Maybe admin blocked it. @vijju123 might know.

In that answer, i had explained the approach of finding leftmost value in unsorted array strictly greater than a given value in logn time O(N) preprocessing.

List array is the core of my sqrt decomposition solution.

Suppose the given array is 1 2 3 4 5 6 7 8

List array will look like

0 1 2 3

0 4 5 6

0 7 8

Block size = sqrt(8)+1 = 3

List(i) stores contents of ith block

Had the given array been 1 4 3 5 7 8 3 2

List will look like

0 1 4
0 5 7 8
0 3

List(i) stores only those elements, which are strictly greater than all previous elements added tolist(i)

Updateblock(i) updates the list(i) contents.

Third thing, min((i+1)*len, N) is used because it is possible that last block may not be completely filled, to avoid IndexOutOfBounds Exception.

You may try changing it into j < (i+1)*len and try running the problem with N= 7 ans one query in which R is greater than maximum of all values in given array. That will make my point clear.

Hope that helps… :slight_smile:

Thanks @taran_1407 for the help , now its clear to me.
Your approach is very unique and easier to understand as compared to official editorials.
After going through your solution i thought that the backbone of the problem is the query 2 which you mentioned above, but how did you come up with this approach?
Again thanks for the help!!!

Well, its a well known technique called Square root decomposition, about which you may read from internet. If u wanna try a similar problem, see HILLJUMP problem of august long challenge, very similar to above problem.

Feel free. :slight_smile: