Facebook Hacker Cup 2018: Round 2

8 лет назад, скрыть # |

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

→ Ответить

mnaeraxr

8 лет назад, скрыть # ^ |

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

→ Ответить

TimonKnigge

8 лет назад, скрыть # ^ |

+60

On Linux just run ulimit -s unlimited.

→ Ответить

mnaeraxr

8 лет назад, скрыть # ^ |

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

→ Ответить

8 лет назад, скрыть # ^ |

← Rev. 2 →

+18

for online judges there's also more convenient way

→ Ответить

duckladydinh

8 лет назад, скрыть # ^ |

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

→ Ответить

sam29

8 лет назад, скрыть # ^ |

+49

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

→ Ответить

teja349

8 лет назад, скрыть # ^ |

+30

They were even enough to qualify I think.

→ Ответить

duckladydinh

8 лет назад, скрыть # ^ |

← 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)

→ Ответить

Gassa

8 лет назад, скрыть # ^ |

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

→ Ответить

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.

→ Ответить

aid

8 лет назад, скрыть # ^ |

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

→ Ответить

8 лет назад, скрыть # ^ |

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

→ Ответить

P___

8 лет назад, скрыть # ^ |

+17

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

→ Ответить

Gassa

8 лет назад, скрыть # ^ |

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.

→ Ответить

adelnobel

8 лет назад, скрыть # ^ |

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

→ Ответить

dkxdjy

8 лет назад, скрыть # |

+22

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

→ Ответить

SlavaSSU

8 лет назад, скрыть # ^ |

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

→ Ответить

dcordb

8 лет назад, скрыть # ^ |

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

→ Ответить

Chilli

8 лет назад, скрыть # ^ |

ulimit -s unlimited is what I usually do.

→ Ответить

yurics

8 лет назад, скрыть # ^ |

Same here

→ Ответить

8 лет назад, скрыть # ^ |

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

→ Ответить

8 лет назад, скрыть # ^ |

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

→ Ответить

8 лет назад, скрыть # ^ |

+27

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

→ Ответить

xu3kev

8 лет назад, скрыть # ^ |

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

→ Ответить

8 лет назад, скрыть # ^ |

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

→ Ответить

fofao_funk

8 лет назад, скрыть # ^ |

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

→ Ответить

dkxdjy

8 лет назад, скрыть # ^ |

+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

→ Ответить

arknave

8 лет назад, скрыть # ^ |

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

→ Ответить

cbosch_carlgauss

8 лет назад, скрыть # ^ |

← 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

→ Ответить

William_Yue

7 лет назад, скрыть # ^ |

Very high quality

→ Ответить

dkxdjy

8 лет назад, скрыть # ^ |

works for me too, thanks!

→ Ответить

oToToT

8 лет назад, скрыть # ^ |

Mac, too.

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

My friends told me to use ulimit -s XXXX

→ Ответить

MofK

8 лет назад, скрыть # ^ |

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

→ Ответить

8 лет назад, скрыть # ^ |

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

→ Ответить

MofK

8 лет назад, скрыть # ^ |

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

→ Ответить

AGrigorii

8 лет назад, скрыть # ^ |

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

→ Ответить

Fazle

8 лет назад, скрыть # |

← Rev. 2 →

+23

Was Jack's Candy Shop just merge smaller to greater set(DSU on Trees)?

UPD- Failed because of stack overflow :(

→ Ответить

8 лет назад, скрыть # ^ |

+11

Segmentation fault here too bro xD

→ Ответить

Hepic_Antony_Skarlatos

8 лет назад, скрыть # ^ |

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

→ Ответить

8 лет назад, скрыть # ^ |

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

→ Ответить

sam29

8 лет назад, скрыть # ^ |

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

→ Ответить

chemthan

8 лет назад, скрыть # |

Simple O(N⁵) passed C.

→ Ответить

Andrei1998

8 лет назад, скрыть # ^ |

+10

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

→ Ответить

Enchom

8 лет назад, скрыть # ^ |

+11

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

→ Ответить

xuanquang1999

8 лет назад, скрыть # ^ |

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

→ Ответить

8 лет назад, скрыть # ^ |

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

→ Ответить

zscoder

8 лет назад, скрыть # ^ |

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

→ Ответить

f2lk6wf90d

8 лет назад, скрыть # ^ |

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?

→ Ответить

https://ideone.com/8w07Sk

8 лет назад, скрыть # ^ |

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

→ Ответить

kalimm

8 лет назад, скрыть # ^ |

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.

→ Ответить

Andrei1998

8 лет назад, скрыть # ^ |

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

→ Ответить

saketh

8 лет назад, скрыть # ^ |

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

→ Ответить

xuanquang1999

8 лет назад, скрыть # ^ |

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

→ Ответить

kalimm

8 лет назад, скрыть # ^ |

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.

→ Ответить

dragoon

8 лет назад, скрыть # ^ |

+15

can you please elaborate?

→ Ответить

8 лет назад, скрыть # ^ |

+18

why not? 50⁵ ≈ 3·10⁸

→ Ответить

GreenGrape

8 лет назад, скрыть # |

-24

This B is a disaster.

→ Ответить

Jakube

8 лет назад, скрыть # ^ |

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

→ Ответить

cbosch_carlgauss

8 лет назад, скрыть # ^ |

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;
}

→ Ответить

racsosabe

8 лет назад, скрыть # ^ |

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

→ Ответить

dalex

8 лет назад, скрыть # ^ |

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

→ Ответить

GreenGrape

8 лет назад, скрыть # ^ |

-7

I was talking about stack memory.

→ Ответить