Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
The Strange Ranking of Sport Climbing CodeChef Solution – Queslers
Problem: The Strange Ranking of Sport Climbing CodeChef Solution
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?
Input Format
- First line contains tt — the number of test cases. Then the test cases follow.
- The first line of each test case contains the two integers n,mn,m — the number of climbers and the number of climbers who have already taken part in the lead contest.
- The second line contains nn integers s1,s2,…,sns1,s2,…,sn — the ranking of the speed contest. In particular sisi is the athlete who ranked ii-th in the speed contest.
- The third line contains nn integers b1,b2,…,bnb1,b2,…,bn — the ranking of the bouldering contest. In particular bibi is the athlete who ranked ii-th in the bouldering contest.
- The fourth line contains mm integers l1,l2,…,lml1,l2,…,lm — the current ranking of the lead contest. In particular lili is the athlete who is currently ranked ii-th in the lead contest.
Output Format
For each test case, print the best final ranking that athlete 11 can have at the end of the competition.
Constraints
- 1≤t≤50001≤t≤5000
- 1≤m≤n≤50001≤m≤n≤5000
- The sum of nn over all test cases is at most 50005000.
- The array s1,s2,…,sns1,s2,…,sn is a permutation of 1,2,…,n1,2,…,n.
- The array b1,b2,…,bnb1,b2,…,bn is a permutation of 1,2,…,n1,2,…,n.
- 1≤li≤n1≤li≤n for all i=1,2,…,mi=1,2,…,m.
- li≠ljli≠lj for all 1≤i<j≤m1≤i<j≤m.
Sample Input 1
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
Sample Output 1
1
1
1
3
3
2
4
4
Explanation
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:
- Athlete 11 has final score of 1⋅3⋅2=61⋅3⋅2=6. Indeed his speed ranking is 11, his bouldering ranking is 33, and his lead ranking is 22.
- Athlete 22 has final score of 2⋅1⋅3=62⋅1⋅3=6. Indeed his speed ranking is 22, his bouldering ranking is 11, and his lead ranking is 33.
- Athlete 33 has final score of 3⋅2⋅1=63⋅2⋅1=6. Indeed his speed ranking is 33, his bouldering ranking is 22, and his lead ranking is 11.
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:
- The lead ranking 1,3,2,41,3,2,4 is impossible since it is not consistent with the current lead ranking (athlete 11 and 33 appear in a different order in the current ranking).
- The lead ranking 3,1,2,43,1,2,4 is consistent with the current lead ranking. In this case, the final scores of the athletes would be (in order) 18,3,16,1618,3,16,16; hence athlete 11 would get final ranking equal to 44 (that is, he would be last).
- The lead ranking 2,4,3,12,4,3,1 is consistent with the current lead ranking. In this case, the final scores of the athletes would be (in order) 36,1,48,836,1,48,8; hence athlete 11 would get final ranking equal to 33 (and this is the best possible final ranking).
The Strange Ranking of Sport Climbing CodeChef Solution in C++14
#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";
}
}
The Strange Ranking of Sport Climbing CodeChef Solution in C++17
#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";
}
}
The Strange Ranking of Sport Climbing CodeChef Solution Review:
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.
Conclusion:
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
