HackerEarth Starting Game development problem solution

In this HackerEarth Starting Game development problem solution Every one is now a days playing games on their smartphones for passing free time. Because of which there are number of game developing companies growing in the market. Not only that, each company is now flooding the market with a lot of games. With such a huge number of games in the market, for each company, with millions of users, keeping track of all the data and maintaining good user experience is now a big problem for them.

One of the very important aspect of building these games is the ability to maintain all the information about the user. This is a very important step in maintaining the user experience. No user would want to restart from the beginning of the game every time he/she restarts it. They would just then switch to a competitive game developer and that is not good for business.

Most of the games now have a similar structure and some of the game companies follows the logic below in their games to handle this problem:

The game has N different parameters on which a user's strength in the game is calculated. The game has a total of M different levels of play.

And hence each parameter also gets these M levels of granularity, i.e. for each parameter itself a user can be on any one of those M levels.

For each parameter, the following is done:

User's strength on the parameter is calculated.

Each of the M levels have some strength value associated with them such that the strength value grows when you move from a lower level to the higher level. It may happen that any two consecutive levels have same required strength.

If a user's strength is more than or equal to the strength value associated with a level, he/she is said to be fit to be on that level of the game for this parameter.

The level for this parameter is the maximum level for which a user satisfies the above criteria.

The level of the game a user is on, is decided from its level in all of the N parameters of the game as follows:

For each parameter, the level user is on for that parameter is computed as described above.

The level of game at which a user is the minimum of all the levels in each of the N parameters.

You are now interested in building a game for the smartphone user's as well. But before that, you would need to solve this problem effeciently. Given the strength of user's for each parameter, print the level they are on.

HackerEarth Starting Game development problem solution.

#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <vector>

using namespace std;

#define MAXN 105
#define MAXM 5005

int mat[MAXN][MAXM];
int ar[MAXN];
int M,N,Q;
    
int solve(){
    int ans = M-1;
    for(int i=0;i<N;i++){
        while(ar[i]<mat[i][ans])
            ans--;
    }
    return ans+1;
}
//O(Q*(N+M))

int main(){
    scanf("%d %d %d", &N, &M, &Q);
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++)
            scanf("%d", &mat[i][j]);
    
    //Q = 2;
    while(Q--){
        for(int i=0;i<N;i++)
            scanf("%d", &ar[i]);
        printf("%d\n", solve());
    }
    return 0;
}

Second solution

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<cassert>
using namespace std;
#define FOR(i,a,b) for(i= a ; i < b ; ++i)
#define rep(i,n) FOR(i,0,n)
#define INF INT_MAX
#define pb push_back
#define mp make_pair
#define min(a,b) ((a)<(b)?(a):(b))
#define si(n) scanf("%d",&n)
#define pin(n) printf("%d\n",n)
#define sl(n) scanf("%lld",&n)
#define scan(v,n) vector<int> v;rep(i,n){ int j;si(j);v.pb(j);}
#define mod (int)(1e9 + 7)
#define ll long long int
#define F first
#define S second
ll modpow(ll a,ll n,ll temp){ll res=1,y=a;while(n>0){if(n&1)res=(res*y)%temp;y=(y*y)%temp;n/=2;}return res%temp;} 
vector<pair<int,int> > arr[5007];
int szit[1000006],brr[1000006];
int searchit(int l, int v)
{
    int low=0,sz=arr[l].size(),high=sz-1,mid,val,val1;
    while(low<=high)
    {
        mid=(low+high)/2;
        val=arr[l][mid].F;
        if(mid!=sz-1)
            val1=arr[l][mid+1].F;
        else
            val1=mod;
        if(val<=v && val1>v)
            return arr[l][mid].S;
        else if(v>=val)
            low=mid+1;
        else
            high=mid-1;
    }
    return 0;
}
int main()
{
    int n,m,q,ans,val,i,j,sz,cnt,ans1,calc;
    si(n);
    si(m);
    si(q);
    assert(n>=1 && n<=100);
    assert(m>=1 && m<=5000);
    assert(q>=1 && q<=5000);
    rep(i,n)
    {
        rep(j,m)
        {
            si(val);
            assert(val>=1 && val<=mod);
            brr[j]=val;
        }
        arr[i].pb(mp(brr[0],1));
        FOR(j,1,m)
        {
            if(brr[j]>=brr[j-1])
                arr[i].pb(mp(brr[j],j+1));
            else 
                break;
        }
        sort(arr[i].begin(),arr[i].end());
    }
    rep(i,q)
    {
        ans=mod;
        rep(j,n)
        {
            si(val);
            //Searching for the maximum level which has value <= val
            calc=searchit(j,val);
            //Taking the minimum of all maximum values as specified in the question
            ans=min(ans,calc);
        }
        pin(ans);
    }
    return 0;
}