Facebook Hacker Cup 2018: Round 2

6 years ago, # |

+126

Tfw stack space screws your B

I hope Facebook changes its contest format like CodeJam did this year. This was just sad and frustrating.

→ Reply

mnaeraxr

6 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 <bits/stdc++.h>
#include <inttypes.h>

using namespace std;

#define endl '\n'

typedef long long int64;
typedef pair<int,int> pii;
typedef vector<int> vi;

const double eps = 1e-9;
const int oo = 0x3f3f3f3f;

int64 dfs(int s, vector<vi> &tree, vector<int> &freq, multiset<int> &valid){
    int64 answer = 0;

    for (auto u : tree[s]){
        multiset<int> 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<int> freq(n);

    for (int i = 0; i < m; ++i){
        int64 c = (a * i + b) % n;
        freq[c]++;
    }

    vector<int> P(n);

    vector<vi> tree(n);

    for (int i = 1; i < n; ++i){
        int p; cin >> p;
        tree[p].push_back(i);
    }

    multiset<int> 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 :(

→ Reply

TimonKnigge

6 years ago, # ^ |

+60

On Linux just run ulimit -s unlimited.

→ Reply

mnaeraxr

6 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 ;)

→ Reply

6 years ago, # ^ |

← Rev. 2 →

+18

for online judges there's also more convenient way

→ Reply

duckladydinh

6 years ago, # ^ |

Unfortunately, not for Codeblocks users, at least I did set it for all terminals but the Codeblocks terminal just failed with Segmentation Fault :'(

→ Reply

sam29

6 years ago, # ^ |

+49

And this becomes more irritating when you realize the first 2 questions were enough to get the T-Shirt.

→ Reply

teja349

6 years ago, # ^ |

+30

They were even enough to qualify I think.

→ Reply

duckladydinh

6 years ago, # ^ |

← Rev. 2 →

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)

→ Reply

Gassa

6 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?

→ Reply

6 years ago, # ^ |

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.

→ Reply

aid

6 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.

→ Reply

6 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.

→ Reply

P___

6 years ago, # ^ |

+17

The easiest solution to this issue, was to do a local testing on max test prior to submit.

→ Reply

Gassa

6 years ago, # ^ |

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.

→ Reply

adelnobel

6 years ago, # ^ |

RE stack issues: You can set your stack size programmatically using this code

  #include <sys/resource.h>
.....
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 <algorithm>
#include <vector>
#include <queue>
#include <cstdlib>
#include <iostream>
#include <ctime>
#include <sys/resource.h>

using namespace std;

const int MAXN = 2e5 + 10;
const int MAXM = 1e6 + 10;

int cands[MAXN], qIdx[MAXN];
long long ans;
priority_queue<int> Q[MAXN];
vector<int> 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<int>();
    }
    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);
}

→ Reply

fmqjpt

6 years ago, # |

+22

