### LoneFox's blog

By LoneFox, history, 2 weeks ago,

Round 1 of the 2021 Facebook Hacker Cup is less than 48 hours away!

The round will begin on September 11th, 2021 at 10am PDT and will last for 24 hours. The contest can be found here.

You're eligible to compete in Round 1 if you solved at least one problem correctly in the Qualification Round.

Everyone who scores at least 24 points (regardless of time taken) will advance to Round 2, which will take place on Sat. Sept. 25th. Please note that all submission judgments will only be revealed after the round ends. More details about rules and other information can be found in the FAQ.

We wish you the best of luck, and hope that you enjoy the contest!

• +134

 » 2 weeks ago, # |   +123 Good luck have fun, and see you all on the scoreboard!
 » 2 weeks ago, # |   +5 Can you please tell the scoring distribution
 » 2 weeks ago, # |   0 24 points out of 100?
•  » » 2 weeks ago, # ^ |   +3 From the past rounds I've looked at, it's usually out of 100, and for round 1 you usually need to have gotten AC on the first two problems to advance.
 » 2 weeks ago, # |   0 May be we will need to solve at least 2 problem to advance to Round 2;)
 » 2 weeks ago, # |   +5 24 points in 24 hrs!Nice :)
 » 13 days ago, # | ← Rev. 2 →   0 Am I the only one who get "This page isn't available" error when trying to access https://www.facebook.com/codingcompetitions/hacker-cup/2021/round-1? I got that error when logged in, but managed to load the page when in incognito.LoneFox can you help check on this issue?
•  » » 13 days ago, # ^ |   +8 It looks like you've been able to submit since. That may be some transient infrastructure issue.
 » 13 days ago, # |   0 Are there any prizes like T-shirts for this round?
•  » » 13 days ago, # ^ |   0 Only for round 2 onwards.
 » 13 days ago, # |   +9 How strong should we expect the "validation input" to be? Should we expect it to be similar to pretests on Codeforces?My understanding is that on Codeforces, authors aim to minimize FST, so they try to make pretests as strong as possible, as opposed to intentionally leaving max-size tests or tricky edge cases for systests (aka "full input" on Hacker Cup).
•  » » 13 days ago, # ^ |   +45 I think the easiest way to find out is to just look at the input, you can even instrument your code to measure coverage.
•  » » » 13 days ago, # ^ |   0 Good idea, I definitely should have looked more closely at the input. (Though it'd be hard to see if it has edge cases that I didn't think of while solving the problem.)LoneFox, my question is more about the authors' intent, if you know.
•  » » » 12 days ago, # ^ | ← Rev. 2 →   -189 You guys are walking on a thin ice. This kind of communication may be interpreted as assistance in solving/debugging problems from the running contest if you push this further. And my question about the scoreboard UI probably wasn't very appropriate either if we interpret contest rules literally. So I'm dropping out of here.Edit: As usual, there's no shortage of simple minded lemmings on codeforces :-) Come on, downvote me more! You will never understand that I just warned people BEFORE they crossed the line. Whether they would or wouldn't make an accidental mistake without this warning is another question. Better be safe than sorry.
•  » » » » 12 days ago, # ^ |   +64 I think the question is a good one. It's fine to ask about general things related to Hacker Cup at large.We typically want the validation input to prevent any possible misinterpretation of the problem, but we don't usually include a truly maximum case.
 » 13 days ago, # |   0 Is there any way to see the total number of problem B submissions done by the other participants during a running contest? Does the scoreboard page track this statistics in real time?
•  » » 12 days ago, # ^ |   +8 The scoreboard is realtime, though it doesn't show any summary stats like how many people have submitted for a given problem. You'd have to page through to get a rough estimate.
•  » » » 12 days ago, # ^ |   +6 Thanks! Are there any plans to implement summary stats? Before people start scraping web pages to automate this process and put an unnecessary burden on Facebook Hacker Cup servers.
•  » » » » 12 days ago, # ^ |   +3 We're indeed considering adding such a feature, either next year or possibly even this year.
 » 13 days ago, # |   +26 Where did the compressed input form go (i.e. used here last year)? The input was huge on C and I'm not sure if that's the reason my code started to segfault (I don't think I used too much memory nor time), but it sucks to pass validation and not be able to even submit on the real thing :\If the input size has no affect on that, then it's fine, but I was still a fan of that form of input.
