### Tobby_And_Friends's blog

By Tobby_And_Friends, history, 7 months ago, ,

If there were only only 2 attributes of the vegetables I would have been able to solve the problem. I would have simply sorted in descending order the vegetables according to it's first attribute. And as for the second attribute I could have easily found the answer using a BIT/Fenwick tree. But I am not able to figure how to solve this problem with 4 attributes of the vegetables. Any help is really appreciated.

•
• -8
•

By Tobby_And_Friends, history, 8 months ago, ,

My solution: https://ideone.com/srH91b

Verdict: TLE

How do I optimize my solution? Any help is really appreciated.

[Update] Got AC :) I missed out the fact that block sizes are of n^(2/3)

•
• +8
•

By Tobby_And_Friends, history, 9 months ago, ,

I have read in a blog that this particular problem involves dynamic programming with binary search. Someone kind enough please provide me an explanation on how to solve this problem using the mentioned topics.

By Tobby_And_Friends, history, 9 months ago, ,

My partial solution:

1) If the given values do not satisfy this equation -> rx + ly = t then there is no solution.

2) Now, in order to find the minimum value I can do a BFS but this will result me a TLE in certain cases. How should I implement this part cleverly?

•
• -8
•

By Tobby_And_Friends, history, 9 months ago, ,

Does anyone maintain a list of problems he/she has solved so far which was interesting and a bit challenging? If so, please share.

•
• +88
•

By Tobby_And_Friends, history, 10 months ago, ,

•
• +3
•

By Tobby_And_Friends, history, 10 months ago, ,

Verdict: TLE

Solution Approach: Trying out all possible row combinations and for each row combination finding the maximum area using binary search

By Tobby_And_Friends, history, 10 months ago, ,

Can anyone please suggest me problems that can be solved using C++ STL: Policy based data structures? I tried looking for some problems but apart from SPOJ ORDERSET I did not find any. Thanks in advance.

•
• +13
•

By Tobby_And_Friends, history, 12 months ago, ,

I was trying this problem from SPOJ: http://www.spoj.com/problems/LVADER/en/. I figured out the recurrence for the problem which is f(x, y) = f(x — 1, y) + f(x, y — 1) + f(x — 1, y — 1), f(x, 0) = f(0, y) = 1. The constraints of the problem does not allow me to use normal DP and I'm not aware how to use matrix exponentiation technique for 2-D recurrence. I read this article: https://threads-iiith.quora.com/Solving-Dynamic-Programming-with-Matrix-Exponentiation but I could not fully understand the idea. Any help is really appreciated.

•
• -2
•

By Tobby_And_Friends, history, 14 months ago, ,

My solve() method where I'm trying to implement dp is wrong. Any help to correctly implement the dp portion will be really appreciated.

•
• +1
•

By Tobby_And_Friends, history, 15 months ago, ,

I just learned centroid decomposition today. Please refer me some problems on Centroid Decomposition. I read the topic from this link: https://tanujkhattar.wordpress.com/2016/01/10/centroid-decomposition-of-a-tree/ so please provide me some additional problems to begin with.

•
• +9
•

By Tobby_And_Friends, history, 15 months ago, ,

I was thinking of solving using euler tour technique (link: http://ideone.com/OEoGL2) but I'm not getting how to update the nodes correctly. Any hints on how to solve this problem will be really appreciated. Thanks in advance.

By Tobby_And_Friends, history, 16 months ago, ,

I just learned about hashing and tried to solve this problem using the technique. My idea is I will pre-process _hash array with the hash values and afterwards I will just extract hashes of all the k-length strings and keep that in a map. Afterwards, I just output the size of the map. Any help to identify my mistake is really appreciated.

•
• -6
•

By Tobby_And_Friends, history, 17 months ago, ,

I understand that LCM is a multiplicative function. So, for the case where n = 6, it should be like f(6) = f(2) * f(3), f(2) = (1 + 2) + (2 + 2) = 7, f(3) = (1 + 3) + (3 + 3) = 10, therefore f(6) = f(2) * f(3) = 7 * 10 = 70. But this is the wrong answer. Someone please help me out to figure out the right solution. Any help is really appreciated.

•
• +3
•

By Tobby_And_Friends, history, 17 months ago, ,

I understand the O(nlog^2n) implementation but I want to learn the nlogn implementation. So, if anyone can suggest me any blog or tutorial related to this it would be very helpful.

•
• -11
•

By Tobby_And_Friends, history, 17 months ago, ,

What are some recommended problems from Kattis online judge?

•
• +1
•

By Tobby_And_Friends, history, 17 months ago, ,

Verdict: TLE

I tried to use Mo's algorithm and segment tree to solve the problem. How do I further optimize my solution? Any help is really appreciated.

By Tobby_And_Friends, history, 17 months ago, ,

I understand that the for n == m answer is 2. But I can't figure out the solution when n != m. I mean I basically do not understand the theory behind the solution (apart from trying out for small test cases). Any help is really appreciated.

By Tobby_And_Friends, history, 17 months ago, ,

I could figure out that let's say for 5 numbers the answer is (Arr[1] + 4 * Arr[2] + 6 * Arr[3] + 4 * Arr[4] + Arr[5])/2^16. So the problem basically reduces to finding the values in the nth row of pascal's triangle and power of 2. But I am not very sure as to how to implement the solution. Any help is really appreciated.

By Tobby_And_Friends, history, 18 months ago, ,

How to determine whether a number is a product of consecutive primes? The number can be at max 10^14. Any hints is really appreciated.

•
• +1
•

By Tobby_And_Friends, history, 19 months ago, ,

My implementation: http://ideone.com/bLGTpc

Verdict: WA

Anyone please help me to figure out my mistake. I learned Suffix Array today and this is my first implementation. Any help is really appreciated.

•
• -10
•

By Tobby_And_Friends, history, 19 months ago, ,

Anyone please suggest me some beginner-level/basic problems on DP on Trees. Thanks in advance.

By Tobby_And_Friends, history, 19 months ago, ,

Any hint is really appreciated.

•
• +11
•

By Tobby_And_Friends, history, 19 months ago, ,

Problem name: Count LCM

Let's say n < m. Then the answer is for each integers i, from 1 to n, how many integers up to m are co-prime with i. I tried solving the problem but it got me a TLE. How do I optimize my solution? Any help is really appreciated.

•
• +5
•

By Tobby_And_Friends, history, 20 months ago, ,