Tobby_And_Friends's blog

By Tobby_And_Friends, history, 6 weeks ago, In English,

Problem link: http://www.spoj.com/problems/ADACABAA/

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.

Read more »

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

By Tobby_And_Friends, history, 6 weeks ago, In English,

Problem link: http://www.spoj.com/problems/ADAUNIQ/

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)

Read more »

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

By Tobby_And_Friends, history, 3 months ago, In English,

Problem Link: http://lightoj.com/volume_showproblem.php?problem=1180&language=english&type=pdf

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.

Read more »

 
 
 
 

By Tobby_And_Friends, history, 3 months ago, In English,

Problem Link: https://uva.onlinejudge.org/external/113/11312.pdf

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?

Read more »

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

By Tobby_And_Friends, history, 3 months ago, In English,

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

Read more »

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

By Tobby_And_Friends, history, 3 months ago, In English,
 
 
 
 
  • Vote: I like it  
  • +3
  • Vote: I do not like it  

By Tobby_And_Friends, history, 4 months ago, In English,

Problem Link: http://lightoj.com/volume_showproblem.php?problem=1424

Solution Link: https://ideone.com/2eUIav

Verdict: TLE

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

Someone please help me out how can I optimize my solution.

Read more »

 
 
 
 

By Tobby_And_Friends, history, 4 months ago, In English,

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.

Read more »

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

By Tobby_And_Friends, history, 5 months ago, In English,

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.

Read more »

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

By Tobby_And_Friends, history, 8 months ago, In English,

Problem Link: https://toph.co/p/keep-moving Solution Link: http://ideone.com/L7pxbT

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

Read more »

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

By Tobby_And_Friends, history, 8 months ago, In English,

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.

Read more »

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

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

Link: https://uva.onlinejudge.org/external/129/12998.pdf

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.

Read more »

 
 
 
 

By Tobby_And_Friends, history, 10 months ago, In English,

Problem: http://www.spoj.com/problems/ADACLEAN/ Solution: http://ideone.com/TracEP Verdict: Wrong Answer

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.

Read more »

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

By Tobby_And_Friends, history, 11 months ago, In English,

Problem Link: https://uva.onlinejudge.org/external/125/12546.pdf

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.

Read more »

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

By Tobby_And_Friends, history, 11 months ago, In English,

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.

Read more »

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

By Tobby_And_Friends, history, 11 months ago, In English,

What are some recommended problems from Kattis online judge?

Read more »

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

By Tobby_And_Friends, history, 11 months ago, In English,

Problem link: http://www.spoj.com/problems/PATULJCI/

Solution link: http://ideone.com/NqSI3j

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.

Read more »

 
 
 
 

By Tobby_And_Friends, history, 11 months ago, In English,

Link: https://uva.onlinejudge.org/external/117/11774.pdf

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.

Read more »

 
 
 
 

By Tobby_And_Friends, history, 11 months ago, In English,

Link: https://uva.onlinejudge.org/external/108/10883.pdf

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.

Read more »

 
 
 
 

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

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.

Read more »

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

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

Problem Link: https://uva.onlinejudge.org/external/12/1223.pdf

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.

Read more »

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

By Tobby_And_Friends, history, 13 months ago, In English,

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

Read more »

 
 
 
 

By Tobby_And_Friends, history, 13 months ago, In English,

Any hint is really appreciated.

Problem link: https://uva.onlinejudge.org/external/17/1734.pdf

Read more »

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

By Tobby_And_Friends, history, 13 months ago, In English,

Problem name: Count LCM

Link: https://uva.onlinejudge.org/external/128/12888.pdf

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.

Solution Link: http://ideone.com/mMoWMS

Read more »

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

By Tobby_And_Friends, history, 14 months ago, In English,

Problem link: https://www.hackerrank.com/challenges/digit-products

My solution: http://ideone.com/wXDPi3

I got a verdict of TLE. How can I optimize my code further? Any help is really appreciated.

Read more »