Meta Hacker Cup Round 3
Round 3 is upon us! Round 3 begins in under 24 hours on the Hacker Cup site. We hope to see you there after Round 984!
As in previous years:
- To qualify for the human track of Round 3, you must have finished within the top 500 of Round 2.
- To qualify for the Finals Round, you must have finished within the top 25 of Round 3.
- For those competing in the human track, the top 200 placing participants have a special badge on their shirt.
Good morning, have fun, and we hope to see you on the scoreboard! Head on over after Codeforces Round 979, and be careful not to make any algorithms mistakes!
That's fantastic! I think it will be funny.
Has T-shirts for round 2 been released yet?
What about the T-shirts for the top 2000 in round 2??
Top 2k in round 2 will get shirts, they just won't have a "Top 200" badge on them.
Well I guess time travel is possible nowadays.
Problem E is one of the best joke statements I've seen. A brilliant idea to use the name of Dijkstra!
I'm glad you like it :)
Agreed! Though I am confused why anyone went for E2 given its point value.
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.
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.
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
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.
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).
Thanks for the weak pretest, I thought I wasn't gonna get a top 200 this year xdd
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!
So are weak pretests in MHC now going to become a thing? Asking for the next year and future version.
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.
Solved D 12 minutes after the contest ended...
2 minutes in my case lol
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.
I FSTed both A and E1, and my B code RTEd on main tests. gg
What manually submitting 50+ submissions for B did to my Downloads folder
I was doing so well on C until Wolfram Alpha told me to use a digamma function ... Tragic.
Are all the correct and incorrect results true now (except for the penalty calculation) ?
They are correct, and penalty is correct. We might DQ some people for plagiarism, but usually there's not too much of that.
Thank you for your prompt reply!
Ah, I solved B and C, but in B I stupidly did
return {set, map}instead ofreturn {move(set), move(map)}, and in C I relied onboost::math::digammato 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.
What is special with p=0 in problem C?
Oh, yes, I mixed up which part(prefix or suffix) I need to approximate using integral.
Sorry for the inconvenience.
Maybe you missed taking this factor into account. I did the same mistake.
I had a different typo, but thank you for mentioning this.
In my approximation I do not need to consider Euler's constant.
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 :)
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.
Okk, I'll treat this as a miscommunication then :p
By running an O(N) DP for a loooooong time :)
I solved E because I have read this paper: Incorrect implementations of the Floyd--Warshall algorithm give correct solutions after three repeats.
What was the issue with B?
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.
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?)
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.
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.
I also had the same submission issue... Judges also helped me created a submission, which is pretty nice :)
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-orE1_).Agree that this would be nice. I always end up having to rename the files manually (e.g., E1_val.txt, E1_act.txt).
I definitely support that suggestion!
Sad for jiangly. I wanted to see him in the finals.
How were the "ground truth" answers found in problem C?
You can use
to compute the answer exactly (up to floating point precision).
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...
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
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.
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.
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?).
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.
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.
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 :(
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?
Are you compiling with
-Wl,-stack_size,20000000as mentioned here? It will increase the stack size limit to 512MB.https://codeforces.me/blog/entry/134678?#comment-1204701
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.
That's exactly the post I tried. I got the same error as you post above when compiling with
-Wl,-stack_size,20000000.Can you share your code?
Made a random subission: 289708610
Tried running locally on the full data, as well as the $$$N=3\cdot 10^6$$$ line I constructed, and it finishes successfully.
About my Mac in case it matters:
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?
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.
t shirt designs reveal pls SecondThread
/\____/\
꒰ ˶• ༝ — ˶꒱
./づᡕᠵ᠊ᡃ࡚ࠢ࠘ ⸝່ࠡࠣ᠊߯᠆ࠣ࠘ᡁࠣ࠘᠊᠊°.~♡︎
FSTed on round 3 — A.
How about a top 500 badge on the shirt for those who managed to qualify to round 3?
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
I evaluated the sums with Wolfram Alpha and it adds up to $$$2.2036974638794566727721073889157678558271191858 \times 10^{10}$$$.
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?
Validation input is the same for everyone. Although, full input is randomized.
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)
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.
You can get extremely accurate estimates of harmonic sums using the Euler-Maclaurin formulas. The first few terms give:
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.
Thanks for the feedback -- with the approach that I took, it would've been worth using BigDecimal or similar to ensure the full 15 digits of precision.
I have upsolved problem D with a $$$O(nm)$$$ complexity solution with $$$O(n)$$$ memory, it runs in about a minute on my laptop for the dataset you can download in the practice. (I used multithreading)
i think facebuk forgor about the tshirt