•  » » 13 days ago, # ^ | ← Rev. 3 →   +5 The input size was quite small compared to a normal Codeforces problem, it's possible you ran out of stack space or something.
•  » » 12 days ago, # ^ |   +72 One of the reasons we added zip files this year was to avoid having you handle that relatively unpleasant format. Unfortunately the zip file for C has an issue that we're investigating. Once that's resolved, I do think the zip files are a much cleaner way of handling large input than making contestants generate the input on their own.
•  » » » 12 days ago, # ^ |   +23 What is the issue with the zip file for C? My program crashed on the judge input, and I only found out after the timer ran out that it was because the zip file had an "Unexpected end of data". Until now, I assumed that I didn't pay enough attention when downloading the file, but your comment makes me wonder.
•  » » » 11 days ago, # ^ |   0 Have you guys resolved this? Would it be possible to set up the encrypted-zip-file format in practice mode so we can test?
•  » » » » 11 days ago, # ^ |   0 We're still working on it. We know what the problem is and when it's fixed we'll be able to be quite confident through our own testing. I appreciate the offer though :D
•  » » » » » 11 days ago, # ^ |   +5 That sounds good, though I wanted to test my own decryption scripts as much as your system.
•  » » » » » » 11 days ago, # ^ |   +13 ಠ_ಠ
•  » » 12 days ago, # ^ |   +14 Input generation is terrible and it doesn't allow the test data to be as flexible as possible. I couldn't submit C too and I can guarantee with you that the input size is perfectly fine.
•  » » 12 days ago, # ^ |   +5 Hey, my C also Segfaulted on the real input, and I couldn't fix it in the 6 minutes. It turned out to be a stack usage problem, because when I set my stack to 200 MB with compiler flags, it ran fine.
•  » » 12 days ago, # ^ |   +46 Lol, you are probably the first person on planet Earth to advocate for compressed input format if there is an option to do it normally
•  » » 12 days ago, # ^ | ← Rev. 4 →   0 vkgainz I have faced the same problem earlier. I solved it by increasing the stack space limit. If you are on ubuntu, the command to increase stack size is ulimit -s desired_space(in KB). For example, if I want to set the stack space to 1GB, I would run ulimit -s 1048576 in the terminal.
•  » » 10 days ago, # ^ | ← Rev. 2 →   -10 I don't know if you solved your problem since, but my solution was actually crashing on a (slightly overloaded) DFS for the C, because of the stack size. When I switched to a native Linux (as opposed to WSL) and increased the stack size (using ulimit -s unlimited in the shell), there was no problem anymore.
 » 12 days ago, # |   -82 Your format of testing literally sucks.. I was not able to get output of large input file and time passed. It was due to stack size of my pc . Now what should one do if the pc limit is not that much. Buy new pc :( ? You should change your way of testing like Google CodeJam etc..
 » 12 days ago, # | ← Rev. 3 →   -26 [deleted]
 » 12 days ago, # | ← Rev. 3 →   -14 My pc wasn't responding when I tried to run the input for 1 problem and the time expired. Did it happened to anyone else too?
•  » » 11 days ago, # ^ |   +5 same even my pc crashed for A1 and B both and now i am out even after solving 2 questions
•  » » 11 days ago, # ^ |   +6 A common issue was people writing O(N^2) solutions to problem A when O(N) solutions are necessary. You won't be able to run an O(N^2) solution in 6 minutes when N = 800,000.
 » 12 days ago, # |   +22 Those who are using c++ and facing problem with stack size adding this "-Wl,--stack=268435456" compiler flag may help. I think facebook should reconsider their judging system as current system is extremely annoying.
