Hello,

I was trying to upsolve this problem (https://codeforces.net/problemset/problem/1254/D), but I don't understand the n sqrt n solution described here (https://codeforces.net/blog/entry/71594?#comment-559559). Can someone explain in more detail how you can do all the sqrt(q) updates in linear time?

Also, I saw in this comment that binary indexed trees can go to constant time (https://codeforces.net/blog/entry/71534?#comment-559225), can someone explain to me how this works, or how I'm misunderstanding this.

-dx24816

Hello,

Up until now, I've been coding in C++ with Codeblocks and debugging using print statements. However, I would like to learn to use GDB and other stuff. Are there any good tutorials, tips, or tricks on using the command line to compile/run/debug code?

-dx24816

Hello,

To prepare for USACO platinum, I'm doing problems from various OI's. However, I can't find editorials for the vast majority of them, and when I can, most of them are in language other than English. Can anyone suggest problems for USACO platinum training (I've done all the past USACO problems pretty much) that have good editorials in English?

-dx24816

Hello,

I was recently reading the solution for the 2016 CEOI problem Kangaroo. However, I can't understand what motivates you from switching from A[n][i][j] and D[n][i][j] to trying to compute X[n][i][j] and Y[n][i][j]. I know it's a common trick to substitute sum and difference, but is there a deeper reason for why I would think of doing this substitution and knowing that it will work out?

Problem: https://oj.uz/problem/view/CEOI16_kangaroo Solution: http://ceoi.inf.elte.hu/probarch/16/kangaroo-solution.pdf

-dx24816

Hello,

Does anyone have a convex hull trick with linear complexity given that the lines you insert are in sorted slope order and the queries are also sorted? I used to just use the Li Chao tree, but it's not fast enough to solve APIO 2014 Split the sequence.

-dx24816

Hello,

Can someone provide and explanation of the DP optimization used to get 100 points on Aliens of IOI 2016? I read their solution, but I still don't see how introducing the constant C helps you solve the problem. I also don't see the purpose of the g function they introduce.

Problem:https://ioinformatics.org/files/ioi2016problem6.pdf Solution: https://ioinformatics.org/files/ioi2016solutions.pdf

-dx24816

Hello,

I have done most to all of the USACO platinum problems and am looking for OI's that are of similar difficulty and content level. Is there a list or something that ranks the OI by relative difficulty?

-dx24816

Hello,

I recently came across a post talking about how it was possible to implement the Li Chao Tree persistently. However, I was unable to get it to work. Does anyone have a working implementation?

-dx24816

Hello,

For Compound Escape (http://www.usaco.org/index.php?page=viewproblem2&cpid=949), I'm not fully clear on how to do the transition states. First of all, what would the connected components represent for a partially processed row as mentioned in the editorial(http://www.usaco.org/current/data/sol_escape_platinum_open19.html)? Can someone give me a clear coded up solution or an explanation of a solution, as I don't fully understand the editorial's solution as I feel a lot of details are missing.

-dx24816

Hello,

Can anyone link my to sources with ugly state DP problems? An example of ugly state is like the standard problem of trying to tile a chessboard with dominoes.

-dx24816

Hello,

I don't quite understand the editorial to Mowing the Field (http://www.usaco.org/index.php?page=viewproblem2&cpid=601). The solution they gave here (http://www.usaco.org/current/data/sol_mowing_platinum_jan16.html) claims that you can answer the range queries in originally log(n)^3 time. However, I don't understand why. For a specific vertical segment i, we want to find how many times it intersects a horizontal segment. I see how we can use a range query tree for the conditions y_i^b < y_j < y_i^t and abs(t_i — t_j) >= T. But I don't see how the range query tree can solve the part x_j^l < x_i < x_j^r as you're querying with i. In addition, I'm not quite clear on how you can update the range tree without having to update at each point on each horizontal line. Can anybody provide some help with these questions?

Edit: I have thought about this some more, and there is no way that I can think of to not have a n^2 on the complexity besides incorporating some for of line sweep. If I am wrong, can someone point out how to remove the n^2 with just the range tree as it says in the editorial without the use of a line sweep?

-dx24816

Hello,

I'm certain this has been asked before, but the USACO platinum problems have changed a lot in the past few years. So nowadays, what's a reasonable/rough comparison between Codeforces level and USACO platinum problems? I've run out of platinum problems to do, so I'd appreciate if anyone could direct me to more similar difficulty problems.

-dx24816

Hello,

Recently, I've been learning about the persistent segment tree. However, is there a way to get a persistent segment tree with range updates, and not just point updates? If so, can someone direct me to a clean and easy implementation in C++? Thanks!

-dx24816

Hello,

Recently, I was doing Cow Run (http://www.usaco.org/index.php?page=viewproblem2&cpid=265), and I at first used the Policy Based Data Structure faster map (https://codeforces.net/blog/entry/60737), but I TLE'd on the last 4 test cases. I then switched back to using the unordered_map, and I passed all the test cases. Can anyone tell me the reason why the unordered_map was faster? I was under the impression that the PBDS map was faster. Thanks!

Code with unordered_map: https://ideone.com/Id7SZM Code using PBDS map: https://ideone.com/sA4UJG

To run this code, simply submit them in a file to the USACO website above, and use C++11.

-dx24816

Hello,

I have been studying the problem of Longest Increasing Subsequence (N log (N)) from the GeeksForGeeks website, but it doesn't make sense to me, and I don't know if their code is right. Can someone explain the algorithm, and also provide working code? Also, can someone tell me how I can modify the code to work for nondecreasing sequences and provide working code? Also, how can I reconstruct the actual sequences? Thanks!

-dx24816

Hello,

Can someone explain the solution to USACO newbarn (Problem: http://www.usaco.org/index.php?page=viewproblem2&cpid=817, Solution: http://www.usaco.org/current/data/sol_newbarn_platinum_feb18.html)? I don't understand what his variables names mean, like tree[c].top, tid, etc. Can someone explain what all of his variables mean and how each part of his program works, including his centroid decomposition? Thanks!

Edit: OK, if anyone has a centroid decomposition solution that's not the official solution (I can't understand how the checking for the same subtree idea works), can you post it and explain it in depth? Also, when you're talking about trees and childs, can you distinguish between children on the actual tree or the centroid tree?

-dx24816

Hello,

Can somebody help me debug my code for USACO newbarn (http://www.usaco.org/index.php?page=viewproblem2&cpid=817)? I am in dire need of help, as I have been debugging for around a week. I have no idea why my program is wrong, as every test case I give it, it gives me the right answer. I eventually gave up and just used the USACO test cases, but I it only gets the wrong answer by like line 1000, everything before is right. My strategy is as follows: I use DSU to find the components of all of the barns, and then put all the barns in each component into the forest vector. To calculate the maximum distance, I arbitrarily root each tree in forest, and DFS to precompute the depths of each node. Let a node x be in the subtree of a neighbor n of the root r. The maximum distance to another node is the maximum depth of any node in the subtrees of the neighbors of r (excluding the subtree that n and x are in), or it is the depth of x, or it is the maximum depth of any node in the subtree of n minus the depth of x. I reorder nodes using the seg map making sure nodes in the same component are consecutive, and put them into a segment tree. The bounds vector stores the left most and right most node in each component in the segment tree. Then for each query, I compute the maximum diameter, or update. Can somebody please find my error? Also, I am in need of debugging tips, as I often have the right idea, but can't implement it correctly. If you have any questions at all about my code, just ask. Thanks!

Code (https://ideone.com/oyX7GA)

Edit: It would also be much appreciated if someone found a test case I could test by hand where my program fails. The problem is that all 30 test cases I came up with were passed by my program.

-dx24816

Hello,

I tried to solve sprinkler, but I was not able to come up with an algorithm faster than O(n^2), which somehow got 11/12 test cases. I read the solution, but it doesn't make sense. First of all, I don't get what it means by acceptable and unacceptable triples. I also don't understand their column argument about the interval of acceptable points, and how they compute their values. Can somebody explain their solution (or another good one) and provide their code? Thanks!

-dx24816

Hello,

I was trying to do the problem pushabox (http://usaco.org/index.php?page=viewproblem2&cpid=769) with biconnected components, and I think my biconnected components algorithm is right, but for some reason my code is producing the wrong answer on test cases 5-15. I have commented my code so it is easy to understand my logic. Can somebody help me figure out where my logical error is? Thanks!

Code: https://ideone.com/SU9VU8

-dx24816

Hello,

I tried to do QTREE5 (https://www.spoj.com/problems/QTREE5/), but I keep getting WA on test case 5. I'm using Centroid Decomposition, and I'm pretty sure it's correct because I tested it on Codeforces 342E and got AC. That means the error is probably in the closest function, the toggle function, getDist function, or something in the main function. Can somebody point out my error? Thanks!

Code: https://ideone.com/gZ85l8

-dx24816

Hello,

Does anyone know of a good C++ centroid decomposition implementation? Also, I'm trying to figure out what types of problems I should be using this technique on. Thanks!

-dx24816

Hello,

I want to submit my code to the problems on USACO 2011-2012 (usaco.org), but for some reason it doesn't have analysis mode like the other years. When I download their test data, some of the data is in some weird language (Chinese or Japanese or Korean?), and they aren't formatted right, as they are all in one line with little or no spaces. Is there any way I can test my code for these USACO problems? Thanks!

-dx24816

Hello,

I was trying to do the USACO problem Grass Planting (http://www.usaco.org/index.php?page=viewproblem2&cpid=102), but couldn't get my Heavy Light Decomposition to work. Can somebody direct me to a Heavy Light Decomposition implementation without LCA? Also, could someone also show me how to implement Heavy Light Decomposition with both the values on vertices and then with the values on the edges? I tried using Al.Cash's implementation, but for some reason, it failed. Thanks!

Edit: I got the edge version to work on the grass planting problem my messing around with Al.Cash's implementation, but can't vertex version to work. I was trying to do Timus 1553 (http://acm.timus.ru/problem.aspx?space=1&num=1553), but keep getting WA on test case 4. I'm pretty sure it's because of my HLD, and I'm not sure what's going on. Can somebody point out my error?

My code (https://ideone.com/k4gvQX)

-dx24816

Hello,

I have recently been reading about the convex hull trick (https://wcipeg.com/wiki/Convex_hull_trick), but I can't seem to implement the fully dynamic version. Can anyone point me to a C++ implementation of the fully dynamic convex hull trick? Thanks!

-dx24816

Hello,

I use to include the following code into my headers because I saw others doing the same.

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

For the most part, it has made some of my programs that previously got TLE get AC. However I recently kept getting TLE with these comments in the header of my program for a problem, and when I removed them, I got AC. So I'm wondering what do these comments do, and when should I use them? Thanks in advance!

Edit:

Here is the TLE: http://codeforces.net/contest/1009/submission/40353118

Here is the AC: http://codeforces.net/contest/1009/submission/40353105

You can check the only difference is the pragma.

-dx24816