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 (61)/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 text
ceil(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 N2 (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 64bit data type. Now there are several possible approaches.
You can write down formula N x N x N(N2) x (N2) x (N2) 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 =(ab) 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 64bit 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(n2) x (n2) x (n2))
[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 (61)/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 text
ceil(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 N2 (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 64bit data type. Now there are several possible approaches.
You can write down formula N x N x N(N2) x (N2) x (N2) 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 =(ab) 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 64bit 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(n2) x (n2) x (n2))
 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 nondecreasing 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,modulo2)
def nCr(n,r):
return (fact[n]*((ifact[r] * ifact[nr]) % 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[i1])%modulo
return fact
def ifactorial_of_n(number):
ifact=[1]*(number)
ifact[1]=InverseEuler(fact[1])
for i in range(number2,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(countpointer>=K1):
# calulate K1 combinations of counted elements
# K1 because one element is fixed
answer=(answer+nCr(countpointer,K1))%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 (jiChooseK) . 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<n1;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(ix>=0) mat[i][ix]=1; if(i+x<n) //less than n1 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][n1]==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] = tdebt = 0
//since anyone can pay any of his friends, so just add the debts/installments.
for i in a:
if(i>0):
debt = debt + iprint(debt)

HAPSET
Consider the given array to be sorted in nondecreasing 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,modulo2)
def nCr(n,r):
return (fact[n]*((ifact[r] * ifact[nr]) % 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[i1])%modulo
return fact
def ifactorial_of_n(number):
ifact=[1]*(number)
ifact[1]=InverseEuler(fact[1])
for i in range(number2,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(countpointer>=K1):
# calulate K1 combinations of counted elements
# K1 because one element is fixed
answer=(answer+nCr(countpointer,K1))%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 (jiChooseK) . 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<n1;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(ix>=0) mat[i][ix]=1; if(i+x<n) //less than n1 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][n1]==1) cout<<"YES\n"; else cout<<"NO\n";
}
int main()
{
// freopen(â€śin00.txtâ€ť,â€śrâ€ť,stdin);
int t;
cin>>t;
while(tâ€“)
{
eval();
}
}