•  » » 12 days ago, # ^ | ← Rev. 2 →   0 where to add , i have submitted the wrong output but then also Edit- i added inside the vs code terminal where flags like c++ , a.out and more like that are given its only taking time and no output is coming and on sublime its giving wrong
•  » » » 12 days ago, # ^ | ← Rev. 2 →   0 My cpp code runner (VS code extension) executor map in vscode "code-runner.executorMap": { "cpp": "cd $dir && g++ -DLOCAL -Wshadow -pedantic -Wall \"-Wl,--stack=268435456\" -Wextra -O2 -std=c++17$fileName -o $fileNameWithoutExt &&$dir$fileNameWithoutExt", },  » 12 days ago, # | -15 It is really annoying. I couldn't submit my A2 due to stack size of my laptop and it is not like I am using too much memory or time. Facebook should consider changing their judging system to something like what Codejam is using in the future. •  » » 12 days ago, # ^ | +62 It is really annoying when purples can't set stack size •  » » » 12 days ago, # ^ | 0 How to set up stack size on Windows , Sublime text 3 , MingW compiler ? •  » » » » 12 days ago, # ^ | +18 Add -Wl,-stack=268435456 to your build file.Here's how my C++.sublime-build looks { "cmd": ["g++.exe", "-Wl,-stack=268435456", "-std=c++17", "-DLOCAL", "${file}", "-o", "${file_base_name}.exe"], "shell": true, "working_dir": "$file_path", "selector": "source.cpp", }
•  » » » » » 12 days ago, # ^ |   +1 The size will be 256 MB ? What if I wanna make it 512 MB ?
•  » » » » » » 12 days ago, # ^ | ← Rev. 3 →   +11 Idk how to increase it further, I've never tried it. The stack size I mentioned is usually good enough.
•  » » » » 12 days ago, # ^ |   +1 or just use Linux.
•  » » » » » 12 days ago, # ^ |   +3 There is limit in Linux as well , u need to use a flag to make it unlimited
•  » » » 12 days ago, # ^ |   +27 Never needed it untill now. Lesson learnt. Will take care from next time onwards.Maybe next time on you should try helping people out with it rather than passing sarcastic comments. That is what the community is for I guess :)).
•  » » » » 12 days ago, # ^ |   -22 There was already a solution 2 comments above yours.Every year, every contest hundreds of people complain to the same issue (that they are unable to read comments).
•  » » » » » 12 days ago, # ^ |   +17 Yes we all suffer from the same problem don't we ( that people are unable to read comments).P.S : You should have read the reply to it.
•  » » » » » 12 days ago, # ^ | ← Rev. 2 →   +64 So, if every year hundreds of people complain (and i guess many others that don't complain publicly) about the same issue, maybe it could be considered to include these common problems in the FAQ? The FAQ already has "What do I need to compete?" as a question and mentions problems "line endings" and "online visibility". This could be expanded with/this could link to an technical FAQ with common problems for common languages/Compilers. Like stacksizes. Pinging LoneFox, are there some discussions in this direction? Or would this clutter the FAQ too much? SpoilerYes, I was a bit salty that my C failed because of this, although I tested beforehand with randomized $T \cdot N=8e6$, but its ok, since now I learned about this problem. Was still an unpleasant surprise.
•  » » » » » » 12 days ago, # ^ |   +8 Thanks for the suggestion, we'll definitely consider including such information in the FAQ.
•  » » » » » 12 days ago, # ^ | ← Rev. 2 →   -25 You are wrong , since I was the one replied to your comment , I read the comment above and also searched through old blogs on CF , but for Windows there wasnt a single comment or blog I found describing where to exactly add the flag , they just wrote add that flag .
•  » » » » » » 12 days ago, # ^ |   -22 You could notice that Codeforces itself doesn't have this issue and find the answer on the official technical information page.
•  » » 12 days ago, # ^ |   0 Really man , my timer got expired on problem A1 because i didn't declared the array globally so i got segmentation fault in my laptop and just after 6 mins i realised that. even though I solved A2 and B1 my rank would have been much better if not for that A1 :(
•  » » 11 days ago, # ^ |   +3 For the sake of completeness I'd like to note that GCC can kind-of auto-grow the stack if you specify the -fsplit-stack compiler flag, — see https://gcc.gnu.org/wiki/SplitStacks There's some overhead involved, of course.
 » 12 days ago, # |   0 Got my A2 validated, but got RTE on the main tests. Figured out it was because of the stack size as I declared the variables in my main function, only after the time passed.
