### LoneFox's blog

By LoneFox, history, 3 years ago,

Round 2 of the 2018 Facebook Hacker Cup is less than 24 hours away!

The round will begin on August 4th, 2018 at 10am PDT and will last for 3 hours. You can check the start time in your local timezone here.

The contest will be available here shortly before the round begins.

You're eligible to compete in Round 2 if you scored at least 35 points in Round 1.

The top 200 contestants will advance to Round 3, which will take place on August 18th, and the top 500 contestants will win Hacker Cup t-shirts! We'll begin shipping out t-shirts in September, at which point the winners will receive emails with tracking information. Please note that all submission judgements will only be revealed after the round ends, and that time penalty will be used to break score ties. More details about rules and other information can be found here.

Good luck!

The corresponding Facebook post can be found here.

Update: The editorial is now available here.

• +71

 » 3 years ago, # |   +11 Not exactly related to this, but do you maybe have any information about t-shirts from last year?
•  » » 3 years ago, # ^ |   -12 We're aware that some winners unfortunately didn't end up receiving their t-shirts in the past, and are working on having those re-delivered through an improved process this year. Please let us know if you were among the top 500 contestants in Round 2 of the 2017 Hacker Cup but didn't receive your t-shirt, thanks!
•  » » » 3 years ago, # ^ |   +8 Do you mean we should send you a message?
•  » » » » 3 years ago, # ^ |   +25 Sure, a message on CodeForces will work.
•  » » » 2 years ago, # ^ |   +8 I received mine today :D (from 2017)
 » 3 years ago, # |   +11 I scored 35 points in Round 1 however did not get an email from Facebook about qualifying for Round 2, like I received about qualifying for Round 1. Is it the case that Facebook just didn't send an email for this round?
•  » » 3 years ago, # ^ |   +6 You're indeed qualified for Round 2 if the Round 1 scoreboard says that you got 35 points. Unfortunately, some qualified contestants may not have received emails for this round.
 » 3 years ago, # |   +70 Out of curiosity — why are there no email reminders about FBHC rounds? I would've forgotten about this one if not for the contest calendar imported to my Google Calendar; I assume many people just forget about these rounds.
 » 3 years ago, # | ← Rev. 2 →   +68 I go to https://www.facebook.com/hackercup/, which is the "main page" of the Hacker Cup. I CAN'T FIND THE LINK TO THE CONTEST. Thankfully, this blog on Codeforces exists, and I can follow the link on this page. Here it is, once more: https://www.facebook.com/hackercup/contest Or https://www.facebook.com/hackercup/round/211051912693116/
 » 3 years ago, # |   +126 Tfw stack space screws your BI hope Facebook changes its contest format like CodeJam did this year. This was just sad and frustrating.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +28 Same issue here. I had Runtime Error in my PC without noting that the problem was with the stack. I'll share a trick that I saw in HackerRank a few years ago. You can increase the size of the stack with one snippet. I'll post my entire solution for problem B of today HackerCup (the contest is over already)The snippet is at the bottom of the code (and one "magic" include in the begining). Spoiler#include #include using namespace std; #define endl '\n' typedef long long int64; typedef pair pii; typedef vector vi; const double eps = 1e-9; const int oo = 0x3f3f3f3f; int64 dfs(int s, vector &tree, vector &freq, multiset &valid){ int64 answer = 0; for (auto u : tree[s]){ multiset tmp; answer += dfs(u, tree, freq, tmp); if (valid.size() < tmp.size()) valid.swap(tmp); for (auto x : tmp) valid.insert(x); } valid.insert(s); for (int i = 0; i < freq[s] && !valid.empty(); ++i){ answer += *valid.rbegin(); auto it = valid.end(); it--; valid.erase(it); } return answer; } void solve(){ int64 n, m, a, b; cin >> n >> m >> a >> b; vector freq(n); for (int i = 0; i < m; ++i){ int64 c = (a * i + b) % n; freq[c]++; } vector P(n); vector tree(n); for (int i = 1; i < n; ++i){ int p; cin >> p; tree[p].push_back(i); } multiset S; int64 answer = dfs(0, tree, freq, S); cout << answer << endl; } static void main2(){ ios_base::sync_with_stdio(0); cin.tie(0); int t; cin >> t; for (int i = 1; i <= t; ++i){ cout << "Case #" << i << ":"; cout << " "; solve(); } } static void run_with_stack_size(void (*func)(), 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(main2, 64*1024*1024); } Without the trick my code crash :(
