Comments (9)
There are actually a fair number of cases where you might/will type in only parts of the code: Treap, FastSubsetTransform (that one's weird), euclid, chinese, 2sat, TreePower, HLD (on the chopping block), sideOf, Angle, KMP, SuffixTree, Hashing, AhoCorasick, IntervalContainer. And in several more I can imagine that the 100->50 line reduction is handy. So if we could come up with some slick UI for indicating sections I'd be all for it. I agree with your comment about ambiguity, though, and I think we can start simple.
from kactl.
Just a note: I updated the hash script in our book to include the -dD
flag, which preserves macro definitions. It's now cpp -dD -P -fpreprocessed | tr -d '[:space:]' | md5sum -
from kactl.
The other argument for hashing sections is that if the hash fails, then you need to look at less of your code. I haven't done many offline contests with a TCR, but from my experience, knowing that you have a mistype in 50 lines of code is only marginally better than knowing you have a mistype in 100 lines of code. Both of these are massively better than not knowing whether you have a mistype or a logic error.
I think knowing you have a mistype in 50 vs 100 lines of code is actually linearly (~2x) better for finding the bug, which amounts to maybe 5 minutes of time (and feeling a lot happier).
from kactl.
Also, I'll note that we would've hashed sections in more files if we used them more/weren't too lazy to add the annotations. Honestly, we mostly used kactl for the stuff we added (which we broke into sections) and the geometry (which is short to begin with).
from kactl.
Thanks for the note, I've made that change: dcdc34a (note also the golfed vimrc: ca Hash w !cpp -dD -P -fpreprocessed \| tr -d '[:space:]' \| md5sum \| cut -c-6
)
from kactl.
Hi, I want to propose an idea for "partial hashes", idea communicated to me by https://codeforces.com/profile/camc
let's say you want a struct:
struct LCA {
...
LCA(vector<vi>& C) : time(sz(C)), rmq((dfs(C,0,-1), ret)) {}
void dfs(vector<vi>& C, int v, int par) {
...
}
int lca(int a, int b) {
if (a == b) return a;
tie(a, b) = minmax(time[a], time[b]);
return path[rmq.query(a, b)];
}
int dist(a,b) {return depth[a] + depth[b] - 2*depth[lca(a,b)];}
int inSubtree(a,b) {return time[a] <= time[b] && time[b] < timeOut[a];}
int nodeOnPath(u,v,w) {...}
...
};
you can split it up like:
LCA.h
:
struct LCA {
...
LCA(vector<vi>& C) : time(sz(C)), rmq((dfs(C,0,-1), ret)) {}
void dfs(vector<vi>& C, int v, int par) {
...
}
#include "lcaFunc.h"
#include "dist.h"
#include "inSubtree.h"
#include "nodeOnPath.h"
};
lcaFunc.h
:
#pragma once
int lca(int a, int b) {
if (a == b) return a;
tie(a, b) = minmax(time[a], time[b]);
return path[rmq.query(a, b)];
}
dist.h
:
#pragma once
int dist(a,b) {return depth[a] + depth[b] - 2*depth[lca(a,b)];}
inSubtree.h
:
#pragma once
int inSubtree(a,b) {return time[a] <= time[b] && time[b] < timeOut[a];}
... etc
Now each member function is in it's own file, thus has it's own hash. Furthermore, you type exactly what you need: if you only need lca function, you only type it;verify hash, then copy into struct.
If you need lca,dist, inSubtree, you type all three, verify all their hashes, then copy them into the struct
Furthermore, the include statements tell you exactly where to put the member functions
from kactl.
Now you don't want to force the user to type those include statements, so for me, when I generate the .pdf
, I have this in a script:
contest/hash.sh
:
tr -d '[:space:]' | md5sum | cut -c-6
generate_pdf.sh
:
shopt -s globstar
for header in ../content/**/*.h; do
hash=$(sed '/^#include/d' "$header" | cpp -dD -P -fpreprocessed | ./../contest/hash.sh)
sed --in-place "1i //hash: $hash" "$header"
done
from kactl.
furthermore, if you use something like the expander script for codeforces rounds where you can copy-paste; this method should still work
from kactl.
for example for you can split apart fenwick tree lower bound https://github.com/kth-competitive-programming/kactl/blob/main/content/data-structures/FenwickTree.h#L24 as you rarely need that function
for example for this
https://github.com/kth-competitive-programming/kactl/blob/main/content/graph/CompressTree.h#L18
where you pass in LCA& lca
as a parameter, Instead, you could add compressTree
as a member function of LCA
; splitting up files using this trick; now no need to pass in lca as a param; also instead of lca.lca(a, b)
syntax, it's now lca(a, b)
syntax
from kactl.
Related Issues (20)
- In whole Geometry section, there are no epsilon. HOT 1
- Interpolation Template
- Add finite state automaton to KMP
- Add wavelet tree HOT 2
- Replace Manacher with Eertree?
- Add Half-plane intersection? HOT 2
- General Matching has unnecessary factor of 8
- Can we have Lyndon Factorization
- Faster hashmap
- Make string hashing ARM-friendly HOT 1
- Beginner-friendliness of Lazy Segment Tree
- Wrong Time Complexity for MinCostMaxFlow HOT 1
- dead link in mod mul
- Lazy segment tree is difficult to modify for other operations HOT 3
- Simplification of "rotate" implementation for splay HOT 1
- make euler walk return edge indexes by default HOT 1
- Factor.h can be hacked HOT 3
- Typedef is outdated
- outdated comment
- run tests with runtime debug flags HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from kactl.