Hack Lockdown 1.0 Editorials

sethhritik · May 23, 2020, 11:33am

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.

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)

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

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.

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)

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

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))

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)

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.

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:

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

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

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;
  }
}

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)
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.

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:

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

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

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;
  }
}

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();
}
}

divyanshgarg97 · May 23, 2020, 11:47am

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

aryan12 · May 23, 2020, 11:52am

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!)

divyanshgarg97 · May 23, 2020, 11:54am

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

ashish_kaur · May 23, 2020, 12:02pm

Happy subsets- Number game | Practice Problems

Ordered Index array- Movement in arrays | Practice Problems

Similarity number- Sum of similarities of string with all of its suffixes - GeeksforGeeks

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

askswaraj · May 23, 2020, 12:18pm

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";
    }
}

anon70990627 · May 23, 2020, 12:25pm

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

askswaraj · May 23, 2020, 12:31pm

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

anon70990627 · May 23, 2020, 12:51pm

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.

sethhritik · May 23, 2020, 12:57pm

Sorry buddy!

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

sethhritik · May 23, 2020, 1:01pm

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

aakash_in · May 23, 2020, 1:12pm

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

askswaraj · May 23, 2020, 1:34pm

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.

anon25430212 · May 23, 2020, 1:51pm

Was this contest rated?

pika123_chu · May 23, 2020, 1:52pm

no

iamvedant_vg · May 23, 2020, 1:52pm

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

sethhritik · May 23, 2020, 1:55pm

Nope.

sethhritik · May 23, 2020, 1:58pm

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

shivensinha4 · May 23, 2020, 2:02pm

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

iamvedant_vg · May 23, 2020, 2:02pm

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.