rachitiitr's blog

By rachitiitr, history, 8 years ago, In English

The following problem deals with finding the biconnected components in an Undirected graph and treating them as vertices. The code provided in editorial isn't easy for me to understand. Can someone share a template code for how to find biconnected components?
The code given on GeeksforGeeks finds the edges in a biconnected component. I do not trust it as in the solution given there, he talks about cross-edge and stuff. Cross-edge in undirected graph?
Link to the Problem --> Problem E. Pursuit For Artifacts

Full text and comments »

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

By rachitiitr, history, 8 years ago, In English

The question I am asking is very vague but if some experts can share some of their tricks or tips while solving DP questions would be really helpful. The problems I face is how to think of such complex DP states, and even if I think of them, how should I initialse the base values(e.g dp[0][0] = 1or0). Consider the two problems
1. D. Magic Numbers
2. B. Numbers
Both of them have DP based solutions.
D.Magic Numbers Tutorial link
Brief Solution: dp[i][j][k] is our dp state that represents number of magic prefixes of length i with remainder j modulo m. If k  =  0 than the prefix should be less than the corresponding prefix in n and if k  =  1 then the prefix should be equal to the prefix of n (it can not be greater).
First of all, how does one realises the need of having that [k] in out DP. Also in the solution, for k = 0, line 54 is letting the digit at new position be greater than a[i]. I understand that the over all number should be less than or equal to the prefix of our original number. So the digits in the number we are forming can exceed the digit at corresponding position in original number a, but how is everything working is really difficult to think. How are so many people able to think about it and how do they begin to solve such DP problems?

Let's assume I magically understood the DP state. After that, the problem I faced was to initialise the base values. I was going to initialise the dp[1][j][k] values but that would be too longer. On looking at the solution, dp[0][0][1] = 1 was enough. It took me time to see how magically it was finding the correct answers.

B. Numbers Tutorial link
Brief Solution: dp[i][j] is our dp state that represents numbers of length i formed by using digits from [j, 9]. Thus dp[i][j] +  = dp[i - x][j + 1] * C[i][x], where x is number of times I use digit j. Perfect! But what I could think of is that I have to count the number of permutations of length [sum(a[i]), n] such that occ[i] >  = a[i], and I began to think of how to solve this.

I clearly understand that more practise is needed, but seeing the tutorials for DP problems I was wondering whether there are some DP states that are very common or some standard DP techniques that one must master. One example being the usage of "Subset Hack" in E. Compatible Numbers. I couldn't even find tutorial on what "Subset Hack" is.

Full text and comments »

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

By rachitiitr, history, 8 years ago, In English

Problem Link — E. Train and Statistics
Working on Ideone whereas
RTE on codeforces
Can some help me find out what's the problem here?

Full text and comments »

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

By rachitiitr, history, 9 years ago, In English

I am solving the problem QTREE2 on Spoj. http://www.spoj.com/problems/QTREE2/ I am learning LCA and I am not able to detect the reason for WA. Could someone help me? Here is my code: http://ideone.com/KTmgd2

Full text and comments »

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