angelg's blog

By angelg, history, 9 years ago, In English

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.

Full text and comments »

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

By angelg, history, 9 years ago, In English

Hello, I've been trying to solve this problem: http://codeforces.me/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?

Full text and comments »

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

By angelg, history, 9 years ago, In English

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.me/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

Full text and comments »

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

By angelg, history, 9 years ago, In English

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

Full text and comments »

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

By angelg, 10 years ago, In English

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:

Full text and comments »

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

By angelg, 10 years ago, In English

Hello, I have been trying to solve a problem from a Gym Contest (http://codeforces.me/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?

Full text and comments »

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