Meta Hacker Cup Round 3

3 недели назад, # ^ |

Top 2k in round 2 will get shirts, they just won't have a "Top 200" badge on them.

→ Ответить

akkafakka

3 недели назад, # |

Well I guess time travel is possible nowadays.

→ Ответить

majk

3 недели назад, # |

+159

Problem E is one of the best joke statements I've seen. A brilliant idea to use the name of Dijkstra!

→ Ответить

3 недели назад, # ^ |

+33

I'm glad you like it :)

→ Ответить

3 недели назад, # ^ |

+28

Agreed! Though I am confused why anyone went for E2 given its point value.

→ Ответить

3 недели назад, # ^ |

+20

The contest organizers had some interesting thoughts about E's value and strategy. If the set is easy and likely to get solved, it would make a lot of sense to do E1/E2, that way your penalty gets significantly improved.

But if solving the set isn't important, then going after E instead of C or D wouldn't be too helpful; because of the double penalty. It's an interesting call you have to make early on in the contest.

→ Ответить

3 недели назад, # ^ |

← Rev. 2 →

+10

Makes sense. I reasoned after finishing E1 that I almost certainly wouldn't have the time to finish everything, so I ended up going for the larger point values.

Though I still think it's a bit strange how C = D = E1 + E2; IMO E1 + E2 should be worth more.

→ Ответить

3 недели назад, # ^ |

+20

I kinda get your point, but I am not the fan of the end result. Solving the whole set is very rarely required to get to the finals. Assuming it is not required, there are basically no advantages of going for E2. Doing so would be ""high risk ... no reward" situation. And even in the unlikely case that the whole set was required ... I think that E2 will still require a lot of effort, even having solving E1 before. I didn't try a lot to solve it, but I'd imagine that B and C were easier for me than E2 would have been

→ Ответить

3 недели назад, # ^ |

E2's existence obviously mattered even without anyone solving set. Without it, tourist wouldn't have qualified for finals, and with it, Errichto and ko_osaga probably would have.

"Assuming it is not required" is not reliable assumption to make given, for example, last year's results. If it were required, E2 likely would be the most important early-solve in the entire set.

The logical jump between E1 and E2 is IMO not too large. It's especially easy to stumble across if you already have a bruteforcer for E1 and look at linked lists. Contestants seemed to have proven us right that it was easier than D. Perhaps the judges overestimated the difficulty of the calculus in C, but at large I think the point distribution makes a lot of sense actually.

If you disagree, vote with the problems you choose to solve (like Benq did). Either you'll be right and perform really well because of it, or you'll learn why you were wrong.

→ Ответить

ExplodingFreeze

3 недели назад, # |

+27

