### dx24816's blog

By dx24816, history, 3 months ago, ,

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

•
• +6
•

By dx24816, history, 4 months ago, ,

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.com/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

•
• +4
•

By dx24816, history, 7 months ago, ,

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

•
• +3
•

By dx24816, history, 7 months ago, ,

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

•
• +5
•

By dx24816, history, 7 months ago, ,

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

•
• +3
•

By dx24816, history, 8 months ago, ,

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

•
• +1
•

By dx24816, history, 8 months ago, ,

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!

-dx24816

•
• +1
•

By dx24816, history, 8 months ago, ,

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!

-dx24816

•
• +3
•

By dx24816, history, 8 months ago, ,

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

•
• +5
•

By dx24816, history, 8 months ago, ,

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

•
• +4
•

By dx24816, history, 8 months ago, ,

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

•
• +2
•

By dx24816, history, 8 months ago, ,

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

•
• -2
•

By dx24816, history, 9 months ago, ,

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.com/contest/1009/submission/40353118

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

You can check the only difference is the pragma.

-dx24816

•
• +14
•

By dx24816, history, 9 months ago, ,

Hello,

I don't quite understand the solution for the USACO Platinum December Contest Problem 1. Can anyone explain it with more detail? Thanks!