Hello all,

I have tried googling this a lot but can't find a good solution. So any help will be greatly appreciated.

today, when I was doing the NOI, I came across a question which required me to use the convex hull trick. This is usually quite standard and easy to implement except for one thing: gradients of the lines can be a fraction. Let me explain:

The "line" that I am talking about isn't really a line. An example would be y = [mx] + c, where [x] means the largest integer small than or equal to x. (yes i know that it's not the right symbol but idk how to write mathematical symbols. Sorry for the inconvenience). If you plug this into desmos, it looks like a staircase. But i'm pretty sure that I can just use the line y = mx + c because if a certain line y = mx + c is minimum at a certain x then it will also be minimum when you take the floor. I have just explained this as maybe there is a different method for this kind of line, so if there is please let me know. Note that here, m can be fractional.

So now the problem is the standard convex hull trick with fractional gradients. However, I don't think using a fraction is correct as when you use fractions, the denominator can get quite large (potentially even bigger than 64 bit int). Also, using floats can, obviously, lead to precision errors.

So please help with a way to implement such a convex hull.

Also some additional information — there aren't really any update queries. You just add all of the lines to the hull at the start, then do all the queries. After queries, you don't have to add anymore lines. Also, all line gradients are negative, and queries can be either decreasing or increasing. (i can implement the solution such that the queries are either increasing or decreasing). So it is basically ur choice if you want queries to be increasing or decreasing, though I don' think it will make much of a difference.

Thank you so much for reading! And any help would be great!

Hello guys, in exactly two hours I am going to be taking the NOI qualification test. It is a 5 hour OI contest to select students to take the actual NOI (singapore) which is going to be a 7.5hr exam.

Does anyone have any tips for me? Any will be greatly appreciated. Thanks.

Hello all, I have a question about the problem in the recent div. 2 contest named in the title.

In the problem we are given a task to find a cyclical array of N numbers given the sum of local minima and local maxima. My claim is that the constraints of the question are incorrect as in an extreme case, my code will TLE.

This is because no constraint on N is given. However, the only constraints given are the sum of local minimas/maximas which is -1e9 <= X < Y <= 1e9. However, it is evident that length of the array will be 2*(X-Y). So if X = 1e9 and Y = -1e9, then N will be 2e9 won't it. And then we will have to output 2e9 numbers which will either TLE or MLE (since i am declaring an array with 2e9 integers which is a lot of space).

Am I misunderstanding? Any help will be appreciated. Thanks for reading.

UPD: I cannot read, and there was a constraint on N that said total sum of N over all test cases <= 2e5.

I have made the same mistake twice now...

Wondering what the mistake is? Well it is using a set instead of a multiset. I made this mistake in the last contest of 2022, which almost cost me the chance to become expert by the end of 2022. And now, i made it again in the first contest of 2023, and, will likely lose me expert status because of it.

I am kicking myself over this... Howwwwww,.. whyyyyyy....

Anyways, hopefully i will learn from this mistake and never make it again.

I also advise everyone reading this blog to always consider whether to use multiset or set as it can be the difference between AC, and WA. oftentimes, there is only one right answer.

Also, it is very important to not make a habit of using one over the other. This is the main reason i made both the mistake. I have never really needed to use multiset in my life. On the other hand, I use set quite frequently. This is why I had a habit of using set and not multiset and i didn't even think about it.

Hope everyone has great contests in 2023!

Actually no, please do shit so I can gain more rating points.

UPD: I only lost 4 rating points! I'm so glad that I didn't lose my expert status although I am very surprised that I only lost 4 points. I thought I would lose at least 30 or so rating points so I am very happy!

On the 1st December, 2022, I decided that by the end of 2022, I want to reach expert. I had commented this goal on to many blogs of the type, "what is your goal for the end of 2022", cementing my resolution in the internet, for all to see.

having a great two first contests in december, i shot up all the way from 1370, to 1589. However, in my penultimate contest of 2022, I had a terrible one. I dropped 34 points and was now 1555. All the pressure mounted on the last contest of 2022. And i had to do well

When the contest started, I got off to a terrible start. I used a set, instead of a multiset to store the elements of the array. And this was a fatal mistake. It took me a whole 30 minutes of debugging and 1 incorrect submission to fix it, after which i was well behind. I was the 7 thousandth person to solve the first question.

However, after this, my brain went into overdrive mode. I solved the second question and third question both in under 30 minutes. And i had a whole hour to solve the 4th question as well.

Although I came up with the correct idea, and even though I had written the entire code, unfortunately I made some mistakes which i didn't have time to debug.

However, despite my terrible start to the performance, as you can already see, I GAINED 64 POINTS AND AM NOW AN EXPERT. WOOHOO. I AM UNBELIEVABLY HAPPY.

This imo, shows the importance of setting high goals for urself. It is important to never lose hope in yourself, no matter what happens. This is also why I aim to become a legendary grandmaster by the end of 2023!

So look out for my blog post then, and i guess we'll see how far we can go!

Anyways, Toodaloo!

Well today I just got the notification that my rating increased by 133 points!! So now I am 1588 with only 12 left to get to EXPERT!!. Well this happened after a great div2 contest for me, (but a really shit problem C in my opinion). Not only was the solution itself kind of weird, but the majority of the time I spent coding was for the testcase where n=3. There were so many different ways to choose indices that i rlly wasn't sure if I counted them all or not. Anyways, I hope questions like C don't come again. Also, I can't help but wonder that if I solved C just a bit quicker, whether I would have gotten those 12 extra points in this contest itself. Anyways, Toodaloo.

I had a brilliant contest today, jumping up by a whole 140 points. AND I AM NOW A SPECIALIST. WOOHOO. I have made it my target to reach at least 1600 by the end of the year and it seems like I MAY DO IT! YAYY.

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.

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!

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"

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!

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.net/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.net/contest/1698/submission/162250574

But then, i made some changes to this code and got AC. This was my next submission: https://codeforces.net/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?

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!