•  » » 12 days ago, # ^ | ← Rev. 2 →   0 Same bruhhhhhh but for A1 , from now on i will declare all arrays and matrices in global scope :(
•  » » » 12 days ago, # ^ | ← Rev. 2 →   +18 Using vector would solve the problem. As you cant make large arrays in stack memory. So either use dynamic arrays or vectors (in c++) or global arrays. Dynamic allocation stores in heap memory in which you can take big size arrays. If I am wrong please correct me.
•  » » » » 12 days ago, # ^ |   0 You are right i will keep in mind this thing.
 » 12 days ago, # |   -23 same with me got validated on A2 but could not submit due to stack size of my pc as i got RTE on main tests. can something be done about it.
 » 12 days ago, # |   +13 I believe LoneFox had made problem 1 :)
 » 12 days ago, # |   +14 My pc too wasn't able to handle the input file as it exceeded the stack_limit. After the timer expired I realized what I could have done is declared all my variables globally. So those who have low end pc can try declaring the variables globally as it worked in my case although I couldn't submit. Hope this helps.
•  » » 12 days ago, # ^ |   0 same happened to me and also did a silly mistake on B. Should have waited for some time to revise the solution considering i am a newbie.
 » 12 days ago, # | ← Rev. 2 →   -8 i solved problem A1, A2 but i can't submit because input was very big, so i losted 24 point, and i give up because i only solved problem B extra(18point)
•  » » 12 days ago, # ^ |   0 You can tell in the clarification section about that issue
•  » » 12 days ago, # ^ |   -20 Does declaring all variables globally solves the problem of stack size?
•  » » » 12 days ago, # ^ |   +46 No
•  » » » 12 days ago, # ^ |   0 If using global variables reduces the number of recursive function arguments, then this reduces stack usage too. Sometimes this may be enough, but I wouldn't count on it. It's always safer to use gigantic 256M+ stacks with deep recursion.
 » 12 days ago, # |   -6 Sucks getting segmentation fault on A2 due to memory constraints and not setting up stack size. Anyways got to learn something now from this which I never paid attention to before
•  » » 12 days ago, # ^ |   -11 yes ! I think so !!! I couldn't submit my solved problem's solution code!
 » 12 days ago, # |   0 g++ -Wl,--stack=268435456 A2.cpp IS this correct ?
•  » » 12 days ago, # ^ |   +10 I had to do g++ -Wl,-stack_size -Wl,160000000 with Homebrew GCC on MacOS.I wish I knew this before, could not submit C in time due to this.
•  » » 12 days ago, # ^ |   0
 » 12 days ago, # |   0 If anyone is facing problem with cmd, then for codeblocks link
 » 12 days ago, # |   -8 How to solve that stack size problem in dev-c++
 » 12 days ago, # | ← Rev. 2 →   +3 My computer shut down and I couldn't submit A2 in time :( Me and my potato luck
•  » » 12 days ago, # ^ |   -78 LoneFox Sir, I ran code on Dev-C++ and A1 submitted successfully. But for A2 my code was correct but couldn't figure out how to set stack size in Dev-C++. Please give a chance to all those who did the 1st question, if you want I can send my source code for A2 to check my submission.
•  » » » 12 days ago, # ^ |   -79 Also LoneFox Sir, if you keep 10 points as criteria for qualifications than we will have 9000 selections out of 12,700 eliminating 3,700.And if you keep 24 points we will have around 7000 selections. I think giving a chance to people who didn't knew about stack size but had correct solution for A2 would definitely be a great move.
•  » » » » 12 days ago, # ^ |   0 If you see previous years, then only 2k participants qualify for round2. So, 42 should be kept as qualifying points.Anyway, B was much easier than A2 imo.
 » 12 days ago, # | ← Rev. 2 →   +22 It looks like 6,809 people advanced to the 2nd round. That's way more than usual.
