https://www.codechef.com/viewsolution/59380718
can anyone help me what i am doing wrong here ?
Hey for the n*(n+1) ~ 10^10 and so int would give overflow. Same with the sum variable for the sum of array.
It goes like this that suppose its possible to form permutation from some X, then
for each A[i]
Ai = Qi*X + Ri : Here Ai is element of array, X is chosen divisor and Ri is remainder left. As we said that we supposed that answer is possible then Ri is actually all numbers form 1 to N. So if we sum up each Ai then
sum(A) = sum(R) + (Q1+Q2+Q3+…Qn)X
so : sum(A)-sum(R) = (Q1+Q2+…Qn)X. So we can say that X is basically a factor of sum(A)-sum(R). Moreover sum(R) = N(N+1)/2 as it is sum of 1 upto N so thus we can find all factors of sum(A)-sum(R) and check which one gives the correct answer But still this approach should give TLE as suppose all A[i] are of order 10^7 and suppose I take N = 3 so sum(R) = 6 but sum(A) would be around 310^7 and now the number of factors of a number is given by multiplication of prime factorisation to some power i.e suppose Z = (a^p).(b^q).(c^r) here a,b,c are prime factors of Z, then number of factors of Z = (p+1)(q+1)(r+1). Now this thing could take up large values and thus the above approach provided in editorial must give TLE. I am sorry to say but each time I give a contest on codechef the level goes down each time. Some times even 10^7 wont work in 1s and sometimes even 10^8 will pass in 1s.
if(s==0) then why are we directlty printing yes and n+1, it’s not necessary for ex: 1 1 4 = (1+1+4 =6) also , 1 2 3 =(1+2+3 =6). Can someone make me clear??
2 Likes
Yeah I guess one check for existence for duplicates should have been there. It’s there in tester’s solution.
For the input
1
3
2 2 2
it returns
YES 4
which is wrong
My one of the subtask is not working can anyone tell me whats wrong with it?
Here is link to my code:code
We need to check because as in final equation: A N=R N +Q N ∗X
So (A N)-R N =Q N ∗X
Let K= (A N)-R N
So K=X*QN which means one of the factor of X will satisfy the equation so we have for all factors of X and check which will satisfy the equation
“Now we can also see that X needs to be the factor of this Q‘”
can anyone help me. how X need to be factor. I unable to get this.
@cherry0697
In editorial why we are multipling if(x<n) x*=2
https://www.codechef.com/viewsolution/59365617
This user solution for MAGICMOD problem should be wrong in this case :
1
4
1 4 4 1
Does it not suffice to check for all factors of (n+1) if they produce the permutation or not?
The question is basically trying to ask, find an integer x such that, all the elements of the given array can be written as (m1x + 1), (m2x + 2), … , (mn*x + n) where m1, m2, m3, …, mn are some integers.
Here, I have assumed mx + (n+1) == 0 for some integer m. (Maybe I went wrong here).
This gives me mx = -(n+1) => m = -(n+1)/x . Since m is a integer, x | (n+1).
So I have checked for all factors x of n+1, if the condition in the question satisfies. It passes the sample test case but gives WA on all other ones ;(.
Help!
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define int ll
#define SETUP ios_base::sync_with_stdio(0);cin.tie(0);init();
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define ed '\n'
#define bug(x) cout << #x << " = " << x << "\n";
#define bugv(x) for(auto i:x){cout << i << ' ';} cout << ed;
#define TEST int t;cin >> t;while(t--)tc();
#define TEST0 tc();
#define GTEST int tt;cin >> tt;for(int t=1;t<=tt;t++){cout << "Case #" << t << ": ";tc();}
#define SORT(v) sort(all(v));
#define REV(v) reverse(all(v));
#define bs(a,x) binary_search(all(a),x);
#define vi vector<int>
#define mpii map<int,int>
#define here cout << "here\n"
#define prii pair<int,int>
#define ONLINE_JUDGE
//#define pbds
#ifdef pbds
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <numeric>
using namespace __gnu_pbds;
#define oset tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#endif
using namespace std;
void init(){
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
}
template <typename t>
t gcd(t x, t y){
if(y==0)return x;
return gcd(y,x%y);}
template <typename t>
t vgcd(vector<t>a){t res = a[0];ll n= a.size();for(ll i=1;i<n;i++){res = gcd(a[i],res);if(res==1)return 1;}return res;}
bool cmp_str_len(string s1,string s2){return s1.size()<s2.size();}
bool cmp_pair_f(pair<int,int>x,pair<int,int>y){return x.ff<y.ff;}
bool cmp_pair_s(pair<int,int>x,pair<int,int>y){return x.ff>y.ff;}
template <typename t>
t ncr(t n , t r){
if(r==0){
return 1;
}
ll N = 1;
ll R = 1;
while(r){
N*=n;
R*=r;
ll g = gcd(N,R);
N/=g;
R/=g;
n--,r--;
}
return N;}
template <typename t>
t powermod(t x, t y, t m){
int r = 1;
x=x%m;
if(!x)return 0;
while(y>0){
if(y&1){
r = (r*x)%m;
}
y = y>>1;
x = (x*x)%m;}return r;}
const int mod = 1e9+7;
//===================================================================================================================================================
int mex(vector<int> a){
sort(all(a));
int r = 1;
int n = a.size();
for(int i=0;i<n;i++){
if(a[i]==r) ++r;
}
return r;
}
vector<int> appmod(vector<int> a, int m){
for(auto &x:a){
x = x%m;
}
return a;
}
vi factors(int n){
vi ret;
for(int i=2;i<=sqrt(n);i++){
if(n%i==0){
if(n/i == i){
ret.pb(i);
}else{
ret.pb(n/i);
ret.pb(n/i);
}
}
}
ret.pb(n);
return ret;
}
void tc(){
int n;
cin >> n;
vi a(n);
for(int i=0;i<n;i++){
cin >> a[i];
}
vi fac = factors(n+1);
vi b;
//bugv(fac)
for(auto x:fac){
b = a;
//bug(mex(appmod(b,x)))
if(mex(appmod(b,x))==n+1){
cout << "YES " << x << ed;
return;
}
}
cout << "NO\n";
}
signed main(){
SETUP
TEST
//GTEST
}
for (int i = 1; i * i <= s ; i++) {
if (s % i == 0) {
if(check(i) && i <= 2e7) {cout << "YES " << i << '\n';return;}
if(check(s/i) && (s/i) <= 2e7) {cout << "YES " << s/i << '\n';return;}
}
}
why we are checking for factor (s/i ) ?
can you please explain why should ignore the divisors(i.e. factors) <=n.
i am having a hard time understanding the implementation.
i would also be grateful if you can suggest me a resource to lookup so i can understand the implementation better
a\%b < b
@cherry0697 Is there something wrong with test cases? Getting AC while not even printing number after YES.
2 Likes
@munch_01 looks like the Validator is incorrect. As mentioned by @treetrie, not printing the number after YES is also accepted.
Hey, thanks for bringing this to our attention. There seems to be a problem with the judge, we will fix it soon
Could anyone help me out with why is this submission failing?
https://www.codechef.com/viewsolution/61232811
I am just not able to understand on which test case this fails
Hey @rs_kgp_19 , I went through your code and your method seems quite different from the usual solution. Can you please explain the logical analysis behind your solution so that I can help you find out where it is going round.
Thanks!