### angelg's blog

By angelg, history, 9 years ago,

Let's suppose you have an array A of numbers (0-255). Then, you pick a single variable K (0-255), and you create another array B. Where Bi = Ai ^ K. Is there a way to restore the original array A? If you are not giving A or K.

• -4

By angelg, history, 9 years ago,

Hello, I've been trying to solve this problem: http://codeforces.com/gym/100733/problem/I. I tried to solve it modeling the problem as a flow network. All edges have capacity one. I build the graph twice, one for considering each tree as tree A and the other as tree B. I add M edges from the sink to the highest branches of tree A, and connect the M lowest branches from tree B to the sink. Then I connect all branches that fulfill the inequity abs(Ha — Hb) < T. But, I'm getting wrong answer in test #21. This is my submission: http://ideone.com/6sC2ek.

I would understand a TLE veredict as my solution creates a huge amount of edges about (500^2) in some cases. What would be a better solution for this problem? Is there a way to build this as a flow network and use less edges? I also tried to come up with a DP solution, but I failed to do so. Can anyone point me in the right direction?

• 0

By angelg, history, 9 years ago,

Hello, today took place round #313. I have recently read some articles regarding hashing and how useful they can be to compare to strings really fast. When I read problem D (Equivalent Strings), I came up with a possible solution using DP and Hashing. It took me quite some time to get it to work properly, but sadly I got a TLE veredict after the final tests came through. This is my solution: http://codeforces.com/contest/560/submission/12189499.

After the contest, I managed to make it work slightly faster, but it only got AC after changing the recursion order, I know this in fact affects the running time of my solution. But I still haven't been able to figure the actual time complexity of this solution. I used four states representing the segment of string A and B we are currently checking if they are equivalent or not. I had to use a map, in order to keep a memo for the states already calculated. With the help of hashing, I believe the string comparisons could be done quite fast.

Cheers, Angel

• +5

By angelg, history, 9 years ago,

Hello, I've been trying to learn new useful data structures, I've tried to implement a couple "sqrt descomposition" problems lately. I came across this problem a couple of weeks ago: http://coj.uci.cu/24h/problem.xhtml?pid=3228. The problem statement is pretty simple and straight to the point. I think I came up with a O( sqrt(N) * log(N) ) solution which might work: http://ideone.com/ibCkwY. But, I keep getting a TLE veredict. Is there a faster approach with Segment Tree or any other data structure? or even a better way to solve this one with Sqrt Descomposition?

Thank for reading, Any kind of help is appreciated

• +9

By angelg, 9 years ago,

At the moment it seems when I try to filter problem by tags, It would only display problems I've solved with that tag? Here's a screenshot of what I'm currently getting:

• 0

By angelg, 10 years ago,

Hello, I have been trying to solve a problem from a Gym Contest (http://codeforces.com/gym/100484/attachments — 100484G — Highways). It seems like an straightfoward Kruskal implementation to me. At first, I was using a vector to store all the edges, but that resulted in MLE in testcase 21. Only then I came to realize N could be upto 10^4, and there's no way to store 10^4 * 10^4 edges without getting a MLE veredict.

Is there an heuristic or data structure to quickly calculate the minimum distance between all the points and generate the MST of the given graph?

• 0