FST fiesta incoming, A's validation cases don't check $$$k = 3$$$ and E1 has $$$5$$$ validation cases for a YES / NO problem lol (where I'm pretty sure 3 are the direct samples).

→ Ответить

Umi

3 недели назад, # |

+25

Thanks for the weak pretest, I thought I wasn't gonna get a top 200 this year xdd

→ Ответить

dario2994

3 недели назад, # |

+55

After the contest I felt quite happy, as I had enjoyed competing. Then I looked at the scoreboard.

In any case, thanks to the organizers!

→ Ответить

antiMathforces

3 недели назад, # |

So are weak pretests in MHC now going to become a thing? Asking for the next year and future version.

→ Ответить

aryanc403

3 недели назад, # ^ |

There is a reason why they say validation input rather than pretests.
These tests exist to just ensure one's output file format is correct.

→ Ответить

wery0

3 недели назад, # |

Solved D 12 minutes after the contest ended...

→ Ответить

Tlatoani

3 недели назад, # ^ |

2 minutes in my case lol

→ Ответить

hxu10

3 недели назад, # |

← Rev. 4 →

Good news: I didn't failed system test this time.

Bad news: I only solve problem A. (And FST only make my ranking drop from 296 to 303)

So saddddd.

→ Ответить

cry

3 недели назад, # ^ |

I FSTed both A and E1, and my B code RTEd on main tests. gg

→ Ответить

Yawp

10 дней назад, # ^ |

fire matchach pfp

→ Ответить

jonathanirvings

3 недели назад, # |

+15

What manually submitting 50+ submissions for B did to my Downloads folder

→ Ответить

mQfZ

3 недели назад, # |

I was doing so well on C until Wolfram Alpha told me to use a digamma function ... Tragic.

→ Ответить

HIR180

3 недели назад, # |

+10

Are all the correct and incorrect results true now (except for the penalty calculation) ?

→ Ответить

3 недели назад, # ^ |

+36

They are correct, and penalty is correct. We might DQ some people for plagiarism, but usually there's not too much of that.

→ Ответить

HIR180

3 недели назад, # ^ |

Thank you for your prompt reply!

→ Ответить

adamant

3 недели назад, # |

← Rev. 3 →

+33

Ah, I solved B and C, but in B I stupidly did return {set, map} instead of return {move(set), move(map)}, and in C I relied on boost::math::digamma to compute the sum of $$$\frac{1}{A+Bk}$$$ over $$$k$$$ from $$$L$$$ to $$$R$$$, but it turned out to be not precise enough (produces relative error of $$$8 \cdot 10^{-6}$$$). Sadge, two avoidable things landed me 17 places away from a better t-shirt :(

UPD: The bug in C was actually because I only checked $$$D$$$ up to $$$100$$$ instead of up to $$$101$$$. I guess I feel somewhat better now, knowing that it was not a precision issue.

→ Ответить

akshaykhandelwal

3 недели назад, # |

+10

What is special with p=0 in problem C?

→ Ответить

Egor.Lifar

3 недели назад, # ^ |

← Rev. 3 →

-10

Oh, yes, I mixed up which part(prefix or suffix) I need to approximate using integral.

Sorry for the inconvenience.

→ Ответить

harsh__h

3 недели назад, # ^ |

← Rev. 2 →

+18

Maybe you missed taking this factor into account. I did the same mistake.

→ Ответить

Egor.Lifar

3 недели назад, # ^ |

I had a different typo, but thank you for mentioning this.

In my approximation I do not need to consider Euler's constant.

→ Ответить

3 недели назад, # ^ |

-12

With that, you claim that your solution is correct, while tens of other contestants who got ACs, actually have wrong answers. And not just that, but all of their answers have relative error from a peculiar interval of $$$[10^{-2} - 10^{-6}, 10^{-2} + 10^{-6}]$$$! I don't think that passes sanity check :)

→ Ответить

Egor.Lifar

3 недели назад, # ^ |

First, I've never claimed that my solution is correct, only that I struggle to find what is wrong.

Second, I was more curious whether Jury knows how to calculate the exact answer somehow, as in the editorial the approximation is mentioned to be "good enough".

Third, last round 95% of submissions failed hidden tests for B, so this scenario(that somehow everybody used the same wrong approximation) is not completely improbable in this type of competition.

→ Ответить

3 недели назад, # ^ |

-12

Okk, I'll treat this as a miscommunication then :p

→ Ответить

3 недели назад, # ^ |

← Rev. 3 →

+10

I was more curious whether Jury knows how to calculate the exact answer somehow

By running an O(N) DP for a loooooong time :)

→ Ответить

woruo27

3 недели назад, # |

← Rev. 3 →

+39

I solved E because I have read this paper: Incorrect implementations of the Floyd--Warshall algorithm give correct solutions after three repeats.

→ Ответить

3 недели назад, # |

+18

What was the issue with B?

→ Ответить

3 недели назад, # ^ |

We're still looking into it. There's nothing fundamentally interesting about the I/O compared to other problems. It has a large input file, but so do other problems, and that doesn't affect uploading the output of course.

Interestingly, the judges had no issue making any of the submissions, and it's the same mechanism under the hood for judges and contestants.

→ Ответить

3 недели назад, # ^ |

← Rev. 7 →

+11

Also on the subject of problem B, I'm curious why there was no test nearing max depth (e.g., a line of length $$$3\cdot 10^6$$$).

I was testing locally before downloading the full test set and noticed that my recursive DFS solution compiled with homebrew GCC would give a runtime error on a line of size $$$3\cdot 10^6$$$ (though it passes on a line of size $$$2\cdot 10^6$$$, or if I switch to clang ...). Anyway, I rewrote my solution to remove the recursive DFS.

(On that note, does anyone know how to increase the stack size limit on Mac past 512 MB?)

→ Ответить

3 недели назад, # ^ |

Oh, that is indeed an oversight. One of the large cases was meant to be such a long line. I see where I've gone wrong in my data generator. I validated a variety of other properties, but not the actual depth.

→ Ответить

Lucina

3 недели назад, # ^ |

Idk if this only happened to me, but I had to redownload input for 5 times. After that I couldn't create submission and got repetitive error responses. (Probably, I requested too much download) Then, the timer expired and I sent my output and code to clar within a minute and they made a submission for me.

It's weird that I could attach and send my submission in clar just fine, but not problem B.

→ Ответить

YaoBIG

3 недели назад, # ^ |

I also had the same submission issue... Judges also helped me created a submission, which is pretty nice :)

