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