abhatter's blog

By abhatter, history, 4 weeks ago, In English

Hello, I am trying to generate all permutations and for each permutation I am checking if the given conditions are satisfied and then counting it as part of the solution. But this approach times out as the time complexity is n*n!

I am not able to understand as to what can be precomputed.

Any help is appreciated.

Click for problem link

Thanks in advance

Read more »

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

By abhatter, history, 6 weeks ago, In English

Hello, Can you please explain how the solution is 22 to the given sample example in the problem description. Click to view problem description

Thanks in advance

Read more »

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

By abhatter, history, 2 months ago, In English

Problem link: https://cses.fi/problemset/task/1163

Hello, I am using an interval tree to solve this problem but for 2 test-cases my solution are timing out. I have provided a drawing for the sample input given in the problem description.

0-8
                 /    \
                /      \
               /        \
             0-3         3-8
            /  \        /   \
           /    \      /     \
       0-2       2-3  3-6    6-8

Each time, I am adding a new interval I am returning the max diff of intervals to the root node and returning it as an answer

Could you please help me

Read more »

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

By abhatter, history, 3 months ago, In English

Hello,

I am learning to apply memoization technique but not able to figure it out. My brute force recursive back tracking solution gives correct answer but then times out quickly. I tried to search answer to this question but then I am not able to understand anything. could you please help me in this regards?

Problem link below...

Thanks in advance

Read more »

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