→ Ответить

hos.lyric

3 недели назад, # |

← Rev. 2 →

+141

Thanks for the round! I was (luckily) just right about how careful I should be.

It was evident that A and E1 have "weak" validation if we download them (before solving). What was not evident for me is C's weakness (the case where you use the 100% option with large $$$N$$$, or where the strategy borderline comes at an integer). I was rescued by stress testing for all of them...

By the way my directory and my brain messed up by downloading validation inputs before solving and caring about the problem titles. Perhaps this has been raised before, but I was wondering if the organizers could attach problem ID as a prefix to input file names (like A- or E1_).

→ Ответить

3 недели назад, # ^ |

← Rev. 2 →

+26

Perhaps this has been raised before, but I was wondering if the organizers could attach problem ID as a prefix to input file names (like A- or E1_).

Agree that this would be nice. I always end up having to rename the files manually (e.g., E1_val.txt, E1_act.txt).

→ Ответить

3 недели назад, # ^ |

+23

I definitely support that suggestion!

→ Ответить

MisterReaper

3 недели назад, # |

← Rev. 2 →

+34

Sad for jiangly. I wanted to see him in the finals.

→ Ответить

jeroenodb

3 недели назад, # |

+30

How were the "ground truth" answers found in problem C?

→ Ответить

3 недели назад, # ^ |

← Rev. 2 →

+10

You can use

to compute the answer exactly (up to floating point precision).

→ Ответить

3 недели назад, # |

I wonder if the setter of problem C played Danganronpa... Literally the same setting is implemented as a "mini-game" there, except for the fact that the formulas are different there, so that it's always optimal to pay 1 dollar...

→ Ответить

3 недели назад, # ^ |

Ooo, I've played the first Danganronpa, but I don't remember such a minigame. Maybe it wasn't in the first one, or (more likely) maybe I've forgotten since then.

What I had in mind when writing this problem was the Super Smash Bros. Melee lottery machine

→ Ответить

arvindf232

3 недели назад, # |

← Rev. 2 →

+24

Somehow problem D went relatively untouched. Putting aside the issue that me and PurpleCrayon both cheesed through with (slightly carefully implemeneted) $$$O(n^2)$$$, the actual solution is only one tiny observation away. With all the precisions with C and weak pretests with E, D is the easiest problem by expected value it seems. I got into finals basically by getting the free D plus very fast (+correct) A and B.

I didn't have the foresight to actually go for D though. I am just forced to do that by standings. After messing up on C, I can only get top 25 by D as E1+E2 would not give enough penalty.

I also thought that I would only ever have enough time to implement it if I went for the $$$O(n^2)$$$. This turns out to be false.

→ Ответить

pkhaustov

3 недели назад, # ^ |

