LETITRIP Editorial

PROBLEM LINK:

Let It Rip!
iiitv.str() 4.0

Author: kalash04
Editorialist: kalash04

DIFFICULTY:

MEDIUM-HARD

PROBLEM:

It’s time for the Beyblade World Tournament. To keep the tournament interesting for the viewers, the World Beyblade Battle Association has decided to keep the match format as follows:

  • Each team can register n beys for the tournament.
  • In each match, x rounds will take place so each team has to choose x beys before the match.
  • A team wins a match if it wins all individual rounds, else it is tied.
  • To make matters more interesting for the viewers, for both teams, beys once chosen for a match are sorted in order of power and paired up against opponent’s beys in order.

Team GanGan Galaxy needs to win this time to qualify for the finals, but their next match up is an anonymous team which is supposed to be stronger than them. Madoka arrives at the match location at the end moment with crucial secretive information about the beys of the opponent. Help her calculate for each query, the total number of ways of choosing the beys so that they can win modulo 10^9 + 7

Prerequisites:

  • Knowledge of Dynamic Programming and state transitions.
  • Basic Hash maps

EXPLANATION:

We need to count the number of ways of choosing the beys so that they can win. Here winning was defined as winning all individual rounds when the beys are paired with the opponent in order of power. So we can directly sort the input beys according to power.

To count the number of ways, we can use dynamic programming.

Here we define our dp vector, in which for the state dp[i][j][k], i stands for the i-th index in the GanGan Galaxy bey array and j stands for the j-th index in the opponent bey array and k stands for the number of left beys to choose.

So according to the conditions given the questions, we define our dp transition to be:

Show

dp[i][j][k] = dp[i][j - 1][k] + dp[i - 1][j][k] - dp[i - 1][j - 1][k]

If the power of the i-th GanGan Galaxy bey is more than that of the j-th opponent then we need to add dp[i - 1][j - 1][k - 1] to the answer because now we have a choice whether or not to take the current bey and if we do then we will be left with only k - 1 beys to choose.

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
using ll = long long;
using ld = long double;
#define int long long int
#define debug(x) cout << #x << " : " << x << endl;
#define debug2(x) cout << #x << " : "; for(auto i : x) cout << i << " "; cout << "\n";
int MOD = 1e9 + 7;
ld PI = 3.14159265358979323846;

void solve() {
 int n, b, q;
 cin >> n >> b >> q;
 vector<string> gangangalaxy(n), anonymous(n);
 map<string, int> beypower;
 vector<int> queries(q);
 for(string &bey : gangangalaxy) cin >> bey;
 for(string &bey : anonymous) cin >> bey;
 for(int i = 0; i < b; i++) {
   string bey; int power;
   cin >> bey >> power;
   beypower[bey] = power;
 }
 for(int i = 0; i < q; i++) cin >> queries[i];

 sort(gangangalaxy.begin(), gangangalaxy.end(), [&](string a, string b) {
   return beypower[a] > beypower[b];
 });
 sort(anonymous.begin(), anonymous.end(), [&](string a, string b) {
   return beypower[a] > beypower[b];
 });

vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1)));
 for(int i = 0; i <= n; i++)
   for(int j = 0; j <= n; j++)
     dp[i][j][0] = 1;
 for(int i = 1; i <= n; i++) {
   for(int j = 1; j <= n; j++) {
     for(int k = 1; k <= n; k++) {
       dp[i][j][k] = dp[i][j - 1][k] + dp[i - 1][j][k] - dp[i - 1][j - 1][k];
       if(beypower[gangangalaxy[i - 1]] > beypower[anonymous[j - 1]]) 
         dp[i][j][k] += dp[i - 1][j - 1][k - 1];
       dp[i][j][k] = (dp[i][j][k] % MOD + MOD) % MOD;
     }
   }
 }
 for(int i = 0; i < q; i++) {
   cout << dp[n][n][queries[i]] << endl;
 }
}

int32_t main() {
 ios_base::sync_with_stdio(false);
 cin.tie(NULL);
 cout.tie(NULL);
 #ifndef ONLINE_JUDGE
   freopen("test.in", "r", stdin);
   freopen("test.out", "w", stdout);
 #endif
 solve();
}
1 Like