Tobby_And_Friends's blog

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

Can anyone please help me figure out what is wrong with my solution?

Problem: https://www.spoj.com/problems/CONSEC/ My solution: https://ideone.com/zXToOA Verdict: WA

I used DSU and processed the queries in reversed order. So, basically I started with the string after the characters of the string were replaced by the '#' character. For query of type 1 i, I stored the current maximum for that character to be printed later on and for query of type 2 i, I tried to incorporate this character with the remaining set and updated the maximum for this character.

Read more »

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

By Tobby_And_Friends, 7 months ago, In English,

[Solved] Problem Link: https://toph.co/p/unbelievable-array

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

Verdict: Wrong Answer

My approach: For all the same numbers I am trying to group them using disjoint set data structure. I am referring the value of the numbers in each of the index of the array A as color. So, each of the distinct colors will have a distinct parent. I am mapping the color to the parent using color array. Also, I am mapping the parent to the color using par array. So, for queries which need replacing one color by other there are two cases where I need to change the value in the color and par array, one is when both the colors are present and another, the color to be replaced by is not present but the color which will get replaced is present in the array. And for the query which asks for the color value in the index idx I am finding it's parent and then displaying the result from the parent to color mapping array (**par**).

Can anyone please help me in finding why I am getting WA? Thanks in advance.

Read more »

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

By Tobby_And_Friends, history, 2 years 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, 2 years 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, 2 years 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 »

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

By Tobby_And_Friends, history, 2 years 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, 2 years 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, 2 years ago, In English,
 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it

By Tobby_And_Friends, history, 2 years 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 »

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

By Tobby_And_Friends, history, 2 years 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, 2 years 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, 3 years 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, 3 years 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, 3 years 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 »

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

By Tobby_And_Friends, history, 3 years 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, 3 years 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, 3 years 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, 3 years ago, In English,

What are some recommended problems from Kattis online judge?

Read more »

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

By Tobby_And_Friends, history, 3 years 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 »

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

By Tobby_And_Friends, history, 3 years 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 »

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

By Tobby_And_Friends, history, 3 years 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 »

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

By Tobby_And_Friends, history, 3 years 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, 3 years 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, 3 years ago, In English,

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

Read more »

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

By Tobby_And_Friends, history, 3 years 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