We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. HourRank 31
  3. Basketball tournament
  4. Discussions

Basketball tournament

Sort by

recency

|

13 Discussions

|

  • mrflingchampion1
     + 0 comments

    pragma GCC optimize("O3")

    pragma GCC optimize("unroll-loops")

    pragma GCC target("avx2")

    include

    using namespace std;

    define rep(i,n) for(int i=0;i

    define per(i,n) for(int i=n-1;i>=0;i--)

    define rng(i,c,n) for(int i=c;i

    define fi first

    define se second

    define pb push_back

    define sz(a) (int)(a.size())

    define all(a) a.begin(),a.end() define _3Wcdivh ios::sync_with_stdio(0),cin.tie(0)

    typedef long long ll; typedef vector vi; typedef pair pii;

    void print() { cout << '\n'; } template void print(const h& v, const t&... u) { cout << v << ' '; print(u...); }

    const int N = (int) 3e5 + 1; const ll LINF = (ll) 1e18 + 123;

    struct DSU { int n; int dsu[N]; int leftmost[N]; int rightmost[N];

    void init(int n_) {
    n = n_ + 1;
    rep(i, n) {
        dsu[i] = -1;
        leftmost[i] = i;
        rightmost[i] = i;
    }
}

int get(int v) {
    if (dsu[v] == v) return v;
    return (dsu[v] = get(dsu[v]));
}

void unite(int u, int v) {
    u = get(u);
    v = get(v);
    dsu[u] = v;
    leftmost[v] = min(leftmost[v], leftmost[u]);
    rightmost[v] = max(rightmost[v], rightmost[u]);
}

bool is_enabled(int v) { return dsu[v] != -1; }

pii get_segment(int v) {
    if (!is_enabled(v)) return {-1, -1};
    v = get(v);
    return {leftmost[v], rightmost[v]};
}

void enable(int v) {
    dsu[v] = v;
    if (v - 1 >= 0 && dsu[v - 1] != -1) unite(v - 1, v);
    if (v + 1 < n && dsu[v + 1] != -1) unite(v, v + 1);
}

    };

    class MinTree { public: void init(int n_) { n = n_ + 1; fill(tree, tree + 4 * n, LINF); }

    void update(int index, ll value) {
    update(0, 0, n, index, value);
}

ll get(int l, int r) {
    return get(0, 0, n, l, r + 1);
}

    private: int n; ll tree[4 * N];

    void update(int i, int tl, int tr, int index, ll value) {
    if (tl == tr - 1) {
        tree[i] = min(tree[i], value);
        return;
    }
    int tm = (tl + tr) / 2;
    if (index < tm) update(2 * i + 1, tl, tm, index, value);
    else update(2 * i + 2, tm, tr, index, value);
    tree[i] = min(tree[2 * i + 1], tree[2 * i + 2]);
}

ll get(int i, int tl, int tr, int l, int r) {
    if (tl >= r || tr <= l) return LINF;
    if (l <= tl && tr <= r) return tree[i];
    int tm = (tl + tr) / 2;
    return min(get(2 * i + 1, tl, tm, l, r), get(2 * i + 2, tm, tr, l, r));
}

    };

    struct Query { int l, r; ll x; int id; };

    int n, m; ll h[N]; ll pref[N]; Query queries[N]; MinTree tree; DSU dsu; ll ans[N];

    ll get_sum(int l, int r) { return pref[r] - pref[l - 1]; }

    void slv() { cin >> n >> m; vector> heights(n); tree.init(n); rng(i, 1, n + 1) { cin >> h[i]; heights[i - 1] = {h[i], i}; pref[i] = pref[i - 1] + h[i]; tree.update(i, -h[i]); }

    rep(i, m) {
    cin >> queries[i].l >> queries[i].r >> queries[i].x;
    queries[i].id = i;
    ans[i] = LINF;
    int left, right;

    left = queries[i].l - 1;
    right = queries[i].r + 1;
    while (right - left > 1) {
        int mid = (left + right) / 2;
        int length = mid - queries[i].l + 1;
        if (get_sum(queries[i].l, mid) * 2 * length >= queries[i].x) right = mid;
        else left = mid;
    }

    if (right != queries[i].r + 1) ans[i] = min(ans[i], -tree.get(queries[i].l, right));

    left = queries[i].l - 1;
    right = queries[i].r + 1;
    while (right - left > 1) {
        int mid = (left + right) / 2;
        int length = queries[i].r - mid + 1;
        if (get_sum(mid, queries[i].r) * 2 * length >= queries[i].x) left = mid;
        else right = mid;
    }
    if (left != queries[i].l - 1) {
        ans[i] = min(ans[i], -tree.get(left, queries[i].r));
        queries[i].r = right - 1;
    }
}

sort(all(heights));
dsu.init(n);
vector<pair<ll, pii>> events;
rep(i, n) {
    int pos = heights[i].se;
    dsu.enable(pos);
    pii segment = dsu.get_segment(pos);
    int left = segment.fi;
    int right = segment.se;
    int length = right - left + 1;
    ll value = get_sum(left, right) * 2 * length;
    events.pb({value, {left, h[pos]}});
}

sort(all(events), [](const auto& x, const auto& y) { return x.fi > y.fi; });
sort(queries, queries + m, [](const auto& x, const auto& y) { return x.x > y.x; });

tree.init(n);
int ptr = 0;
rep(i, m) {
    while (ptr < n && events[ptr].fi >= queries[i].x) {
        tree.update(events[ptr].se.fi, events[ptr].se.se);
        ptr++;
    }
    int id = queries[i].id;
    if (ans[id] == LINF) continue;
    ans[id] = min(ans[id], tree.get(queries[i].l, queries[i].r));
}

rep(i, m) cout << (ans[i] == LINF ? -1 : ans[i]) << "\n";

    }

    int main() { _3Wcdivh; slv(); return 0; }

  • physioshah
     + 0 comments

    I love basketball very much! I have been wacthing different basketball tournaments since my school life. Now I am working as a senior and help people with having nudits chat rooms around the world so that they could find a way to have a wonderful time! Thanks for sharing this post.

  • goHacking17
     + 0 comments

    Hello, the below is my solution : I get error on this line : temp_li.append(list(itertools.combinations(varying_range, r=i))) Memory Error. Please help me in resolving the same.

    ''' https://www.hackerrank.com/contests/hourrank-31/challenges/basketball-tournament-1/problem '''

    import itertools
from functools import reduce
n, m = list(map(int, input().split()))
heights = list(map(int, input().split()))
heights = sorted(heights)

def list_of_l_r(l, r):
    temp_li = []
    temp_li.clear()
    varying_range = list(range(l,r+1))
    len_ = len(varying_range)
    for i in range(1, len_+1):
        temp_li.append(list(itertools.combinations(varying_range, r=i)))
        print(len(temp_li))
        # yield list(itertools.combinations(varying_range, r=i))
        # li1 = list(itertools.combinations(varying_range, r=i))

    print(temp_li)
    return temp_li

def f(i, j):
    return i+j
def calculate_power(collection):
    # retrieve the heights from the index
    # index comes from collections
    selected_height = []
    for i in collection:
        selected_height.append(heights[i-1])
    # calculate power for them
    combinations = list(itertools.product(selected_height, repeat=2))
    # print(combinations)

    power = 0
    for items in combinations:
        power += sum(items)
    # print(power)
    return power

def returnMin(matrix_of_indexes, x):
    height_max = []
    for matrix_items in matrix_of_indexes:
        for list_items in matrix_items:
            # print(list_items)
            power = calculate_power(list_items)
            if power >= x:
                # check for max value of height

                for i in list_items :
                    height_max.append(heights[i-1])
                # print("final_heights", height_max)
                # print("minimum is :")
                # print(height_max)
                # print("before returning height_max:", list_items)
                return max(height_max);
    if height_max == []:
        return -1
for i in range(m):
    l, r, x = list(map(int, input().split()))
    # print(l, r, x)

    # reproduce the sequences
    matrix_of_indexes = list_of_l_r(l, r)
    print(returnMin(matrix_of_indexes, x))

  • ritikojharoo
     + 0 comments

    k=2

  • Capitano
     + 0 comments
    #include <cstdio>
My C++ program. It does not pass all test cases due to excessive time but it took 50 points. As far as the algorithm is concerned is right.
int main(){
	long long n = 0; long long m = 0;
	FILE* fin = stdin; //fopen("basket.txt", "rt");
	
	fscanf(fin, "%lld %lld", &n, &m);
	
	long long height[n+1]; height[0] = 0;
	long long total_sum[n+1]; total_sum[0] = 0;
	long long P[n+1]; P[0] = 0;
	
	for(long long i = 1; i < n+1; i++){
		fscanf(fin, "%lld", &height[i]);
		total_sum[i] = total_sum[i - 1] + height[i];
	}
	
	long long k = 100000000; long long subk; long long subk_i;
	long long i, j;
	long long l, r, x;
	bool flag1 = true; bool flag2 = true;
	long long power;
	
	for(long long a = 0; a < m; a++){
		fscanf(fin, "%lld %lld %lld\n", &l, &r, &x);
		flag1 = true; flag2 = true;
		k = 100000000;
		power = 0;
		i = l; j = l;
		long long max_power;
			flag2 = true;
			power = 0;
			subk = 0;
			subk_i = -1;
			while(j <= r && flag2){
				//printf("\t%lld\n", j);
				if(height[j] > k){
					i = j+1;
					j++;
					power = 0;
					subk = 0;
					subk_i = -1;
				}
				else{
					power += 2*(total_sum[j - 1] - total_sum[i - 1] + (j - i)*height[j]) + 2*height[j];
					if(height[j] >= subk){
						subk = height[j];
						subk_i = j;
					}
					if(power >= x){
						k = subk;
						power -= 2*height[i] + 2*(total_sum[j] - total_sum[i] + (j - i)*height[i]);
						i++;
						if(subk_i < i){
							subk = 0;
							for(int b = i; b <= j; b++){
								if(height[b] > subk){
									subk = height[b];
									subk_i = b;
								}
							}
						}
						if(i > j) j=i;
						else power -= 2*(total_sum[j - 1] - total_sum[i - 1] + (j - i)*height[j]) + 2*height[j];
					}
					else{
						j++;
					}
					if(j > r && power < x){
						flag1 = false;
						flag2 = false;
						j--;
					}
				}
			}
			power -= 2*height[i] + 2*(total_sum[j] - total_sum[i] + (j - i)*height[i]);
			i++;
			if(subk_i < i){
				subk = 0;
				for(int b = i; b <= j; b++){
					if(height[b] > subk){
						subk = height[b];
						subk_i = b;
					}
				}
			}
			while(i <= r){
				if(power >= x){
					k = subk;
				}
				else break;
				power -= 2*height[i] + 2*(total_sum[j] - total_sum[i] + (j - i)*height[i]);
				i++;
				if(subk_i < i){
					subk = 0;
					for(int b = i; b <= j; b++){
						if(height[b] > subk){
							subk = height[b];
							subk_i = b;
						}
					}
				}
			}
		
		if(k == 100000000) k = -1;
		printf("%lld\n", k);
	}
	
	return 0;
}