Unfortunately, there was no way for me to beat properly optimized $$$O(N^{2})$$$ solutions with only ~70MB of input data in total. But I agree that having such a solution required having all the observations in place, only the data structure to perform it with better complexity could be the missing part. I even had multiple solutions that are $$$O(N^{2})$$$ and use most of the obervations, but are not optimized enough and those worked for approximately 10 minutes on my machine. I wonder if anyone expected the data structure in the model solution to be SQRT-decomposition though.

→ Ответить

3 недели назад, # ^ |

← Rev. 5 →

Hm, I'm looking at arvindf232's solution and it doesn't look like it requires any observations? It clearly does proportional to $$$N\times M$$$ operations per test. I assume "slightly careful" refers to improving the constant factor (e.g., by removing modulus operations) and doing the DP in HLD order so that the memory usage is $$$O(N + M\log N)$$$.

Tried it in C++ just now and it took just under 6 minutes with multithreading. Though I had to rewrite the DFS to get around the stack size limit of 512MB on Mac (anyone know a way to increase this?).

benjaminqi:Desktop % g++-14 -std=c++17 -O2 -Wl,-stack_size,30000000 D_threaded.cpp 
ld: -stack_size must be <= 512MB on arm64 platforms

Code (Less efficient, but same time complexity as below)

void solve(int tc) {
	cerr << "Doing TC #" << tc << endl;
	dbg(time_elapsed());
	def(int, N, M);
	vi A(N + 1);
	FOR(i, 1, N + 1) re(A.at(i));
	V<vi> adj(N + 1);
	rep(N - 1) {
		def(int, u, v);
		adj.at(u).pb(v), adj.at(v).pb(u);
	}
	ll ans = 0;
	const ll MODMOD = (ll)MOD * MOD;
	y_combinator([&](auto dfs, int x, int p) -> vl {
		vl ret;
		for (int c : adj.at(x))
			if (c != p) {
				auto ret2 = dfs(c, x);
				if (!sz(ret)) swap(ret, ret2);
				else {
					assert(sz(ret) == sz(ret2));
					F0R(i, sz(ret)) ckmin(ret[i], ret2[i]);
				}
			}
		if (!sz(ret)) ret = vl(M + 1);
		R0F(i, sz(ret) - 1) ckmax(ret[i + 1], ret[i] + A[x]);
		each(t, ret) {
			ans += t;
			if (ans >= MODMOD) ans -= MODMOD;
		}
		return ret;
	})(1, 0);
	ans %= MOD;
	ps(ans);
}

Code (More efficient)

struct Solution {  // update per problem
	int N, M;
	vi A;
	V<vi> adj;
	Solution() {  // init and read input
		dbg(time_elapsed());
		re(N, M);
		A.rsz(N + 1);
		FOR(i, 1, N + 1) re(A.at(i));
		adj = V<vi>(N + 1);
		rep(N - 1) {
			def(int, u, v);
			adj.at(u).pb(v), adj.at(v).pb(u);
		}
	}
	void solve(stringstream &os) {  // solve and write answer to os
		vi sub_size(N + 1);
		{
			vpi stk;
			stk.pb({1, 0});
			while (sz(stk)) {
				auto [x, adj_idx] = stk.bk;
				if (adj_idx == 0) sub_size.at(x) = 1;
				if (adj_idx == sz(adj.at(x))) {
					stk.pop_back();
					if (sz(stk)) sub_size.at(stk.bk.f) += sub_size.at(x);
					continue;
				}
				int y = adj.at(x).at(adj_idx);
				++stk.bk.s;
				if (!sub_size.at(y)) stk.pb({y, 0});
			}
		}
		// y_combinator([&](auto dfs, int x, int p) -> void {
		// 	sub_size.at(x) = 1;
		// 	for (int y : adj.at(x))
		// 		if (y != p) {
		// 			dfs(y, x);
		// 			sub_size.at(x) += sub_size.at(y);
		// 		}
		// })(1, 0);
		// ^ this exceeds stack size limit ...
		assert(sub_size.at(1) == N);
		ll ans = 0;
		ll MODMOD = (ll)MOD * MOD;
		y_combinator([&](auto dfs, int orig, int depth) -> vl {
			assert(depth <= 20);
			vi heavy_chain{orig};
			while (true) {
				int x = heavy_chain.bk;
				int heavy_child = -1;
				for (int c : adj.at(x))
					if (sub_size.at(c) < sub_size.at(x))
						if (heavy_child == -1 ||
						    sub_size.at(c) > sub_size.at(heavy_child))
							heavy_child = c;
				if (heavy_child == -1) break;
				heavy_chain.pb(heavy_child);
			}
			vl ret(M + 1);
			R0F(i, sz(heavy_chain)) {
				int x = heavy_chain.at(i);
				for (int c : adj.at(x))
					if (c != (i + 1 == sz(heavy_chain)
					              ? -1
					              : heavy_chain.at(i + 1)) &&
					    sub_size.at(c) < sub_size.at(x)) {
						auto ret2 = dfs(c, depth + 1);
						assert(sz(ret) == sz(ret2));
						F0R(i, sz(ret)) ckmin(ret[i], ret2[i]);
					}
				R0F(i, sz(ret) - 1) ckmax(ret[i + 1], ret[i] + A[x]);
				for (auto t : ret) {
					ans += t;
					if (ans >= MODMOD) ans -= MODMOD;
				}
			}
			return ret;
		})(1, 0);
		ans %= MOD;
		os << ans;
	}
};

