TheOpChicken123's blog

By TheOpChicken123, history, 4 weeks ago, In English

This is the question i am trying to solve: https://open.kattis.com/problems/abinitio

This is my logic. I will represent the graph using a 2d adjacency matrix. adj[i][x] represents if there is a directed connection from i to x. And I also hold two booleans values. "transposed", and "complmented". So this is how I will handle the queries. My logic is that transposing or complementing the graph twice (no matter the updates in between) will always be the same as not complementing or transposing at all. So when I want to detect whether or not there is an edge between two nodes, u, v. If the graph is transposed, I will check adj[v][u] == complemented^1. Otherwise I will check adj[u][v] = complemented^1. (If complemented is 1, i am looking for 0 and vice versa).

So this is the code I produced: https://pastebin.com/Khp01P70

However, I get WA on testcase 4. Can someone please help me debug this? Thanks in advance.

Read more »

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

By TheOpChicken123, history, 2 months ago, In English

I have been recently doing this problem: https://codebreaker.xyz/problem/truck . Please read it before reading my question.

I have written code for it which has a time complexity of O(nlogn + q * logn) which should be sufficient to solve the question. Also, my code passes the two example testcases given in the problem statement. However, when I submit my code, it fails EVERY SINGLE other testcase. I have been debugging my code for almost a week now, trying to see if I am getting integer overflow anywhere, or if my logic is wrong. But i simply haven't found anything. I am asking you guys, PLEASE, for the sake of my sanity, help me solve my problem.

My code: https://pastebin.com/fnWh1Xbc

Definitions: Even though tolls are assigned to edges, I'm going to assign nodes tolls instead. Namely, the toll of a node is the toll of the edge from its parent, to itself. Also, total distance of some node a is the distance from the root to a. Total toll of some node a is the sum of tolls from the path from the root to a.

