Does anyone know/have any good K-D Tree implementation in C++/Java?

# | User | Rating |
---|---|---|

1 | tourist | 3602 |

2 | Radewoosh | 3246 |

3 | LHiC | 3236 |

4 | W4yneb0t | 3181 |

5 | TakanashiRikka | 3178 |

6 | Petr | 3146 |

7 | moejy0viiiiiv | 3122 |

8 | izrak | 3109 |

9 | Um_nik | 3105 |

9 | ershov.stanislav | 3105 |

# | User | Contrib. |
---|---|---|

1 | rng_58 | 178 |

2 | csacademy | 167 |

3 | tourist | 165 |

3 | Errichto | 165 |

5 | Petr | 164 |

6 | Swistakk | 158 |

7 | matthew99 | 153 |

8 | Zlobober | 151 |

9 | zscoder | 143 |

10 | GlebsHP | 137 |

Does anyone know/have any good K-D Tree implementation in C++/Java?

Hi. I am having problem trying to solve JOI 2013/2014 — Historical Research. The english problem statement can be found here.

For those who understand Japanese, the editorial can be found here

The input and output data can be found here

My approach is as follows:

Let *product* = *element* × *frequency* in subarray [*L*, *R*]

We use a BST to answer our max product queries and element updates efficiently, Each element of the BST would be < *product*, *element*, *frequency* > and the elements in the BST are sorted by *product*.

Let *N* be the number of elements in our array and *Q* be the number of queries.

Perform square root decomposition on the queries by breaking them into blocks and sorting them in increasing order of left bound followed by increasing order of right bound. Time-complexity of this operation is *O*(*Q* × *logQ*).

We keep 2 pointers to track the left and right bound of the subarray that we have calculated the element frequency for. Every time we shift the left pointer, we remove the elements from the left side of the subarray from the BST. Every time we shift the right pointer, we add the new elements in the subarray to the BST.

Of course, we have to update the product accordingly. Time-complexity of this operation is . This is because each query can only be in one block and block size is . Hence, the left pointer can only move by on each query (i.e. in total) and the right pointer moves by *O*(*N*) in every block and we have blocks. Hence, right pointer moves by in total. Finally, each movement incurs an update operation in the BST which is *O*(*logN*). That proves the time-complexity for this part.

Every time we need to query the maximum product, we just query the largest element in the BST, which is *O*(*logN*).

Hence, the total time-complexity is . However, 1 ≤ *N*, *Q* ≤ 100, 000, which implies that the algorithm will perform operations in the worst case (do note that the time-limit is only 4s). I tried coding this solution and as expected, it passed all but the last subtask (which uses the largest input).

Could someone please advise me on how I could optimize my solution's time-complexity?

I am trying to solve the HackerRank problem "Bytelandian Tours".

Here is the link to the problem.

I think that the problem requires us to count the number of Hamiltonian circuits in a general graph — which is a NP-complete problem. Hence, I think that there must be some way to avoid the direct enumeration of all possible Hamiltonian circuits like what this solution did. I am unable to comprehend the author's logic though. Could someone please advise me on how to solve this problem?

Thanks in advance.

Hi. I am having problem trying to upsolve the "Max Score" problem which was used in HackerRank's Rookie Rank 3.

Here is the link to the problem.

After reading the editorial, I am puzzled why the recurrence does not consider all permutations of elements in subset(S,i) because the order in which we choose the elements in the subset also affects the overall sum.

For easier reference, I have reproduced the puzzling part of the editorial here. Credits to HackerRank for the editorial.

I tried asking in the problem's forum but I have not received any reply for more than 3 weeks. Could someone please advise me why we do not need to consider all permutations of elements?

Thanks in advance.

There is a component in the bottom right of every contest page with the heading "Contest materials". However, this component seems to be missing from the contest page of round #415 (both div 1 and 2). Link.

Is it just me or this a bug?

I am trying to solve an interactive problem from atcoder's practice contest. The abridged problem statement is as follows:

```
Given the value of N where N ranges from [1,26] and Q where Q is the maximum number of queries that one can make, sort a list of distinct uppercase alphabets in ascending order. N indicates that there are N characters starting from 'A'. Hence, N = 5 means that our final list must contain 'A', 'B', 'C', 'D' and 'E'.
A single query is defined as printing out a string "? x y" where x and y represent the characters we want to check the relation between (e.g. "? A B"). The problem restricts the number of such queries to Q. Hence, we must determine the final order of the characters using at most Q queries.
For each query, we get a binary answer '<' or '>' from stdin. '<' indicates that x comes before y in the final list. '>' means otherwise.
```

Problem link: here (Do note that atcoder account is needed to view the task)

My attempt:

I tried using merge sort to solve the problem — I changed the comparison at the merging step to get the ordering of characters using the console. I managed to solve constraints for N=26, Q=100. However, the strictest task requires a solution that fulfils the constraints N=5, Q=7.

After some research, I found that merge sort's worst case number of comparisons is n * ceil(logn) — 2^(ceil(logn)) + 1 which gives 8 in this case. I couldn't find a better sorting algorithm that would solve the problem — I even tried STL sort which proved to be worse than merge sort.

Could anyone please advise me on how I could solve this problem?

