Skip to content

Add virtual trees article and tests #1433

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Closed
wants to merge 1 commit into from

Conversation

spike1236
Copy link

No description provided.

@mhayter
Copy link
Contributor

mhayter commented Mar 27, 2025

Thanks for your article! This is a little out of my expertise so I usually defer to more senior people for article publishing like @adamant-pwn or @jakobkogler. With that, in the next few days I hope to give you at least some feedback.

For now, the README.md will need to be updated.

@spike1236
Copy link
Author

spike1236 commented Mar 28, 2025

Sure, glad to help!

@mhayter
Copy link
Contributor

mhayter commented Apr 10, 2025

Some super quick feedback:

Please add prerequisites with links to our articles if possible. This is an advanced topic so people who don't know binary lifting, dp, etc. don't really need to read this article.

What is an induced graph? It's not defined and I've gone to university for CS and don't know lol.

What is dfs order? Is it preorder, postorder, in order, level order? I'm not familiar with this term.

The article is quite similar to the editorial for the stated problem on atcoder (https://atcoder.jp/contests/abc340/editorial/9256) Are you the author of the editorial or are you just slightly rewording things? At the very least, it seems significant credit and/or citation should be given I think.

Question to @adamant-pwn :Is posting a problem and solving it so specifically allowed?
I mean some problems are so generic as to not be proprietary, but this one seems quite specific. Again, assuming it's ok, I'd probably like quotes and a reference to atcoder (like an official citation in university).

A visual of what a virtual tree is or does would be nice. I'd prefer an original otherwise I do feel we're getting into the realm of just linking to the tutorial.

I'm not sure we're using lambdas in C++ as they don't really carryover well with people who aren't familiar with them in other languages.

How were these comments generated? Some of them feel like chatgpt. They sometimes describe very obvious things but aren't descriptive enough on what's happening.

For instance, "// DP transitions: combining current state with result from subtree

int nxt0 = (dp[v][0] + sum[to]) % MOD;
int nxt1 = ((dp[v][0] + dp[v][1]) * 1ll * sum[to] % MOD + dp[v][1]) % MOD;
dp[v][0] = nxt0;
dp[v][1] = nxt1;"

This is is sort of obvious, but what isn't is why they're be in added in the way that they are. I'm also not sure why the 'ntx0' and 'nxt1' variables exist.

Also would prefer 'col' to be 'color' and be consistent with underscore ( 'get_lca').

****** Please make sure the code compiles some constants are not defined ******

Please add the update the README.md as well.

More feedback will likely be coming.

@spike1236
Copy link
Author

Surely, the prereqs will be added.
Yes, mostly this is just a fork of editorial by original author, Nyaan (I mentioned them at my cf blog but seems like when I added problems here I accidentally removed them from md).
Code comments are mostly chatgpt generated. I didn't care much about the dp calculation part since it's more related to the stated problem itself and is independent of virtual trees, such calculation can be done on any other dp problem.
Induced graphs are simply graphs generated by choosing some vertex subset and corresponding edges between them; I thought it was a popular term. Will rewrite it
Same goes for dfs order, and I agree I should state which order exactly.
Regarding code, I referred to segment tree testing suits so that's why I don't declare constants in the main code; rather, I declare them in tests. If they need to be declared in the main code, I can surely change the code accordingly.

@mhayter
Copy link
Contributor

mhayter commented Apr 10, 2025

I admire your honesty.

With that said, are you the author of this article or is Nyaan and ChatGPT?

Do you have permission from him? I'm not sure on the terms of service of atcoder is but it really seems like Nyaan should be submitting this article given is extreme similarity to the original editorial.

@spike1236
Copy link
Author

spike1236 commented Apr 10, 2025

I mean... in no way did I say this is my article or I'm the author. I just wanted to share it since it was posted on the free and open platform for everyone. This is why I wrote this is fork. Moreover, this is why I attached exactly that Atcoder problem for analysis. This is how I first learnt about this idea.
If you expect Nyaan to submit this article, no problem.

@spike1236 spike1236 closed this Apr 10, 2025
github-actions bot added a commit that referenced this pull request Apr 10, 2025
@mhayter
Copy link
Contributor

mhayter commented Apr 10, 2025

Perhaps there's misunderstanding. Articles not translated from the original website are assumed to be written by the author. You will be credited on the website as an author (look at the bottom of the articles.)

@adamant-pwn
Copy link
Member

We have the text in the footer: "Text is available under the Creative Commons Attribution Share Alike 4.0 International License". Anything that is added to the website should generally conform to the license. With translations of e-maxx.ru it is OK because Maksim dedicated his articles to the public domain.

For anything else, it must either be created by the person contributing the article, or the original content must be also licensed under CC BY-SA 4.0 or compatible license, and even then any contribution should be appropriately attributed to the original author in the text.

@spike1236
Copy link
Author

ok sir

@mhayter
Copy link
Contributor

mhayter commented Apr 10, 2025

@adamant-pwn So we can't cite problems that are public domain or CC license?

@adamant-pwn
Copy link
Member

We can't word-for-word copy them. Rewording in our terms is fine. Also when the material is very short and technical, it can be sometimes argued that it doesn't pass originality / creativity threshold and is thus not copyrightable.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

3 participants