Page Contents
Multiple Games Solution February Challenge 2021
You are given a strictly increasing sequence of positive integers A1,A2,…,ANA1,A2,…,AN. It is also guaranteed that for each valid ii, Ai+A1≥Ai+1Ai+A1≥Ai+1.
Alice and Bob want to play QQ independent games using this sequence. Before they play these games, Alice should choose a positive integer GG between 11 and MM (inclusive). The rules of each game are as follows:
- There is a set SS of positive integers representing allowed moves in this game. For each valid ii, in the ii-th game, this set is S={ALi,ALi+1,…,ARi}S={ALi,ALi+1,…,ARi} (in other words, given by a contiguous subsequence of AA).
- The game is played with a single pile. Let’s denote the number of objects in this pile by PP. At the beginning of the game, P=GP=G. In other words, Alice and Bob play all the games with the same initial number of objects that Alice chooses.
- The players alternate turns; Alice plays first.
- In each turn, the current player must choose a positive integer bb from the set SS such that b≤Pb≤P and remove bb objects from the pile, i.e. change PP to P−bP−b.
- When the current player cannot choose any such integer bb, this player loses this game.
Both players play optimally. You need to find the maximum number of games Alice can win if she chooses GG optimally.
Also See: February Long Challenge 2021 Solutions
Input
- The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
- The first line of each test case contains three space-separated integers NN, QQ and MM.
- The second line contains NN space-separated integers A1,A2,…,ANA1,A2,…,AN.
- QQ lines follow. For each valid ii, the ii-th of these lines contains two space-separated integers LiLi and RiRi.
Output
For each test case, print a single line containing one integer ― the maximum number of games Alice can win.
Constraints
- 1≤T≤501≤T≤50
- 1≤N,Q,M≤2⋅1051≤N,Q,M≤2⋅105
- 1≤Ai≤1081≤Ai≤108 for each valid ii
- Ai+A1≥Ai+1>AiAi+A1≥Ai+1>Ai for each valid ii
- 1≤Li≤Ri≤N1≤Li≤Ri≤N for each valid ii
- the sum of NN over all test cases does not exceed 2⋅1052⋅105
- the sum of QQ over all test cases does not exceed 2⋅1052⋅105
- the sum of MM over all test cases does not exceed 2⋅1052⋅105
Subtasks
Subtask #1 (5 points):
- N,Q,M≤400N,Q,M≤400
- the sum of NN over all test cases does not exceed 400400
- the sum of QQ over all test cases does not exceed 400400
- the sum of MM over all test cases does not exceed 400400
Subtask #2 (30 points):
- N,Q,M≤5,000N,Q,M≤5,000
- the sum of NN over all test cases does not exceed 5,0005,000
- the sum of QQ over all test cases does not exceed 5,0005,000
- the sum of MM over all test cases does not exceed 5,0005,000
Subtask #3 (65 points): original constraints
Example Input
1 3 2 10 2 3 4 1 2 2 3
Example Output
2
Explanation
Example case 1: The set of allowed moves in the first game is S={2,3}S={2,3} and in the second game, it is S={3,4}S={3,4}. If Alice chooses G=3G=3, she can win both
Follow us on telegram for quick update an abundance of free knowledge: Click Here
Solution
Program C:
#include <stdio.h> int main(void) { int t; scanf("%d",&t); while(t--) { long long int n,q,m; scanf("%lld %lld %lld",&n,&q,&m); long long int a[n],b[q][2],i,x=999999999; for(i=0;i<n;i++) { scanf("%lld",&a[i]); } for(i=0;i<q;i++) { long long int l,r; scanf("%lld %lld",&l,&r); l--;r--; b[i][0]=l; b[i][1]=r; if(x>l) x=l; } long long int maxi=0; for(i=a[x];i<=m;i++) { long long int t=0,j; for(j=0;j<q;j++) { if(i%(a[b[j][1]]+a[b[j][0]])>=a[b[j][0]]) t++; } if(maxi<t) maxi=t; if(maxi==q) break; } printf("%lld\n",maxi); } return 0; }
Program C++:
#include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int test=1; cin>>test; while(test--) { int n,q,m; cin>>n>>q>>m; int a[n]; for(int i=0;i<n;i++) cin>>a[i]; int b[1000001]={}; map<pair<int,int>,int>mp; while(q--) { int l,r; cin>>l>>r; --l; --r; if(a[l]>m) continue; else if(a[l]<=m && a[r]>m) { b[a[l]]++; b[m+1]--; } else if(a[r]<=m) { b[a[l]]++; b[m+1]--; mp[{a[l],a[r]}]++; } } for(auto x:mp) { int k=x.first.first; int p=x.first.second; int l=x.second; b[p+k]-=l; b[p+2*k]+=l; int c=p+2*k; while(c+p<=m) { c+=p; b[c]-=l; b[c+k]+=l; c+=k; } } int mx=0; for(int i=1;i<=m;i++) { b[i]+=b[i-1]; mx=max(mx,b[i]); } cout<<mx<<endl; } return 0; }
Program Java:
import java.util.*; import java.lang.*; import java.io.*; class Codechef { public static int solve(BufferedReader br) throws Exception { String[] st = br.readLine().split(" "); int n = Integer.parseInt(st[0]); int q = Integer.parseInt(st[1]); int m = Integer.parseInt(st[2]); st = br.readLine().split(" "); int[] arr = new int[n+1]; for(int i = 1; i <= n; i++) arr[i] = Integer.parseInt(st[i-1]); int l, r; int[] range = new int[1000001]; HashMap<String, Integer> map = new HashMap<>(); while(q-- > 0) { st = br.readLine().split(" "); l = Integer.parseInt(st[0]); r = Integer.parseInt(st[1]); if(arr[l] > m) continue; if(arr[l] <= m && m < arr[r]) { range[arr[l]]++; range[m+1]--; } else { range[arr[l]]++; range[m+1]--; String s = arr[l] + " " + arr[r]; map.put(s, map.getOrDefault(s, 0)+1); } } int v, x; for(Map.Entry<String, Integer> e : map.entrySet()) { st = e.getKey().split(" "); l = Integer.parseInt(st[0]); r = Integer.parseInt(st[1]); v = e.getValue(); range[r + l] -= v; range[r + 2 * l] += v; x = r + 2 * l; while(x+r <= m) { x += r; range[x] -= v; range[x + l] += v; x += l; } } int max = 0; for(int i = 1; i <= m; i++) { range[i] += range[i-1]; max = Math.max(max,range[i]); } return max; } public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int t = Integer.parseInt(br.readLine()); StringBuilder sb = new StringBuilder(); while(t-- > 0) sb.append(solve(br)+"\n"); System.out.print(sb.toString()); } }
Program Python:
t=int(input()) for _ in range(t): d={} n,q,m=(map(int, input().split())) a=list(map(int, input().split())) lb=[0]*(m+1) ub=[0]*(m+1) ans=0 for __ in range(q): l,r=(map(int, input().split())) x=d.get((a[l-1],a[r-1]),0) x=x+1 d[(a[l-1],a[r-1])]=x d1=list(d.keys()) for i in range(len(d1)): lv=d1[i][0] rv=min(m,d1[i][0]+d1[i][1]-1) if(rv>=lv): ub[rv]+=d[d1[i]] lb[lv]+=d[d1[i]] while(lv+d1[i][0]+d1[i][1]<=m): lnv=lv+d1[i][0]+d1[i][1] rnv=min(m,rv+d1[i][0]+d1[i][1]) ub[rnv]+=d[d1[i]] lb[lnv]+=d[d1[i]] rv=rnv lv=lnv temp=ans=lb[0] for i in range(1,m+1): temp+=lb[i]-ub[i-1] ans=max(ans,temp) print(ans)
Codechef Long Challenges
September Long Challenge 2021 Solution
- Airline Restrictions
- Travel Pass
- Shuffling Parities
- XOR Equal
- 2-D Point Meeting
- Minimize Digit Sum
- Minimum Digit Sum 2
- Treasure Hunt
- Covaxin vs Covishield
February Long Challenge 2021
- Frog Sort Solution Codechef
- Chef and Meetings Solution Codechef
- Maximise Function Solution Codechef
- Highest Divisor Solution Codechef
- Cut the Cake Challenge Solution Codechef
- Dream and the Multiverse Solution Codechef
- Cell Shell Solution Codechef
- Multiple Games Solution Codechef
- Another Tree with Number Theory Solution Codechef
- XOR Sums Solution Codechef
- Prime Game Solution CodeChef
- Team Name Solution Codechef
- Bash Matrix Solution CodeChef