LunaticPriest's blog

By LunaticPriest, history, 18 months ago, In English

Hello, the mightly CodeForces community! It's me with another question because there are only 4 days left until the Turkey Olympiad in Informatics!!! I am trying to write the code that finds the LCA of 2 nodes with NlogN precomputation and logN per query. All the trees that I tested my code against, and all the corresponding edge cases give the correct output, so I don't really know where to fix. I've been debugging it for hours now :( Here is the code. I appreciate all your help, and I promise I will try to do my best to understand and implement your ideas!

Read more »

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

By LunaticPriest, history, 18 months ago, In English

Hi, the mightly Codeforces community! I'm having some problems with an easy shortest path question. I'm trying to solve Jzzhu and Cities and my code gets a TLE at 45th test case :( I'm basically using Dijkstra's Algo, only with the optimization that I store the information whether a node is reached by a railroad or a normal one. Here is the code. Thanks in advance for all your optimization advice, I'll do my best!

Read more »

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

By LunaticPriest, history, 19 months ago, In English

Hello Codeforces community, I am trying to find the sum of XOR of all pairs in an array, where: n < 3*10^5 and A[i] < 2^60. My algorithm works as follows: For each bit 0 to 59, find how many 0s and 1s there are. Then add (zero_count*one_count*bit_value) to the answer, and finally, print the answer MOD 1e10+7. I know that the algorithm is correct, but I'm still getting wrong answers. In the beginning, I was getting an overflow because of the bit-shifting, but I fixed it. I am taking mods everywhere, and I can't find where the bug is. Here is the code. Thanks a lot for taking your time and helping me.

Read more »

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

By LunaticPriest, history, 22 months ago, In English

Hello, I'm solving a basic connected components . My code is this . I tried switching to bitsets and a map instead of vectors, and also wrote my dfs iteratively in case of stack overflow. What can be the problem? Thanks!

Read more »

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

By LunaticPriest, history, 2 years ago, In English

Prim's algorithm requires a binary heap. At first, I thought I could easily use a priority queue, but it turns out that I have to reduce the weights of vertices in the priority queue, but it takes O(n) to find the vertex and modify its weight. A min-heap has the ability to reduce the weights of the vertices but it takes a lot of time to code it up, so it isn't useful for competitions. How to reduce the weight of the vertex with less complexity?

Read more »

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

By LunaticPriest, history, 2 years ago, In English

Is "checking if a graph can be colored by two colors" problem the same as "checking if a graph contains a cycle of an odd number of nodes"? Can we say that a graph is bipartite if it doesn't contain an odd cycle? Are they equivalent statements?

Read more »

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