CRYPTCEPT - Editorial

Problem Statement
Contest Source

Author, Tester and Editorialist : Rohail Alam

DIFFICULTY:

Easy

PREREQUISITES:

Knowledge of Implementation in preferred language

PROBLEM:

Given the timer values of initially present Miners, find out the total miners (i.e Cloned + Initial Miners) after a given number of days.

QUICK EXPLANATION:

Instead of individually updating the timer value of each miner for every day, it would be a lot faster to track the number of miners with the timer value of X.

EXPLANATION:

You might have noticed that if you simply iterate through the timer values of all miners, decremented them and if required, append the timer array, you would end up getting a Time Limit Exceeded (TLE) Verdict. With that, you may have understood that the number of miners increase on an exponential manner.
As suggested in the quick explanation, it will be a lot faster if we just classified the miners based on their timer values.

Assume that the number of miners with the timer value of X be denoted as Timer_X.
With each passing day, the following statements hold:

  • Timer_{X-1} = Timer_X (where X \neq 1)
  • Timer_{10} = Timer_{10} + Timer_{1} (As the timers are reset)
  • Timer_{15} = Timer_{1} (As the cloned miners have a timer value of 15)

Carrying out the above three operations for each day will yield you the final answer, which will just be the sum of all miners having timer values from 1 to 15.

COMPLEXITY ANALYSIS:

O(D*15) where D is the number of Days entered by the user.

SOLUTION:

C++ Solution
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007

int main(){
    int t;
    cin>>t;
    while(t--){
	    int n;
	    cin>>n;
	    int d;
	    cin>>d;
	    map<int,int> timer;
		
	    for(int i = 0; i<n; ++i){
		    int val;
		    cin>>val;
		    timer[val]++;
	    }
	    for(int days=0;days<d;++days){
		    int temp = timer[1];    // Storing the value of timer[1] before it gets updated
		    for(int X=2;X<=15;++X){
			    timer[X-1] = timer[X];
		    }
		    timer[10] += temp;
		    timer[15] = temp;
	    }
	
	    int ans = 0;
	    for(auto x:timer){
		    ans+=x.second;
	    }
	    ans%=mod;
	    cout<<ans<<endl;
    }
}
Python Solution
t = int(input())
while(t>0):
    t-=1
    n,d = map(int,input().split())
    a = list(map(int,input().split()))
    timer = {}
    for i in range(1,16):
        timer[i] = 0
    for x in a:
        timer[x]+=1
        
    for _ in range(d):
        temp = timer[1]
        for X in range(2,16):
           timer[X-1] = timer[X]
        timer[10] += temp
        timer[15] = temp
    
    print(sum(timer.values())%1000000007)