•  » » » 3 years ago, # ^ |   +60 On Linux just run ulimit -s unlimited.
•  » » » » 3 years ago, # ^ |   +24 I guessed there exist some flags to increase stack size, but didn't know at contest time :( and couldn't find anything in the 6min time window. Anyway this snippet is really useful for ONLINE judges, where you can't control flags to compiler ;)
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   +18 for online judges there's also more convenient way
•  » » » » 3 years ago, # ^ |   0 Unfortunately, not for Codeblocks users, at least I did set it for all terminals but the Codeblocks terminal just failed with Segmentation Fault :'(
•  » » 3 years ago, # ^ |   +49 And this becomes more irritating when you realize the first 2 questions were enough to get the T-Shirt.
•  » » » 3 years ago, # ^ |   +30 They were even enough to qualify I think.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 Maybe they already count the ability to detect and fix such error :V, no way to easily get thing from Facebook, u know :V (even if u did pass, it is known to take a life to wait for the T-Shirt to come)
•  » » 3 years ago, # ^ |   +97 This sounds sad and strange.A failure is an opportunity to learn. If you don't know how to increase stack size locally, and it costed you a problem in an important contest, the natural reaction is to learn how to do it, once and for all.Hoping that the platform changes its contest format instead is counterproductive, as it doesn't make your own situation any better. Are you not going to test your solutions locally then?
•  » » » 3 years ago, # ^ |   +8 Ofcourse I'm going to learn it now. I agree that some fault lies in me not knowing how to increase the stack size locally, but I believe that at a major contest like Facebook HackerCup, this non-CP knowledge should not be the deciding factor. I knew how to solve the question, and had it passed (which it would have — I checked later), I would have gotten atleast a T-Shirt and some morale to solve further questions.
•  » » » » 3 years ago, # ^ |   +71 It's not a deciding factor. There were 2 other problems which were enough to advance. You should be glad that they put such problem in round 2 and not in round 3 or Finals, where every problem matters.Putting the fault on organizers is stupid. It's a programming competition and they even give you complete freedom to use any software you want. If you don't know how to compile and run programs properly it's your and only your fault.
•  » » » » » 3 years ago, # ^ |   +11 I'm not putting the fault on them. I just said that I prefer CodeJam style contest over this. I wasn't the only one who suffered, and I do believe that it distorted the ranklist a little.
•  » » 3 years ago, # ^ |   +17 The easiest solution to this issue, was to do a local testing on max test prior to submit.
•  » » » 3 years ago, # ^ |   +3 Yeah, especially since the generators are short enough. Here are some example max-test generators in Python2 for this problem: random (non-uniform), star, binary, bamboo. Python 3 would need a few more parentheses.
•  » » 3 years ago, # ^ |   +8 RE stack issues: You can set your stack size programmatically using this code  #include ..... int main() { const rlim_t kStackSize = 60 * 1024 * 1024; struct rlimit rl; int result; result = getrlimit(RLIMIT_STACK, &rl); if (result == 0) { if (rl.rlim_cur < kStackSize) { rl.rlim_cur = kStackSize; result = setrlimit(RLIMIT_STACK, &rl); if (result != 0) { fprintf(stderr, "setrlimit returned result = %d\n", result); } } } ..... you can put it at the start of the main function and things will run well here is a sample solution that sets the stack size this way Solution#include #include #include #include #include #include #include using namespace std; const int MAXN = 2e5 + 10; const int MAXM = 1e6 + 10; int cands[MAXN], qIdx[MAXN]; long long ans; priority_queue Q[MAXN]; vector adj[MAXN]; void solve(int n) { int myIdx = n, otherIdx; if (adj[n].size() > 0) { solve(adj[n][0]); myIdx = qIdx[adj[n][0]]; for (int j = 1; j < adj[n].size(); ++j) { solve(adj[n][j]); otherIdx = qIdx[adj[n][j]]; if (Q[otherIdx].size() > Q[myIdx].size()) { swap(myIdx, otherIdx); } while (!Q[otherIdx].empty()) { Q[myIdx].push(Q[otherIdx].top()); Q[otherIdx].pop(); } } } qIdx[n] = myIdx; Q[myIdx].push(n); while ((cands[n]--) && (!Q[myIdx].empty())) { ans += Q[myIdx].top(); Q[myIdx].pop(); } } int main() { // 60 MB const rlim_t kStackSize = 60 * 1024 * 1024; struct rlimit rl; int result; result = getrlimit(RLIMIT_STACK, &rl); if (result == 0) { if (rl.rlim_cur < kStackSize) { rl.rlim_cur = kStackSize; result = setrlimit(RLIMIT_STACK, &rl); if (result != 0) { fprintf(stderr, "setrlimit returned result = %d\n", result); } } } freopen( "/Users/adelaly/Documents/workspace/test/bin/Debug/out.out", "r", stdin); ios::sync_with_stdio(false); std::clock_t start; start = std::clock(); int T, N, M, A, B, p; cin >> T; for (int tt = 1; tt <= T; ++tt) { ans = 0; cin >> N >> M >> A >> B; memset(cands, 0, MAXN * sizeof(int)); ans = 0; for (int i = 0; i < N; i++) { adj[i].clear(); Q[i] = priority_queue(); } for (int i = 1; i < N; i++) { cin >> p; adj[p].push_back(i); } for (int i = 0; i < M; i++) { long long x = (1LL * A * i + B) % N; ++cands[x]; } solve(0); cout << "Case #" << tt << ": " << ans << endl; std::cout << "Time: " << (std::clock() - start) / (double)(CLOCKS_PER_SEC) << std::endl; } return (0); } 
 » 3 years ago, # |   +22 Feels bad, I didn't get the second problem since my computer's stack memory is too small :(
