LunaticPriest's blog

By LunaticPriest, history, 6 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, 6 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, 6 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, 10 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, 11 months 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, 11 months 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