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!
It’s actually similar to the editorial solution. I am using the remainder theorem, and the remainder’s would generate the permutation. Then qsum is the sum of the array- (sum of numbers from 1 to n). Then I am finding the factors of qsum…and one of its factors is supposed to be X…and I am then checking if the generated factor makes the array a permutation.
PS: After I changed all the variables to long long int, the code was accepted.
Editorialist Code is wrong .
For ex
1
5
1 1 1 1 11
its ans will be NO
tester code is wrong for testcases like
1
5
1 2 3 4 5
hello do you have any site or way where we can talk