•  » » 3 years ago, # ^ |   +7 I also failed B cuz of stack overflow. S**t.
•  » » 3 years ago, # ^ | ← Rev. 3 →   +12 If you are on linux you can change the computer stack memory with the command ulimit -s 1048576. It will set stack size to 1 Gb, which is enough.
•  » » » 3 years ago, # ^ |   +8 ulimit -s unlimited is what I usually do.
•  » » 3 years ago, # ^ |   +8 Same here
•  » » 3 years ago, # ^ |   0 well, it's not that hard to google in 6min how to fix that
•  » » » 3 years ago, # ^ |   +59 Except that you do not know it's definitely Stack Space causing RTE, and not some minor fault in your program, which you are more likely to check first?
•  » » » » 3 years ago, # ^ |   +27 well, you run debugger and see stack trace where it fails. It shows you both minor errors and stack overflow.
•  » » » » » 3 years ago, # ^ |   0 Could you provide an example how to use the debugger like gdb or lldb to examine the stack trace? When I use lldb I only found "stop reason = EXC_BAD_ACCESS". When I use gdb I only found "error reading variable: Cannot access memory at address 0x0>".
•  » » » » » » 3 years ago, # ^ |   +3 I use visual debugger in clion. But in gdb it should be enough to enter command bt
•  » » » » 3 years ago, # ^ |   +5 You may use the GCC's flag -fsanitize=address.
•  » » » 3 years ago, # ^ |   +27 I tried, but nothing I found in time workedI'm on a Mac so much of what I found online didn't help
•  » » » » 3 years ago, # ^ |   +25 Also, on a mac, this worked for meg++ -std=c++17 -Wl,-stack_size -Wl,0x10000000 candy.cppthat is, this worked for me after my window expired :-(
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   +14 In windows I use this compile line during the contest: g++ -O2 -std=c++11 -Wall -Wl,--stack=268435456 a.cpp -o a.exe Thanks to Gassa
•  » » » » » » 20 months ago, # ^ |   0 Very high quality
•  » » » » » 3 years ago, # ^ |   0 works for me too, thanks!
•  » » » » 3 years ago, # ^ |   0 Mac, too.And I can’t find anything useful on google, eitherMy friends told me to use ulimit -s XXXX
•  » » » 3 years ago, # ^ |   +14 Suuuure... But you have to spend X minutes to figure out wtf is going on. I straight up thought that my solution was wrong somewhere, then debugged in panic before realizing that my code suddenly crashed randomly at node 50000, hence X=5 for me D:
•  » » » » 3 years ago, # ^ |   +15 Well, I don't know what is your debug strategy, but first thing I do when I get runtime error is I run debugger and examine a stack trace to get to know actual line where it fails. Seeing stack of thousands functions says you you have either too small stack or you recourse infinitely.
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 Your strategy makes sense, but in my case, stack overflowing is the last thing I would ever think of because I recall having increased it a loooong time ago. Then I realized I was coding on a computer I just bought recently xD.Otherwise yeah, debugger should have prevented that.
•  » » 3 years ago, # ^ |   0 Very strange. Had the same problem. There was segment tree on 1 << 19 verticies, fixed by changing this count to 1 << 20 (after six minutes another solution of this problem was appeared stack 300m -> 500m). Here code of my program without stack overflow 1 << 20
 » 3 years ago, # | ← Rev. 2 →   +23 Was Jack's Candy Shop just merge smaller to greater set(DSU on Trees)?UPD- Failed because of stack overflow :(
