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 
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.
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. ( 
)
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.
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…