NeverSayNever's blog

By NeverSayNever, 10 years ago, In English

Hello all,

I am trying to solve this problem .. http://www.hackerearth.com/sudo-code-2/algorithm/shyam/ but could not able to come up with a solution which works in given time with given constraints .. . So i opened some solution .. They smells like greedy approaches .. but can anybody elaborate the idea or help me in verifying the given approach..

Here is one simple implementation ... link

http://www.hackerearth.com/sudo-code-2/algorithm/shyam/submission/1194446/

Thanx in advance ..

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By NeverSayNever, 10 years ago, In English

Hello all,

I am trying to solve this problem from Hack 101 Hackerrank .

https://www.hackerrank.com/contests/101hack20/challenges/superpowers

I was not able to click any other solution so i applied brute force and got TLE for some file then i decided to open some accepted solution and find a number of interesting code.

Here are the link to those solution.

Roman Rubanenko submission's : extremely small code (may be idea is very big) c++ code http://ideone.com/MI4uUA

python code link http://ideone.com/RhYWli

Surprise to see such codes..

Can anybody of you elaborate the idea behind these submission.. This will make me learn a lot..

Thanx in advance ..

Full text and comments »

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

By NeverSayNever, 10 years ago, In English

Hello all,

I am trying to solve this problem .

1
                           2   3
                         4   5   6
                       7    8   9  10 
                     11  12  13  14  15... and on so

Given three points A,B,C such that A <= B <= C. We have to report whether given points form an equilateral triangle or not .

I made this solution and but this is not considering all the cases. Here is my solution .

SOLUTION:

we know that a triangle ABC is equilateral if A==B && B==C. (equality is an equivalence relation).

  1. So Let us consider A,B,C such that A < B < C . Now we can find the side BC as C-B+1.

  2. Next step is to check whether the other two sides are equal to this or not .for that purpose .. we can calculate the level of each of A,B and C then take the difference.. for any nodes its level will be x A<=(x*(x+1))/2 for the smallest possible x.

comparing all the three to check the existence of an equilateral triangle .

Here is the python implementation link of the above idea http://ideone.com/V5fuhe

but this will fail on the test case 5 , 13 , 15 answer should be false but my code will report is true .

Can anyone suggest me some idea to solve this problem ..

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By NeverSayNever, 10 years ago, In English

Hello all,

I am trying to solve this problem

https://www.hackerrank.com/contests/101hack19/challenges/journey-scheduling

Editorial for this problem mentioned that the query for the longest distance for any given node in a tree can be performed with standard DP approach ... I am not familiar with the approach and also unable to find content regarding this on internet so please can anyone help me understanding this .. or provide me link for good tutorial for this standard approach with reference to some more problem ...

Thanx in advance ..

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By NeverSayNever, 10 years ago, In English

Hello everyone, I was reading how to find LCA lowest common Ancestor using DP so that each of type LCA(x,y) can be handled in log(n)

int _getlca(int x,int y){

if(y>x)
    swap(x,y);
for(int i=16;i>=0;i--){
    if(pa[x][i]!=-1 && L[pa[x][i]] >= L[y])
       x = pa[x][i];
}
if(x==y)
    return x;
assert(L[x]==L[y]); /*here ... */
for(int i=16;i>=0;i--){
    if(pa[x][i]!=-1 && pa[x][i]!=pa[y][i]){
       x = pa[x][i],pa[y][i];
    }
}
return P[x];

}

Here is the code .. Checkout the assert condition in this code . I put that condition because i thought at this step Level or depth of both the nodes must be equal . But this is not true can anybody provide me any test case for this ....

Full text and comments »

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

By NeverSayNever, 10 years ago, In English

Hello Everyone,

I would like to ask something about range update in Binary Indexed Tree. I am familiar with the range update in BIT in log(N).

adding of function F(x) = x*(x+1)/2 or other polynomial function to the range can be easily handled with bit.

But what if we need to replace the old values with the new values in the range like instead of adding x to every number in the range [L,R] we need to replace every number in the range [L,R] by x.

I also know that this can be handled using lazy propagation in segment tree. But i want to know if there exists any approach which make use of BIT.

If somehow we are able to make every element in range[L,R] zero then we can simply add the number x to the range[L,R].

If anyone has some idea or can help me ....

Full text and comments »

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

By NeverSayNever, 10 years ago, In English

void init(bool A[MAX][MAX],bool res[MAX][MAX]){

for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
       res[i][j] = A[i][j] = 0;
/**
    memset(res,0,sizeof(res));
    memset(A,0,sizeof(A));
**/
for(int i=0;i<n;i++)
    A[P[i]][i] = 1,res[i][i] = 1;

}

Here is the code snippet. If i used the commented part instead of two loops it fails and produce a weird output.

here is the full code link and problem link. http://ideone.com/cdsWYE http://www.spoj.com/problems/PDECODE/

Please if anyone can help then suggest me a valid reason for this.

Full text and comments »

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

By NeverSayNever, 10 years ago, In English

A topic that appears alot these days in many programming contests is Matrix exponentiation. Can someone suggest a good tutorial on that with the variety of problems. Any help will be highly appreciated.

Full text and comments »

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

By NeverSayNever, 10 years ago, In English

I am trying to solve this problem but could not able to solve it. www.codechef.com/problems/LCMSUM

After searching a lot on the web i find this.

summation of (LCM[i,n]) for all i belongs to [1,n] = (((summation of ETF(d)) + 1)*n)/2.

where ETF() euler totient function . and d belongs to set of diviors of n.

Can anybody explain the logic behind it or how does it work. I am unable to find any explanation or details about it. So, can anyone help me.

Full text and comments »

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

By NeverSayNever, 10 years ago, In English

https://www.hackerrank.com/contests/101sep14/challenges/jim-and-the-skyscrapers

Firstly I know the solution that is mentioned in the editorial. I thought whether this problem can be solved without using any such data structure or can i used simple set and finally i clicked to a solution.

Solution is very simple i can sort these element using vector pair and then i can use a set to find out the element which is greater than me using upper_bound and bigger than me but this solution giving this verdict TLE for some files. what is the reason for this. I think my solution's complexity is O(nlog(n)). Can anyone help me in verifying the complexity of my solution. Thanx in advance.

here is my code link here .

Please do have a look.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By NeverSayNever, 10 years ago, In English

This problem appears in the CodeSprint Elimination Round 2. I request all of you to please explain how to solve this problem.

https://www.hackerrank.com/contests/csindia14-er1/challenges/the-blacklist

I think it requires DP but could not able to come up with a approach.

Full text and comments »

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

By NeverSayNever, 10 years ago, In English

Jacobi's Two Square Theorem: The number of representations of a positive integer as the sum of two squares is equal to four times the difference of the numbers of divisors congruent to 1 and 3 modulo 4.

I find this on Google , but not able to find any proof . I have brute force it and find that this is correct. Can anyone tell me any proof or whether any test case on which this theorem fails. Really needed please help.

Full text and comments »

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