My main piece of logic: Consider wanting to find out the fuel needed to go from the root to some node, a. This is just equal to going from the root to the parent of a + (toll of a * total distance of parent of a) because adding the node a to the end of the path from the root to parent of a increases the toll you have to carry from root to parent of a by the toll of a. So in my fenwick tree, called to_node, I update the in time of node a to this value (toll of a * distance from root to parent of a) and the out time of node a to negative of this value. This is so that only nodes in the subtree of node a should get added with this value when wanting to find out fuel needed to go to root. So to calculate fuel needed to go from some node a, to root, it is just equal to from_node.sum(in_out[a].first). Now consider wanting to go from some node a to root. Notice that for every node x you reach in the path from a to root, you have to hold toll of x less gold bars in the path from x to root. So the total fuel saved by paying the toll of x at x is = total distance of x * toll of x. Therefore, to the fenwick tree, called from_node, at the in time of x i change the value to this (total distance of x * toll of x) and at the out time of x i change the value to the negative of this value for the same reason above. Then to calculate going from some node a, to root, it is just total toll of a * total distance of a — to_node.sum(in_out[a].first). (sorry if i didn't explain this bit very well. I learned this idea from another similar question i have done before.) Namely, this one: https://codebreaker.xyz/problem/dragonfly

Note; to_root and from_root functions are explained above. And so are all the update functions so I won't explain them again.

explanation of my code: I first do a dfs call (called calculate_city_info in my code) to calculate the depth, in_out time, distance from root of each city, as well as create the euler tour for finding LCA. I also update total_toll, from_node, and to_node at each node in the way described above. Next, for each query operation, I first find the LCA of the start and end. So first, i calculate going from the start to the LCA. This is equal to to_root(start) — to_root(LCA) — total toll of LCA * distance to LCA. I have to minus the additional (total toll of LCA * distance to LCA) because I carry the total toll of LCA gold bars extra in the path from start to LCA. However, I also have to add (distance to LCA * total toll from LCA to end) because that is how much more gold bars I have to carry in order to have enough to go from the LCA to the end and i have to carry it from the start to LCA. Next, I need to calculate fuel needed to go from the LCA to the end. This would be equal to from_root(end) — from_root(LCA) but I have to minus an additional (total toll from LCA to end * total distance of LCA) Because I carry more gold bars from the start when i'm going to the end vs when I'm only going to LCA. So now, I just have to add these two values. But wait, I haven't even taken into account for g yet. But this is quite simple, For the whole distance from the start to end, I just have to carry g extra gold bars. So i just add (distance from start to end * g). And when I add up all these values, I get my answer. I also have modded my values everywhere I can in order to stop integer overflow.

Also, all update operations just involve me updating the to_node, from_node, and total_toll in the same way that I did for dfs for the node with higher depth.

So what is wrong with my code or with my logic? I would be eternally debted to you if you can help me. Thanks!

Read more »

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

By TheOpChicken123, history, 2 months ago, In English

I have been trying to solve a question but I have a bug in my code which I need to fix. I also have files with inputs and corresponding outputs for this question. However the problem is that the input files are extremely big (about 3.5MB). Therefore, I cannot run it on my laptop as I get a segfault (I am certain it is because of stack overflow when I am doing dfs as I have done many tests). And I cannot run it on any online compiler, including codeforces, because the input file is too big. Most websites only allow input as big as a few hundred KB.

So my question is — How am i supposed to run my code with this input? The online grader where I found this problem only tells me if I got a testcase right or wrong or TLE, MLE, etc. It doesn't tell me anything as to the difference between expected and my output. So what should i do?

Note: I can't really find any smaller testcases either and every testcase that I make myself seems to work.

Edit: If you guys want to try on your own computers, here is the code: https://pastebin.com/fnWh1Xbc. And here is the input: https://paste.ee/p/FJKWt Please let me know if you don't recieve a segfault. Also note that if you want to copy the input, view the file as raw (there is a button on the linked website).

Also, this is the debug code that I used to make sure that the segfault is because of stackoverflow: https://pastebin.com/w9WV7Znx

The only difference between the two pieces of code is that in the debug code, I output "second" right before I go to a new node and the first thing that I do when I am at a new node is output "first". When I do this, the last thing my program outputs is "second" which means that it is the very act of calling the function which produces a segfault, which must mean that it is stackoverflow. Note that the dfs function is called "calculate_city_info"

Read more »

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

By TheOpChicken123, history, 3 months ago, In English

Hello all, I am a 15 year old student in Singapore, and one of my biggest dreams is to qualify to participate in the IOI, if not, get a medal in it. I know a lot of you are probably looking at my grey handle and questioning this goal but I am never going to give up and I study quite a lot for it. But anyways — because of this — I have a few questions of how IOI questions compare to the questions on CodeForces.

  1. Are the type of questions that you get in IOI similar to the ones you get on CodeForces? Or is there a subset of problems in CodeForces that are similar to the IOI? Do you get more Ad Hoc questions, or more algorithm + data structure intensive questions? Are there more array questions? Graph questions? Permutations and Combinations? I am looking for more of a general answer for this, i.e. If they appear not at all, rarely, frequently, or all the time.

  2. If the types of questions that you get in IOI and CodeForces are comparable, what would the rating distribution of questions be of the 3 questions you get over 1 day (5 hours) (if it were in a CodeForces contest). Also, what would be the lowest ranking on CodeForces to be able to solve these questions within the 5 hours. For example would a high yellow coder be able to do well in IOI?

I am asking the above two questions as if CodeForces is a good website to prepare for IOI, I can assign myself goals in CodeForces that would help me achieve in IOI. For example if my CodeForces rating is a good way to measure how well I would do in IOI, I can focus on improving my CodeForces rating and solving CodeForces questions.

However, if CodeForces is not a good website, or there is a better one:

  1. What would be the best website to test my problem solving skills on? I want a website with questions which have a similar difficulty and type to the questions that one would get in the IOI.

  2. What would be the best books or articles or videos (basically anything) that you recommend for me to read/watch to learn advanced algorithms and data structure's as well as advanced problem solving. I want a book that is challenging and has a target audience of advanced competitive programmers. Note, I am currently reading cp4 book 1 by Steven and Felix Halim.

Thank you so much for answering these questions (you don't have to answer them all, maybe just one would be greatly appreciated.) I would go through IOI past papers to answer these questions myself but unfortunately I don't have enough experience to figure out the underlying concept in questions or the intended solutions by the problem author. Thanks for helping!

Read more »

Tags ioi
 
 
 
 
  • Vote: I like it
  • +24
  • Vote: I do not like it

By TheOpChicken123, history, 3 months ago, In English

Hey all, I know that this is a very common topic and you are probably quite turned off by it but i still don't quite understand it. Please take the time to read through this post. Thanks a lot!

During the contest yesterday, I was solving 3SUM — closure: https://codeforces.com/contest/1698/problem/C I figured out the logic to the question and started implementing it. I used unordered_map — passed the pretests — but then TLE'd on the main tests. This was my submission: https://codeforces.com/contest/1698/submission/162250574

But then, i made some changes to this code and got AC. This was my next submission: https://codeforces.com/contest/1698/submission/162252261

Notice the difference between these two pieces of code? Yes! I used a map instead of unordered_map. Now, I have read many threads and articles advising to use maps instead of unordered_maps in my life, for all sorts of reasons, like slow hash functions, frequent collisions which cause the use of buckets which slow the unordered_map down, etc. But in this case, the only thing I'm doing is inserting and using the unordered_map::count function. are these not examples of where the unordered_map's O(1) time complexity should beat the map's O(logN)? Unlike, for example, iterating through the map, in which case, using a map instead of unordered_map would be faster? I was specifically asking myself this question during the contest and because of the fact that this was the only thing I was doing, I chose to use unordered_map — which turned out to stab me in the back and lose me quite a bit of rating. Basically, my question is, during competitive programming, is there EVER a time in which I would want to use unordered_map instead of map?

Read more »

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

By TheOpChicken123, history, 3 months ago, In English

Hey all, I have been struggling with this question for quite a while now (almost three months) and there are no solutions that I can find online. It is from the Singaporean NOI qualification 2022 qualification test. The problem is described in the title —

given a tree, find the maximum diameter of the tree if you can remove one edge, and put that edge anywhere else. However, in the end, it must remain a tree. This is the link to the problem which also contains two testcases. https://codebreaker.xyz/problem/treecutting

I have been able to do it in O(n*n) by brute force but it is too slow. Can anyone help? Any help will be greatly appreciated. Thank you!

Read more »

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