Matrix.code's blog

By Matrix.code, history, 3 years ago, In English,
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

Read more »

 
 
 
 

By Matrix.code, history, 3 years ago, In English,

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

Read more »

 
 
 
 

By Matrix.code, 3 years ago, In English,
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

Read more »

 
 
 
 
  • Vote: I like it  
  • +13
  • Vote: I do not like it  

By Matrix.code, 3 years ago, In English,

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +3
  • Vote: I do not like it  

By Matrix.code, 3 years ago, In English,
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

Read more »

 
 
 
 
  • Vote: I like it  
  • -4
  • Vote: I do not like it  

By Matrix.code, 3 years ago, In English,
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 ?? 

Read more »

 
 
 
 
  • Vote: I like it  
  • +3
  • Vote: I do not like it  

By Matrix.code, 3 years ago, In English,

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +4
  • Vote: I do not like it  

By Matrix.code, 3 years ago, In English,

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 ????

Read more »

 
 
 
 
  • Vote: I like it  
  • +11
  • Vote: I do not like it  

By Matrix.code, 3 years ago, In English,

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 )

Read more »

 
 
 
 
  • Vote: I like it  
  • -4
  • Vote: I do not like it  

By Matrix.code, 3 years ago, In English,
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 :) 

Read more »

 
 
 
 
  • Vote: I like it  
  • +7
  • Vote: I do not like it  

By Matrix.code, 4 years ago, In English,
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 

Read more »

 
 
 
 
  • Vote: I like it  
  • +2
  • Vote: I do not like it  

By Matrix.code, 4 years ago, In English,

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 ??

Read more »

 
 
 
 
  • Vote: I like it  
  • +8
  • Vote: I do not like it