Hello everyone!

I would like to invite you to participate in HackerEarth monthly long contest August Circuits 2018. It has already started on 17th August 2018 and will run for 9 days.

The problem set consists of 7 traditional algorithmic tasks of various difficulties and 1 approximate problem. For traditional algorithmic tasks, you will receive points for every test case your solution passes, so you can get some points with partial solutions as well. For the approximation task, your score depends on the best solution in the contest so far. Please check the contest page for more details.

The problems have been prepared by the users: MazzForces, BishalG, bciobanu, flash_7 and me. The problems have been tested by zscoder and MazzForces. We have tried our best to ensure a really good contest for all of you. The editorial will be published soon after the contest ends.

As usual, there will be some prizes for the winners:

• First Prize: $100
• Second Prize: $75
• Third Prizes: $50

Top 5 will also win HackerEarth T-shirts.

You are given a undirected unweighted graph. 
Output the minimum number of edges need to be added to the graph so that , every pair of vertices has at least a even length path between them.
Imput:
A line denoting number of vertex n , and number of edges m . next m line contains the edges of the graph.
Output:
The minimum number of edges.followed by the edges

Sample input: 
3 2 
1 2
1 3
Output: 
1
2 3

I am trying to solve Uva -1136

Link : 1136

My Approach :

I am using A segment tree ,each containing Maximum Value of The range. For each box, I am finding The smallest index ,where I can load Star-ship , Then update

But ,Getting TLE , (Time Limit : 18s )

Please Suggest Any Faster Update Method

My code : Code

Given an array with n integers, and you are given two indices i and j (i ≠ j) in the array. You have to find two integers in the range whose difference is minimum. You have to print this value. The array is indexed from 0 to n-1...

This problem easy version : http://lightoj.com/volume_showproblem.php?problem=1100 But , If The input numbers in range [-10^9 , 10^9] , How to solve it ?

I solved easy version just iterating the range :P

I am given N Points with integer co-ordinates and two integer D , M ; All the given points will be in one side of y = M straight line . I need to find The minimum number of guard placed on y = M line (with integer x coordite ), so that all the N points is at most D euclidian distance away from the guards... Like

1 1
2 2
3 1

These are 3 points. I am given D = 2 , M = 0;
Then Minimum Number of guard needed is 1. placed in (2,0) coordinate.

N = 10^4

It is two player(Alice ,Bob : Alice to play first)  impartial game. N empty pillar is given an An integer L ,Initially , a set S contains all element from 1 to L . 
In each turn
1 . A player chooses an integer from set S.
2. A player chooses an empty pillar(if any), put the number , erase it from The set
3. A player chooses a non-empty pillar, But (The integer + last number inserted on that pillar) should be a square number. , erase the number.

Example : If a pile contain 1 as the last inserted number, A player can insert 3,8,15 …. 

The player who can not play his/her turn loses.

N , L is given , Determine who will win if they play optimally..

N <= 10^3 , L = 10^9

Here is the given information : 
Q1 = a; n = 1
Q2 = b; n = 2

Qn = n * ( 1 + Q(n-1))/ (Q(n-2))
// integer division 
n <= 10^15
a , b < 10^9

Input : a, b , n ;
Output : Qn 

How to solve it ?? 

The problem statement as follows :

I have total N coins & I have to make K piles . I have to distribute the coins into the piles so that each piles contain >=1 coins . 
Output a permutation of K number (Which denotes the number of coins in each piles ) that the first player to move lose in **Normal Nim Game**
More specefic : two condition :
1. n1 + n2 + n3 +... ... + nk = N
2. n1 ^ n2 ^ n3 ^ ... ... ^nk = 0

Here n <= 10^8 , k <=N Time : 3s

I am thinking of a programming problem about segment tree .. Here is the statement :

An array of N ( N < 10^5) integers is given. I have 2 type of total M (10^5) operation on the array

1. U a b d v // Means Update value of index a , a+d, a+2d , a + 3d ..... <=b by value v ( add the value of v to those index ) 
2. Q a b d // Meaning sum of arr[a] , arr[a+d] , arr[a+2d] , ..... until b 

O based index system
Here is an example :
Input : 
6 5    // N M
0 1 2 3 4 5 // The array
U 1 5 2 2
Q 1 2 1
Q 1 5 3