•  » » 12 days ago, # ^ |   +8 The problems are much easier than I expected, feels like it's another Qualification round after all.
•  » » 12 days ago, # ^ |   +20 cutoff was too low, it should have been at least A1+A2+B1 imo
•  » » 12 days ago, # ^ |   0 Maybe this is the reason: https://codeforces.cc/blog/entry/94802
•  » » » 12 days ago, # ^ |   0 We do double check all similar solutions for plagiarism after the contest ends. If there were large groups of contestants using the same code structure, they will be DQ'd.
•  » » » » 10 days ago, # ^ |   +4 Is plag check done as I can see everyone with score >= 24 have been registered for round 2?
•  » » » » » 10 days ago, # ^ |   +3 I see this, so I think plag check is done.
•  » » » » » 9 days ago, # ^ |   0 Yep, we're done :)
•  » » » » » » 8 days ago, # ^ |   0 No solution was plagiarized
 » 12 days ago, # |   +3 Please, can stack size warning be put into FAQ? I remember this was an issue in the past which I fixed and then I got a new computer and forgot. Problem shouldn't be scored by who remembers best and has appropriate setup.(Side note: I guessed the issue immediately, then I found out you can't set stack size on windows subsystem for linux, goodbye C. Don't use WSL, instead use native g++.)
•  » » 12 days ago, # ^ |   0 You can set stack in WSL2 (you cannot in WSL1). Just do ulimit -s unlimited and it's gonna work. That's what I did. Also I feel like people should be prepared for this. It happens every single year. Especially if you hit it before.I hit it on a Round 3 and failed the B problem, and I knew it was only my fault I didn't prepare to have stack extra command up. So people should complain even less that it's happening on a round that only qualification matters.
•  » » » 12 days ago, # ^ |   -44 I was using WSL1 since 2 required more work to install. I forgot since it didn't happen to me last year. It should be reminded to participants in the FAQ instead of giving experienced users the unfair advantage. This should not be technicalforces or "I remember having the same issue 2 years ago"forces.
•  » » » » 12 days ago, # ^ |   +11 I disagree, preparation for FBHC matters, and this is one of the things you should prepare for: running your solution locally. Similarly how you have a library of pre-implemented things (that's where I store how to increase stack size for different environments). Secondly this complain is even less relevant, as I previously mentioned, considering it was on a round that everyone with >= 26 points qualifies. This happened to people on Round 3 (me for example), when actually every point matters.
•  » » » » » 12 days ago, # ^ |   -35 A warning to keep your limbs in the vehicle on an amusement park ride is not replaceable by a trial ride at 10 km/h where you will only get a laceration instead of an amputation
•  » » 12 days ago, # ^ |   +22 Putting it into FAQ would be surely useful. But the whole situation is really weird. People, who are supposed to be competent programers, happen to be unable to create programs that run correctly on their own computers! A wheelbarrow without a wheel.
•  » » » 12 days ago, # ^ |   -29 I don't think most of "competent programmers" can install new tools within 6 minutes, so this doesn't create a contradiction
•  » » » » 12 days ago, # ^ |   +10 Did you never test any of your recursive solutions with max constraints edge cases on your own computer when participating in other contests?
•  » » » » » 12 days ago, # ^ | ← Rev. 2 →   -6 I stopped doing that years ago, there's no meaningful algorithmic insight to learn from giant cases. I only do small cases and mental checks.
•  » » » » » » 11 days ago, # ^ |   +36 Isn’t “well, my code doesn’t crash or run incredibly slow” on max test a good enough insight?
•  » » 12 days ago, # ^ |   -16 You don't need a stack to solve it.
•  » » 11 days ago, # ^ |   +36 Just in case you don't want to deal with platform specific issues, there is a way to use allocate a custom stack on the heap, and use that for the duration of the program. I found this code in some comment quite a while back, and it works on Linux at least (it would be great if someone could confirm if it works on other platforms, although I would presume it to work on Windows/MacOS as well). To get a 1GB stack#include using namespace std; void main_() { int n; cin >> n; cout << n << '\n'; } static void run_with_stack_size(void (*func)(void), size_t stsize) { char *stack, *send; stack = (char *)malloc(stsize); send = stack + stsize - 16; send = (char *)((uintptr_t)send / 16 * 16); asm volatile( "mov %%rsp, (%0)\n" "mov %0, %%rsp\n" : : "r"(send)); func(); asm volatile("mov (%0), %%rsp\n" : : "r"(send)); free(stack); } int main() { run_with_stack_size(main_, 1024 * 1024 * 1024); return 0; } 
•  » » » 10 days ago, # ^ |   +5 It works like a charm on windows as well.
 » 12 days ago, # |   -13 Its really the most hurting moment when you are able to find out the logic of problem and able to code it also, but a single mistake (not putting MOD at the very end step) make your whole submission wrong.Happened today with me (in Problem A3)Takeaways: In problems, where we have to take mod , Don't forget to take the mod again at very last step also because putting extra mods will not create harm rather than missing single one.