→ Ответить

arvindf232

3 недели назад, # ^ |

+10

It doesn’t, but I thought the only observation after that is just the “key observation” as in the tutorial, and it doesn’t seem to be particularly hard to find.

I am saying “carefully Implemented” just as a caution since, I see a few people attempted to download data but cannot make a submission, and I am guessing this might have been what happened.

It is also totally trivial to do O(n) memory total if you only keep upto the height of the vertex, alongside an easy factor of 2 improvement. I didn’t end up doing so as I believe it is already fast enough to pass, after knowing a max case would run in 1.2 minutes.

→ Ответить

3 недели назад, # ^ |

← Rev. 3 →

it doesn’t seem to be particularly hard to find.

I agree — I'm surprised that my solve was the only "legitimate" one. I thought my $$$O(N\log M)$$$ implementation was quite clean, though as evidenced both above and below it seems that many others got caught up in implementation issues.

→ Ответить

ko_osaga

3 недели назад, # ^ |

I would've probably tried $$$O(n^2)$$$ if I ran out of time because I literally wrote it and verified it with pretests. What happened instead is that I was able to optimize it to $$$O(n \log n)$$$, along with some stupid bugs that took ages to find :(

→ Ответить

3 недели назад, # |

← Rev. 2 →

Might be skill issue but B stack overflows up to N = 300000 (1/10 the biggest tc) on my mac with whatever tricks I find online. Ended up spending 30+ minutes getting my school's clusters to work.. Anyone get it to run on mac?

→ Ответить

https://codeforces.me/blog/entry/134678?#comment-1204701

3 недели назад, # ^ |

← Rev. 4 →

Are you compiling with -Wl,-stack_size,20000000 as mentioned here? It will increase the stack size limit to 512MB.

That being said, 512MB is not always enough (see my comments above) and idk how to increase further. If you are near the stack size limit and don't want to change any code, you can try switching from GCC to clang or vice versa.

→ Ответить

3 недели назад, # ^ |

That's exactly the post I tried. I got the same error as you post above when compiling with -Wl,-stack_size,20000000.

→ Ответить

3 недели назад, # ^ |

Can you share your code?

→ Ответить

3 недели назад, # ^ |

Made a random subission: 289708610

→ Ответить

3 недели назад, # ^ |

← Rev. 4 →

Tried running locally on the full data, as well as the $$$N=3\cdot 10^6$$$ line I constructed, and it finishes successfully.

g++-14 -std=c++17 -O2 -Wl,-stack_size,20000000 B.cpp -o B && ./B < Bact.txt

About my Mac in case it matters:

