hrshenk It seems to me that if there exists a solution, then there exists infinitely many solutions. For, given a solution S, simply add two occurances of any element to S. For instance, S + {3501, 3501} will also be a solution, and by the definition of multisets is a distinct multiset from S.
hopehour at maximum the number of occurrences of times
LingoRag Finally got AC by DP, some of my thoughts here:
Note the uppper bound of N is 1e5, it tells us to come up with a linear or NlogN solution for each case, but I failed.
So let's look at the range of a[i], it's in [3500, 4500], much smaller than range of N, furthermore, the XOR of any multiset must be in range [0, 8191] (8191==2^13-1). These two observations are the key to my DP solution:
Count the number of each unique integer in input array, then for each unique number, I enumerate every possible integer in [0, 8191] and do some simple calculation to get the number of multiset.
The time complexity of my DP solution is O(M*P), M is the number of unique input integers, P is the range of possible XOR sum, so the upper bound of N*M is 1e7, quite resonable.
kashyap_142 [deleted]slim1972 'Count the number of each unique integer in input array, then for each unique number, I enumerate every possible integer in [0, 8191] and do some simple calculation to get the number of multiset.'
can you please explain this more
sigma316 [deleted]pramodprajapati1 how did you conclude this -> the XOR of any multiset must be in range [0, 8191] (8191==2^13-1)
ahn_jeff The xor-sum of an array can be at most 2^(log2(max(Ai)) + 1) - 1.
Wow. That's a messy formula. Let's try to break it down. I'm assuming you know that taking log2(k) yields the number of bits used to represent k. We start with the largest element in an array call it Ai. If we xor elements that are less than Ai, the largest the xor-sum can be is when all of its bits are set. Example, Ai is the largest element in an array say 1010 (binary), since all other elements are less than or at most equivalient to Ai, we can only set or unset the bits of 1010 (we cannot add more bits since this would be a larger number but this is a contradiction since Ai max). In the max possible case, all bits of Ai are set (ex. 1010 ^ 0100 ^ 0001 = 1111) and it can never exceed that.
So what is this number exactly? Well how do we set all bits in a binary string? Set the next most significant bit and subtract 1 from it. In our example 2^(log2(1010)+1) - 1 => 2^(4+1) - 1 = 1111 or in general 2^(log(2(k)+1) -1. That's how you derive the formula.
Now in back to the problem, Ai will be at most 4500 stated in the constraints. Plug into formula 2^(log2(4500)+1) - 1 = 2^(12+1) - 1 = 2^13 - 1 = 8191. We won't need more than this many states to find the max xor-sum in any given array because it will never exceed this amount!
vipulvikram If we have to xor two binay numbers with n bits each , then there xor also contains maximum of n bits, and the max value of binary number containing n bits is 2^n-1. In this case 2^13-1. 13, because 4500 takes 13 bits in binary representation.
gwylim_a I have implemented the same solution in Java and Python 2, and the Python solution times out on some larger cases while the Java solution works. My solution is the same as the editorial. It also seems like no one has submitted a Python solution which gets full score, so it seems like the constraints make it impossible to solve in Python.
kirakira Finally AC...this is my attempt written in C++14
#include<bits/stdc++.h> #define LL long long #define M 1000000007 using namespace std; int q, n, f[8200] = {0}; LL dp[1005][8200] = {0}, cnt[1005] = {0}; vector<int> P; void makePrime(){ f[0] = f[1] = 1; for(int i=2; i*i < 8200; i++){ if(!f[i]){ for(int j=i+i; j< 8200; j+=i) f[j] = 1; } } for(int i=2; i<8200; i++) if(!f[i]) P.push_back(i); } int main() { cin >> q; makePrime(); while(q--){ cin >> n; memset(cnt, 0, sizeof(cnt)); memset(dp,0,sizeof(dp)); for(int i=0,x; i<n; i++) cin >> x, cnt[x-3500]++; dp[0][3500] = (cnt[0] + 1)/2; dp[0][0] = (cnt[0] + 2) / 2; for(int i=1; i<1005; i++){ for(int j=0; j<8200; j++){ dp[i][j] = (dp[i-1][j]*((cnt[i]+2)/2) + dp[i-1][j^(i+3500)]*((cnt[i]+1)/2) ) % M ; } } LL ans = 0; for(int p : P){ (ans += dp[1004][p]) %= M; } cout << ans%M << endl; } return 0; }
shaurya_nsit How did you arrive at: dp[i][j] = (dp[i-1][j]((cnt[i]+2)/2) + dp[i-1][j^(i+3500)]((cnt[i]+1)/2) ) % M ;
I can't understand it?
kirakira You will find it obvious if you first think in plain English for the recurrence relation:
DP(i, j) := The # of subset using numbers within [3500, i] which XOR result of the subset equals to j (3500 <= i <= 4500)
Now, DP(i, j) should consists of two disjoint parts:
- DP(i-1, j) which means i has no effect at all on the XOR result
- DP(i-1, j^i) which means i has effect at all on the XOR result
So Part 1 includes subsets of DP(i-1, j) union even number of i, as even number of i will produce 0 on the XOR result (no effect)
Part 2 on the contrast includes subsets of DP(i-1, j^i) union odd number of i, as odd number of i will produce a XOR i effect
Combined these points, the problem becomes counting how many even / odd i to produce XOR result j, which is the (cnt[i]+2)/2 or (cnt[i]+1)/2
sriniakhilgl13 why dp of 1st 0 elements with sum 0 is dp[0][0] = (cnt[0] + 2) / 2; ??? it must be 0 i guess
MiloLu Your result will be 0. You can verify that easily
ashish136sharma #include <bits/stdc++.h> #define MOD 1000000007 using namespace std; long long int dp[1001][8192]={0}; vector <int> P; void make_prime() { bool prime[8192]; memset(prime, true, sizeof(prime)); for (int p=2; p*p<=8191; p++) { if (prime[p] == true) { for (int i=p*2; i<=8191; i += p) prime[i] = false; } } for(int i=2;i<8192;i++) { if(prime[i]) P.push_back(i); } } int main() { int t,n,i,l,j,temp; long long int ans=0; make_prime(); cin>>t; while(t--) { unordered_map <int,int> f; vector <int> v; cin>>n; for(i=0;i<n;i++) { cin>>temp; if(!f[temp])v.push_back(temp); f[temp]++; } l=v.size(); dp[0][0] = (f[v[0]]+2)/2; dp[0][v[0]]= (f[v[0]] + 1)/2; for(i=1;i<l && i<1001;i++) for(j=0;j<8192;j++) dp[i][j] = ((dp[i-1][j] * ((f[v[i]]+2)/2)) + (dp[i-1][v[i]^j] * ((f[v[i]] + 1)/2))) % MOD; for(j=0;j<P.size();j++)ans=(ans+ dp[l-1][P[j]])%MOD; cout<<ans<<endl; ans=0; memset(dp,0,sizeof(dp)); } return 0; } MY code is almost same as yours but i am getting time out for last 4 cases rest cases are correct. Can you tell me what is the problem
asimple1 Replace unordered_map with array, should pass then.
michaellty2520 thx
CiPHeR33 why loop is from 1 to 1004 and 0 to 8199??
michaellty2520 in makeprime, did you use sieve of sundaram?
monkeycoder A simple solution in Python is below. It unfortunately times out in larger test cases despite runtime complexity being the same as other solutions.
Note that the solution below uses less space than other solutions that store a full two dimensional array for dynamic programming.
from collections import Counter import sys def isPrime(x): if x == 1: return False if x == 2: return True for d in range(2, max(2, int(x**0.5)) + 1): if x%d == 0: return False return True def get_nevens(y): return y//2 + 1 def get_nodds(y): return y//2 + y%2 def primeXor(a): n = len(a) c = Counter(a) E = list(c.keys()) M = 8192 Sp = [0] * M Sn = [0] * M e = E[0] Sp[e] = get_nodds(c[e]) Sp[0] = get_nevens(c[e]) for e in E[1:]: for x in range(0, M): Sn[x^e] += Sp[x] * get_nodds(c[e]) Sn[x] += Sp[x] * get_nevens(c[e]) # next Sp = Sn Sn = [0] * M result = 0 for e in range(0, M): if isPrime(e): result += Sp[e] return int(result%(1e9 + 7))
The key to understand the dynamic programming solution is that the solution needs not propagate the "primeness". In other words, dynamic programming in this case is not aware of anything being prime. It merely propagates all possible XOR sums (i.e. 0 to 8192 - 1) and later tallies up which XOR sums are primes. A more technical way of saying is that optimal substructure does not involve primeness but rather simple XOR sums.
hamiabdi What is the role of flag in the editorial?
Bobthebuilder24 This times out on the last 4 test cases in Java, but passes when written in c++, is there anything obviously wrong with something I'm doing in Java?
import java.util.*; public class PrimeXor { private static long mod = 1000000007; private static List<Integer> getPrimes(int max) { List<Integer> prime_list = new ArrayList<>(); boolean[] primes = new boolean[max]; Arrays.fill(primes, true); primes[0] = false; primes[1] = false; for (int i = 0; i < primes.length; i++) { if (primes[i]) { prime_list.add(i); for (int inner = i * 2; inner < primes.length; inner += i) { primes[inner] = false; } } } return prime_list; } public static void main(String[] args) { List<Integer> primes = getPrimes(8192); Scanner scn = new Scanner(System.in); int queries = scn.nextInt(); for (int query = 0; query < queries; query++) { int values = scn.nextInt(); long dp[][] = new long[1000][8192]; long element_counts[] = new long[3500]; for (int value = 0; value < values; value++) { element_counts[scn.nextInt() - 3500]++; } dp[0][0] = (element_counts[0] + 2) / 2; dp[0][3500] = (element_counts[0] + 1) / 2; for (int numbers = 1; numbers < dp.length; numbers++) { for (int primes_nums = 0; primes_nums < dp[numbers].length; primes_nums++) { dp[numbers][primes_nums] = (((dp[numbers - 1][primes_nums]) % mod) * (((element_counts[numbers] + 2) / 2) % mod)) + ((dp[numbers - 1][(numbers + 3500) ^ primes_nums] % mod) * (((element_counts[numbers] + 1) / 2) % mod)); } } long total_sum = 0; for (Integer prime : primes) { total_sum = ((total_sum % mod) + (dp[dp.length - 1][prime] % mod)) % mod; } System.out.println(total_sum); } } }
breaker_00011 In mem[flag^1][j^v[i-1]]*odd why j^v[i-1] is used to store value
shivanandyadav11 1 4 3511 3511 3511 3511 output is 2. could anyone explain this testcase why it gives output 2 ?
gauravmhkd25 1 and 4 are not in the range and 3511 is in the range which forms only 1 set and when you take the XOR of the 'inRange' elements you get 1 more set of prime number. So 1+1=2
wpopielarski I didn't find cues too helpful. But remember this is yet another knapsack problem :).
Sort 29 Discussions, By:
Please Login in order to post a comment