Feels bad, I didn't get the second problem since my computer's stack memory is too small :(

→ Reply

SlavaSSU

6 years ago, # ^ |

I also failed B cuz of stack overflow. S**t.

→ Reply

dcordb

6 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.

→ Reply

Chilli

6 years ago, # ^ |

ulimit -s unlimited is what I usually do.

→ Reply

yurics

6 years ago, # ^ |

Same here

→ Reply

6 years ago, # ^ |

well, it's not that hard to google in 6min how to fix that

→ Reply

6 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?

→ Reply

6 years ago, # ^ |

+27

well, you run debugger and see stack trace where it fails. It shows you both minor errors and stack overflow.

→ Reply

xu3kev

6 years ago, # ^ |

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>".

→ Reply

6 years ago, # ^ |

I use visual debugger in clion. But in gdb it should be enough to enter command bt

→ Reply

fofao_funk

6 years ago, # ^ |

You may use the GCC's flag -fsanitize=address.

→ Reply

fmqjpt

6 years ago, # ^ |

+27

I tried, but nothing I found in time worked

I'm on a Mac so much of what I found online didn't help

→ Reply

arknave

6 years ago, # ^ |

+25

Also, on a mac, this worked for me

g++ -std=c++17 -Wl,-stack_size -Wl,0x10000000 candy.cpp

that is, this worked for me after my window expired :-(

→ Reply

cbosch_carlgauss

6 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

→ Reply

William_Yue

5 years ago, # ^ |

Very high quality

→ Reply

fmqjpt

6 years ago, # ^ |

works for me too, thanks!

→ Reply

oToToT

6 years ago, # ^ |

Mac, too.

And I can’t find anything useful on google, either

My friends told me to use ulimit -s XXXX

→ Reply

MofK

6 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:

→ Reply

6 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.

→ Reply

MofK

6 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

AGrigorii

6 years ago, # ^ |

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

→ Reply

Fazle

6 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 :(

→ Reply

6 years ago, # ^ |

+11

Segmentation fault here too bro xD

→ Reply

Hepic_Antony_Skarlatos

6 years ago, # ^ |

I got segmentation fault too. Is it possible that it happened because of stack overflow in my computer ?

→ Reply

6 years ago, # ^ |

Yeah, I think that's exactly what happened...

→ Reply

sam29

6 years ago, # ^ |

Yes, I tried the question using the same approach but couldn't generate the output file because of stack-overflow issue.

→ Reply

chemthan

6 years ago, # |

Simple O(N⁵) passed C.

→ Reply

Andrei1998

6 years ago, # ^ |

+10

I genuinely couldn't come up with it and found D easier.

→ Reply

Enchom

6 years ago, # ^ |

+11

How do you solve D? I found C pretty doable (in O(N⁵)) but came up with nothing for D for an hour.

→ Reply

xuanquang1999

6 years ago, # ^ |

DP optimization can be done with segment tree and lazy update (I think).

→ Reply

6 years ago, # ^ |

I think it's very similar to USACO 2012 Bookshelf.

→ Reply

zscoder

6 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] = min_{j ≥ L[i]}(dp[j - 1] + max(a_j, a_j + 1, ..., a_i)) + S, where L[i] is the largest index such that P_i - P_{L_i} ≤ 2M.

My solution is to store maintain the values F[j] = dp[j - 1] + max(a_j, a_j + 1, ..., a_i) as i increases and note that when we have a new value a_i + 1 and a_k, a_k + 1, ..., a_i ≤ a_i + 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.

→ Reply

f2lk6wf90d

6 years ago, # ^ |

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?

→ Reply

https://ideone.com/8w07Sk

6 years ago, # ^ |

It's O(N) because you add at most N elements and remove at most N elements

→ Reply

kalimm

6 years ago, # ^ |

It's dp optimization. I think O(N²) is easy and optimizing it is easy too.

For O(N²) 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.

→ Reply

Andrei1998

6 years ago, # ^ |

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 i^th of which has weight W_i, 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 dp_i = 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(N²) 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).

→ Reply

saketh

6 years ago, # ^ |

+23

I was able to do it without any segment trees / range updates. Code: https://pastebin.com/5661e30m

First, 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 x_i.

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.

→ Reply

xuanquang1999

6 years ago, # ^ |

I did the same. Wonder if this problem can be solved in better complexity.

→ Reply

kalimm

6 years ago, # ^ |

https://ideone.com/D1DMBH

I did it in O(N³). 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.

→ Reply

dragoon

6 years ago, # ^ |

+15

can you please elaborate?

→ Reply

6 years ago, # ^ |

+18

why not? 50⁵ ≈ 3·10⁸

→ Reply

GreenGrape

6 years ago, # |

-24

This B is a disaster.

→ Reply

Jakube

6 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.

→ Reply

cbosch_carlgauss

6 years ago, # ^ |

I did exactly that on B and accepted.

Spoiler

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

typedef long long int ll;

const int MAX = 2e5+7;

vector<int>g[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<st)return -1;
	if(qx<=st&&ed<=qy)return T[id];
	int piv = (st+ed)>>1;
	return max(qry(qx,qy,id<<1,st,piv),qry(qx,qy,id<<1|1,piv+1,ed));
}

pair<pair<int,int>,int> enc(int qx, int qy, int v, int id = 1, int st = 1, int ed = n)
{
	if(qx>ed||qy<st)return {{2e9,2e9},2e9};
	if(qx<=st&&ed<=qy)
		return (T[id]==v ? make_pair(make_pair(st,ed),id) : make_pair(make_pair(int(2e9),int(2e9)),int(2e9)));
	int piv = (st+ed)>>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<MAX; ++i)g[i].clear();
		for(int i = 2; i<=n; ++i)
		{
			int pi;cin>>pi;++pi;
			g[pi].emplace_back(i);
		}
		for(int i = 0; i<m; ++i)
			c[i] = (1ll*a*i + b)%n + 1;
        pr = 1;
		dfs();euler();ll ans = 0ll;
		sort(c,c+m,cmp);build();
        for(int i = 0; i<m; ++i)
		{
			int r = qry(dt[c[i]],pt[c[i]]);
			if(r==-1)
				continue;
			ans +=r;
			pair<pair<int,int>,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;
}

→ Reply

racsosabe

6 years ago, # ^ |

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 :'(

→ Reply

dalex

6 years ago, # ^ |

A disaster from educational rounds? It was very straightforward application of small-to-large technique.

→ Reply

GreenGrape

6 years ago, # ^ |

-7

I was talking about stack memory.

→ Reply