14-inch, 2023
Chip: Apple M2 Pro
Memory: 16GB

→ Ответить

3 недели назад, # ^ |

← Rev. 3 →

Are you sure it is stack overflow? The trees in the full data aren't particularly deep, so even if you don't increase stack size past the default it should pass.

Can you include the exact error are you getting?

→ Ответить

3 недели назад, # ^ |

← Rev. 2 →

Thanks for running my code btw.

To clarify I get stack overflow on mine extreme tc when the tree is a chain. Therefore, I didn't even bother running locally the full data during the contest. However, it turns out the full data has max depth < 9000, so when I run it just now it passed. I guess that explained why nobody else mentioned stack overflow for B.

It's weird though so many people FST'ed other problems but the full data for B is weak in this sense.

→ Ответить

-0.00

3 недели назад, # |

+23

t shirt designs reveal pls SecondThread

/\____/\
꒰ ˶• ༝ — ˶꒱
./づᡕᠵ᠊ᡃ࡚ࠢ࠘ ⸝່ࠡࠣ᠊߯᠆ࠣ࠘ᡁࠣ࠘᠊᠊°.~♡︎

→ Ответить

ScorpioDagger

3 недели назад, # |

FSTed on round 3 — A.

How about a top 500 badge on the shirt for those who managed to qualify to round 3?

→ Ответить

ecnerwala

3 недели назад, # |

+94

What's the correct answer to the 6th sample in problem C? The sample statement says $$$2.203697500670872 \times 10^{10}$$$, but Wolfram Alpha seems to evaluate to something smaller by relative error of $$$\approx 2 \times 10^{-8}$$$, which is quite large.

I believe the formula is

$$$ \displaystyle \sum_{i=1}^{3052126200} 3 \cdot \frac{9988776655 * 100}{i * (100 - (3-1) * 44) + 9988776655 * ((3-1) * 44)} + \sum_{i=3052126201}^{ 9988776655 } 1 \cdot \frac{9988776655}{i} $$$

I evaluated the sums with Wolfram Alpha and it adds up to $$$2.2036974638794566727721073889157678558271191858 \times 10^{10}$$$.

→ Ответить

Wielomian

3 недели назад, # ^ |

Sorry for changing the topic but you surprised me with the "6th sample". I always assumed that MHC has randomized tests that come from a larger pool, selected by some hash for each contestant individually to prevent cheating with multiple accounts (downloading datasets from burnable account, running some bruteforce for like an hour, and submitting from main account within 6 minutes). It seems that's not true then?

→ Ответить

pkhaustov

3 недели назад, # ^ |

+26

Validation input is the same for everyone. Although, full input is randomized.

→ Ответить

Wielomian

3 недели назад, # ^ |

← Rev. 2 →

Okay, this makes a lot of sense actually, since randomizing validation inputs could give more lucky contestants an unfair edge if they got some corner case to a validation set by chance. And also would enable a cheater to sample the testcase pool by requesting validation inputs from burnable accounts (though this would be much more cumbersome compared to everyone having the same full input)

→ Ответить

3 недели назад, # ^ |

← Rev. 2 →

+10

The O(N) DP that I used to compute the "ground truth" answers can indeed have some errors up to about 2e-8. We made the judger slightly more lenient to account for this.

→ Ответить

ecnerwala

3 недели назад, # ^ |

+28

You can get extremely accurate estimates of harmonic sums using the Euler-Maclaurin formulas. The first few terms give:

$$$ \displaystyle \sum_{i=a}^{b} \frac{1}{i} = \log(b) - \log(a) + \frac{1}{2}\left( \frac{1}{a} + \frac{1}{b} \right) + \frac{1}{12} \left(\frac{1}{a^2} - \frac{1}{b^2}\right) + O\left(\frac{1}{a^4}\right) $$$

with analogous formulas for the linear-progression case.

In general, I think it's pretty misleading to give so many digits of the sample output that aren't even correct. I know strictly speaking this is a possible correct answer, but for floating point in particular, the sample output really should allow people to accurately check their precision.

→ Ответить