•  » » 3 years ago, # ^ |   +11 Segmentation fault here too bro xD
•  » » » 3 years ago, # ^ |   +5 I got segmentation fault too. Is it possible that it happened because of stack overflow in my computer ?
•  » » » » 3 years ago, # ^ |   +5 Yeah, I think that's exactly what happened...
•  » » 3 years ago, # ^ |   +5 Yes, I tried the question using the same approach but couldn't generate the output file because of stack-overflow issue.
 » 3 years ago, # |   +8 Simple O(N5) passed C.
•  » » 3 years ago, # ^ |   +10 I genuinely couldn't come up with it and found D easier.
•  » » » 3 years ago, # ^ |   +11 How do you solve D? I found C pretty doable (in O(N5)) but came up with nothing for D for an hour.
•  » » » » 3 years ago, # ^ |   +3 DP optimization can be done with segment tree and lazy update (I think).
•  » » » » 3 years ago, # ^ |   0 I think it's very similar to USACO 2012 Bookshelf.
•  » » » » 3 years ago, # ^ |   +11 I got it 3 mins after contest ended.Obviously, sort the fossils by position first.The idea is that we have dp of the form dp[i] = minj ≥ L[i](dp[j - 1] + max(aj, aj + 1, ..., ai)) + S, where L[i] is the largest index such that Pi - PLi ≤ 2M.My solution is to store maintain the values F[j] = dp[j - 1] + max(aj, aj + 1, ..., ai) as i increases and note that when we have a new value ai + 1 and ak, ak + 1, ..., ai ≤ ai + 1, then we can remove F[k + 1], F[k + 2], ..., F[i] from our set, since dp is non-decreasing and the max part is the same. However, when we increment L[i] to L[i + 1], we might need some of the values F[k + 1], F[k + 2], ..., F[i] back. However, we can do that by adding the F[.] values one by one as we increment our pointer from L[i] to L[i + 1]. Finally, we just need to take the minimum from the set to update the dp.My explanation might not be very clear. Here is my code.
•  » » » » » 3 years ago, # ^ |   0 I came up with the exact same solution (that I didn't manage to code in time, unfortunately). However, I can't figure out the complexity of maintaining a stack/deque of prefix maxima. Could somebody post it?
•  » » » » » » 3 years ago, # ^ |   0 It's O(N) because you add at most N elements and remove at most N elements
•  » » » » 3 years ago, # ^ |   0 https://ideone.com/8w07SkIt's dp optimization. I think O(N2) is easy and optimizing it is easy too.For O(N2) just sort x coordinates and create a shaft between consecutive indices using dp.For O(N * log(N)), get minimum from segment tree, also update "maximum value till the index i\$ values simultaneously using stack.
•  » » » » 3 years ago, # ^ |   0 First of all, the rectangles don't need to intersect. Afterwards, you can reduce the problem to the following:Given N points on the OX axis, the ith of which has weight Wi, cover these points with intervals of length at most 2M. Let K be the number of intervals used, then the cost of such a covering is given by K·S plus the maximum weight in each of the K ranges.Sort the points in increasing order. Let dpi = the minimum cost of a covering of the first i points with intervals of maximum length 2M.It's pretty easy to implement this in O(N2) time. You can do better by close inspection of the recurrence relation — maintain a stack of maximums while going from i = 1 to i = n and updating the costs used in the dp in a segment tree (operations: add value to range, query maximum in range). Time complexity O(NlogN).
•  » » » » 3 years ago, # ^ |   +23 I was able to do it without any segment trees / range updates. Code: https://pastebin.com/5661e30mFirst, sort all the fossils by x-coordinate. Let f(i) denote the minimum cost to get all fossils  ≥ i. We compute f(i) in decreasing order of i.For any group of fossils  ≥ i, the first (leftmost) shaft should have its left edge at xi.Case 1: The first shaft does not overlap any other shaft. In this case it needs to cover all the fossils within its width. As i decreases we use a set of pairs to maintain the set of fossils that are in this range and retrieve the greatest depth among them.Case 2: The first shaft overlaps some other shaft. The second shaft will need to have its left edge at the first fossil not covered by the first shaft. The second shaft is assumed to be at least as deep as the first; otherwise we could just move it to the right until it no longer overlaps. These two facts together mean that there should not exist any fossil that is both to the left and deeper than the first fossil not covered by the first shaft. We refer to the set of fossils that could satisfy this constraint as the dominating set. We can maintain the dominating set using a deque. They are kept ordered by their x-coordinate. We pop fossils off the back once their x-coordinate is too great to be the left edge of the overlapping second shaft. Before inserting any new fossil to the front, we pop from the front all fossils that are dominated by it.Note that for any group  ≥ i, the dominating set of fossils includes fossil i. For any fossil j ≠ i in the dominating set, the total cost if the second shaft begins at that fossil is given by S + D + f(j), where D is the depth of the fossil appearing to the left of j in the dominating set (its depth determines the necessary depth for the first shaft). We can maintain a separate set of these "candidates" for f(i) and update it accordingly whenever the dominating set is modified.The answer for f(i) is given by the minimum among the candidate from Case 1 and the set of candidates from Case 2. The solution is fast enough because each fossil enters and leaves the dominating set at most once.
•  » » 3 years ago, # ^ |   0 I did the same. Wonder if this problem can be solved in better complexity.
•  » » » 3 years ago, # ^ |   0 https://ideone.com/D1DMBHI did it in O(N3). It's not more than just some case analysis. For example, we can use RIGHT, UP pair before s or UP, LEFT after s, to cover s. Same thing for e.
•  » » » » 3 years ago, # ^ |   +15 can you please elaborate?
•  » » 3 years ago, # ^ |   +18 why not? 505 ≈ 3·108
 » 3 years ago, # |   -24 This B is a disaster.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +13 There is a really neat solution. Put the Euler path into a segment tree, and then satisfy the customer in increasing depth[C_i] order by extracting the maxima of the subtrees.