•  » » 12 days ago, # ^ |   0 ...Or you could generate random maxtests to check wheither your solution processes them reasonably fast and then notice that the answer overflows. That was precisely my case with that problem.And, by the way, "always do not forget to test wheither maxtest processing fits in time limit" was my takeaway from another failed round (it's highly possible that was a FHC round).
•  » » » 12 days ago, # ^ |   0 Thanks for sharing experience:)How to generate random maxtests in given input format? Can you please provide me any sources...
•  » » » » 12 days ago, # ^ |   +1 Here are my solutions for A2 and A3. One can see that both contain testing functions.
•  » » 11 days ago, # ^ |   +1 There are a couple of ways you can avoid falling into this pit. If you look at lots of solutions from top competitors you'll see that they use a structure called 'Mint', on 'Mod_int', or something similar. The functions +, — etc are then re-defined according to modular definitions. This means you can't 'forget' to take the mod, as it happens automatically.My solution contains a similar idea, where I define operations add_, sub_, etc. I've pasted it here for you. I think the first way is probably neater but I developed this myself before I saw that and it works for me.
 » 12 days ago, # | ← Rev. 3 →   +5 I misread problem B and though the path lengths can be arbitrarily large, but you're limited to 1000 per cell. Does anyone have ideas on how to solve this problem with modified constraints?Like it's a bit weird since you can solve 4 4 7 5002 with: 1 1 1000 1000 1000 1 1 1000 1000 1000 1 1 1000 1000 1000 1 You can't solve 4 4 8 5003 (because the right path will just go through the 1s). same with 4 4 9 5003But you can actually solve 4 4 10 5003 1 2 1000 1000 1000 1 2 1000 1000 1000 1 2 1000 1000 1000 1 And also 4 4 11 5003 (just switch which numbers are 1 vs 2 in the left path).
•  » » 12 days ago, # ^ | ← Rev. 4 →   -42 .
•  » » » 12 days ago, # ^ |   +7 I'm asking how to solve the problem with the constrains modified
•  » » 12 days ago, # ^ | ← Rev. 2 →   -9 .
 » 12 days ago, # | ← Rev. 3 →   -11 .
 » 12 days ago, # |   +1 My O(N) space bottom up solution for A2.Also can be optimised to O(1) space easily Spoilertypedef long long int ll; ll P = 1e9 + 7; void solve() { ll n; cin >> n; ll ans = 0; string s; cin >> s; s = '#' + s; vector dp(n + 1); ll last = 0; for(ll i = 1; i <= n; i ++) { dp[i]=dp[i - 1]; if(s[i] == 'X' || s[i] == 'O') { if(s[last] == 'X' && s[i] == 'O') { dp[i] += last; dp[i] %= P; } if(s[last] == 'O' && s[i] == 'X') { dp[i] += last; dp[i] %= P; } last = i; } ans += dp[i]; ans %= P; } cout << ans << endl; } 