Output :
5
7

The Time limit is standard (3s) How to solve it Efficiently ????

The problem is about bracket matching . link

I have solved it. Didn't thought it would pass the time limit . I used segment tree. My update function seems too slow to me, but couldn't think of other way Please Help to optimise

struct dta {
        vector<char> V; // Using vector , stack may be the best
        dta(){}
        dta(char n){V.push_back(n);}
        
}T[3 * MX];


void init( int node , int b , int e)
{
        if(b == e ){
                T[node] = dta(str[b]);
                return;
        }
        int mid = ( b + e ) / 2;
        init(node * 2, b, mid);
        init(node *2 +1 , mid + 1, e);
        T[node].V = T[node *2].V;
        int top = T[node].V.size() - 1;

        // merging the two segments 

        for(int i = 0 ; i< T[node *2+ 1].V.size(); i ++ ){
                if(top>=0 && T[node *2+ 1].V[i] == ')' && T[node].V[top] == '('){
                        T[node].V.pop_back();
                        top -- ;
                }
                else {
                        T[node].V.push_back(T[node *2+ 1].V[i]);
                        top ++;
                }
        }
        
}

void upd ( int node, int b , int e , int pos )
{
        if(b == e ){
                T[node] = dta(str[b]);
                return;
        }
        int mid = ( b + e ) / 2;
        if(pos <= mid ){
                upd(node * 2, b, mid, pos);
        }
        else upd(node *2 +1, mid +1 ,e, pos);
        T[node].V = T[node *2].V;
        int top = (int)T[node].V.size() - 1;
        
        // Update & merge The left & right segment

        for(int i = 0 ; i< T[node *2+ 1].V.size(); i ++ ){
                if(top>=0 && T[node *2+ 1].V[i] == ')' && T[node].V[top] == '('){
                        T[node].V.pop_back();
                        top -- ;
                }
                else {
                        T[node].V.push_back(T[node *2+ 1].V[i]);
                        top ++;
                }
        }
        
        
}

But storing the whole segments and update is too heavy, Don't know the complexity of update operation ( may be n lg n )

I have found many problems Involving
To **find the length of the sub-array with varied property**
An array of whole (Positive,0,Negative ) ::

1. Find the length sub-array which have maximum Sum ( First maximise sum , then length )
Solution : kadane Algorithm O(n) for 1D , O(n^3) for 2D

2. Find the largest sub-array which elements_sum <= N ( First maximise length , then minimise sum as possible )
Solution : ?? If O(n) possible ?? I found one with O(n log n)

3. Find the largest sub-array which elements_sum is divisible by a number Q
Solution : O(n) Solution exists . [here](http://stackoverflow.com/questions/16605991/number-of-subarrays-divisible-by-k?rq=1)

4. Find the largest sub-sequences which elements form an arithmetic progression / geometric progration 
Solution : O(n^2) [Here](http://www.geeksforgeeks.org/length-of-the-longest-arithmatic-progression-in-a-sorted-array/) Can We do better ??? 

5. Find the largest sub-array where all the elements are different
Solution : I know O(n^2) , O(n) possible ?? or better solution . Please

6. Find A permutation of an array  which sum_of_score is maximum (Here score =
 |(previous_position_of_an_element - current_position_of_an_element)| * element_value )

Solution : ???


...... And More & More

Please discuss about this problem and Find if we can make better :) 

An array of integer is given.. 
For each element of i th index , I need to find the length of the longest sub-array starting from i+1 index where all the element is smaller than arr[i]

Sample : arr[]={10 , 2 , 7 , 4 , 12 ,2 }

for i = 0 , arr[0] = 10 , the sub-array is = {2,7,4} . All are smaller than 10 and starting from 
i + 1 th index ... 
and for i = 1 , length = 0
This need to be done for all the index of the array 

How to find the length ??
Constrains: 
Size of The array = 10^6

I think RMQ will prove necessary here 

I have a multiset . Using a loop I am inserting elements. In each loop , I am asked to access n th element of the multiset . where n is increasing in ascending order,1,2,3,4

I used iterator and pointed it to the begin. But for every loop , I have to iterate . This gives me TLE.

Is there any process for fast accessing in multiset ??