Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
There are nn climbers, numbered 1,2,…,n1,2,…,n, taking part in the sport climbing final at the olympic games and you are a fan of athlete 11.
A climbing competition features three contests, one for each discipline: speed, bouldering, and lead.
For each of the three disciplines, all the nn athletes compete in the respective contest and they are ranked, depending on their performance, from 11-st to nn-th (there are no ties).
At the end, the score of each athlete is the product of his three ranking positions. The final ranking is obtained ordering, nondecreasingly, athletes by score (e.g., the winner is the one with the smallest score). To take care of equal scores, we say that an athlete has final ranking equal to rr if there are exactly r−1r−1 other athletes with a strictly smaller score (notice that distinct athletes may have the same final ranking).
Currently the competition is ongoing. The speed and bouldering contests have finished, but only some athletes have taken part in the lead contest so the ranking for the lead is partial (i.e., only some athletes are ranked and their ranking may change as other athletes still have to compete). For example, if n=3n=3 and the current lead ranking is [3,1][3,1] (athlete 33 is first, athlete 11 is second, athlete 22 has not competed yet); the final possible lead rankings are [2,3,1][2,3,1], [3,2,1][3,2,1], and [3,1,2][3,1,2].
What is the best final ranking that athlete 11 can have at the end of the competition?
For each test case, print the best final ranking that athlete 11 can have at the end of the competition.
8
1 1
1
1
1
3 3
1 2 3
2 3 1
3 1 2
5 1
3 4 2 1 5
4 1 5 2 3
1
4 2
2 4 1 3
2 4 1 3
3 1
4 2
3 2 4 1
4 2 3 1
3 2
4 2
4 2 3 1
4 1 2 3
1 3
7 4
7 5 1 3 2 6 4
3 6 4 1 2 7 5
6 4 5 1
7 6
4 3 6 7 1 2 5
5 3 7 4 6 2 1
1 7 4 2 5 3
1
1
1
3
3
2
4
4
Explanation of test case 1: There is only athlete 11, who has already taken part in the lead contest. His ranking positions in the three contests are 11, 11, 11, hence is final score is 11 and he gets final ranking position 11.
Explanation of test case 2: There are 33 athletes and all of them have already taken part in the lead contest. Their scores are:
All the athletes have final score equal to 66, hence all of them (and in particular athlete 11) get final ranking position 11.
Explanation of test case 3 There are 55 athletes and only athlete 11 has already taken part in the lead contest. The best final ranking positions for athlete 11 is 11 and can be achieved if the lead ranking in the end is 1,2,3,4,51,2,3,4,5. With this lead ranking, the final scores of the 55 athletes would be (in order): 8,24,15,8,658,24,15,8,65. Since athlete 11 has the minimum score (tying with athlete 44), his final ranking position is 11.
Explanation of test case 4: There are 44 athletes; athletes 11 and 33 have already taken part in the lead contest with 33 being ranked first and 11 being ranked second. Let us describe some (not necessarily possible) lead rankings:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define SZ(x) ((int)((x).size()))
LL get_time() {
return chrono::duration_cast<chrono::nanoseconds>(
chrono::steady_clock::now().time_since_epoch())
.count();
}
template <typename T1, typename T2>
string print_iterable(T1 begin_iter, T2 end_iter, int counter) {
bool done_something = false;
stringstream res;
res << "[";
for (; begin_iter != end_iter and counter; ++begin_iter) {
done_something = true;
counter--;
res << *begin_iter << ", ";
}
string str = res.str();
if (done_something) {
str.pop_back();
str.pop_back();
}
str += "]";
return str;
}
template <typename S, typename T>
ostream& operator <<(ostream& out, const pair<S, T>& p) {
out << "{" << p.first << ", " << p.second << "}";
return out;
}
template <typename T>
ostream& operator <<(ostream& out, const vector<T>& v) {
out << "[";
for (int i = 0; i < (int)v.size(); i++) {
out << v[i];
if (i != (int)v.size()-1) out << ", ";
}
out << "]";
return out;
}
template<class TH>
void _dbg(const char* name, TH val){
clog << name << ": " << val << endl;
}
template<class TH, class... TA>
void _dbg(const char* names, TH curr_val, TA... vals) {
while(*names != ',') clog << *names++;
clog << ": " << curr_val << ", ";
_dbg(names+1, vals...);
}
///////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////
const int MAXN = 10010;
// AB_lead_ranking[i] = true <-> In the i-th position of the lead ranking there
// is a contestant in A.
bool AB_lead_ranking[MAXN];
int A_leq[MAXN]; // prefix sum of AB_lead_ranking
int merge_AB(int n, vector<int> B) {
int b = 0;
for (int i = 1; i <= n; i++) {
if (b < SZ(B) and B[b] <= i) AB_lead_ranking[i] = false, b++;
else AB_lead_ranking[i] = true;
}
int B_strong = 0;
for (int i = 1; i <= n; i++) {
if (AB_lead_ranking[i] and b + B_strong < SZ(B)) {
AB_lead_ranking[i] = false;
B_strong++;
}
}
for (int i = 1; i <= n; i++) A_leq[i] = A_leq[i-1] + AB_lead_ranking[i];
return B_strong;
}
// i = 1, .., n denotes a ranking position.
// x = 1, .., n denotes a contestant.
// A is the set of participants who already competed in lead.
// B is the set of participants who still have to compete in lead.
// j = 0, .., m-1 or 0, .., n-m-1 denotes an index in A or B.
int solve() {
int n, m;
cin >> n >> m;
vector<int> score(n+1, 1);
for (int _ = 0; _ < 2; _++) {
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
score[x] *= i;
}
}
vector<int> A(m);
int j1 = -1;
for (int j = 0; j < m; j++) {
cin >> A[j];
if (A[j] == 1) j1 = j;
}
if (j1 == -1) {
m++;
A.insert(A.begin(), 1);
j1 = 0;
}
vector<int> B;
vector<bool> in_A(n+1);
for (int x: A) in_A[x] = true;
for (int x = 1; x <= n; x++) if (!in_A[x]) B.push_back(x);
sort(B.begin(), B.end(), [&](int x, int y) { return score[x] > score[y]; });
int res = n;
vector<int> A_i(m);
vector<int> B_i(n-m);
for (int i1 = j1 + 1; i1 <= n-(m-1-j1); i1++) {
LL score1 = score[1] * (LL)i1;
for (int j = 0; j < m; j++) {
LL scorej = score[A[j]];
A_i[j] = min((LL)n+1, (score1 + scorej-1)/scorej);
if (j < j1) {
int i = i1 - (j1 - j);
if (A_i[j] > i) A_i[j] = n+1;
}
if (j > j1) {
int i = n-(m-1-j);
if (A_i[j] > i) A_i[j] = n+1;
}
}
for (int j = 0; j < n-m; j++) {
LL scorej = score[B[j]];
B_i[j] = min((LL)n+1, (score1 + scorej-1)/scorej);
}
// B_strong + q = # of contestants in B who rank better than 1 at the end.
int B_strong = merge_AB(n, B_i);
vector<int> A_beaten(n-m-B_strong+1);
int q1 = 0;
for (int j = 0; j < m; j++) {
int i = A_i[j];
if (i > n) continue;
int q = max(0, A_leq[i-1]-j);
if (j == j1) q1 = q;
else A_beaten[q]++;
}
for (int q = 1; q < SZ(A_beaten); q++) A_beaten[q] += A_beaten[q-1];
int ris = n;
for (int q = q1; q < SZ(A_beaten); q++) {
ris = min(ris, m + B_strong + q - A_beaten[q]);
}
res = min(res, ris);
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
for (int i = 1; i <= t; i++) {
int res = solve();
cout << res << "\n";
}
}
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define SZ(x) ((int)((x).size()))
// Returns the time elapsed in nanoseconds from 1 January 1970, at 00:00:00.
LL get_time() {
return chrono::duration_cast<chrono::nanoseconds>(
chrono::steady_clock::now().time_since_epoch())
.count();
}
template <typename T1, typename T2>
string print_iterable(T1 begin_iter, T2 end_iter, int counter) {
bool done_something = false;
stringstream res;
res << "[";
for (; begin_iter != end_iter and counter; ++begin_iter) {
done_something = true;
counter--;
res << *begin_iter << ", ";
}
string str = res.str();
if (done_something) {
str.pop_back();
str.pop_back();
}
str += "]";
return str;
}
template <typename S, typename T>
ostream& operator <<(ostream& out, const pair<S, T>& p) {
out << "{" << p.first << ", " << p.second << "}";
return out;
}
template <typename T>
ostream& operator <<(ostream& out, const vector<T>& v) {
out << "[";
for (int i = 0; i < (int)v.size(); i++) {
out << v[i];
if (i != (int)v.size()-1) out << ", ";
}
out << "]";
return out;
}
template<class TH>
void _dbg(const char* name, TH val){
clog << name << ": " << val << endl;
}
template<class TH, class... TA>
void _dbg(const char* names, TH curr_val, TA... vals) {
while(*names != ',') clog << *names++;
clog << ": " << curr_val << ", ";
_dbg(names+1, vals...);
}
#if DEBUG && !ONLINE_JUDGE
ifstream input_from_file("input.txt");
#define cin input_from_file
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#define dbg_arr(x, len) clog << #x << ": " << print_iterable(x, x+len, -1) << endl;
#else
#define dbg(...)
#define dbg_arr(x, len)
#endif
///////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////
const int MAXN = 10010;
// AB_lead_ranking[i] = true <-> In the i-th position of the lead ranking there
// is a contestant in A.
bool AB_lead_ranking[MAXN];
int A_leq[MAXN]; // prefix sum of AB_lead_ranking
int merge_AB(int n, vector<int> B) {
int b = 0;
for (int i = 1; i <= n; i++) {
if (b < SZ(B) and B[b] <= i) AB_lead_ranking[i] = false, b++;
else AB_lead_ranking[i] = true;
}
int B_strong = 0;
for (int i = 1; i <= n; i++) {
if (AB_lead_ranking[i] and b + B_strong < SZ(B)) {
AB_lead_ranking[i] = false;
B_strong++;
}
}
for (int i = 1; i <= n; i++) A_leq[i] = A_leq[i-1] + AB_lead_ranking[i];
return B_strong;
}
// i = 1, .., n denotes a ranking position.
// x = 1, .., n denotes a contestant.
// A is the set of participants who already competed in lead.
// B is the set of participants who still have to compete in lead.
// j = 0, .., m-1 or 0, .., n-m-1 denotes an index in A or B.
int solve() {
int n, m;
cin >> n >> m;
vector<int> score(n+1, 1);
for (int _ = 0; _ < 2; _++) {
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
score[x] *= i;
}
}
vector<int> A(m);
int j1 = -1;
for (int j = 0; j < m; j++) {
cin >> A[j];
if (A[j] == 1) j1 = j;
}
if (j1 == -1) {
m++;
A.insert(A.begin(), 1);
j1 = 0;
}
vector<int> B;
vector<bool> in_A(n+1);
for (int x: A) in_A[x] = true;
for (int x = 1; x <= n; x++) if (!in_A[x]) B.push_back(x);
sort(B.begin(), B.end(), [&](int x, int y) { return score[x] > score[y]; });
int res = n;
vector<int> A_i(m);
vector<int> B_i(n-m);
for (int i1 = j1 + 1; i1 <= n-(m-1-j1); i1++) {
LL score1 = score[1] * (LL)i1;
for (int j = 0; j < m; j++) {
LL scorej = score[A[j]];
A_i[j] = min((LL)n+1, (score1 + scorej-1)/scorej);
if (j < j1) {
int i = i1 - (j1 - j);
if (A_i[j] > i) A_i[j] = n+1;
}
if (j > j1) {
int i = n-(m-1-j);
if (A_i[j] > i) A_i[j] = n+1;
}
}
for (int j = 0; j < n-m; j++) {
LL scorej = score[B[j]];
B_i[j] = min((LL)n+1, (score1 + scorej-1)/scorej);
}
// B_strong + q = # of contestants in B who rank better than 1 at the end.
int B_strong = merge_AB(n, B_i);
vector<int> A_beaten(n-m-B_strong+1);
int q1 = 0;
for (int j = 0; j < m; j++) {
int i = A_i[j];
if (i > n) continue;
int q = max(0, A_leq[i-1]-j);
if (j == j1) q1 = q;
else A_beaten[q]++;
}
for (int q = 1; q < SZ(A_beaten); q++) A_beaten[q] += A_beaten[q-1];
int ris = n;
for (int q = q1; q < SZ(A_beaten); q++) {
ris = min(ris, m + B_strong + q - A_beaten[q]);
}
res = min(res, ris);
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
for (int i = 1; i <= t; i++) {
int res = solve();
cout << res << "\n";
}
}
In our experience, we suggest you solve this The Strange Ranking of Sport Climbing CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.
The Strange Ranking of Sport Climbing Problem is available on Hacker Rank for Free, if you are stuck anywhere between a compilation, just visit Queslers to get The Strange Ranking of Sport Climbing CodeChef Solution.
I hope this The Strange Ranking of Sport Climbing CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Hacker Rank, Leetcode, Codechef, Codeforce Solution.
This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.
Keep Learning!
More CodeChef Solutions >>
Olympics Ranking CodeChef Solution
Problem Difficulties CodeChef Solution
Chef and Bulb Invention CodeChef Solution