•  » » 12 days ago, # ^ |   0 hey could you please explain this?
•  » » » 11 days ago, # ^ |   0 Oh Thanks for reaching out. This dp[i] denotes the number of hand changes for all subarrays ending with position i. To compute this. if the current character is F we do not need to do any computation as no hand changes will be there on reaching to i from i — 1. remember dp[i-1] already have answer to all the subarrays ending with poistion i — 1. so in case current character is 'F' dp[i] = dp[ i — 1]. else if current character is 'X' and last non 'F' character is also 'X' then also we need not compute anything as dp[i — 1] already contains the moves.if current character is 'X' but the last non 'F' character is 'O' then for all subarrays which ended at last 'O' WE need to change the hand once thus adding the answer as index of 'O' which represents number of subarrays ending with 'O'.
 » 12 days ago, # |   +60 There's actually a solution to C which doesn't depend on the maximum capacity being small.As with the official solution, it's easier to compute, for each edge, how much the capacities would decrease if it were blocked. Let's sort the edges in decreasing weight and insert them into the tree one at a time. Consider an edge between $u$ and $v$ with weight $w$, and let the current sizes of the components containing $u$ and $v$ be $s_u$ and $s_v$. Then, for each edge $e$ already inserted into the component of $u$, we need to apply $\text{ans}[e] += \text{subtree_size}_u(e) * w * s_v$, where $\text{subtree_size}_u(e)$ means the current size of the subtree of $e$ when rooted at $u$. It turns out this can be modeled using lazy propagation on HLD or a top tree, as the answer is a linear function of the subtree size at any point.The top tree is a simpler interface, as we can reroot the tree by flipping the root path (this means that we need to store two lazy-increments, one assuming the root is leftwards, and one assuming the root is rightwards).The HLD solution is more complex, but has the same ideas. It's essentially equivalent to the top tree solution, where we follow each solution with a reroot to the original HLD root; that view can help inform which pieces you need after each update.At the end, we propagate all changes all the way down the tree to read out the answers.
•  » » 12 days ago, # ^ |   +114 I had no idea what top trees are and decided to look them up. According to Google, Penn State is very concerned about the dangerous environmental impact of a data structure this OP becoming common knowledge:
•  » » 5 days ago, # ^ |   0 ecnerwala Do you know of any tutorial for top tree?
•  » » » 5 days ago, # ^ |   +13 There might be one in Chinese, but probably not, because they're very overkill/advanced and are essentially never necessary. HLD will essentially always suffice. If you really want to learn top tree, learn Link-Cut Tree first; top tree is a (conceptually) straightforward extension. This paper describes the standard splay-tree-based implementation: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.87.9754&rep=rep1&type=pdfI might write a tutorial someday, but no promises on that. If I do, it'll still assume HLD knowledge beforehand, so focus on that at most.
•  » » » » 5 days ago, # ^ |   0 Awesome, thanks for the link.
•  » » 5 days ago, # ^ |   0 I fail to come up with the way to lazily propagate push to all nodes of a connected component in HLD. Usually what I would do is to just increase all values in a subtree, which is expressed as range addition. Can you provide some insight on that, please?
 » 12 days ago, # | ← Rev. 3 →   -8 How come there's a logarithm in the written analysis/editorial of problem $C: Blockchain$ ?Editorial proposed complexity: $O(N \times (\log(N) + maxC))$ My proposed time/space complexity (if you can call >1GB worth of stack use 'efficient', kappa)$O(N \times maxC) = O(N \times 20)$