•  » » » 3 years ago, # ^ |   0 I did exactly that on B and accepted. Spoiler#include using namespace std; #define endl '\n' typedef long long int ll; const int MAX = 2e5+7; vectorg[MAX]; int c[MAX*10], h[MAX], dt[MAX], pt[MAX], idt[MAX], pr = 1; int n,m,a,b; int T[4*MAX]; void dfs(int st = 1, int p = 0) { h[st] = p; for(int nn : g[st]) dfs(nn,p+1); } void euler(int st = 1) { dt[st] = pr; idt[pr++] = st; for(int nn : g[st]) euler(nn); pt[st] = pr-1; } int build(int id = 1, int st = 1, int ed = n) { if(st==ed)return T[id] = idt[st]-1; int piv = (st+ed)>>1; return T[id] = max(build(id<<1,st,piv),build(id<<1|1,piv+1,ed)); } int qry(int qx, int qy, int id = 1, int st = 1, int ed = n) { if(qx>ed||qy>1; return max(qry(qx,qy,id<<1,st,piv),qry(qx,qy,id<<1|1,piv+1,ed)); } pair,int> enc(int qx, int qy, int v, int id = 1, int st = 1, int ed = n) { if(qx>ed||qy>1; return min(enc(qx,qy,v,id<<1,st,piv),enc(qx,qy,v,id<<1|1,piv+1,ed)); } int kill(int id = 1, int st = 1, int ed = n) { if(st==ed)return st; int piv = (st+ed)>>1; if(T[id<<1]>=T[id<<1|1]) return kill(id<<1,st,piv); else return kill(id<<1|1,piv+1,ed); } int ers(int p, int id = 1, int st = 1, int ed = n) { if(st==ed)return T[id] = -1; int piv = (st+ed)>>1; if(p<=piv)T[id<<1] = ers(p,id<<1,st,piv); else T[id<<1|1] = ers(p,id<<1|1,piv+1,ed); return T[id] = max(T[id<<1],T[id<<1|1]); } bool cmp(int a, int b) { return h[a]>h[b]; } int main() { ios_base::sync_with_stdio(false); cin.tie(0),cout.tie(0); int tc;cin>>tc; for(int t = 1; t<=tc; ++t) { cin>>n>>m>>a>>b; for(int i = 0; i>pi;++pi; g[pi].emplace_back(i); } for(int i = 0; i,int> iv = enc(dt[c[i]],pt[c[i]],r); int p = kill(iv.second,iv.first.first,iv.first.second); ers(p); } cout << "Case #" << t << ": " << ans << endl; } return 0; } 
•  » » » 3 years ago, # ^ |   0 I did so too, with Timestamps + Segment Tree, but my stack crashed. Had to change it to iterative DFS but couldn't make it on time :'(
•  » » 3 years ago, # ^ |   +3 A disaster from educational rounds? It was very straightforward application of small-to-large technique.
•  » » » 3 years ago, # ^ |   -7 I was talking about stack memory.
•  » » 3 years ago, # ^ |   -13 So are the pretests of B of your contest.
 » 3 years ago, # |   +31 When you forgot to print the number of edges in A...
