Multiple Games Solution Codechef

by

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

February Long Challenge 2021

Leave a Comment