**U.D.** I just revisited this problem today. I solved it by using a single comparison to detect if there were exactly 5 elements with at most 7-comparisons. If this were true, I hard-coded a separate comparison-efficient function to handle this. Otherwise, just use merge-sort.

AC code here.

I am trying to solve an algorithmic problem that is described as follows:

There are K types of items and 2 supermarkets. Each selling all K types of items but at different prices. Please find the maximum number of unique items that can be bought given that we can spend only X dollars in supermarket 1 and Y dollars in supermarket 2.

Bounds:

1 <= K <= 2000

1 <= X, Y <= 10000Example:

K = 5, X = 6, Y = 12

Supermarket 1 (We have 6 dollars):

Type 1: 5

Type 2: 1

Type 3: 5

Type 4: 6

Type 5: 3Supermarket 2 (We have 12 dollars):

Type 1: 3

Type 2: 5

Type 3: 4

Type 4: 6

Type 5: 7In this case, the optimal answer would be 4 because we can buy item types 1 and 2 in supermarket 1, item types 3 and 4 in supermarket 2.

Problem source: here

I have interpreted it as a coin change problem where one must collect the maximum number of different denominations. Hence, I don't think that a greedy algorithm can work here (since it fails for coin change). More precisely, if one sorts the 2 item lists according to item-price pairs, it would clearly fail since one type of item may be very expensive in both lists.

The next method of my list is to use DP. But, I think DP might be too slow.

Could anyone please advise me on a better solution to solve this problem?

Edit:

I managed to solve the problem thanks to data_h and Narenji58's help in the comments. The complete solution can be found here

Once again, thanks a lot for all your help!

I am trying to solve round #383 problem D (div 2):

Problem statement:here

I can complete every step up till the usage of DP. In my code, I used 2-D DP like what was mentioned in the editorial. Somehow, my code is failing the following test case:

```
10 5 100
6 18 35 6 87 58 4 53 37 71
465782 57034 547741 748298 315223 370368 679320 349012 9740 622511
1 2
10 9
6 7
3 6
7 1
```

Expected Output: 2050129
My Program Output: 1836591

My attempt:

```
#include <iostream>
#include <vector>
#include <unordered_map>
//#define debug
using namespace std;
#define ll long long
#define v64 vector<ll>
#define um unordered_map<ll,ll>
#define mp make_pair
ll n,m,w,a,b;
typedef struct woman {
ll w, b;
} woman;
woman ww[1005];
ll par[1005], rk[1005],dp[1005][1005];
um cw, cb;
int val[1005];
ll find(ll x) {
ll p = x;
if(par[x]!=x) p = find(par[x]);
return par[x] = p;
}
inline void un(ll x,ll y) {
ll px = find(x), py = find(y);
if(px != py) {
if(rk[px] > rk[py]) {
par[py] = px;
rk[px] += rk[py];
} else {
par[px] = py;
rk[py] += rk[px];
}
}
}
ll solve(ll cur, ll t) {
if(dp[cur][t]!=-1) return dp[cur][t];
if(cur <= n && t>0) {
if(ww[cur].w<=t) {
if(val[find(cur)]) {
val[find(cur)] = 0;
ll a1 = 0;
if(cw[find(cur)]<=t) a1 = cb[find(cur)]+solve(cur+1,t-cw[find(cur)]);
ll a2 = ww[cur].b+solve(cur+1,t-ww[cur].w);
val[find(cur)] = 1;
ll a3 = solve(cur+1,t);
return dp[cur][t] = max(a1,max(a2,a3));
} else {
return dp[cur][t] = solve(cur+1,t);
}
} else {
return dp[cur][t] = solve(cur+1,t);
}
}
return dp[cur][t]=0;
}
int main(void) {
#ifdef debug
freopen("in","r",stdin);
#else
ios_base::sync_with_stdio(false);
cin.tie(0);
#endif
cin >> n >> m >> w;
fill_n(rk,n+1,1);
fill_n(val,n+1,1);
for(int i = 1; i <= n; ++i) fill_n(dp[i],w+1,-1);
for(int i = 1; i <= n; ++i) {
cin >> ww[i].w;
par[i] = i;
}
for(int i = 1; i <= n; ++i) {
cin >> ww[i].b;
}
for(int i = 1; i <= m; ++i) {
cin >> a >> b;
un(a,b);
}
for(int i = 1 ; i <= n; ++i) {
cw[find(i)] += ww[i].w;
cb[find(i)] += ww[i].b;
}
cout << solve(1,w) << endl;
return 0;
}
```

If I remove the DP (from the solve function), my program will pass the test case. Hence, it is clear that my DP is wrong. However, I do not know how to write the DP properly. Could someone please advise me on why my code is wrong?

This was the given solution for round #383 (Div 2) problem C:

The problem statement: Here

The solution:

Make a directed graph and put edge from i and crushi. If the graph has vertex such that its in-degree is 0 then obviously answer doesn't exists. Otherwise the graph consists of some cycles. For each cycle suppose that its length is len. If it has odd length, add len to S, otherwise, add len / 2.

Answer is the LCM of numbers in S.

I am unsure why the LCM is the answer. Is anyone able to advise me?

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/17/2017 06:47:30 (c4).

Desktop version, switch to mobile version.

User lists

Name |
---|