•  » » 12 days ago, # ^ |   0 The official solutions suggested a traditional sort of the edges to seed the DSU at the beginning. O(N log N) -- Radix sort could have been used to get that down to N*maxC as well, but they didn't mention that.
•  » » » 12 days ago, # ^ |   0 The whole first paragraph in the solution is unnecessary. We can just compute that while we're computing $D_{i, j}$ anyway.
 » 12 days ago, # |   -40 whom should someone contact if he think that his output is correct but the judge has give wa verdict but that also only on 1 test case, the solution is exactly the same as given in the editorial and all the test cases are passing except 1. someone please help.
•  » » 12 days ago, # ^ |   +22 We're pretty confident that the judge data is correct. Not only do we have multiple independently-discovered judge solutions which have the same output, but we agree with lots of LGMs who participated in the contest, some using completely different approaches to any of the judge solutions too.If you disagree with the judge data on a case, please double check your solution first.
•  » » » 11 days ago, # ^ |   +23 yes it was my fault i used value >1000 in problem B which wasn't allowed. sorry for any inconvenience caused.
 » 12 days ago, # |   +6 I thought the problems were reasonably fun. Missed C due to a stupid error (was packing fields into an int64 to speed up python sorting, and now realized that 0x3ffff is only 18 bits and not 20 bits, so I missed the 800k inputs). I'll try to be more careful in round 2.
 » 11 days ago, # | ← Rev. 4 →   0 Hi, I got wrong solution on one test case for problem A2 and I am not able to understand why is it so ? Can someone help me understand why my output is wrong ? For test case: N(rows) = 50, M(columns) = 2, A = 70, B = 500My output - Possible 10 225 1 1 1000 1 (Repeat this row 47 times like below) 1000 1 ........... 226 11(last row) Official output - Possible 20 450 1 1 1 1(Repeat this row 47 times like below) 1 1 .... 1 1(last row) 
•  » » 11 days ago, # ^ | ← Rev. 2 →   0 In Your solution, B is coming out to be 510 but B should be 500 ,so imo your output is wrong. How B is 510 in your solution225+1+47+11+226 = 510
•  » » » 11 days ago, # ^ |   0 Thanks.
 » 11 days ago, # |   0 It is showing me not registered for round 2 even I scored 24 in round 1
•  » » 11 days ago, # ^ |   0 Will show after a few days..you will get a mail also
•  » » » 11 days ago, # ^ |   0 Ok thanks
 » 10 days ago, # |   0 Guys, just uploaded approach for problem A2, you can checkout here: https://youtu.be/HWv1FWrrMj0
 » 10 days ago, # | ← Rev. 3 →   0 LoneFox Can you clarify the presentation error issue? Whenever I try to submit for practice in Round1 I always get a presentation error. To investigate the issue, I downloaded the exact file that got AC for me during the contest and that too showed presentation error, which is really confusing! Imagine getting a presentation error after solving the whole problem correctly in the real contest!
•  » » 10 days ago, # ^ |   0 I don't know the exact reason but I want to share how I resolved this issue.You can see the template in any of my codes and notice that I use functions to input and output variables. For example, to output, the code is like this inline void op() { cout << '\n'; } template inline void op(T var1, Types... var2) { cout << var1 << ' '; op(var2...); } So what it does is that while outputting the last variable, it outputs like variable_value + space + '\n'. In codeforces and many other sites, this rarely gives me a problem(It only hampers me sometimes in very old questions as I think new checkers trim the white spaces or something, IDK), but sometimes it does WA's my code just due to this.So I just changed it to normal `cout<
•  » » 10 days ago, # ^ |   0 Okay, it's resolved, who would have thought that the final input of the problems gets changed!. During the contest, the final input files had different inputs and the final input files for practice submits are different!
 » 4 days ago, # | ← Rev. 2 →   +3 LoneFox In the scorecard of Round 1 many participants are named as Unknown Competitor. Is this a bug or something, or my system hasn't loaded the site properly.Edit — fixed.