•  » » 3 years ago, # ^ |   +8 Same :c
•  » » 3 years ago, # ^ |   0 When you put 3 nodes as an edge case with solution set to 0 and you don't realize that 3 4 has solution 1 :((. Short and sad history for me that end in not getting a t-shirt since i only manage to solve B.
 » 3 years ago, # |   +5 When you found you should change your computer due to the stack sizeI bought my computer about 8 years, ago...
•  » » 3 years ago, # ^ |   +11 Well, I bought my computer just 1 month ago. I forgot to increase my stack size...Seems like both extreme cases screw people up the same way :P
 » 3 years ago, # |   0 When you have high hopes for top 500 and then fail B due to stack size... :^)
 » 3 years ago, # |   0 Aren't editorials out?
•  » » 3 years ago, # ^ |   0 Editorials are here.
 » 3 years ago, # |   +21 I had a really simple solution for B: since we want to sell the most expensive candy possible, iterate candies from n-1 to 0. We can buy a candy if it has a grandparent with at least 1 buyer remaining. Let's check this by moving up the parent chain until we either find some buyers or reach the root. Naive implementation of this idea would be O(nodes*edges), but we can speed it up by not traversing the same chains over and over again. Let's say we traversed nodes from 9->5->7->2->3 and we found first buyer at node 3. We use this buyer for node 9 and it's possible there are more buyers at 3 or at its grandparents. Since we know that there are no buyers before node 3, we can mark that down to all nodes we traversed (5,7,2). For example, later when we want to know if node 5 can be bought, we don't have to traverse from 5 again, we can start traversing from 3.I thought that this would run in O(nodes + edges), but surprisingly it took 3 minutes to run. The time limit was 6 minutes so I got it in barely in time. Can anyone analyze why it's slower than expected?
