shahianshu's blog

By shahianshu, history, 9 months ago, In English,

Hello,

BBRICKS — link

in the editorial for the problem BBRICKS one of the guy posted his solution which uses matrix exponentiation to solve the problem and i couldn't make much from his solution on how to solve the question using matrix exponentiation, so if anyone could please just tell me how this problem can be solved using matrix exponentiation.

solution which uses matrix exponentiation

Even the editorialist has no clue on how to solve it using matrix exponentiation.

Thanks in advance :)

update :- the blog written by abba5 explains the solution of the problem using matrix exponentiation very nicely .

Read more »

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

By shahianshu, history, 9 months ago, In English,

Hello,

EXPTREE Problem link

i was reading the editorial for Exptree i was not able to understand the proof mentioned by @gil_vegliach in the commments, as he mentioned that for any two vertices v1 and v2 in [1..n] in tree T1 , T2 resp., if we remove (parent[v1],v1) and (parent[v2],v2) will lead to same tree only if T1 = T2 initially but i came up with a counter example of 7 nodes

(T1)                                           (T2)
               0                  and                           0
             /   \                                            /   \
           0      0                                          0     0
         /         \                                                \
   ( 0 )            0                                                 0
                  /   \                                             /  \
                 0     0                                            0    0
                                                                          \
                                                                          ( 0 )

v1 is the vertex marked with () in T1 and v2 is the vertex marked with () in T2 , now if i remove the edge between v1 and it's parent , and remove the edge between v2 and it's parent then i get the same tree but T1 != T2. Now i am not able to understand wheather the proof is wrong or i have understood it incorrectly

Read more »

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

By shahianshu, history, 9 months ago, In English,

hello , i am getting wa for my code of the problem round robin scheduling , I have tried many test case I couldn't come up with a test case where my code fails.

MY APPROACH :- i have made an observation that for each task Ti it will become zero only at an iteration equal to Ti . For example, suppose Ti = 9 then this element will become zero at the 9th iteration irrespective of all the other tasks . So i thought that i need to just sort the array based on the value of Ti and then the smallest value Ti will be the one going 1st and then all the Ti's whose values are greater than it . So , i kept two values in the vector , first :- value of Ti , and second :- index of particular Ti . Now i sorted the vector , if values of some element a and b are equal then i sort them in increasing order of index. I also maintained a binary indexed tree denoted by bit[] , this is used to tell me how many total tasks are still present before a particular element.

MY SOLUTION( i have commented each and every part ) :- link

UPDATE :- MY EDITED SOLUTION :- link

Read more »

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

By shahianshu, history, 12 months ago, In English,

i am trying to solve paradox using graph coloring but i am getting wrong anwser , i have tried all the test case which are there on spojtoolkit and my code is giving correct answer for everyone of them ( it gave wrong answer for only those testcases in which x > n , which is not possible due to given constraints in the question although i have tried doing that also but still it is giving wrong answer)

MY APPROACH :- the statement which says y : x true , we can group x and y into one group as we know that both of them can either be true or be false , similarly statement wich says y : x false , x and y belong to different group because if x is true , y is false and vice-versa . We have a paradox if two elements of the same group are said to be of the different groups i,e if one statement says y : x true and other says x ; y false , otherwise we don't have a paradox

problem : — PARADOX

My Solution : solution

I will be very thankful for the help and thanks in advance.

Read more »

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