Hack Lockdown 1.0 Editorials

Hello everyone!

Thank you for participating in the contest. I hope you liked the contest.
For those who had any problem will now be able to understand after reading the editorials.

  1. LOGIC

A simple approach which can be understood by the sample is that is that n=5 and ouput = 15 = (n x 3) = (n x (6-1)/2) or (n x ceil(n/2)) and for n = 10 , output = 50 = (n x 5) = n x n//2 or n x ceil(n/2).

So only check that n is even or odd else print n x Preformatted textceil(n/2).

Solution (Python 3)

> t = int(input())
> for i in range(t):
>     if n%2==0:                                 OR    Just print(n x math.ceil(n/2))
>        print(n x n//2)
>     else:
>        print(n x (n+1)//2)
  1. SMVOL

In case the original cube had side length more than 1, you’ll end up with cube having side length N-2 (for 1 this formula gives you -1, while you obviously can’t have cube with negative side length as a result). So you problem turns into finding difference between volume of these two cubes. Only tricky part here is - volume of a cube will be too big even for 64-bit data type. Now there are several possible approaches.

You can write down formula N x N x N-(N-2) x (N-2) x (N-2) and see that multiplier at NxNxN is equal to 0, therefore your result is O(N x N), and after finding exact formula you can avoid any overflows. You can use the fact that aaa - b x b x b =(a-b) x (axa+bxb+axb).

Another way to handle it is to use __int128 in C++. Or you can go even further and try BigInteger in Java… Or use python :slight_smile:

And the last one is to do all calculations in 64-bit data type, in case it is going to work fine in your programming language. You are only interested in correct final value, not in correct intermediate results. For example, in C++ you are not formally guaranteed that all overflow calculations are going to work fine, but in practice at any modern compiler they work just like you are working with modulo, therefore if you’ll calculate both volumes as long long - you’ll have their result modulo long long, and therefore their difference will give you correct value.

Solution (Python 3)

t=int(input())
for _ in range(t):
    n=int(input())
    if n==1 or n==2:
        print(n x n x n)
    else:
        print(n x n x n-(n-2) x (n-2) x (n-2))

[quote="sethhritik, post:1, topic:66461, full:true"]

Hello everyone!

Thank you for participating in the contest. I hope you liked the contest.
For those who had any problem will now be able to understand after reading the editorials.

  1. LOGIC

A simple approach which can be understood by the sample is that is that n=5 and ouput = 15 = (n x 3) = (n x (6-1)/2) or (n x ceil(n/2)) and for n = 10 , output = 50 = (n x 5) = n x n//2 or n x ceil(n/2).

So only check that n is even or odd else print n x Preformatted textceil(n/2).

Solution (Python 3)

> t = int(input())
> for i in range(t):
>     if n%2==0:                                 OR    Just print(n x math.ceil(n/2))
>        print(n x n//2)
>     else:
>        print(n x (n+1)//2)
  1. SMVOL

In case the original cube had side length more than 1, you’ll end up with cube having side length N-2 (for 1 this formula gives you -1, while you obviously can’t have cube with negative side length as a result). So you problem turns into finding difference between volume of these two cubes. Only tricky part here is - volume of a cube will be too big even for 64-bit data type. Now there are several possible approaches.

You can write down formula N x N x N-(N-2) x (N-2) x (N-2) and see that multiplier at NxNxN is equal to 0, therefore your result is O(N x N), and after finding exact formula you can avoid any overflows. You can use the fact that aaa - b x b x b =(a-b) x (axa+bxb+axb).

Another way to handle it is to use __int128 in C++. Or you can go even further and try BigInteger in Java… Or use python :slight_smile:

And the last one is to do all calculations in 64-bit data type, in case it is going to work fine in your programming language. You are only interested in correct final value, not in correct intermediate results. For example, in C++ you are not formally guaranteed that all overflow calculations are going to work fine, but in practice at any modern compiler they work just like you are working with modulo, therefore if you’ll calculate both volumes as long long - you’ll have their result modulo long long, and therefore their difference will give you correct value.

Solution (Python 3)

    t=int(input())
    for _ in range(t):
        n=int(input())
        if n==1 or n==2:
            print(n x n x n)
        else:
            print(n x n x n-(n-2) x (n-2) x (n-2))
  1. MINIST
An easy approach to calculate total installments is to simply update the lent money information and then calculate the **number of installments**.

n,m = map(int,input().split(" "))
 
a = [0 for i in range(n+1)]

//updating money lended m times 

for k in range(m):
    i,j,t = map(int, input().split(" "))
    a[i] += t
    a[j] -= t
 
 
debt = 0

//since anyone can pay any of his friends, so just add the debts/installments.

for i in a:
    if(i>0):
        debt = debt + i
 
print(debt)
  1. HAPSET

Consider the given array to be sorted in non-decreasing order. Now, Assume you want to find out for each i, the number of good subsets in which integer A[i] is present as the minimum element of that subset. The maximum in such a good subset will never exceed A[i] + X.

So, we can binary search over this array for each i, to find the maximum index j, such that A[j]<=A[i] + X . Now any subset that includes A[i] and any other arbitary elements from the range will be a good subset.

Why is that? As element A[i] is the minimum of that subset, and the difference between any other element and A[i] is <=X.

Solution (Python 3)

def main():
	# this function calculates (a^b)%modulo
	def pow (a,b):
		ans = 1
		while(b!=0):
			if((b&1) == 1):
				ans *= a
				ans %= modulo
			a *= a
			a %= modulo
			b>>=1
		return ans
 
	def InverseEuler(n):
		return pow(n,modulo-2)
 
	def nCr(n,r):
		return (fact[n]*((ifact[r] * ifact[n-r]) % modulo)) % modulo
 
	# calculation of factorials from 1 to number with modulo
	def factorial_of_n(number):
		fact=[1]*(number)
		for i in range(1,number):
			fact[i]=(i*fact[i-1])%modulo
		return fact
 
	def ifactorial_of_n(number):
		ifact=[1]*(number)
		ifact[-1]=InverseEuler(fact[-1])
		for i in range(number-2,-1,-1):
			ifact[i]=(ifact[i+1]*(1+i))%modulo
		return ifact
 
	# intialize variables
	pointer=0;count=0;answer=0;modulo=(10**9)+7
 
	# taking input
	N,K,X = map(int,input().split())
	arr = [int(z) for z in input().split()]
	fact=factorial_of_n(N)
	ifact=ifactorial_of_n(N)
 
	# sorting the array
	arr.sort()
 
	while(pointer<N):
 
		while((count<N) and ((arr[count]-arr[pointer]) <= X)):
			count+=1
		count -= 1
		if(count-pointer>=K-1):
			# calulate K-1 combinations of counted elements
			# K-1 because one element is fixed
			answer=(answer+nCr(count-pointer,K-1))%modulo
		# fix pointer on next element till pointer<N
		pointer+=1
 
 
	print (answer)
 
main()

Now we want to find the number of good subsets of size K. This will be (j-iChooseK) . The final answer will be the sum of this procedure for each i.

  1. SIMNUM

An easy solution to solve this problem is to build a Suffix Array on string S. If you do not know what a Suffix Array is, here is a very good tutorial.

Given a string S, by building a suffix array on S, we can:

  1. Efficiently “sort” all its suffixes.
  2. Know the LCP(longest common prefix) of any two suffixes.

For this particular problem a Suffix Array is overkill, but it works. :slight_smile:

Solution (C++14)

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main() {
  int t;
  cin >> t;
  string s;
  while (t--) {
    cin >> s;
    ll len = s.size();
    int z[len] = {0};
    int left = 0, right = 0;
    for (int i = 1; i < len; i++) {
      if (i > right) {
        left = right = i;
        while (right < len and (s[right] == s[right - left]))
          right++;
        z[i] = right - left;
        right--;
      } else {
        int k = i - left; // do a mistake here.
        if (z[k] < (right - i + 1)) {
          z[i] = z[k];
        } else {
          left = i;
          while (right < len and (s[right] == s[right - left]))
            right++;
          z[i] = right - left;
          right--;
        }
      }
    }
    cout << accumulate(z, z + len, len) << endl;
  }
}
  1. INDMOV

    #include<bits/stdc++.h>
    using namespace std;
    vector<vector > multiply(vector<vector > a,vector<vector > b)
    {
    int i,j,k;
    int r1=a.size();
    int r2=b.size();
    int c1=a[0].size();
    int c2=b[0].size();

    vector<vector<bool> > c(r1,vector<bool> (c2));
    for(i=0;i<r1;i++)
      {
      	for(j=0;j<c2;j++)
      	  {
      	  	for(k=0;k<r2;k++)
      	  	  {
      	  	  	 if(a[i][k]&&b[k][j])
      	  	  	 	c[i][j]=true;
      	  	  }
      	  }
      }
    return c;
    

    }
    vector<vector > pow(vector<vector > a,long long n)
    {
    if(n==0)
    {
    //will not go here;
    assert(0);
    return a;
    }
    if(n==1)
    return a;
    vector<vector > b=pow(a,n/2);
    b=multiply(b,b);
    if(n%2)
    b=multiply(a,b);
    return b;
    }
    vector getFactors(int x)
    {
    vector fact;
    if(x%2==0)
    {
    fact.push_back(2);
    while(x%2==0)
    x/=2;
    }
    for(int i=3;i*i<=x;i+=2)
    {
    if(x%i==0)
    {
    fact.push_back(i);
    while(x%i==0)
    x/=i;
    }
    }
    if(x!=1)
    fact.push_back(x);
    return fact;
    }
    void eval()
    {
    int n;
    cin>>n;
    vector a(n);
    for(int i=0;i<n;i++)
    cin>>a[i];
    int moves;
    cin>>moves;

    vector<vector<bool> > mat(n, vector<bool>(n));
    vector<vector<bool> > graph(1, vector<bool>(n));
    graph[0][0]=1;
    
    for(int i=0;i<n-1;i++)
     {
    	vector<int> factors = getFactors(a[i]);
    	for(int j=0;j<factors.size();j++)
    		{
    			int x = factors[j];
    		//	cout<<"factor of "<<a[i]<<" is "<<x<<endl;
    			if(i-x>=0)
    				mat[i][i-x]=1;
    			if(i+x<n)	//less than n-1
    				mat[i][i+x]=1;
    		}
     }
    

    /*
    for(int i=0;i<graph.size();i++)
    {
    for(int j=0;j<graph[0].size();j++)
    cout<<graph[i][j]<<" “;
    cout<<endl;
    }
    cout<<endl;
    for(int i=0;i<mat.size();i++)
    {
    for(int j=0;j<mat[0].size();j++)
    cout<<mat[i][j]<<” ";
    cout<<endl;
    }

    cout<<endl;*/
    mat = pow(mat, moves);
    

    /* for(int i=0;i<mat.size();i++)
    {
    for(int j=0;j<mat[0].size();j++)
    cout<<mat[i][j]<<" ";
    cout<<endl;
    }

    cout<<endl;
    

    */
    graph = multiply(graph,mat);

    /*
    for(int i=0;i<graph.size();i++)
    {
    for(int j=0;j<graph[0].size();j++)
    cout<<graph[i][j]<<" ";
    cout<<endl;
    }
    */

    if(graph[0][n-1]==1)
    	cout<<"YES\n";
    else
    	cout<<"NO\n";
    

    }
    int main()
    {
    // freopen(“in00.txt”,“r”,stdin);
    int t;
    cin>>t;
    while(t–)
    {
    eval();
    }
    }
    [/quote]

    n,m = map(int,input().split(" "))

    a = [0 for i in range(n+1)]

    //updating money lended m times

    for k in range(m):
    i,j,t = map(int, input().split(" "))
    a[i] += t
    a[j] -= t

    debt = 0

    //since anyone can pay any of his friends, so just add the debts/installments.

    for i in a:
    if(i>0):
    debt = debt + i

    print(debt)

  2. HAPSET

Consider the given array to be sorted in non-decreasing order. Now, Assume you want to find out for each i, the number of good subsets in which integer A[i] is present as the minimum element of that subset. The maximum in such a good subset will never exceed A[i] + X.

So, we can binary search over this array for each i, to find the maximum index j, such that A[j]<=A[i] + X . Now any subset that includes A[i] and any other arbitary elements from the range will be a good subset.

Why is that? As element A[i] is the minimum of that subset, and the difference between any other element and A[i] is <=X.

Solution (Python 3)

def main():
	# this function calculates (a^b)%modulo
	def pow (a,b):
		ans = 1
		while(b!=0):
			if((b&1) == 1):
				ans *= a
				ans %= modulo
			a *= a
			a %= modulo
			b>>=1
		return ans
 
	def InverseEuler(n):
		return pow(n,modulo-2)
 
	def nCr(n,r):
		return (fact[n]*((ifact[r] * ifact[n-r]) % modulo)) % modulo
 
	# calculation of factorials from 1 to number with modulo
	def factorial_of_n(number):
		fact=[1]*(number)
		for i in range(1,number):
			fact[i]=(i*fact[i-1])%modulo
		return fact
 
	def ifactorial_of_n(number):
		ifact=[1]*(number)
		ifact[-1]=InverseEuler(fact[-1])
		for i in range(number-2,-1,-1):
			ifact[i]=(ifact[i+1]*(1+i))%modulo
		return ifact
 
	# intialize variables
	pointer=0;count=0;answer=0;modulo=(10**9)+7
 
	# taking input
	N,K,X = map(int,input().split())
	arr = [int(z) for z in input().split()]
	fact=factorial_of_n(N)
	ifact=ifactorial_of_n(N)
 
	# sorting the array
	arr.sort()
 
	while(pointer<N):
 
		while((count<N) and ((arr[count]-arr[pointer]) <= X)):
			count+=1
		count -= 1
		if(count-pointer>=K-1):
			# calulate K-1 combinations of counted elements
			# K-1 because one element is fixed
			answer=(answer+nCr(count-pointer,K-1))%modulo
		# fix pointer on next element till pointer<N
		pointer+=1
 
 
	print (answer)
 
main()

Now we want to find the number of good subsets of size K. This will be (j-iChooseK) . The final answer will be the sum of this procedure for each i.

  1. SIMNUM

An easy solution to solve this problem is to build a Suffix Array on string S. If you do not know what a Suffix Array is, here is a very good tutorial.

Given a string S, by building a suffix array on S, we can:

  1. Efficiently “sort” all its suffixes.
  2. Know the LCP(longest common prefix) of any two suffixes.

For this particular problem a Suffix Array is overkill, but it works. :slight_smile:

Solution (C++14)

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main() {
  int t;
  cin >> t;
  string s;
  while (t--) {
    cin >> s;
    ll len = s.size();
    int z[len] = {0};
    int left = 0, right = 0;
    for (int i = 1; i < len; i++) {
      if (i > right) {
        left = right = i;
        while (right < len and (s[right] == s[right - left]))
          right++;
        z[i] = right - left;
        right--;
      } else {
        int k = i - left; // do a mistake here.
        if (z[k] < (right - i + 1)) {
          z[i] = z[k];
        } else {
          left = i;
          while (right < len and (s[right] == s[right - left]))
            right++;
          z[i] = right - left;
          right--;
        }
      }
    }
    cout << accumulate(z, z + len, len) << endl;
  }
}
  1. INDMOV

    #include<bits/stdc++.h>
    using namespace std;
    vector<vector > multiply(vector<vector > a,vector<vector > b)
    {
    int i,j,k;
    int r1=a.size();
    int r2=b.size();
    int c1=a[0].size();
    int c2=b[0].size();

    vector<vector<bool> > c(r1,vector<bool> (c2));
    for(i=0;i<r1;i++)
      {
      	for(j=0;j<c2;j++)
      	  {
      	  	for(k=0;k<r2;k++)
      	  	  {
      	  	  	 if(a[i][k]&&b[k][j])
      	  	  	 	c[i][j]=true;
      	  	  }
      	  }
      }
    return c;
    

    }
    vector<vector > pow(vector<vector > a,long long n)
    {
    if(n==0)
    {
    //will not go here;
    assert(0);
    return a;
    }
    if(n==1)
    return a;
    vector<vector > b=pow(a,n/2);
    b=multiply(b,b);
    if(n%2)
    b=multiply(a,b);
    return b;
    }
    vector getFactors(int x)
    {
    vector fact;
    if(x%2==0)
    {
    fact.push_back(2);
    while(x%2==0)
    x/=2;
    }
    for(int i=3;i*i<=x;i+=2)
    {
    if(x%i==0)
    {
    fact.push_back(i);
    while(x%i==0)
    x/=i;
    }
    }
    if(x!=1)
    fact.push_back(x);
    return fact;
    }
    void eval()
    {
    int n;
    cin>>n;
    vector a(n);
    for(int i=0;i<n;i++)
    cin>>a[i];
    int moves;
    cin>>moves;

    vector<vector<bool> > mat(n, vector<bool>(n));
    vector<vector<bool> > graph(1, vector<bool>(n));
    graph[0][0]=1;
    
    for(int i=0;i<n-1;i++)
     {
    	vector<int> factors = getFactors(a[i]);
    	for(int j=0;j<factors.size();j++)
    		{
    			int x = factors[j];
    		//	cout<<"factor of "<<a[i]<<" is "<<x<<endl;
    			if(i-x>=0)
    				mat[i][i-x]=1;
    			if(i+x<n)	//less than n-1
    				mat[i][i+x]=1;
    		}
     }
    

    /*
    for(int i=0;i<graph.size();i++)
    {
    for(int j=0;j<graph[0].size();j++)
    cout<<graph[i][j]<<" “;
    cout<<endl;
    }
    cout<<endl;
    for(int i=0;i<mat.size();i++)
    {
    for(int j=0;j<mat[0].size();j++)
    cout<<mat[i][j]<<” ";
    cout<<endl;
    }

    cout<<endl;*/
    mat = pow(mat, moves);
    

    /* for(int i=0;i<mat.size();i++)
    {
    for(int j=0;j<mat[0].size();j++)
    cout<<mat[i][j]<<" ";
    cout<<endl;
    }

    cout<<endl;
    

    */
    graph = multiply(graph,mat);

    /*
    for(int i=0;i<graph.size();i++)
    {
    for(int j=0;j<graph[0].size();j++)
    cout<<graph[i][j]<<" ";
    cout<<endl;
    }
    */

    if(graph[0][n-1]==1)
    	cout<<"YES\n";
    else
    	cout<<"NO\n";
    

    }
    int main()
    {
    // freopen(“in00.txt”,“r”,stdin);
    int t;
    cin>>t;
    while(t–)
    {
    eval();
    }
    }

3 Likes

Can you please format this editorial one more time? :sweat_smile:
We can wait for sometime,no problem in that.

13 Likes

Yeah, what you can do is preformat your code by putting ``` in the start and at the end of your code.
Secondly, there is an options of hide details, in which you can hide the code. Basically, if someone doesn’t want to see your code, only the tutorial, he can do that.
Thirdly, you can try learning how to differentiate variable terms, numbers etc for other words. Just use the dollar sign before and after the variable / number.

Example:
87. I did this by $87$$ (The last dollar sign is not required, just to show you how I did it!) :slight_smile:

1 Like

Some amount of time that editorialist will spend formatting this editorial will save hell lot of cummulative time for upsolvers like us.

3 Likes

Happy subsets- https://www.hackerearth.com/practice/math/combinatorics/basics-of-combinatorics/practice-problems/algorithm/number-game-10/description/

Ordered Index array- https://www.hackerearth.com/practice/basic-programming/recursion/recursion-and-backtracking/practice-problems/algorithm/jumpingjack-488ce744/

Similarity number- https://www.geeksforgeeks.org/sum-of-similarities-of-string-with-all-of-its-suffixes/

Minimum installment- https://www.hackerearth.com/ru/practice/basic-programming/implementation/basics-of-implementation/practice-problems/algorithm/debts-429c5441/

8 Likes

Problem 2: Small Volume
I am getting wrong answer but I am using the same approach.
Instead of writing nnn, I am using pow(n,3). Please Help me.
Here is my code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t;
    cin>>t;
    while(t--)
    {
        ll n;
        cin>>n;
        ll v=n*n*n;
        ll sv;
        if(n<=2)
        {
            sv=0;
        }
        else
        {
            sv=pow(n-2,3);
        }
        cout<<v-sv<<"\n";
    }
}

Since N can be 10^9 , your answer is overflowing. Use binary exponentiation to calculate a^n

1 Like

I know binary exponentiation but I don’t understand
why will it prevent overflow?
could you please elaborate the reason.

In binary exponentiation we can calculate a^n in log(N) time instead of the naive O(n) method, which is why it will not overflow. Basically, it breaks the number, when the number is even and calculates the product.

Sorry buddy!

This is my first post on discussion forum. I’ll format it by tomorrow.

I don’t know much about cpp but do pow() fiction returns floating number or integer?

Very weak test cases of Ordered Indexed array.
for ex . test case 1
3
2 4 11
3
Correct answer is NO
but many solutions are giving wrong answer (i.e YES ) including mine

1 Like

NO, you check yourself. The correct answer is 8 for n=2. I have checked it. But please explain me when I am replacing pow(n-2,3) with (n-2)(n-2)(n-2) then My solution is getting accepted.

Was this contest rated?

no

1 Like

i think thats because pow function return floating point value by default. If you will explicitly do the type conversion, I think your solution will get accepted.
And yes, correct ans for n=2 is 8

Nope.

I don’t know much about cpp pow() function.

Copied problems, yet poor statements. That’s laughable.

3 Likes

I think the problem statements in the contest were a bit confusing.
Also, in the minimum trans. question, someone asked that is it necessary that ui != vi and you said its not necessary, but when i opened the hackearth link provided above, it was clearly mentioned that ui and vi are guaranteed to be distinct.

Its just a suggestion that you please try to explain the statement properly.
Take it positively. :slightly_smiling_face:

1 Like