•  » » 3 years ago, # ^ |   +8 Because you shoud use this: Link to DSU This make the algorithm O(M+N*alpha(N))
•  » » 3 years ago, # ^ |   +13 I got some help with this and improved my solution so it's now linear: https://pastebin.com/PTsahgpw(Worst case to my old code was a long chain such as 0->6->5->4->3->2->1. The new code traverses it fast by making "small jumps" when necessary.)
•  » » 3 years ago, # ^ |   +43 Yup, I did exactly like this (+DSU trick). It's a neat 30 lines of codes imo! :D Code#include using namespace std; long long t,tt,n,m,a,b,i,ans; long long kid[2000007],p[2000007]; int getpar(int pos) { if (pos == -1) return -1; if (kid[pos] > 0) { kid[pos]--; return pos; } return p[pos] = getpar(p[pos]); } int main() { scanf("%lld",&t); for (tt=1 ; tt<=t ; tt++) { scanf("%lld%lld%lld%lld",&n,&m,&a,&b); p[0] = -1; for (i=1 ; i=0 ; i--) { if (getpar(i) != -1) ans += i; } printf("Case #%lld: %lld\n",tt,ans); } } 
 » 3 years ago, # |   -88 why only 200 persons advance to round 3 ? i think it would be fair if at lease 250 advanced as it's the half size of the people who will get T-Shirts, can you really consider it ?
•  » » 3 years ago, # ^ |   +40 why only 200 persons advance to round 3 ? i think it would be fair if at lease 500 advanced as it's the people who will get T-Shirts, can you really consider it ?
•  » » » 3 years ago, # ^ |   +177 Why as many as 200 person advance to round 3? I think it would be fair if exactly 71 advanced as it would make me advance yet keep the competition in the next round as small as possible.
•  » » » » 3 years ago, # ^ |   +23 Meh, why as many as 200 if it could have been 194?
•  » » » » » 3 years ago, # ^ |   +21 Or 195 (just to troll Radewoosh) :)
•  » » » » » » 3 years ago, # ^ |   +55 Why even make round 3? They could just let top 25 advance to the Finals.
•  » » » » » » » 3 years ago, # ^ |   +200
 » 3 years ago, # | ← Rev. 2 →   +8 Sorry, my friends posted it just wanted me to get downvotes.Sorry about that.
•  » » 3 years ago, # ^ | ← Rev. 3 →   -82 Sorry, my friend posted it just wanted to play a joke on me. I was not mean to make the comment in Rev 1. Sorry.
 » 3 years ago, # |   +1 Is there any way to increase stack limit (say to 40MB) permanently (i.e, for all programs I run on my PC) ? P.S : I use Ubuntu 16.04 and use Sublime Text Editor
•  » » 3 years ago, # ^ |   0 Yes. I just increased my stack size permanently, after I got Seg. fault on B. :( To set stack limit (say 32MB), open you ~/.bashrc file, and paste this line. (change the number to your desired limit in KB). ulimit -s 32768 This will increase your stack limit everytime you open up your terminal.
 » 3 years ago, # |   +13 Not a complain, just funny fact. My solution for C was ready 15 minutes before contest is over. I build it successfully, run .... and got message that 'executable file format is not recognized by Windows'. Whaaaaat? I use VS with the same solution file for all problems in contest and never had such issue. Tried to rebuild it, played with different configurations (Release, Debug, Win64), deleted all auto-generated folders, copied source code in well project for problem A. Nothing helped. Build succeeded without any warning, run/debug doesn't work because windows don't recognize file format. As it turned out problem was in array I statically allocated for the DP: int dp[55][55][55][55][55]; It seems it exceeded some limit and when I changed it to int dp[51][51][51][51][51]; It magically start working (not immediately, but after I wiped out all auto-generated folders including .vs). Unfortunately, this was done after contest was over. And what is more sad this solution without any changes passed all tests. I could ended up in first 120 and advance to 3rd round. :) Lesson learned — if you allocate memory close to 1.5Gb be prepared to get 'non-Windows executable binary' if compile in VS.